Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
การกระโดดวนซ้ำไปยังจุดยึดสําหรับวิธีซิมเพล็กซ์
Year (A.D.)
2019
Document Type
Thesis
First Advisor
Krung Sinapiromsaran
Second Advisor
Aua-aree Boonperm
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Department (if any)
Department of Mathematics and Computer Science (ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์)
Degree Name
Doctor of Philosophy
Degree Level
Doctoral Degree
Degree Discipline
Applied Mathematics and Computational Science
DOI
10.58837/CHULA.THE.2019.17
Abstract
The basic idea of an iterative jump method is moving a feasible point along the direction that improves the objective value maintaining the feasibility. It is applied for solving a linear programming (LP) model without artificial variables by applying the iterative jump on the LP relaxation having only acute constraints with respect to the objective direction and reinsert all non-acute constraints to find the optimal solution which is named SAJS. However, it may cause the last jump point to locate far away from the optimal solution so another approach for initially finding a suitable starting point is proposed. The new proposed method, AJSP use this technique together with the perturbation of the right-hand side values of violated constraints to be able to start at the feasible point before applying the iterative jump method. Both SAJS and AJSP outperform the standard simplex method and the artificial-free simplex algorithm based on the non-acute constraint relaxation on synthetic linear programming problems and Netlib problems.
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
Visuthirattanamanee, Rujira, "Iterative jump to binding point for simplex method" (2019). Chulalongkorn University Theses and Dissertations (Chula ETD). 8393.
https://digital.car.chula.ac.th/chulaetd/8393