Please use this identifier to cite or link to this item:
https://cuir.car.chula.ac.th/handle/123456789/67604
| Title: | ขั้นตอนวิธีความชันน้อยสุดในทิศทางจุดประสงค์สำหรับปัญหากำหนดการเชิงเส้นสองมิติที่มีเงื่อนไขเกินจำเป็น |
| Other Titles: | Minimal slope algorithm along objective direction for 2D linear programming problem with redundant constraints |
| Authors: | นัฐพงศ์ วิชัยศรี |
| Advisors: | กรุง สินอภิรมย์สราญ |
| Other author: | จุฬาลงกรณ์มหาวิทยาลัย. คณะวิทยาศาสตร์ |
| Advisor's Email: | Krung.S@Chula.ac.th |
| Subjects: | การโปรแกรมเชิงเส้น Linear programming Minimal slope |
| Issue Date: | 2554 |
| Publisher: | จุฬาลงกรณ์มหาวิทยาลัย |
| Abstract: | วิทยานิพนธ์นี้นําเสนอขั้นตอนวิธีใหม่ในการแก้ปัญหากําหนดการเชิงเส้นสองมิติที่มี เงื่อนไขบังคับที่เกินจําเป็นโดยมีพื้นฐานจากขั้นตอนวิธีการแก้ปัญหาของเมกิดโด และเอื้ออารี โดยผลเฉลยของวิธีการของเอื้ออารีไม่ได้รับประกันจุดเหมาะที่สุดในกรณีที่ปัญหามีเงื่อนไข บังคับที่เกินจําเป็น ขั้นตอนวิธีใหม่จะเพิ่มเติมการตรวจสอบว่าจุดดังกล่าวมีความเป็นไปได้ หรือไม่ พร้อมทั้งปรับปรุงเงื่อนไขบังคับที่มีค่าความชันน้อยสุดที่สอดคล้องกับเงื่อนไขบังคับ จนถึงจุดที่เหมาะที่สุด และเปรียบเทียบจํานวนการทําซ้ําและเวลาที่ใช้โดยใช้ขั้นตอนวิธีที่สร้าง ขึ้นกับวิธีซิมเพล็กซ์กับ 5 ปัญหาที่แตกต่างกัน ขั้นตอนวิธีนี้สามารถแก้ปัญหาการหาค่าสูงสุด และต่ําสุดได้ในเวลาเดียวกัน แต่ในบางปัญหาที่มีเงื่อนไขบังคับที่เกินจําเป็นอาจใช้จํานวนการ ทําซ้ําและเวลาที่มากกว่าวิธีชิมเพล็กซ์ |
| Other Abstract: | This thesis presents a new algorithm for solving a 2-dimensional linear programming problem with redundant constraints based on Megiddo and Aua-Aree's method. The solution from Aua-Aree's method does not guarantee optimal point if the problem has redundant constraints. The new algorithm performs additional check to verify a validity of the current solution and update a new set of constraints in minimal slope method until it reaches the optimal point. We, compare the number of iterations and time using this algorithm and Simplex method on 5 different problem sets. This algorithm can be used to solve both minimum and maximum problem at the same time. The weak point is this algorithm may take longer iterations than Simplex algorithm for a problem with redundant constraints. |
| Description: | วิทยานิพนธ์ (วท.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2554 |
| Degree Name: | วิทยาศาสตรมหาบัณฑิต |
| Degree Level: | ปริญญาโท |
| Degree Discipline: | วิทยาการคณนา |
| URI: | http://cuir.car.chula.ac.th/handle/123456789/67604 |
| Type: | Thesis |
| Appears in Collections: | Sci - Theses |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Nattapong_wi_front_p.pdf | หน้าปก บทคัดย่อ และสารบัญ | 829.47 kB | Adobe PDF | View/Open |
| Nattapong_wi_ch1_p.pdf | บทที่ 1 | 835.03 kB | Adobe PDF | View/Open |
| Nattapong_wi_ch2_p.pdf | บทที่ 2 | 1.79 MB | Adobe PDF | View/Open |
| Nattapong_wi_ch3_p.pdf | บทที่ 3 | 1.3 MB | Adobe PDF | View/Open |
| Nattapong_wi_ch4_p.pdf | บทที่ 4 | 799.03 kB | Adobe PDF | View/Open |
| Nattapong_wi_back_p.pdf | บรรณานุกรม และภาคผนวก | 695.3 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.