เรื่องที่ 4.1 วิธีการที่ใช้ในกำหนดการเชิงเส้น
การแก้ปัญหาโปรแกรมเส้นตรงด้วยวิธีกราฟนี้เหมาะสำหรับการแก้ปัญหาที่มีตัวแปรที่ต้องการทราบค่าเพียง 2 ตัว
เนื่องจากการเขียนกราฟ 2 มิติ ง่ายและสะดวก แต่ถ้าตัวแปรมีตั้งแต่ 3 ตัวขึ้นไปควรใช้วิธีซิมเพลก
การคำนวณด้วยวิธีกราฟ
ให้นำตัวแบบที่สร้างไว้แล้วนั้นมา plot graph แล้วพิจารณาขอบเขตที่เป็นไปได้ โดยพิจารณาจากข้อจำกัด
เมื่อได้ขอบเขตดังกล่าวแล้ว ให้พิจารณาค่าที่ต้องการเพื่อให้ได้เป้าหมายที่วางไว้ การพิจารณาขอบเขตที่เป็นไปได้ ต้อง
นำข้อจำกัดที่เขียนอยู่ในรูปอสมการเส้นตรงมาพิจารณาเป็นเส้นๆไป เช่น
นำตัวอย่างที่ 2 มาplot graph
Maximize X0 = 3X1+4X2
ให้ขึ้นอยู่กับ
5X1 + 4X2  200
3X1 + 5X2 150
5X1 + 4X2  100
8X1 + 4X2 80
X1 0, X2 0
ข้อยับยั้งที่ไม่ติดลบได้ X1 0 และ X2 0 แสดงว่าค่า X1 และ X2 จะต้องอยู่ในควอแดรนท์ที่ 1 ส่วนผลที่ได้
ในข้อยับยั้งอื่นๆ แสดงเพิ่มขึ้นจากรูป 4-1 ด้วยการจุดข้อยับยั้งทั้งหมดด้วยอสมการที่เปลี่ยนรูปเป็นสมการ ดังตัวอย่าง
ในรูป 4-2 แสดงให้เห็นข้อยับยั้ง 5X1 + 4X2 200 อยู่ในทิศทางที่เข้าหา origin
รูปที่ 4-1
พื้นที่ที่เข้ากับข้อยับยั้งได้ (รวมทั้งเส้นที่เป็นขอบ) เรียกว่าเขตผลลัพธ์ ( solution space) ดังแสดงในรูป 4-2 พื้นที่ที่แรเงา
ABCDE
รูปที่ 4-2
ข้อยับยั้ง 8X1 + 4X2 80 ไม่มีผลต่อเขตผลลัพธ์เพราะถูกบังคับโดยข้อยับยั้ง 5X1 + 4X2 100 แล้ว
ดังนั้นข้อยับยั้ง 8X1 + 4X2 80 เรียกว่า ข้อยับยั้ง redundant จุดใดก็ตาม (X1, X2 ) หรือบนขอบในเขตผลลัพธ์จะ
เข้ากับข้อยับยั้งทั้ง 4 ได้หมด เป็นที่แน่นอนว่าจะมีจุดนับไม่ถ้วน อย่างไรก็ดีเราสนใจที่จะพิจารณาจุดในเขตผลลัพธ์ที่จะให้
ค่าสูงสุดของ X0 อันดับต่อไปคือพิจารณาสมการเป้าหมาย X0 = 3X1+4X2 ซึ่งจะต้องให้ค่า X0 สูงขึ้นเรื่อยๆ ลองให้เส้นตรง
X0 = 3X1+4X2 ซึ่งเป็นเส้นขนานเคลื่อนที่จาก origin ขีดจำกัดในการเพิ่มขึ้นนี้คือ จะต้องมีอย่างน้อยหนึ่งจุดอยู่ในเขตผลลัพธ์
จากรูป 4-2 เส้น X0 = 3X1+4X2 สัมผัสเขตผลลัพธ์ที่จุด C โคออดิเนทของจุดจะให้ผลลลัพธ์ที่ดีที่สุดนั่นคือ X1 = 30.77 และ
X2 = 11.54 ซึ่งเป็นจุดเหมาะสมที่สุด และจะให้ค่า X0 = 138.5
|
