แจ้งเอกสารไม่ครบถ้วน, ไม่ตรงกับชื่อเรื่อง หรือมีข้อผิดพลาดเกี่ยวกับเอกสาร ติดต่อที่นี่ ==>
หากไม่มีอีเมลผู้รับให้กรอก thailis-noc@uni.net.th
หากไม่มีอีเมลผู้รับให้กรอก thailis-noc@uni.net.th
Natdanai Kafakthong. Preceding-Jump Simplex method. Master's Degree(Mathematics). Chulalongkorn University. Office of Academic Resources. : Chulalongkorn University, 2018.
Preceding-Jump Simplex method
วิธีซิมเพล็กซ์แบบกระโดดก่อน
Name: Natdanai Kafakthong
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.
Abstract:
ซอฟต์แวร์แก้ปัญหากำหนดการเชิงเส้นในเชิงปฏิบัติใช้วิธีซิมเพล็กซ์เพื่อระบุผลเฉลยที่เหมาะที่สุดโดยการค้นแบบซ้ำจากบรรดาจุดยอดที่เป็นไปได้ที่อยู่ติดกัน วิธีนี้อาจเยี่ยมจุดยอดมากมายก่อนที่จะพบผลเฉลยที่เหมาะที่สุดสำหรับปัญหากำหนดการเชิงเส้นขนาดใหญ่ ซึ่งใช้ระยะเวลานานก่อนหยุด งานวิจัยนี้เสนอวิธีฮิวริสติกเพื่อบรรเทาประเด็นนี้โดยการกระโดดไปจุดยอดใหม่ใกล้กับจุดยอดที่เหมาะที่สุดก่อนใช้วิธีซิมเพล็กซ์ จุดยอดใหม่จะถูกระบุด้วยการ กระโดดครั้งแรกจากจุดยอดเริ่มต้นตามทิศทางของเวกเตอร์เกรเดียนต์ของฟังก์ชันจุดประสงค์หรือทิศทางเลือกอื่นในกรณีทิศทางของฟังก์ชันจุดประสงค์ชี้ออกนอกบริเวณที่เป็นไปได้ จุดยอดดังกล่าวจะหยุดที่จุดที่เป็นไปได้จุดแรกซึ่งผูกกับเงื่อนไขหนึ่งเงื่อนไข จุดที่เป็นไปได้ใหม่นั้นจะถูกเลื่อนไปยังจุดเพื่อนบ้านที่เป็นไปได้ถัดไปโดยคงเงื่อนไขที่ผูกไว้ก่อนหน้า จนกระทั่งวิธีนี้เลื่อนไปถึงจุดยอดที่เป็นไปได้เพื่อเริ่มวิธีซิมเพล็กซ์ ขั้นตอนวิธีนี้ถูกทดสอบกับปัญหาสังเคราะห์ซึ่งจุดศูนย์เป็นจุดยอดเริ่มต้นจาก 100 ถึง 2500 ตัวแปร ซึ่งมีจำนวนตัวแปรเท่ากับจำนวนเงื่อนไขบังคับ มากไปกว่านั้นวิธีซิมเพล็กซ์แบบกระโดดก่อนขยายเพื่อนำไปแก้ปัญหากำหนดการเชิงเส้นทั่วไปตั้งแต่ 100 ถึง 1000 ตัวแปร จากผลการทดลองพบว่าวิธีซิมเพล็กซ์แบบกระโดดก่อนช่วยลดจำนวนการทำซ้ำและเวลาทำงานอย่างมีนัยสำคัญ
Chulalongkorn University. Office of Academic Resources
Address:
BANGKOK
Email:
cuir@car.chula.ac.th
Name: Krung Sinapiromsaran
Role:
advisor
Created:
2018
Modified:
2024-10-14
Issued:
2024-10-14
วิทยานิพนธ์/Thesis
application/pdf
URL: http://doi.org/10.58837/CHULA.THE.2018.332
eng
DegreeName: Master of Science
Level: Master's Degree
Descipline: Mathematics
Grantor: Chulalongkorn University
©copyrights Chulalongkorn University
RightsAccess:
ใช้เวลา
0.024782 วินาที
Natdanai Kafakthong
| Title | Contributor | Type |
|---|---|---|
| Preceding-Jump Simplex method
จุฬาลงกรณ์มหาวิทยาลัย Natdanai Kafakthong | Krung Sinapiromsaran | วิทยานิพนธ์/Thesis |
Krung Sinapiromsaran