|
วิธีมุมน้อยที่สุดสำหรับปัญหากำหนดการเชิงเส้น 3 มิติ |
|---|---|
| รหัสดีโอไอ | |
| Title | วิธีมุมน้อยที่สุดสำหรับปัญหากำหนดการเชิงเส้น 3 มิติ |
| Creator | เอื้ออารี บุญเพิ่ม |
| Contributor | กรุง สินอภิรมย์สราญ |
| Publisher | จุฬาลงกรณ์มหาวิทยาลัย |
| Publication Year | 2550 |
| Keyword | การโปรแกรมเชิงเส้น |
| 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 เงื่อนไขเท่านั้น |
| URL Website | cuir.car.chula.ac.th |
