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 ตัวแปร จากผลการทดลองพบว่าวิธีซิมเพล็กซ์แบบกระโดดก่อนช่วยลดจำนวนการทำซ้ำและเวลาทำงานอย่างมีนัยสำคัญ

Included in

Mathematics Commons

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.