Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
หลักเกณฑ์การหมุนแบบเปลี่ยนสองขั้นสำหรับวิธีซิมเพล็กซ์
Year (A.D.)
2024
Document Type
Thesis
First Advisor
Krung Sinapiromsaran
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Department (if any)
Department of Mathematics and Computer Science (ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์)
Degree Name
Master of Science
Degree Level
Master's Degree
Degree Discipline
Applied Mathematics and Computational Science
DOI
10.58837/CHULA.THE.2024.914
Abstract
The simplex method is a fundamental method for solving linear programming problems proposed by George B. Dantzig in 1963. The simplex method’s efficiency hinges on the choice of the entering variable, determined by the pivot rule. Dantzig’s original pivot rule, while effective in many cases, can exhibit exponential behavior on certain problems. To address this problem, this thesis proposes a new pivot rule for the simplex method, called the two-step-change pivot rule. The idea is to obtain the two-step-change improvement from the objective value by computing the direction of change for each entering variable to determine the cost per unit. The one with the best improvement is chosen as the entering variable and the leaving variable using the minimum ratio test. The experimental results are conducted to compare the performance of this pivot rule with three established pivot rules which are Dantzig, Absolute change, and the largest distance. By our experiments with a family of Klee-Minty cubes and the randomly generated multi-period planning problems from small-sized to medium-sized, the two-step-change pivot rule is faster than Dantzig, Absolute change, and the largest distance pivot rule on average ranking of average computational time across different problem sizes, its average ranking of average computational time is consistently achieving the lowest average rank. On Netlib LP problems, the proposed pivot rule performed the most effective result, achieving the best average ranking of computational time across all Netlib problems. In addition, the proposed pivot rule performed with less number of iterations than other rules although the computational time was larger for most problems on randomly generated problems with 2 up to 15 variables and no more than 750 constraints.
Other Abstract (Other language abstract of ETD)
วิธีซิมเพล็กซ์เป็นระเบียบวิธีพื้นฐานที่ใช้ในการแก้ปัญหากำหนดการเชิงเส้น นำเสนอโดย จอร์จ แดนท์ซิก ในปี 1963 ซึ่งประสิทธิภาพของวิธีซิมเพล็กซ์ขึ้นอยู่กับการเลือกตัวแปรเข้า ตามหลักเกณฑ์การหมุน หลักเกณฑ์การหมุนแบบดั้งเดิมของแดนท์ซิก แม้จะมีประสิทธิผลในหลายกรณี แต่ในหลายปัญหาหลักเกณฑ์การหมุนนี้แสดงพฤติกรรมแบบเอกซ์โพเนนเชียล เพื่อป้องกันปัญหานี้ วิทยานิพนธ์นี้นำเสนอหลักเกณฑ์การหมุนใหม่สำหรับวิธีซิมเพล็กซ์ เรียกว่าหลักเกณฑ์การหมุนแบบเปลี่ยนสองขั้น โดยแนวคิดคือการปรับปรุงการเปลี่ยนสองขั้นจากค่าฟังก์ชันจุดประสงค์โดยคำนวณทิศทางการเปลี่ยนแปลงสำหรับตัวแปรเข้าแต่ละตัวเพื่อกำหนดค่าการปรับปรุงต่อหน่วย สำหรับตัวแปรที่มีค่าการปรับปรุงที่ดีที่สุดจะถูกเลือกเป็นตัวแปรเข้า ส่วนตัวแปรออกนั้นใช้การทดสอบอัตราส่วนขั้นต่ำ ผลการทดลองที่ได้ถูกเปรียบเทียบประสิทธิภาพกับอีกสามหลักเกณฑ์การหมุนที่เคยถูกนำเสนอมาแล้ว คือ แดนท์ซิก, การเปลี่ยนสัมบูรณ์ และระยะทางที่ใหญ่ที่สุด จากการทดสอบกับแฟมมิลี่ของปัญหาลูกบาศก์ คลี-มินตี้ และ ปัญหาการวางแผนหลายช่วงเวลาที่สร้างขึ้นแบบสุ่มตั้งแต่ขนาดเล็กไปจนถึงขนาดกลาง พบว่าหลักเกณฑ์การหมุนแบบเปลี่ยนสองขั้นนั้นให้ผลลัพธ์เร็วกว่าหลักเกณฑ์การหมุนแบบ แดนท์ซิก, การเปลี่ยนสัมบูรณ์ และระยะทางที่ใหญ่ที่สุด จากการจัดอันดับเฉลี่ยของเวลาคำนวณโดยเฉลี่ยในปัญหาขนาดต่างๆ ซึ่งอันดับเฉลี่ยมีค่าต่ำสุดอย่างสม่ำเสมอ สำหรับปัญหาจากเน็ตลิบหลักเกณฑ์การหมุนที่เสนอให้ผลลัพธ์ที่มีประสิทธิภาพสูงสุดโดยให้อันดับเฉลี่ยของเวลาการคำนวณที่ดีที่สุดในปัญหาเน็ตลิบทั้งหมด นอกจากนี้หลักเกณฑ์การหมุนที่เสนอจะใช้จำนวนการวนซ้ำที่น้อยกว่าหลักเกณฑ์การหมุนแบบอื่นๆ ถึงแม้ว่าจะใช้เวลาในการคำนวณนานกว่า สำหรับส่วนใหญ่ของปัญหาที่สร้างขึ้นแบบสุ่มที่มีจำนวนตัวแปร 2 ถึง 15 ตัวแปร และมีจำนวนเงื่อนไขบังคับไม่เกิน 750 เงื่อนไข
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Chaiareekij, Rawit, "Two-step-change pivot rule for simplex method" (2024). Chulalongkorn University Theses and Dissertations (Chula ETD). 74752.
https://digital.car.chula.ac.th/chulaetd/74752