1、2020/9/3,1,第4節(jié) 單純形法計算步驟,2020/9/3,2,Step 1 化為標(biāo)準(zhǔn)型，找出初始可行基，并列出初始單純形表,上述初始單純形表中，最后一行稱為檢驗數(shù)j,2020/9/3,3,2020/9/3,4,Step2：檢查非基變量所對應(yīng)的檢驗數(shù)j，若所有的j0，則當(dāng)前的基可行解就是最優(yōu)解，當(dāng)前的目標(biāo)函數(shù)值就是最優(yōu)值，停止計算。 否則，轉(zhuǎn)入下一步。 Step3：若存在一個k0，k所對應(yīng)的變量xk的系數(shù)列向量Pk0(即Pk中每一個分量aik0)，則該LP無有限最優(yōu)解，停止計算。 否則，轉(zhuǎn)入下一步。 Step4：進(jìn)行可行基的迭代。 重復(fù)以上步驟,2020/9/3,5,例7 用單純形法求解

2、例6。 max z = 2x1 + 3x2,s.t.,x1 + 2x2 +x3 =8 4x1 +x4 =16 4x2 +x5 =12 xj0，j=1,2,5,2020/9/3,6,練習(xí)：,分別用圖解法和單純形法求解下列線性規(guī)劃問題，并指出單純形法迭代的每一步相當(dāng)于圖形上哪一個頂點。,Max Z = 10 x1+ 5x2 3x1+ 4x29 5x1+ 2x2 8 x1 ，x20,2020/9/3,7,解：,j,10,5,0,0, ,3,8/5, ,x1入,x4出,j,0,1,0,-2, ,x2入,x3出,3/2,4,j,0,0,-5/14,-25/14,所以：X*=(x1,x2)T=(1,3/2

3、)T Z*=35/2, ,對應(yīng)0,對應(yīng)A,對應(yīng)B,2020/9/3,8,回顧：單純形法求解步驟：,2020/9/3,9,第5節(jié) 單純形法的進(jìn)一步討論,2020/9/3,10,第5節(jié) 單純形法的進(jìn)一步討論,一、人工變量法（大M法） 約束條件： “” 加一個松弛變量 “” 減一個剩余變量后，再加一個人工變量 “” 加一個人工變量 目標(biāo)函數(shù)： 人工變量的系數(shù)為“M”，即罰因子 若線性規(guī)劃問題有最優(yōu)解則人工變量必為0。,2020/9/3,11,MaxZ=-3x1+x3 x1+ x2+ x34 -2x1+ x2- x31 3x2+x3=9 xi 0,j=1,2,3,增加人工變量后，線性規(guī)劃問題中就存在一

4、個B為單位矩陣， 后面可以根據(jù)我們前面所講的單純形法來進(jìn)行求解。,MaxZ=-3x1+x3-Mx6-Mx7 x1+ x2+ x3+x4 =4 -2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi 0,j=1,7,標(biāo)準(zhǔn)化及變形,2020/9/3,12,練習(xí)：列出初始單純形表，并求解第2小題的最優(yōu)解 P55，2.2（1） 2.,2020/9/3,13,單純形表,j,-3-2M,4M,1,0,0, ,3,x2入，x6出,-M,0,4,1, ,j,6M-3,0,4M+1,0,-4M, ,-,x1入，x7出,3M,0,1,1, ,j,0,0,3,0,-M-3/2, ,9,x3入，x

5、1出,3/2,-M+1/2,3/2,-, ,j,-9/2,0,0,0,-M+3/4,-3/4,-M-1/4,所以：X*=(x1,x2,x3)T=(0,5/2, 3/2)T Z*=3/2,2020/9/3,14,二、兩階段法 第一階段暫不考慮原問題是否存在基可行解，給原問題加入人工變量，并構(gòu)建一個僅含人工變量的目標(biāo)函數(shù)（求極小化），人工變量的價值系數(shù)一般為1，約束條件和原問題的一樣。 當(dāng)?shù)谝浑A段中目標(biāo)函數(shù)的最優(yōu)值0，即人工變量0，則轉(zhuǎn)入第二階段；若第一階段中目標(biāo)函數(shù)的最優(yōu)值不等于0，即人工變量不等于0，則判斷原問題為無解。 第二階段：將第一階段計算所得的單純形表劃去人工變量所在的列，并將目標(biāo)函數(shù)

6、換為原問題的目標(biāo)函數(shù)作為第二階段的初始單純形表，進(jìn)行進(jìn)一步的求解。,2020/9/3,15,求解輔助問題，得到輔助問題的最優(yōu)解,引進(jìn)人工變量x6，x7，構(gòu)造輔助問題，輔助問題的目標(biāo)函數(shù)為所有人工變量之和的極小化,Max W = 0 ?,原問題沒有可行解。,把輔助問題的最優(yōu)解作為原問題的初始基礎(chǔ)可行解,用單純形法求解原問題，得到原問題的最優(yōu)解,否,是,兩階段法的算法流程圖,MaxZ=-3x1+x3 x1+ x2+ x34 -2x1+ x2- x31 3x2+x3=9 xi 0,j=1,2,3,Max W= -x6 - x7 x1+ x2+ x3+x4 =4 -2x1+ x2-x3 -x5+x6

7、=1 3x2+x3 +x7=9 xi 0,j=1,7,2020/9/3,16,(第一階段）單純形表1,j,-2,4,0,0,0, ,3,x2入，x6出,-1,0,4,1, ,j,6,0,4,0,-4, ,x1入，x7出,3,0,1,1, ,j,0,0,0,0,-1,0,-1,所以：已得最優(yōu)解，且人工變量為非基變量，則可去掉人工變量，得原問題的一個即可行基。,2020/9/3,17,（第二階段）單純形表2,j,0,0,3,0,3/2, ,-,9,3/2, ,x3入，x1出,j,-9/2,0,0,0,-3/4,所以： X*=(x1,x2,x3)T=(0,5/2, 3/2)T Z*=3/2,2020

8、/9/3,18,單純形法小結(jié),給定LP問題首先化為標(biāo)準(zhǔn)型，選取或構(gòu)造一個單位矩陣作為基，求出初始基可行解，并列出初始單純形表。標(biāo)準(zhǔn)化過程按第1.3節(jié)內(nèi)容分7種情況：,2020/9/3,19,第5節(jié) 單純形法的進(jìn)一步討論,人工變量法（大M法）和兩階段法 約束條件： “” 加一個松弛變量 “” 減一個剩余變量后，再加一個人工變量 “” 加一個人工變量 若線性規(guī)劃問題有最優(yōu)解則人工變量必為0。,2020/9/3,20,目標(biāo)函數(shù)極小化時解的最優(yōu)性判別； 無可行解的判別； 無界的判別； 無窮多最優(yōu)解的判別； 唯一最優(yōu)解的判別.,三、單純形法計算中的幾個問題,當(dāng)所有非基變量的j0時為最優(yōu)解；,最優(yōu)解中人工

9、變量為非0的基變量時；,存在某個k0，且所有的aik0時；,得最優(yōu)解時，有檢驗數(shù)為0的非基變量；,得最優(yōu)解時，所有非基變量檢驗數(shù)為負(fù)；,2020/9/3,21,j,40,45,0,25,100/3,40, 3 ,x2入，x4出,j,0,0,0,-5,因為全j 0,且1=0,則有無窮多最優(yōu)解。 所以：其中一個最優(yōu)解為X*=(0,80/3,20,0,0) T,Z*=1700,例1:,0,-10,思考：無窮多最優(yōu)解的一般形式？,2020/9/3,22,j,1,1,0,0,-,50, ,x1入，x4出,j,0,2,0,-1,因為2 = 2,且ai2 全0所以：無界,例2:,2020/9/3,23,例3

10、:,下表為一極大化問題對應(yīng)的單純形表,討論在a1,a2,a3,a4,a5,a6取何值的情況下，該表中的解為： 唯一最優(yōu)解； 無窮多最優(yōu)解； 無界； 無可行解； 非最優(yōu)，繼續(xù)換基： X3換入，x2換出,a40,a20, a30 a40,a50, x4或x2為人工變量，a60 ； x1為人工變量，a60 a40,a4a5;a6/a12a10 a60 a1 0,2020/9/3,24,復(fù)習(xí)題：下表為一求解極大值線性規(guī)劃問題的初始單純型表及迭代后的表， 為松弛變量，試求表中aL的值及各變量下標(biāo)mt的值；,2020/9/3,25,第6節(jié) 應(yīng)用舉例,一般而言，一個經(jīng)濟(jì)、管理問題凡是滿足以下條件時，才能建立

11、線性規(guī)劃模型。 .要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù)； .存在著多種方案； .要求達(dá)到的目標(biāo)是在一定條件下實現(xiàn)的，這些約束可用線性等式或不等式描述。,2020/9/3,26,建模步驟：, 第一步：設(shè)置要求解的決策變量。決策變量選取得當(dāng)，不僅能順利地建立模型而且能方便地求解，否則很可能事倍功半。 第二步：找出所有的限制，即約束條件，并用決策變量的線性方程或線性不等式來表示。 第三步：明確目標(biāo)要求，并用決策變量的線性函數(shù)來表示，確定對函數(shù)是取極大還是取極小的要求。 決策變量的非負(fù)要求可以根據(jù)問題的實際意義加以確定。,2020/9/3,27,一般的產(chǎn)品計劃問題舉例 例1：,某工廠生

12、產(chǎn)A、B兩種產(chǎn)品，均需經(jīng)過兩道工序，每生產(chǎn)一噸產(chǎn)品A需要經(jīng)第一道工序加工2小時，第二道工序加工3小時；每生產(chǎn)一噸產(chǎn)品B需要經(jīng)第一道工序加工3小時，第二道工序加工4小時。可供利用的第一道工序為12小時，第二道工序為24小時。 生產(chǎn)產(chǎn)品B的同時產(chǎn)出副產(chǎn)品C，每生產(chǎn)一噸產(chǎn)品B，可同時得到2噸產(chǎn)品C而毋需外加任何費用；副產(chǎn)品C一部分可以盈利，剩下的只能報廢。 出售產(chǎn)品A每噸能盈利400元、產(chǎn)品B每噸能盈利1000元，每銷售一噸副產(chǎn)品C能盈利300元，而剩余要報廢的則每噸損失200元。經(jīng)市場預(yù)測，在計劃期內(nèi)產(chǎn)品C最大銷量為5噸。試列出線性規(guī)劃模型，決定A、B兩種產(chǎn)品的產(chǎn)量，使工廠總的利潤最大。,2020

13、/9/3,28,數(shù)學(xué)模型：,設(shè)：x1產(chǎn)品A的產(chǎn)量， x2產(chǎn)品B的產(chǎn)量，x3產(chǎn)品C的銷售量，x4產(chǎn)品C的報廢量。依題意，可得,2020/9/3,29,例2 合理下料問題。 現(xiàn)要截取2.9米、2.1米和1.5米的圓鋼各100根。而現(xiàn)在僅有一批長7.4米的棒料毛坯，問應(yīng)如何下料，才能使所消耗的原材料最省。,解：依題意，在排除明顯不合理的方案后?？梢粤谐?種套裁方案，前5種更合理。,2020/9/3,30,例3,2020/9/3,31,練習(xí)1：,練習(xí)2：P57，T2.9,2020/9/3,32,2020/9/3,33,例4. 連續(xù)投資問題。P53, 2-13,2020/9/3,34,練習(xí)：,設(shè)某投資者

14、有30 000元可供為期四年的投資，現(xiàn)有五個投資機(jī)會可供選擇： A: 可在每年年初投資，每年每元投資可獲0.2元。 B: 第一年年初或第三年年初投資，每兩年每元投資可獲利潤0.5元，兩年后獲利。 C: 第一年初投資，三年后每元投資獲利0.8元。這項投資最多不超過20 000元。 D: 第二年年初投資，兩年后每元投資可獲利0.6元。這項投資最多不超過15 000元。 E: 第一年年初投資，四年后每元獲利1.7元，這項投資最多不超過20 000元。 投資者應(yīng)如何投資，使他在四年后所擁有資金總額最大？,2020/9/3,35,第一章 總結(jié),基本概念： 可行解，基，基解，基可行解，可行基，凸集，頂點 基本定理： 可行域為凸集； 基可行解 頂點； 最優(yōu)解一定在頂點上取得。,2020/9/3,36,基本問題：,什么