เรื่องที่ 4.1 วิธีการที่ใช้ในกำหนดการเชิงเส้น
2.วิธีซิมเพลก เนื่องจากสมการเป้าหมายมี 2 ชนิดคือหาค่าสูงสุดและหาค่าต่ำสุด จึงต้องแยกพิจารณาว่าเป็นกรณีใด ส่วนใหญ่
ใหญ่เรามักใช้กรณีหาค่าสูงสุด และข้อจำกัดมีเครื่องหมาย เป็นพื้นฐาน
วิธีคำนวณเพื่อหาคำตอบให้ทำเป็นระบบย้อนซ้ำ ( Iteration ) จนกว่าจะได้จุดที่เหมาะสมตามต้องการ หลังจาก ที่ตั้ง Initial Basic Solution แล้ว ให้ใช้ขั้นตอนดังนี้
ขั้นที่ 1 เลือกตัวแปรเข้า Basis (entering variable) คือการเลือกตัวแปรที่เป็น ให้เป็น nonbasic ให้เป็น
basic โดยดูจากสัมประสิทธิ์ของตัวแปรที่ติดลบมากที่สุดแสดงว่าจะให้กำไรต่อหน่วยมากที่สุด แต่ถ้าสัมประสิทธิ์ของตัวแปร
ในสมการเป้าหมายเป็น + หรือ 0 แล้วแสดงว่าถึงจุดที่เหมาะสม ไม่ต้องทำต่อไปอีก
ขั้นที่ 2 เลือกตัวแปรออกจาก basis ด้วยการหาอัตราส่วนของคำตอบปัจจุบันกับสัมประสิทธิ์ของตัวแปรที่จะเข้า
basis ที่เลือกไว้ในขั้นที่ 1 (ไม่ต้องคำนึงถึงสัมประสิทธิ์ที่เป็นลบหรือศูนย์) เลือกอัตราส่วนที่ต่ำสุด อัตราส่วนต่ำสุดของตัว
basic variable อยู่ที่ตัวใดแสดงว่าตัวนั้นจะต้องออกจาก basis
ขั้นที่ 3 เปลี่ยน basis ด้วยการแลกที่กันระหว่างตัวแปรที่จะเข้า basis และตัวแปรที่จะออกจาก ด้วยการคำนวณ
โดยใช้แถวนอน (row operation)
ขั้นที่ 4 ให้กลับไปทำขั้นที่ 1, 2 และ 3 ต่อไปเรื่อย ๆ จนกระทั่งถึงจุดที่เหมาะสมแล้ว
2.1 สมการเป้าหมาย และข้อจำกัดมีเครื่องหมาย ตัวอย่าง Maximize X0 = 4X1 + 5X2 + 9X3 + 11X4 โดยขึ้นอยู่กับ X1 + X2 + X3 + X4 15 7X1 + 5X2 + 3X3 + 2X4 120 3X1 + 5X2 + 10X3 + 15X4 100 X1, X2, X3, X4 0
เปลี่ยนเป็นแบบมาตรฐาน X0 = 4X1 + 5X2 + 9X3 + 11X4 ภายใต้เงื่อนไข X1 + X2 + X3 + X4 + X5 = 15 7X1 + 5X2 + 3X3 + 2X4 + X6 = 120 3X1 + 5X2 + 10X3 + 15X4 + X7 = 100
เนื่องจากตัวแปรขาด slack variables ได้แก่ X5, X6, X7 พร้อมที่จะเป็นไอเดนดิตี้เมทริกได้จึงไม่ต้องบวก
ตัวแปรเทียม ก่อนที่จะคำนวณต้องจัดให้อยู่ในรูปของการเริ่มต้นหาคำตอบมาตรฐาน (Initial Basic Solution) ได้แก่
X0 4X1 5X2 9X3 - 11X4 = 0 R0 X1 + X2 + X3 + X4 + X5 = 15 R1 7X1 + 5X2 + 3X3 + 2X4 + X6 = 120 R2 3X1 + 5X2 + 10X3 + 15X4 + X7 = 100 R3 X0 X5 X6 X7 เรียกว่า basic variables หรือ basis X1 X2 X3 X4 เรียกว่า nonbasic variables เมื่อตั้ง Initial basic solution แล้ว ให้ดำเนินเป็นขั้น ๆ ดังนี้
1. เลือก entering variable
ถ้า nonbasic variables มีสัมประสิทธิ์ ใน Row 0 เป็น - ให้เลือกตัวแปรที่มีสัมประสิทธิ์ที่มีค่าลบมากที่สุด
ถ้าหาสัมประสิทธิ์เป็น + หรือ 0 ใน Row 0 แสดงว่าถึงจุดที่เหมาะสมแล้ว
จากตัวอย่าง เราต้องนำ X4 เข้า เพราะแต่ละหน่วยของ X4 จะทำกำไรให้ เพิ่มขึ้น 11 ถ้าเราเพิ่ม X4 มากเท่าใด
ก็เท่ากับเป็นการเพิ่ม X0 มากเท่านั้น ในการเพิ่ม X4 เราต้องลด basic variable ปัจจุบันที่เกี่ยวข้องกับ X4 ที่มีสัมประสิทธิ์
เป็นบวก เมื่อเรานำ X4 เข้ามาใน เราจะต้องหาตัว basic variable ออกจาก basis เพื่อแลกเปลี่ยนกับ X4
2.หาอัตราส่วนต่ำสุดเพื่อเอาตัว basis variable ออก
|
|
3.เปลี่ยน basis
จากตัวอย่างที่แล้ว X4 เข้า basis แต่ X7 ออกจาก basis หมายความว่า เราต้องใช้วิธีการคำนวณจากแนวนอน
นอน (row operation) เพื่อทำสัมประสิทธิ์ของ X4 ในแถวที่มี X7 อยู่ให้เป็น 1 แล้วทำสัมประสิทธิ์ของ X4ในแถวอื่น
ให้เป็น 0 ดังนี้
X0 - 4X1 - 5X2 - 9X3 - 11X4 = 0 R0 X1 + X2 + X3 + X4 + X5 = 15 R1 7X1 + 5X2 + 3X3 + 2X4 + X6 = 120 R2 R3 R3 % 15 1/5X1 +1/3X2 +2/3X3 + X4 +1/15 X7 = 20/3 R3 R0 R0 + 11R3 X0 - 9/5X1- 4/3X2 5/3X3 + 11/5X7 = 220/3 R0 R1 R1 + (-1)R3 4/5X1+ 2/3X2+ 1/3X3 - X5 - 1/15 X7 = 25/3 R1 R0 R0 + 11R3 33/5X1+13/3X2+5/3X3 + X6 - 2/15X7 = 320/3 R2 1/5X1 +1/3X2 +2/3X3 + X4 = 20/3 R3 X1 = X2 = X3 = X7 = 0 X4 = 20/3 กำไรใหม่จาก X0 4X1 5X2 9X3 11X4 กำไรใหม่ = (กำไรจากคำตอบที่แล้ว) + (จำนวนหน่วยของ basis variable ใหม่ ) x (กำไรที่เป็นไปได้ต่อหน่วย
ของ basis variable ใหม่ดังที่กำหนดไว้เป็นสัมประสิทธิ์ใน R0 แถวก่อน) = 0+20/3(11) = 220/3
การคำนวณซ้ำครั้งที่ 2 1.เลือกตัวแปรเข้า basis ปรากฏว่าสัมประสิทธิ์ของ X1 มีค่าลบมากที่สุด X1 จึงเลือก เป็นตัวแปรเข้า basis 2.เลือกตัวแปรออกจาก basis ด้วยการหาอัตราส่วนต่ำที่สุด
|
|
แสดงว่า X1 เข้า basis X5 ออกจาก basis
3. เปลี่ยน basis
ใช้การคำนวณแถวนอนเพื่อให้สัมประสิทธิ์ X1 เป็น 1
X0 - 9/5X1 - 4/3X2 - 5/3X3 +11/15 X7 = 220/3 R0 R1 R1 % 4/5 X1 + 5/6X2+ 5/12X3 +5/4X5 + 1/12X7 = 125/12 R1 33/5X1+13/3X2 + 5/3X3 + X6 -2/15 X7 = 320/3 R2 1/5X1 + 1/3X2 + 2/3X3 + X4 - 1/15X7 = 20/3 R3 ใช้การคำนวณแถวนอนเพื่อให้สัมประสิทธิ์ ในแถวอื่นยกเว้นแถวที่ เป็น R0 R0 +9/5R1 X0 + 1/6X2 11/12X3 + 9/4X5 +7/12X7 = 1105/12 R0 R1 R1 X1 + 5/6X2 + 5/12X3 + 5/4X5 - 1/12X7 = 125/12 R1 R2 R2 33/5R1 - 7/6X2 -13/12X3 -33/4X5 + X6 +5/12X7 = 455/15 R2 R3 R3 - 1/5R1 1/6X2 + 7/12X3+ X4 -1/4X5 +1/12X7 = 55/12 R3 กำไรใหม่ = 220/3 + 9/5 x 125/12 = 1105/12 เนื่องจากสัมประสิทธิ์ ยังมีลบอยู่แสดงว่ายังทำกำไรได้อีก จึงต้องคำนวณต่อไป
การคำนวณซ้ำครั้งที่ 3
1.เลือกตัวแปรเข้า basis ปรากฏว่าสัมประสิทธิ์ของ X3 มีค่าลบมากที่สุด จึงเลือก X3 เป็นตัวแปรเข้า 2.เลือกตัวแปรออกจาก basis ด้วยการหาอัตราส่วนต่ำที่สุด
|
|
ตัวแปรที่ออกจาก basis ได้แก่ X4
3. เปลี่ยน basis
R R X0 + 1/6X2 11/12X3 + 9/4X5 +7/12X7 = 1105/12 R0 R1 R1 X1 + 5/6X2 + 5/12X3 + 5/4X5 - 1/12X7 = 125/12 R1 R2 R2 -7/6X2 - 13/12X3 -33/4X5 + X6 + 5/12X7 = 455/15 R2 R3 R3 x12/7 2/7X2 + X3 + 12/7X4 -3/7X5 + 1/7X7 = 55/7 R3
R0 R0 +11/12R3 X0 + 3/7X2 +11/7X4 +13/7X5 +5/7X7 = 695/7 R0 R1 R1 +(-5/12R3) X1 +5/7X2 - 5/7X4 +10/7X5 - 1/7X7 = 50/7 R1 R2 R2 +(13/12R3) -6/7X2 + 13/7X4 - 61/7X5 +X6 + 4/7X7 = 325/7 R2 R3 R3 2/7X2 + X3 +12/7X4 - 3/7X5 + 1/7X7 = 55/7 R3 เนื่องจากสัมประสิทธิ์ใน R0 ไม่เป็นลบแสดงว่าถึงจุดที่เหมาะสมแล้ว นั่นคือ กำไร = X0 = 695/7 X1 = 50/7 X6 = 325/7 X3 = 55/7
|