Chulalongkorn University Theses and Dissertations (Chula ETD)
Artificial-Variable-Free simplex method for frimal and dual linear programming models
Other Title (Parallel Title in Other Language of ETD)
วิธีซิมแพล็กซ์แบบไร้ตัวแปรเทียมสำหรับตัวแบบกำหนดการเชิงเส้นหลักและคู่ควบ
Year (A.D.)
2013
Document Type
Thesis
First Advisor
Krung Sinapiromsaran
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Degree Name
Doctor of Philosophy
Degree Level
Doctoral Degree
Degree Discipline
Mathematics
DOI
10.58837/CHULA.THE.2013.877
Abstract
Solving a general linear programming problem using the simplex algorithm relies on introducing artificial variables that deals with a large search space. This dissertation presents the non-acute constraint relaxation technique that not only eliminates the need for artificial variables but also reduces the start-up time to solve the initial relaxation problem. To guarantee the optimal solution or infeasibility or unboundedness of a linear programming problem, the algorithm reinserts the non-acute constraints back to the relaxation problem. The results of this algorithm are superior than the original simplex algorithm with artificial variables for a linear programming problem which the relaxed problem obtains the optimal solution before the the reinsertion of non-acute constraints.
Other Abstract (Other language abstract of ETD)
การแก้ปัญหากำหนดการเชิงเส้นโดยใช้ขั้นตอนวิธีซิมเพล็กซ์ด้วยการเพิ่มตัวแปรเทียมเป็นการเพิ่ม ปริภูมิการค้นหาให้มีขนาดใหญ่ขึ้น วิทยานิพนธ์นี้นำเสนอเทคนิคการผ่อนปรนเงื่อนไขบังคับที่ไม่ใช่มุม แหลมซึ่งไม่เพียงแต่กำจัดความต้องการตัวแปรเทียมเท่่านั้น ยังลดเวลาเริ่มต้นของการแก้ปัญหาผ่อน ปรน การรับประกันผลเฉลยเหมาะที่สุดหรือไม่มีผลเฉลยหรือไม่มีขอบเขตของปัญหากำหนดการเชิง เส้น ทำได้โดยขั้นตอนวิธีจะนำเงื่อนไขบังคับที่ไม่ใช่มุมแหลมกลับเข้ามารวมในปัญหาผ่อนปรน ซึ่ง ผลลัพธ์ของขั้นตอนวิธีนี้ดีกว่าขั้นตอนวิธีซิมเพล็กซ์แบบดั้งเดิมซึ่งใช้ตัวแปรเทียม เมื่อปัญหากำหนดการ เชิงเส้นที่ปัญหาผ่อนปรนมีคำตอบที่เหมาะที่สุดก่อนการนำเงื่อนไขที่ไม่ใช่มุมแหลมเข้ามา
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Boonperm, Aua-aree, "Artificial-Variable-Free simplex method for frimal and dual linear programming models" (2013). Chulalongkorn University Theses and Dissertations (Chula ETD). 62263.
https://digital.car.chula.ac.th/chulaetd/62263