เรื่องที่ 4.1 วิธีการที่ใช้ในกำหนดการเชิงเส้น 

             วิธีซิมเพลก เป็นขั้นตอนที่ 2 ต่อจากขั้นตอนที่ 1 คือ สร้างตัวแบบซึ่งประกอบด้วยสมการเป้าหมาย ข้อจำกัดและข้อยับยั้ง
ที่ไม่ติดลบ  ก่อนที่จะใช้วิธีซิมเพลก  งานขั้นแรกคือ เปลี่ยนอสมการให้อยู่ในรูปสมการเสียก่อน  งานขั้นต่อไปจึงใช้วิธีคำนวณ
ด้วยการเขียนตาราง
1. การแปรรูปของตัวแบบ
              โปรแกรมเส้นตรงให้อยู่ในรูปมาตรฐาน  รูปมาตรฐานของ SP มีลักษณะดังนี้ 
                          Max.   Z   =  p1X1    +    p2X2  … +    pnXn
                หรือ   Min.    C   =  c1X1     +    c2X2  … +    cnXn
                ภายใต้เงื่อนไข
                          a11X1    +    a12X2  … +    a1nXn   = b1
                          a21X1    +    a22X2  … +    a2nXn   = b2
                                                                 	.
                                                                     .
                                                                     .
                         am1X1    +    am2X2  … +    amnXn   = bn
                         X1 , X2, … Xn   0
                         b1 , b2, … bn   0
                ดังได้กล่าวแล้ว  รูปมาตรฐานมีลักษณะที่สำคัญคือ
                        1.สมการเป้าหมายจะอยู่ในรูปทำให้ค่าสูงสุด (Maximization) หรือทำให้ค่าต่ำสุด (minimization)
                        2.ข้อจำกัดจะอยู่ในรูปที่แปลงจากอสมการให้เป็นสมการ (ใช้เครื่องหมายเท่ากับ)
                        3.ตัวแปรทุกตัวจะมีค่าเป็นลบไม่ได้
                        4.ตัวคงที่ขวามือของเครื่องหมายเท่ากับต้องเป็นบวก
                รูปมาตรฐานแบบเมทริกมีลักษณะดังนี้
                                 Max.   Z  =  PX           Min.   C  =  cX
                ภายใต้เงื่อนไข     AX  =  B                      AX  =  B 
                                              X    0                         X    0
                                              B    0                        B    0
               A  เป็นเมทริกขนาด         n x n  ซึ่งเป็นเมทริกสัมประสิทธิ์
               X  เป็นเวคเตอร์แนวตั้ง     n x 1  หรือที่เรียกว่า  decision  vector
               B  เป็นเวคเตอร์แนวตั้ง     n x 1  หรือ  requirement  vector
               C  เป็นเวคเตอร์แนวนอน  1 x n  หรือ  profit (cost) vector
               การปรับโปรแกรมเส้นตรงเพื่อใช้ซิมเพลก  จำเป็นต้องรู้จักตัวแปรเพิ่มอีก 3 ตัว ได้แก่ ตัวแปรขาด(slack variables)  
กับตัวแปรเกิน (surplus  variables) และตัวแปรเทียม (artificial variables) โดยแยกพิจารณาดังนี้

              1.1 กรณีที่น้อยกว่า  หมายความว่าข้างซ้ายน้อยกว่าข้างขวา ใช้สัญลักษณ์เพื่อที่จะทำให้ข้างซ้ายเท่ากับข้างขวา
ขวาก็ต้องเพิ่มตัวแปรขึ้นจำนวนหนึ่งเพื่อช่วยส่วนที่ขาดไปให้เท่ากับข้างขวา  ตัวแปรที่เพิ่มเข้านี้ไปเรียกว่า slack variables 
ตัวอย่างเช่น
                                 Max.  Z  =  3X1  +  5X2
            โดยขึ้นอยู่กับ           X1     5                    -------- (1)
                                          X1     6                    -------- (2)
                          3X1  + 2X2      18                 -------- (3)
                                         X1     0
                                         X2     0
               จะเห็นว่าข้อจำกัดข้างบนเป็นชนิด       จึงต้องหาตัวแปรมาเพิ่มทางซ้ายมือเพื่อให้เท่ากับด้านขวาโดยสมการที่ 
(1) + X3   สมการที่ (2) + X4 สมการที่ (3) + X5 เราจะได้
                                                   X1  +  X3  =  5
                                                   X2  +  X4  =  6
                                      3X1 +  2X2 + X5  =  18
              แล้วเพิ่มข้อยับยั้งให้เข้าเกณฑ์คือ  X3 , X4 , X5    0
             ส่วนสมการเป้าหมายจะไม่เปลี่ยนแปลงแต่อย่างใดเพราะเราสมมติให้  C3 =  0, C4 =  0  และ C5 =  0  จากตัวอย่างนี้ 
X3 , X4  และ X5  เรียกว่าตัวแปรขาดหรือ slack  variables ดังนั้น  L.P. ในรูปมาตรฐานจะเป็น

                                              Max.  Z  =  3X1 +  5X2 +  0X3  +  0X4  +  0X5  
                     ภายใต้เงื่อนไข
                                            X1  +  X3  =  5
                                            X2  +  X4  =  6
                               3X1 +  2X2 + X5  =  18
                        X1 , X2 , X3 , X4 , X5    0
             1.2 กรณีที่มากกว่า  หมายความว่าข้างซ้ายมากกว่าข้างขวา  ใช้สัญลักษณ์เพื่อที่จะทำข้างซ้ายให้มากกว่าข้างขวา
ก็ต้องหักข้างซ้ายด้วยตัวแปรจำนวนหนึ่งเพื่อช่วยให้ส่วนที่เหลือเท่ากับด้านขวามือ    ตัวแปรที่นำมาหักออกนี้เรียกว่า surplus
variables ตัวอย่างเช่น
                                             Max.  Z  =  3X1 +  5X2
                    โดยขึ้นอยู่กับ
                                            X1  +  X2     5              -------- (1)
                                       2X1  +  5X2     10            -------- (2)
                                                       X1     5              -------- (3)
                                               X1 , X2     0
             เนื่องจากข้อจำกัดอยู่ในรูป    จึงต้องหักสมการที่ 1 ด้วย  สมการที่ 2 ด้วย  และสมการที่ 3 ด้วย  เพื่อที่จะทำให้ทั้ง 
ข้างเท่ากัน  เราจะได้
                                           Max.  Z  =  3X1 +  5X2 +  0X3  +  0X4  +  0X5
          ภายใต้เงื่อนไข
                               X1  +  X 2 -  X3  =  3
                              2X1 +  5X2 - X4 =  10
                                           X1 -  X5  =  5
                     X1 , X2 , X3 , X4 , X5    0
       X3 , X4  และ X5 เป็นตัวแปรเกินที่เรียกว่า surplus  variables
            1.3 กรณีที่เท่ากัน  หมายความว่า  ข้างซ้ายเท่ากับข้างขวาอยู่แล้ว  ในบางครั้งเมื่อเราเติม slack variables 
หรือหัก surplus  variables  ออก  และเพื่อจะเพิ่มไอเดินติตี้แมทริก  เราอาจบวกตัวแปรเทียม (artificial variables)
เข้ากับสมการที่เป็นข้อยับยั้ง  ในการนี้ต้องบวกสมการเป้าหมายด้วยตัวแปรเทียม  พร้อมทั้งสัมประสิทธิ์ของตัวแปรเทียม
แต่ละตัวซึ่งสมมติให้มีค่ามาก  นิยมใช้ M  แทนจำนวนหนึ่งซึ่งมีค่ามาก  ตัวอย่างเช่น
                                              Min.  C  =  6X1 +  X2
                     โดยขึ้นอยู่กับ
                                       10X1 +  X2    20
                                         X1 +  5X2    15
                                       2X1 +  6X2    12
                     เปลี่ยนรูปเป็น
                                              Min.  C  =  6X1 +  X2 +  MX6  +  MX7  +  MX8
                     โดยขึ้นอยู่กับ
                                       10X1 +  2X2 – X3 + X6 =  20
                                          X1 +  5X2 -  X4  + X7 =  15
                                         2X1 +  6X2 - X5  + X8 =  12
                      X3 , X4 , X5       เป็นตัวแปรเกิน     surplus  variables
                      X5 , X6 , X7       เป็นตัวแปรเทียม  artificial variables