การแก้ปัญหา Linear Programming ด้วยวิธีกราฟ

[kekhuay]

กำหนดให้ $P$ เป็นสมการจุดประสงค์ โดยที่ $P = 6x + 7y$ และมีอสมการข้อกำหนดดังต่อไปนี้
$3x + 4y \leqslant 12$
$x - y \geqslant 0$
$x \geqslant 0, y \geqslant 0$
จงหาค่าสูงสุดของ $P$
ที่ผมสงสัยก็คือเงื่อนไข $x - y \geqslant 0$ นี่มันพล็อตยังไงครับ

[nooonuii]

วาด $x-y=0$ ก่อน จากนั้นเลือกจุดที่ไม่ได้อยู่บนเส้นกราฟมาทดสอบโดยการแทนลงในอสมการ

ถ้าแทนแล้วสอดคล้องกับอสมการ เซตคำตอบทั้งหมดจะอยู่ฝั่งเดียวกับจุดนั้นโดยมีสมการ $x-y=0$ เป็นเส้นแบ่ง

แต่ถ้าแทนแล้วไม่สอดคล้องอสมการ เซตคำตอบทั้งหมดจะอยู่ฝั่งตรงข้ามจุดนั้นแทน เช่น

เลือกจุด $(2,1)$ มาแทนจะได้ $2-1\geq 0$ ซึ่งเป็นจริง ดังนั้นเซตคำตอบของอสมการจะเป็น half plane ที่อยู่ข้างเดียวกับจุด $(2,1)$

แต่ถ้าแทนด้วยจุด $(1,2)$ จะพบว่าไม่สอดคล้องอสมการ เซตคำตอบก็จะอยู่ฝั่งตรงข้ามกับจุด $(1,2)$ ซึ่งก็จะอยู่ฝั่งเดียวกับจุด $(2,1)$ นั่นเอง