<%@LANGUAGE="VBSCRIPT" CODEPAGE="874"%> การวิจัยดำเนินการ [ Operation Research ]
บทนำ
CPM/PERT
เกม
กำหนดการเชิงเส้น
ดูอัล
สินค้าคงเหลือ
ระบบแถวคอย
ปัญหาการขนส่ง
เมทริกซ์
 

Course Introduction
Course Syllabus
Lesson
Course Map
Webboard
E-mail
Course Team
 




                             เรื่องที่ 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
เรื่องที่