Iterative jump to binding point for simplex method

การกระโดดวนซ้ำไปยังจุดยึดสําหรับวิธีซิมเพล็กซ์

Name: Rujira Visuthirattanamanee

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.

Abstract: แนวคิดพื้นฐานของวิธีกระโดดแบบวนซ้ำคือการเคลื่อนที่จากจุดที่เป็นไปได้ไปตามทิศทาง ที่ปรับปรุงค่าวัตถุประสงค์ที่คงความเป็นไปได้ วิธีดังกล่าวถูกนำมาประยุกต์ใช้กับการหาผล เฉลยของปัญหากำหนดการเชิงเส้นไร้ตัวแปรเทียมโดยการประยุกต์วิธีกระโดดแบบวนซ้ำกับ ปัญหากำหนดการเชิงเส้นแบบผ่อนคลายที่ประกอบไปด้วยเงื่อนไขมุมแหลมเทียบกับทิศทาง ของวัตถุประสงค์และแทรกเงื่อนไขมุมไม่แหลมเข้าใหม่เพื่อหาผลเฉลยที่เหมาะที่สุด โดยตั้งชื่อ ว่าเอสเอเจเอส อย่างไรก็ตามวิธีดังกล่าวอาจทำให้จุดกระโดดสุดท้ายไกลจากจุดที่เหมาะที่สุด ดังนั้นวิธีอื่นสำหรับการหาจุดเริ่มต้นที่เหมาะสมจึงถูกนำเสนอ วิธีใหม่ที่ถูกนำเสนอ เอเจเอสพี ได้ใช้เทคนิคนี้กับการรบกวนค่าด้านขวาของเงื่อนไขบังคับที่ไม่สอดคล้องเพื่อให้วิธีนั้นสามารถ เริ่มต้นด้วยจุดที่เป็นไปได้ก่อนการประยุกต์ใช้วิธีกระโดดแบบวนซ้ำ ทั้งเอสเอเจเอสและเอเจเอสพีมีประสิทธิภาพเหนือกว่าวิธีซิมเพล็กซ์มาตรฐานและขั้นตอนวิธีซิมเพล็กซ์ปราศจากตัวแปร เทียมขึ้นอยู่กับการผ่อนคลายเงื่อนไขที่มุมไม่แหลมบนปัญหากำหนดการเชิงเส้นที่ถูกสร้างขึ้น และปัญหาจากเน็ตลิบ

Chulalongkorn University. Office of Academic Resources

Address: BANGKOK

Email: cuir@car.chula.ac.th

Name: Krung Sinapiromsaran

Role: advisor

Name: Aua-aree Boonperm

Role: co-advisor

Created: 2019

Modified: 2024-01-02

Issued: 2024-01-02

วิทยานิพนธ์/Thesis

application/pdf

eng

DegreeName: Doctor of Philosophy

Level: Doctoral Degree

Descipline: Applied Mathematics and Computational Science

Grantor: Chulalongkorn University

©copyrights Chulalongkorn University

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	5772884323[1].pdf	1.52 MB

ใช้เวลา

0.032923 วินาที