Chulalongkorn University Theses and Dissertations (Chula ETD)

Simplex pivot rule emphasizing increment of nonbasic variables

Other Title (Parallel Title in Other Language of ETD)

หลักเกณฑ์การหมุนของวิธีซิมเพล็กซ์ที่เน้นการเพิ่มค่าของตัวแปรไม่พื้นฐาน

Year (A.D.)

2013

Document Type

Thesis

First Advisor

Boonyarit Intiyot

Second Advisor

Krung Sinapiromsaran

Faculty/College

Faculty of Science (คณะวิทยาศาสตร์)

Degree Name

Master of Science

Degree Level

Master's Degree

Degree Discipline

Mathematics

DOI

10.58837/CHULA.THE.2013.948

Abstract

The simplex algorithm, first presented by George B. Dantzig, is a widely used method for solving a linear programming (LP) problem. One of the important steps of the simplex algorithm is applying a pivot rule, the rule to select an entering variable. An effective pivot rule can lead to an optimal solution of an LP problem with a small number of iterations but not necessarily small computational time if each iteration spends a lot of time. In a minimization problem, Dantzig’s pivot rule selects an entering variable corresponding to the most negative reduced cost. The concept is to have the maximum improvement in the objective value per unit change of an entering variable. However, in some problems, Dantzig’s rule may visit a large number of extreme points before reaching the optimal solution. In this thesis, we propose a pivot rule, called the absolute change pivot rule, that could reduce the number of such iterations over the Dantzig’s pivot rule. The idea is to have the maximum improvement in the value of an objective function by trying to block a leaving variable that makes a little change in the objective value as much as possible. This absolute change pivot rule is tested and compared the efficacy with Dantzig’s original pivot rule and other pivot rules.

Other Abstract (Other language abstract of ETD)

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

Link to Full Text

Share

COinS