Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
วิธีซิมเพล็กซ์แบบกระโดดก่อน
Year (A.D.)
2018
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
Mathematics
DOI
10.58837/CHULA.THE.2018.332
Abstract
A practical linear programming solver uses the simplex method to identify the optimal solution by iteratively searching among adjacent feasible vertices. It may visit numerous vertices before finding the optimal one for a large linear programming problem taking a long time to succeed. This research proposes a heuristic method to alleviate this issue by jumping to a new vertex close to the optimal one before performing the simplex method. The new vertex is identified by first jumping from the initial vertex along the gradient vector of the objective function or alternative direction if the objective direction points out of the feasible region and stops at the first feasible point binding at one constraint. It then shifts to a neighbor feasible point preserving previous binding constraints until it reaches the feasible vertex so the simplex method can start. The algorithm is tested on synthetic problems with the origin point as the initial vertex from 100 to 2500 variable having the same number of constraints. Moreover, the preceding jump simplex method is extended to solve general synthetic linear programming problems of 100 to 1000 variables. The experimental results show that the preceding-jump simplex method significantly reduces the number of iterations and total running time.
Other Abstract (Other language abstract of ETD)
ซอฟต์แวร์แก้ปัญหากำหนดการเชิงเส้นในเชิงปฏิบัติใช้วิธีซิมเพล็กซ์เพื่อระบุผลเฉลยที่เหมาะที่สุดโดยการค้นแบบซ้ำจากบรรดาจุดยอดที่เป็นไปได้ที่อยู่ติดกัน วิธีนี้อาจเยี่ยมจุดยอดมากมายก่อนที่จะพบผลเฉลยที่เหมาะที่สุดสำหรับปัญหากำหนดการเชิงเส้นขนาดใหญ่ ซึ่งใช้ระยะเวลานานก่อนหยุด งานวิจัยนี้เสนอวิธีฮิวริสติกเพื่อบรรเทาประเด็นนี้โดยการกระโดดไปจุดยอดใหม่ใกล้กับจุดยอดที่เหมาะที่สุดก่อนใช้วิธีซิมเพล็กซ์ จุดยอดใหม่จะถูกระบุด้วยการ กระโดดครั้งแรกจากจุดยอดเริ่มต้นตามทิศทางของเวกเตอร์เกรเดียนต์ของฟังก์ชันจุดประสงค์หรือทิศทางเลือกอื่นในกรณีทิศทางของฟังก์ชันจุดประสงค์ชี้ออกนอกบริเวณที่เป็นไปได้ จุดยอดดังกล่าวจะหยุดที่จุดที่เป็นไปได้จุดแรกซึ่งผูกกับเงื่อนไขหนึ่งเงื่อนไข จุดที่เป็นไปได้ใหม่นั้นจะถูกเลื่อนไปยังจุดเพื่อนบ้านที่เป็นไปได้ถัดไปโดยคงเงื่อนไขที่ผูกไว้ก่อนหน้า จนกระทั่งวิธีนี้เลื่อนไปถึงจุดยอดที่เป็นไปได้เพื่อเริ่มวิธีซิมเพล็กซ์ ขั้นตอนวิธีนี้ถูกทดสอบกับปัญหาสังเคราะห์ซึ่งจุดศูนย์เป็นจุดยอดเริ่มต้นจาก 100 ถึง 2500 ตัวแปร ซึ่งมีจำนวนตัวแปรเท่ากับจำนวนเงื่อนไขบังคับ มากไปกว่านั้นวิธีซิมเพล็กซ์แบบกระโดดก่อนขยายเพื่อนำไปแก้ปัญหากำหนดการเชิงเส้นทั่วไปตั้งแต่ 100 ถึง 1000 ตัวแปร จากผลการทดลองพบว่าวิธีซิมเพล็กซ์แบบกระโดดก่อนช่วยลดจำนวนการทำซ้ำและเวลาทำงานอย่างมีนัยสำคัญ
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Kafakthong, Natdanai, "Preceding-Jump Simplex method" (2018). Chulalongkorn University Theses and Dissertations (Chula ETD). 2463.
https://digital.car.chula.ac.th/chulaetd/2463