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

สรุป
            ขั้นที่ 1 ตั้ง  initial  basis  solution
            ขั้นที่ 2 เลือกตัวแปรเข้า basis
            ขั้นที่ 3 เลือกตัวแปรออกจาก basis
            ขั้นที่ 4 เปลี่ยน basis แล้วกลับไปทำขั้นที่ 2

                                                               ตารางซิมเพลก

            ระเบียบวิธีซิมเพลกดังที่ได้กล่าวแล้วนั้น  นายยอร์ชบีดานซิก  เป็นผู้คิดขึ้น  ซึ่งมีจุดสำคัญ 3 จุดในการที่จะลดขั้นตอน
จากจำนวนผลลัพธ์ที่มีนับไม่ถ้วน  เป็นจำนวนผลลัพธ์ที่ดี และนับได้ดังนี้คือ 
           1.การที่จะได้ผลลัพธ์ที่เหมาะสมนั้นต้องกำหนดตัวที่ไม่ทราบค่า  n ค่า (จากตัวที่ไม่ทราบค่า m+n ค่า) ให้เท่ากับศูนย์  
แล้วหาตัวที่ไม่ทราบค่าที่เหลือ m ค่านั้น  ทั้งนี้หมายความว่าถ้ามีผลลัพธ์และเป็นเอกลักษณ์  ตัวอย่างเช่น
                                                        2X1  +  3X2  +  8X3  =  9
                                                        4X1  +  6X2  +  7X3  =  8
         ด้วยการกำหนด  X3 = 0 สมการทั้งสองนี้จะลงท้ายด้วยการหาคำตอบไม่ได้  ในทำนองเดียวกัน  ถ้าข้างขวาของเครื่องหมาย
ในสมการที่สองเป็น 18 แทน 8 ดังนั้น ถ้า ทั้งสองสมการนี้จะเหมือนกันที่ X3 = 0 ซึ่งจะลงท้ายด้วยการมีการมีจำนวนผลลัพธ์ที่
มากจนนับไม่ได้
         ในกรณีนี้ ตัวแปรที่มีค่าเป็นศูนย์ n ตัวนี้เรียกว่า nonbasic  variable  ตัวแปรที่เหลือ m ตัวนั้นเรียกว่า  basic
variable และจะประกอบกันเป็นผลลัพธ์ที่เรียกว่า basic  solution เป็นที่สังเกตได้ว่า  โดยเงื่อนไขเช่นนี้  จำนวนผลลัพธ์
ที่เหมาะสมจะลดจำนวนลงจากจำนวนมากที่นับไม่ได้จนเป็นจำนวนที่นับได้  โดยมีขีดจำกัดสูงสุดคือ
                                                        (m+n)/m     =     (m+n)!/m!n!
          2.ดังได้กล่าวแล้วในคำนิยามของโปรแกรมเส้นตรงว่าตัวแปรทุกตัวจะติดลบไม่ได้เนื่องจากผลลัพธ์พื้นฐาน  (basic  
solution) ที่คัดเลือกมาจากข้อ (1) ดังได้กล่าวแล้วไม่จำเป็นที่จะไม่ติดลบเสมอไป  การลดจำนวนเพื่อหาผลลัพธ์ที่เหมาะสม
ก็ยังพอทำได้ด้วยการกำจัดผลลัพธ์พื้นฐานที่เป็นไปไม่ได้ (infeasible  basic  solution)ได้  นั่นคือผลลัพธ์ที่มีตัวแปร
ค่าต่ำกว่าศูนย์  ในการนี้ทำได้ในระเบียบวิธีซิมเพลก  ด้วยการคัดเลือกผลลัพธ์พื้นฐานที่ไม่ติดลบ  (  0 ) ถ้าตัวแปรพื้นฐาน 
ฐาน (basic  solution) เป็นบวกหมดทุกตัว  ผลลัพธ์ที่ได้เรียกว่า  nondegenerate (แย้งกัน) basic variable 
variable ที่ถูกกำหนดค่าให้เป็นศูนย์เรียกว่า  leaving  variable ในขณะที่ในตัวแปรใหม่เข้ามาแทนนั้นเรียกว่า
entering  variable (สังเกตได้ว่าทุกครั้งผลลัพธ์พื้นฐานจะต้องมีตัวแปร n ตัว) 
          3.ดังได้กล่าวแล้วในข้อ (2)  สามารถสร้างผลลัพธ์พื้นฐานใหม่จากพื้นฐานที่แล้วด้วยการคัดเลือกตัวแปรที่เข้าและออก  
ออก  เราต้องเลือกตัวแปรเข้าซึ่งจะทำให้มีการปรับค่าตามเป้าหมายได้ดีขึ้นกว่าเดิม  ด้วยการคัดเลือก nonbasic  variable 
variable ที่จะทำให้มีการปรับค่าตามเป้าหมายได้ดีขึ้นกว่าเดิม  ด้วยการคัดเลือก  ที่จะให้กำไรต่อหน่วยสูงสุด  ในสมการ
เป้าหมายเป็นตัวแปรเข้า  ให้ทำดังนี้ซ้ำกันจนกระทั่งปรับปรุงไม่ดีขึ้นไปกว่าเดิม  เรียกว่าได้ผลลัพธ์พื้นฐานที่เหมาะสมแล้ว 
optimal basic infeasible solution นั่นคือถึงจุดที่เหมาะสม
ตัวอย่างเช่น  จงพิจารณาโปรแกรมเส้นตรงต่อไปนี้
                                            maximize  X0  =  3X1  +  5X2  -  2X3
          โดยขึ้นอยู่กับ
                                         X1  +  2X2  +  2X3    10
                                        2X1  +  4X2   -  3X3   15
                                      X1  0,  X2  0, X3    0
         หลังจากที่บวก  slack  variable  S1  และ S2  แล้ว   จัดให้อยู่ในตารางได้  ดังนี้