รูปแบบง่ายที่สุดของกำหนดการเชิงเส้น-กำหนดการเชิงเส้น (linear programming) คณิตศาสตร์ ม.ปลาย

รูปแบบง่ายที่สุดของกำหนดการเชิงเส้น

               ลักษณะของรูปแบบง่ายที่สุดของกำหนดการเชิงเส้น

1. ตัวแปรตัดสินใจต้องไม่เป็นลบ
2. ทุกๆข้อจำกัดอยู่ในรูปอสมการ ≤
3. ฟังก์ชันเป้าหมายอยู่ในรูปการหาค่าสูงสุด

               กรณีการหาค่าต่ำสุด

1.                         ถ้าต้องการหาค่า Z ที่น้อยที่สุด สามารถเขียนในรูป –Z และ –Z  ที่มากที่สุด
2. เครื่องหมายของอสมการ ≤ หรือ ≥ จะเปลี่ยนตรงกันข้ามโดยเอา -1 คูณตลอดสมการ

                                                a₁x₁ + a₂x₂   ≥ b สมมูลกับ –a₁x₁ – a₂x₂   ≤ – b หรือ

                                                  p₁x₁ +p₂x₂ ≤ q สมมูลกับ – p₁x_{1 –} p₂x₂  ≥ – q 

3. ข้อจำกัดสมการจะเขียนอยู่ในรูปอสมการ 2 อสมการที่มี เครื่องหมาย

                                                 a₁x₁ + a₂x₂ ≥ b ตรงข้ามกับ เช่น

                                          เขียนได้เป็น    a₁x₁ + a₂x₂  ≤ b สมมูลกับ    a₁x₁ + a₂x₂  ≥ b

                                                      หรือ    a₁x₁ + a₂x₂ ≤ b สมมูลกับ –a₁x₁ – a₂x₂    ≤  -b

4. อสมการข้อจำกัดค่าสมบูรณ์จะสามารถเขียนอยู่ในรูป 2 อสมการ เช่น

                                             |a₁x₁ + a₂x₂ |≤ b, b ≥ 0 จะได้  a₁x₁ + a₂x₂ ≥ -b 

                                                                                      และ a₁x₁ + a₂x₂  ≤ b

                                  หรือ                                                 

                                            |a₁x₁ + a₂x₂ |≥ b, b ≥ 0   จะได้ a₁x₁ + a₂x₂ ≥ b

                                                                                       และ a₁x₁ + a₂x₂ ≤ -b

5. ตัวแปรที่ไม่จำกัดเครื่อง (อาจจะเป็น +,-) จะสมมูลกับผลต่างระหว่างตัวแปรที่ไม่เป็นลบ 2 ตัว เช่น  X เป็นตัวแปรที่ไม่จำกัดเครื่องหมาย จะเขียนแทน x ด้วย x ⁺ – x ⁻ เมื่อ x ⁺≥ 0 และ x ⁻ ≥ 0

ตัวอย่าง 3 

   หาค่าต่ำสุด Z = 3 X₁– 3 X₂+ 7 X₃                           หาค่าสูงสุด Z’ = -Z =  3 X₁– 3 X₂+ 7 (x ⁺ – x ⁻)

    ข้อจำกัด  X₁– X₂+ 3X₃          ≤ 40                     ข้อจำกัด     X₁– X₂ + 3X₃ (x ⁺ – x ⁻)   ≤  40                               

                  X₁ + 9 X₂– 7 X₃      ≥ 50                                – X₁– 9X₂+ 7(x ⁺ – x ⁻)         ≤ 50

                 

                   5 X₁+ 3 X₂            = 20              ⇨                       5X₁+ 3 X₂                  = 20                                                   

                         |5X₁+ 8X₂|      ≤ 100                                     -5 X₁– 3 X₂                  = 20                                                 

                                 X₁, X₂      ≥ 0                                       5X₁+ 8X₃(x ⁺ – x ⁻)       ≤ 100                                                                    

                    X₃ ไม่จำกัดเครื่องหมาย                                      -5 X₁– 8 X₃(x ⁺ – x ⁻)      ≤ 100

                                                                                                  X₁, X₂ ,x ⁺ , x ⁻         ≥ 0     

กำหนดการเชิงเส้น (linear programming)  เป็นวิธีการทางคณิตศาสตร์ประยุกต์ ซึ่งได้พัฒนาขึ้นตั้งแต่ก่อน พ.ศ. 2483 เพื่อช่วยในการตัดสินใจเกี่ยวกับการใช้ทรัพยากรที่มีอยู่อย่างจำกัดให้เกิดประโยชน์สูงสุด คำว่า ทรัพยากร ในที่นี้หมายถึง เครื่องจักร กำลังคน วัตถุดิบ เวลา หรือเงินลงทุนก็ได้ วิธีการของกำหนดการเชิงเส้นทำให้เราทราบว่าควรตัดสินใจเกี่ยวกับการลงทุนอย่างไร จึงจะได้ผลกำไรสูงสุดภายใต้ข้อจำกัดและเงื่อนที่มีอยู่ ปัจจุบันมีการประยุกต์ใช้วิธีการกำหนดการเชิงเส้นในหลายวงการ เช่น