Chulalongkorn University Theses and Dissertations (Chula ETD)

วิธีมุมน้อยที่สุดสำหรับปัญหากำหนดการเชิงเส้น 3 มิติ

Other Title (Parallel Title in Other Language of ETD)

Minimal angled method for 3-dimensional linear programming problems

Year (A.D.)

2007

Document Type

Thesis

First Advisor

กรุง สินอภิรมย์สราญ

Faculty/College

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

Degree Name

วิทยาศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิทยาการคณนา

DOI

10.58837/CHULA.THE.2007.910

Abstract

วิทยานิพนธ์นี้นำเสนอวิธีใหม่สองวิธีคือวิธี Minimal Angled Projection (MAP) และวิธี KKT- Minimal Angled Projection (KKT-MAP) โดยใช้มุมระหว่างเวกเตอร์แนวฉากของเงื่อนไขบังคับอสมการเชิงเส้นกับเกรเดียนต์ของฟังก์ชันจุดประสงค์เพื่อแก้ปัญหากำหนดการเชิงเส้น 3 มิติที่มีผลเฉลยที่เหมาะที่สุด วิธีนี้ลดปัญหากำหนดการเชิงเส้นใน 3 มิติไปเป็นปัญหาย่อยใน 2 มิติและใช้ขั้นตอนวิธีมุมน้อยที่สุดสำหรับการแก้ปัญหากำหนดการเชิงเส้น 2 มิติแก้ปัญหานั้น วิธี MAP จะทำซ้ำทีละหนึ่งเงื่อนไขบังคับไปจนครบทุกเงื่อนไขและในแต่ละครั้งจะประยุกต์ขั้นตอนวิธีมุมน้อยที่สุด 2 มิติเพื่อสร้างผลเฉลยสำหรับปัญหา 3 มิติ จากนั้นผลเฉลยที่เหมาะที่สุดจะถูกเลือกจากกลุ่มผลเฉลยนี้ซึ่งมีค่าดีที่สุดและสอดคล้องกับทุกเงื่อนไขบังคับ ในขณะที่วิธี KKT-MAP จะเรียงลำดับเงื่อนไขบังคับตามมุมระหว่างเกรเดียนต์ของเงื่อนไขบังคับกับเกรเดียนต์ของฟังก์ชันจุดประสงค์ จากนั้นใช้ขั้นตอนวิธีมุมน้อยที่สุด 2 มิติสร้างผลเฉลย โดยผลเฉลยที่ได้นี้จะถูกตรวจสอบกับเงื่อนไข KKT ถ้าสอดคล้องจะได้ว่าผลเฉลยนี้เป็นผลเฉลยที่เหมาะที่สุด มิเช่นนั้นเงื่อนไขบังคับที่ทำมุมน้อยที่สุดถัดไปจะถูกใช้จนกว่าจะได้ผลเฉลยที่เหมาะที่สุด จากการทดสอบกับปัญหาที่มีเงื่อนไขบังคับ 4 ถึง 20 เงื่อนไข พบว่าวิธี KKT-MAP ให้ผลลัพธ์เร็วกว่าวิธีซิมเพล็กซ์ และวิธี MAP มาก นอกจากนี้วิธี MAP จะเร็วกว่าวิธีซิมเพล็กซ์ในปัญหาที่มีเงื่อนไขบังคับ 4 ถึง 18 เงื่อนไขเท่านั้น

Other Abstract (Other language abstract of ETD)

This thesis proposes two new algorithms to solve a 3-dimensional linear programming problem: The Minimal Angled Projection (MAP) algorithm and the KKT-Minimal Angled Projection (KKT-MAP) algorithm based on an angle between normal vector of linear inequality constraints and the gradient of the objective function for solving 3- dimensional linear programming (LP) with an optimal solution. Both algorithms reduce a 3-dimensional LP problem into 2-dimensional LP sub-problems and uses the minimal angled algorithm for solving sub-problems. The MAP method iteratively binds one constraint and applies the minimal angled algorithm in 2-dimension for generating the optimal solution of the original 3-dimensional LP problem. The optimal solution is then selected among these candidates with the best objective value and satisfies all constraints. While, the KKT-MAP method sorts constraints according to the angles between their normal vectors and the gradient of the objective function. Then it applies the minimal angled algorithm in 2-dimension for generating a candidate solution which will be checked with the KKT conditions of the original 3-dimensional LP problem. If the candidate solution satisfies the KKT conditions, that solution is the optimal solution. Otherwise, the next minimal angled from the constraint will be used until the optimal solution is found. By our experiments with 4 up to 20 constraints, the KKT-MAP algorithm is faster than the simplex method and the MAP algorithm. Moreover, MAP algorithm is faster than the simplex method for problems with 4 up to 18 constraints.

Link to Full Text

Share

COinS