กำหนดการเชิงเส้น 2

เทคนิคการแก้ปัญหากำหนดการเชิงเส้นโดยวิธีใช้กราฟ

หลักการ

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

กำหนดการเชิงเส้น

กำหนดการเชิงเส้น เป็นคณิตศาสตร์ประยุกต์แขนงหนึ่งที่คิดค้นขึ้นเพื่อการแก้ปัญหาเพื่อให้ได้กับความต้องการของมนุษย์สูงสุด โดยที่มีทรัพยากรจำกัด เช่น การเคลื่อนย้ายทหารให้มากที่สุดโดยที่เสียค่าใช้จ่ายน้อยที่สุด หรือการผลิตสินค้าให้ได้มากที่สุดโดยที่เสียค่าใช้จ่ายให้น้อยที่สุด
    กำหนดการเชิงเส้น จะอยู่ในรูปแบบทางคณิตศาสตร์ของสมการเชิงเส้นและอสมการเชิงเส้น แล้วหาค่าสูงสุด ต่ำสุดของฟังก์ชันที่สอดคล้องกับสมการ (และอสมการ) ที่กำหนด
ตัวแบบคณิตศาสตร์ ประกอบด้วย
1. ฟังก์ชันเชิงเส้น เป็นสมการที่สร้างให้ตรงกับจุดประสงค์ที่ต้องการ เรียกฟังก์ชันนี้ว่า ฟังก์ชันเป้าหมาย (Objective function)
2. เงื่อนไขจำกัด (เงื่อนไขบังคับ) ได้แก่อสมการหรือสมการที่เป็นเงื่อนไขที่กำหนดให้

การแก้ปัญหาโจทย์กำหนดการเชิงเส้น
1. กำหนดตัวแปรที่ใช้ในฟังก์ชันเป้าหมาย
2. สร้างฟังก์ชันเป้าหมายให้สอดคล้องกับที่โจทย์ต้องการ
3. สร้างเงื่อนไขบังคับตามข้อมูลที่โจทย์สั่ง
4. เขียนกราฟตามเงื่อนไขบังคับ ส่วนที่แรเงาของกราฟ จะเป็น คำตอบที่เป็นไปได้ และค่า (x,y) ที่ทำให้ฟังก์ชันเชิงเส้นมีค่าสูงสุด จะเรียกว่า คำตอบที่เหมาะสมที่สุด
5. หาพิกัด (x,y) ที่เป็นจุดมุมของกราฟ นำแต่ละจุดไปแทนค่าในฟังก์ชันเป้าหมาย จะได้ค่าสูงสุดหรือต่ำสุดตามต้องการ

ข้อควรระวัง
1. ถ้าโจทย์ถามเกี่ยวกับคำตอบที่เหมาะสม คำตอบที่เหมาะสมจะเป็นจุดมุมของกราฟของคำตอบที่เป็นไปได้
2. ในกรณีที่หาจุด (x,y) ซึ่งคำตอบที่เหมาะสมที่สุดได้ 2 จุด เช่น จุด A(x₁,y₁) B(x₂,y₂) จะได้ว่า จุดที่อยู่ระหว่างจุด A กับ B จะเป็นคำตอบที่เหมาะสมด้วย
3. โจทย์บางข้ออาจไม่มีคำตอบที่เหมาะสมที่สุด เช่น ให้ P = 2,200 + 1800y และมีสมการเงื่อนไขดังรูป