เทคนิคการแก้ปัญหากำหนดการเชิงเส้นโดยวิธีใช้กราฟ
หลักการ
1. ถ้าโจทย์ที่ให้มาเป็นเรื่องราวที่ให้มาเป็นเรื่องราวที่ไม่ได้บอกตัวแปรออกมาตรงๆ เราซึ่งเป็นผู้อ่านโจทย์
จะต้องตั้งตัวแปรให้เป็นปริมาณต่างๆ จากโจทย์และสร้างสมการจุดประสงค์ กับอสมการข้อจำกัด
จะต้องตั้งตัวแปรให้เป็นปริมาณต่างๆ จากโจทย์และสร้างสมการจุดประสงค์ กับอสมการข้อจำกัด
2. เขียนกราฟของระบบอสมการข้อจำกัด เพื่อแสดงจุดทุกจุดในบริเวณส่วนที่แรเงาที่สอดคล้องกับระบบ
อสมการข้อจำกัด
อสมการข้อจำกัด
3. หาจุดหักมุมในบริเวณส่วนที่แรเงา
4. นำจุดหักมุมแต่ละจุดไปแทนค่าในสมการจุดประสงค์
4.1 ถ้าได้ค่าน้อยที่สุด (มากที่สุด) เพียงคำตอบเดียว แล้วค่านั้นคือ ค่าน้อยที่สุด (มากที่สุด)
ของสมการจุดประสงค์
ของสมการจุดประสงค์
4.2 ถ้ามีจุดหักมุม 2 จุด ที่มีแขนของจุดหักมุมร่วมกันทำให้สมการจุดประสงค์ มีค่าน้อยที่สุด
(มากที่สุด)
(มากที่สุด)
แล้วจุดทุกจุดบนแกนของมุมนั้น คือ ค่าน้อยที่สุด(มากที่สุด) ของสมการจุดประสงค์ แสดงว่าคำตอบที่เหมาะสม จะมีจำนวนนับไม่ถ้วน
ตัวอย่าง กำหนดให้สมการจุดประสงค์ คือ P = 30x + 50y
และอสมการข้อจำกัด คือ 2x + y ≤ 10
x + 2y ≤ 11
x ≥ 0
y ≥ 0
แล้วจงหาว่า P มีค่ามากที่สุดเป็นเท่าไร
วิธีทำ เขียนกราฟของระบบอสมการข้อจำกัด พร้อมจุดหักมุม
จากรูปจะเห็นได้ว่าจุดหักมุมของรูปสี่เหลี่ยมคือ (0,0) , (0,5.5) , (3,4) และ (5,0) นำจุดหักมุมแทนค่าในจุดประสงค์ ดังตารางต่อไปนี้
ดังนั้น จากตาราง จะพบว่า ค่ามากที่สุดของ P คือ 290 เมื่อ x = 3 และ y = 4
ไม่มีความคิดเห็น:
แสดงความคิดเห็น