Chulalongkorn University Theses and Dissertations (Chula ETD)

ขั้นตอนวิธีใหม่สำหรับการแก้ปัญหากำหนดการเชิงเส้นใน 2 มิติ

Other Title (Parallel Title in Other Language of ETD)

A novel algorthm for solving linear programming problems in two dimensions

Year (A.D.)

2003

Document Type

Thesis

First Advisor

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

Faculty/College

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

Degree Name

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

Degree Level

ปริญญาโท

Degree Discipline

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

DOI

10.58837/CHULA.THE.2003.924

Abstract

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

Other Abstract (Other language abstract of ETD)

This thesis proposes a new algorithm for solving 2-dimensional linear programming problems with nonempty feasible region and a large number of constraints. The main concept of this novel algorithm is the use of the gradient vector of the objective function in categorizing constraints into two groups. For each iteration, the angle between the gradient vector of the objective function and the gradient vector of the constraints is used to find a representative for each group. Finally, two constraints are selected from different groups leading to solutions of the problems. The complexity of this novel algorithm is quadratic with respect to the number of constraints.

Link to Full Text

Share

COinS