Please use this identifier to cite or link to this item:
https://cuir.car.chula.ac.th/handle/123456789/25934
| Title: | ขั้นตอนวิธีใหม่สำหรับการแก้ปัญหากำหนดการเชิงเส้นใน 2 มิติ |
| Other Titles: | A novel algorthm for solving linear programming problems in two dimensions |
| Authors: | กฤษดา นารอง |
| Advisors: | กรุง สินอภิรมย์สราญ |
| Other author: | จุฬาลงกรณ์มหาวิทยาลัย. คณะวิทยาศาสตร์ |
| Issue Date: | 2546 |
| Publisher: | จุฬาลงกรณ์มหาวิทยาลัย |
| Abstract: | ขั้นตอนวิธีใหม่มุ่งเน้นแก้ปัญหากำหนดการเชิงเส้นในสองมิติที่มีบริเวณที่เป็นไปได้ไม่เป็นเซตว่าง และจำนวนเงื่อนไขบังคับมาก โดยใช้เวกเตอร์เกรเดียนต์ของฟังก์ชันจุดประสงค์เป็นตัวแบ่งเงื่อนไขบังคับทั้งหมดออกเป็นสองกลุ่ม แล้วใช้มุมระหว่างเวกเตอร์เกรเดียนต์ของฟังก์ชันจุดประสงค์กับเวกเตอร์เกรเดียนต์ของเงื่อนไขบังคับเป็นตัวระบุว่าเงื่อนไขบังคับใดเป็นตัวแทนของแต่ละกลุ่มในแต่ละรอบการทำงาน สุดท้ายเลือกเงื่อนไขข้อบังคับสองเงื่อนไขที่เป็นตัวแทนของแต่ละกลุ่มโดยที่สองเงื่อนไขดังกล่าวจะนำไปสู่ผลเฉลยที่เหมาะสมที่สุดของปัญหา เมื่อพิจารณาระยะเวลาการทำงานแล้วขั้นตอนวิธีใหม่ใช้เวลาในการทำงานเป็นแบบกำลังสองของจำนวนเงื่อนไขบังคับ |
| Other Abstract: | 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. |
| Description: | วิทยานิพนธ์ (วท.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2546 |
| Degree Name: | วิทยาศาสตรมหาบัณฑิต |
| Degree Level: | ปริญญาโท |
| Degree Discipline: | วิทยาการคณนา |
| URI: | http://cuir.car.chula.ac.th/handle/123456789/25934 |
| ISBN: | 9741751664 |
| Type: | Thesis |
| Appears in Collections: | Sci - Theses |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Kridsada_na_front.pdf | 1.33 MB | Adobe PDF | View/Open | |
| Kridsada_na_ch1.pdf | 4.39 MB | Adobe PDF | View/Open | |
| Kridsada_na_ch2.pdf | 4.54 MB | Adobe PDF | View/Open | |
| Kridsada_na_ch3.pdf | 4.6 MB | Adobe PDF | View/Open | |
| Kridsada_na_ch4.pdf | 1.61 MB | Adobe PDF | View/Open | |
| Kridsada_na_back.pdf | 3.9 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.