單純形法 (3)講稿

1、關于單純形法 (3)第一張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出圖解法只能解決二維的線性規(guī)劃問題，那更多變量的問題怎么辦？(jsj)通過代數算法搜尋最優(yōu)解。單純形法，就是這樣的一種代數搜尋法。線性規(guī)劃問題的解一般有無窮多個，如果不縮小搜尋范圍，工作量太大！我們首先將最優(yōu)解縮小在一個有限的范圍。第二張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出回顧圖解法，我們知道：最優(yōu)解必定在可行域的頂點上取得，而頂點的個數總是有限的。多維線性規(guī)劃問題的可行域也存在有限個頂點。如果能夠從一個頂點開始，通過某種方式向更優(yōu)頂點轉移，總會找到最優(yōu)點。首先面臨的問題：如何通過代數方法找

2、到第一個頂點？第三張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出圖解法中的例1.5模型為： Max z= 50 x1+100 x2 s.t. 1x1+1x2300 2x1+1 x2400 0 x1+1 x2250 x1 0， x2 0第四張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出從其標準形的解向量開始研究： Max z= 50 x1+100 x2 s.t. 1x1+1x2+1x3+0 x4+0 x5300 2x1+1x2+0 x3+1x4+0 x5400 0 x1+1x2+0 x3+0 x4+1x5250 xj 0 (j=1,2,3,4,5)第五張，PPT共一百

3、一十二頁，創(chuàng)作于2022年6月一、問題的提出頂點對應的解向量有何代數特征？O (0,0,300,400,250)A (0,250,50,150,0)B (50,250,0,50,0)C (100,200,0,0,50)D (200,0,100,0,50)答案：都有兩個變量取值為0，且非負。X1X2O(0,0) A(0,250)B(50,250)C(100,200)D(200,0)第六張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出既然頂點解向量中有兩個變量取值為0，而標準形中又有三個約束方程，是否可以直接通過這種方式找頂點？如令x10，x20，則x3300，x4400，x5250可

4、得到解（0，0，300，400，250）第七張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出又如：令x30，x50，由約束條件：x1+x2+x33002x1+x2+x4400 x2+x5250可得到解（50，250，0，50，0）第八張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出若令x20，x50，會怎樣？由約束方程可知：x1+x2+x3300 x1+x3300 2x1+x2+x4400 2x1+x4400 x2+x5250 0250？顯然不能得到相應的解。第九張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出為什么令x20，x50時不能得到解？因為其余三個

5、變量的系數列向量為該矩陣是非可逆矩陣，即去掉x2和x5后的三個約束方程線性相關，這種情況下得不到解。第十張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出既然如此，如果我們在技術矩陣中取出三列，組成一個可逆陣，令其余兩列對應的變量為零，則一定可以得到一個解。第十一張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出如，取1、2、3列得到：此矩陣為可逆陣，故令x40，x50，一定可以得到一個解。對應的解為（75，250，-25，0，0）。第十二張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出基的概念：已知A是約束條件的mn階系數矩陣，其秩為m。設B是A矩陣中的一個非

6、奇異（可逆）的mm階子矩陣，則稱B為線性規(guī)劃問題的一個基。B由A中的m個線性無關列向量組成。第十三張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出一個基對應一組概念：非基變量基變量基向量非基向量對應基本解：（0，0，300，400，250）第十四張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出(0,0,300,400,250)(0,300,0,100,-50)(0,400,-100,0,150)(0,250,50,150,0)(300,0,0,-200,-50)(200,0,100,0,50)不存在(100,200,0,0,50)(50,250,0,50,0)(75,2

7、50,-25,0,0)基本解是x3 ,x5p3 ,p5x1 ,x2 ,x4p1 ,p2 ,p4B2=(p1,p2 ,p4 )是x3 ,x4p3 ,p4x1 ,x2 ,x5p1 ,p2 ,p5B3=(p1 ,p2 ,p5) 是x1 ,x2p1 ,p2x3 ,x4 ,x5p3 ,p4 ,p5B10 =(p3,p4,p5)否x1 ,x3p1 ,p3x2 ,x4 ,x5p2 ,p4 ,p5B9=(p2,p4,p5)否x1 ,x4p1 ,p4x2 ,x3 ,x5p2 ,p3 ,p5B8=(p2 ,p3,p5)是x1 ,x5p1 ,p5x2 ,x3 ,x4p2 ,p3 ,p4B7=(p2 ,p3,p4)否

8、x2 ,x3p2 ,p3x1 ,x4 ,x5p1 ,p4 ,p5B6=(p1 ,p4 ,p5)是x2 ,x4p2 ,p4x1 ,x3 ,x5p1 ,p3 ,p5B5=(p1 ,p3 ,p5)x2 ,x5p2 ,p5x1 ,x3 ,x4p1 ,p3 ,p4B4=(p1 ,p3 ,p4) 否x4 ,x5p4 ,p5x1 ,x2 ,x3p1 ,p2 ,p3B1=(p1 ,p2 ,p3)是否可行非基變量非基向量基變量基向量基第十五張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出基本解可能可行，也可能不可行。滿足非負約束條件的基本解叫基本可行解，相應的基稱為可行基。否則為非可行基。第十六張，

9、PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出A：(0,250,50,150,0)B：(50,250,0,50,0)C：(100,200,0,0,50)D：(200,0,100,0,50)O：(0,0,300,400,250)E：(75,250,-25,0,0)F：(0,300,0,100,-50)G：(0,400,-100,0,150)H：(300,0,0,-200,-50)X1X2O(0,0)A(0,250)B(50,250)C(100,200)D(200,0)G(0,400)E(75,250)F(0,300)H(300,0)第十七張，PPT共一百一十二頁，創(chuàng)作于2022年6月一

10、、問題的提出線性規(guī)劃解的集合關系：基本解最優(yōu)解基本可行解可行解第十八張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出顯然，將搜索范圍控制在基本可行解內，將大大減少搜索工作量。但是，即使取得一個基，得到的解還不一定可行。如何才能保證取得一個可行基呢？第十九張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出總結：1、可行域頂點對應的解必為基本可行解：有n-m個變量取值為0，滿足非負條件。2、一個基對應一組基本解，可能可行，也可能不可行；3、最優(yōu)解必定在基本可行解中；第二十張，PPT共一百一十二頁，創(chuàng)作于2022年6月二、單純形法的基本思路和原理單純形法的基本思路：首先找到一個

11、頂點；然后判斷它是否最優(yōu)；如果不是，則通過更換頂點的方式找到更優(yōu)的頂點；直到找到最優(yōu)頂點。第二十一張，PPT共一百一十二頁，創(chuàng)作于2022年6月二、單純形法的基本思路和原理第一步：找到一個頂點 （初始基本可行解）第二十二張，PPT共一百一十二頁，創(chuàng)作于2022年6月二、單純形法的基本思路和原理思考：1、令n-m個變量為0（非基變量）是否一定可以找到？答案：不一定。如例中x20，x50時不能得到解。可行的辦法：找到一個基。第二十三張，PPT共一百一十二頁，創(chuàng)作于2022年6月二、單純形法的基本思路和原理2、一個基是否一定對應可行域頂點？答案：不一定。必須是可行基。一般來說，判斷一個基是否是可行基

12、，需要在求出其基本解后才能判斷。第二十四張，PPT共一百一十二頁，創(chuàng)作于2022年6月二、單純形法的基本思路和原理3、那有沒有辦法在求出解之前保證我們取得的基為可行基？解決辦法：保證右端項非負，找到一個單位矩陣，必定是一個可行基。第二十五張，PPT共一百一十二頁，創(chuàng)作于2022年6月二、單純形法的基本思路和原理如范例系數陣：存在3階單位陣（初始可行基）右端項非負第二十六張，PPT共一百一十二頁，創(chuàng)作于2022年6月二、單純形法的基本思路和原理基本可行解為（0，0，300，400，250）此可行基稱為初始可行基。對應的解稱為初始基本可行解。初始基本可行解在上頁矩陣中一目了然。第二十七張，PPT共

13、一百一十二頁，創(chuàng)作于2022年6月二、單純形法的基本思路和原理第二步：最優(yōu)性檢驗第二十八張，PPT共一百一十二頁，創(chuàng)作于2022年6月二、單純形法的基本思路和原理對應于每一組基本解，目標函數都可以表示成非基變量的函數，稱為典式。如：初始基本可行解（0，0，300，400，250）其非基變量為x1，x2目標函數為Max z= 50 x1+100 x2第二十九張，PPT共一百一十二頁，創(chuàng)作于2022年6月二、單純形法的基本思路和原理典式Z= 50 x1+100 x2如果x1增加1，Z會怎樣？答案：Z增加50。如果x2的值增加1，Z會怎樣？答案：Z增加100。第三十張，PPT共一百一十二頁，創(chuàng)作于2

14、022年6月二、單純形法的基本思路和原理x1，x2的取值是否有增加的可能？分析：該解中非基變量 x1，x2的取值為0，其值完全有可能增加。說明此時目標函數值還有增加的可能，沒有達到最優(yōu)。第三十一張，PPT共一百一十二頁，創(chuàng)作于2022年6月二、單純形法的基本思路和原理再如：基本解（50，250，0，50，0）其非基變量為x3，x5由約束方程可得：x150-x3+x5 x2250 -x5目標函數為Max z= 50 x1+100 x2 27500-50 x3-50 x5第三十二張，PPT共一百一十二頁，創(chuàng)作于2022年6月二、單純形法的基本思路和原理典式Z= 27500-50 x3-50 x5如果x3增加1，Z會怎樣？答案：Z減少50。如果x5的值增加1，Z會怎樣？答案：Z減少50 ?？梢娨筞增加，只有使x3和x5減少。第三十三張，PPT共一百一十二頁，創(chuàng)作于2022年6月二、單純形法的基本思路和原理x3，x5的取值是否有減少的可能？分析：該解中非基變量 x1，x2的取值為0，其值不可能再減少。所以Z值不可能再增加。說明此基本解對應的目標函數值已經達到最優(yōu)。第三十四張，PPT共一百一十二頁，創(chuàng)作于20