กำหนดการเชิงเส้น
สมการเชิงเส้น
คือ
สมการซึ่งตัวแปรทุกตัวมีกำลังเป็นหนึ่ง
และกราฟเป็นเส้นตรง
อสมการเชิงเส้น คือ
อสมการซึ่งตัวแปรทุกตัวในอสมการมีกำลังหนึ่ง
การเขียนกราฟ
การเขียนกราฟอสมการเชิงเส้น
ทำได้โดยการเปลี่ยนอสมการเชิงเส้นเป็นสมการเชิงเส้น
(ทำให้ได้กราฟเป็นเส้นตรง L)
แล้วจัดรูปแบบอสมการใหม่ โดยที่
|
ตัวแบบทางคณิตศาสตร์ของกำหนดการเชิงเส้น
กำหนดการเชิงเส้น
เป็นคณิตศาสตร์ประยุกต์แขนงหนึ่งที่คิดค้นขึ้นเพื่อการแก้ปัญหาเพื่อให้ได้กับความต้องการของมนุษย์สูงสุด
โดยที่มีทรัพยากรจำกัด เช่น
การเคลื่อนย้ายทหารให้มากที่สุดโดยที่เสียค่าใช้จ่ายน้อยที่สุด
หรือการผลิตสินค้าให้ได้มากที่สุดโดยที่เสียค่าใช้จ่ายให้น้อยที่สุด
กำหนดการเชิงเส้น
จะอยู่ในรูปแบบทางคณิตศาสตร์ของสมการเชิงเส้นและอสมการเชิงเส้น
แล้วหาค่าสูงสุด
ต่ำสุดของฟังก์ชันที่สอดคล้องกับสมการ
(และอสมการ) ที่กำหนด
ตัวแบบคณิตศาสตร์ ประกอบด้วย
1. ฟังก์ชันเชิงเส้น
เป็นสมการที่สร้างให้ตรงกับจุดประสงค์ที่ต้องการ
เรียกฟังก์ชันนี้ว่า
ฟังก์ชันเป้าหมาย (Objective function)
2. เงื่อนไขจำกัด
(เงื่อนไขบังคับ)
ได้แก่อสมการหรือสมการที่เป็นเงื่อนไขที่กำหนดให้
การแก้ปัญหาโจทย์กำหนดการเชิงเส้น
1.
กำหนดตัวแปรที่ใช้ในฟังก์ชันเป้าหมาย
2.
สร้างฟังก์ชันเป้าหมายให้สอดคล้องกับที่โจทย์ต้องการ
3.
สร้างเงื่อนไขบังคับตามข้อมูลที่โจทย์สั่ง
4. เขียนกราฟตามเงื่อนไขบังคับ
ส่วนที่แรเงาของกราฟ จะเป็น
คำตอบที่เป็นไปได้ และค่า (x,y)
ที่ทำให้ฟังก์ชันเชิงเส้นมีค่าสูงสุด
จะเรียกว่า
คำตอบที่เหมาะสมที่สุด
5. หาพิกัด (x,y)
ที่เป็นจุดมุมของกราฟ
นำแต่ละจุดไปแทนค่าในฟังก์ชันเป้าหมาย
จะได้ค่าสูงสุดหรือต่ำสุดตามต้องการ
ข้อควรระวัง
1.
ถ้าโจทย์ถามเกี่ยวกับคำตอบที่เหมาะสม
คำตอบที่เหมาะสมจะเป็นจุดมุมของกราฟของคำตอบที่เป็นไปได้
2. ในกรณีที่หาจุด (x,y)
ซึ่งคำตอบที่เหมาะสมที่สุดได้ 2
จุด เช่น จุด A(x1,y1) B(x2,y2)
จะได้ว่า จุดที่อยู่ระหว่างจุด A
กับ B จะเป็นคำตอบที่เหมาะสมด้วย
3.
โจทย์บางข้ออาจไม่มีคำตอบที่เหมาะสมที่สุด
เช่น ให้ P = 2,200 + 1800y
และมีสมการเงื่อนไขดังรูป
|
|
