Chulalongkorn University Theses and Dissertations (Chula ETD)

Solving linear programming problems by the interior-point method

Other Title (Parallel Title in Other Language of ETD)

การแก้ปัญหากำหนดการเชิงเส้นด้วยวิธีจุดภายใน

Year (A.D.)

2001

Document Type

Thesis

First Advisor

Wanida Hemakul

Second Advisor

Krung Sinapiromsaran

Faculty/College

Faculty of Science (คณะวิทยาศาสตร์)

Degree Name

Master of Science

Degree Level

Master's Degree

Degree Discipline

Computational Science

DOI

10.58837/CHULA.THE.2001.989

Abstract

This research aims to survey methods of solving linear programming problems by the interior-point method in 3 approaches: Karmarkar's projective scaling, the primal affine scaling and the primal-dual algorithm. We construct a program by C++ language on the Windows operating system. In our results, we tested our program with our small problems and problems in MPS (Mathematical Programming System) files. Typically, if problem has a small size then our program uses iteration numbers of processing more than program which bases of the simplex method. If problem has a large-scale size then our program uses iteration numbers of processing less than program which bases on the simplex method.

Other Abstract (Other language abstract of ETD)

งานวิจัยนี้รวบรวมขั้นตอนวิธีในการแก้ปัญหากำหนดการเชิงเส้นด้วยวิธีจุดภายใน 3 ขั้นตอนวิธี คือ ขั้นตอนวิธีโพรเจกทีฟสเกลลิ่งของคาร์มาร์คาร์, ขั้นตอนวิธีไพรมอลแอฟฟีนสเกลลิ่ง และขั้นตอนวิธีไพรมอลดูอัล เราสร้างโปรแกรมด้วยภาษาซีบวกบวกบนระบบปฏิบัติการวินโดว์ ผลการทดสอบโปรแกรมกับปัญหาขนาดเล็กและปัญหาที่เก็บอยู่ในแฟ้มข้อมูลรูปแบบเอ็มพีเอส (ระบบโปรแกรมมิ่งเชิงคณิตศาสตร์) พบว่าถ้าปัญหาขนาดเล็ก โปรแกรมของเราใช้จำนวนรอบในการประมวลผลมากกว่าโปรแกรมที่ใช้วิธีซิมเพลทซ์ ถ้าปัญหาขนาดใหญ่ โปรแกรมของเราใช้จำนวนรอบในการประมวลผลน้อยกว่าโปรแกรมที่ใช้วิธีซิมเพลทซ์

Link to Full Text

Share

COinS