單純形法 (3)講稿

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

2、到第一個頂點(diǎn)？第三張，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月一、問題的提出從其標(biāo)準(zhǔn)形的解向量開始研究： 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月一、問題的提出頂點(diǎn)對應(yīng)的解向量有何代數(shù)特征？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，且非負(fù)。X1X2O(0,0) A(0,250)B(50,250)C(100,200)D(200,0)第六張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出既然頂點(diǎn)解向量中有兩個變量取值為0，而標(biāo)準(zhǔn)形中又有三個約束方程，是否可以直接通過這種方式找頂點(diǎn)？如令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？顯然不能得到相應(yīng)的解。第九張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出為什么令x20，x50時不能得到解？因?yàn)槠溆嗳齻€

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

6、奇異（可逆）的mm階子矩陣，則稱B為線性規(guī)劃問題的一個基。B由A中的m個線性無關(guān)列向量組成。第十三張，PPT共一百一十二頁，創(chuàng)作于2022年6月一、問題的提出一個基對應(yīng)一組概念：非基變量基變量基向量非基向量對應(yīng)基本解：（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月一、問題的提出基本解可能可行，也可能不可行。滿足非負(fù)約束條件的基本解叫基本可行解，相應(yīng)的基稱為可行基。否則為非可行基。第十六張，

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

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

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

13、一百一十二頁，創(chuàng)作于2022年6月二、單純形法的基本思路和原理第二步：最優(yōu)性檢驗(yàn)第二十八張，PPT共一百一十二頁，創(chuàng)作于2022年6月二、單純形法的基本思路和原理對應(yīng)于每一組基本解，目標(biāo)函數(shù)都可以表示成非基變量的函數(shù)，稱為典式。如：初始基本可行解（0，0，300，400，250）其非基變量為x1，x2目標(biāo)函數(shù)為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，其值完全有可能增加。說明此時目標(biāo)函數(shù)值還有增加的可能，沒有達(dá)到最優(yōu)。第三十一張，PPT共一百一十二頁，創(chuàng)作于2022年6月二、單純形法的基本思路和原理再如：基本解（50，250，0，50，0）其非基變量為x3，x5由約束方程可得：x150-x3+x5 x2250 -x5目標(biāo)函數(shù)為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īng)的目標(biāo)函數(shù)值已經(jīng)達(dá)到最優(yōu)。第三十四張，PPT共一百一十二頁，創(chuàng)作于20