單純形法(第三章線性規(guī)劃2)課件

1、一、求解LP問題的單純形法 1.單純形法的求解原理 單純形法引例標(biāo)準(zhǔn)化1一、求解LP問題的單純形法 1.單純形法的求解原理 單純形Step2. 確定換入換出變量，進(jìn)行第一次迭代 Step1. 確定初始基可行解。 初始基可行解為：X1=(0 0 360 200 300)Tf1=0*Step2. 確定換入換出變量，進(jìn)行第一次迭代 Step1.f2 =360 Step3.確定新的換入換出變量，進(jìn)行第二次迭代*f2 =360 Step3.確定新的換入換出變量，進(jìn)行第二目標(biāo)函數(shù)值 f 3 = 428。即當(dāng)A產(chǎn)品生產(chǎn)20kg，B產(chǎn)品生產(chǎn)24kg，工廠才能獲得最大利潤428百元。x3=84代表煤的剩余量為8

2、4t，x4 = x5 = 0表示電力和勞動日完全利用，沒有剩余。X3為最優(yōu)解目標(biāo)函數(shù)值 f 3 = 428。即當(dāng)A產(chǎn)品生產(chǎn)20kg，B產(chǎn)2.單純形法的主要步驟Step1. 標(biāo)準(zhǔn)化，找初始基可行解，建立初始的單純形表；對于(max , )，松弛變量對應(yīng)的列構(gòu)成一個單位陣Step2.檢驗(yàn)當(dāng)前基可行解是否為最優(yōu)解所有檢驗(yàn)數(shù) j 0，則得到最優(yōu)解（若存在k 0，且pk 0,則該問題無最優(yōu)解，停止計(jì)算） 否則進(jìn)行下一步。Step3.換基迭代（改進(jìn)基可行解）從 j 0 中找最大者 k ，其對應(yīng)變量xk稱為換入變量（若最大判別數(shù)有同樣大的，選對應(yīng)下標(biāo)小的變量為換入變量)xk所在列稱為主元列確定換入變量的最大

3、值和換出變量最小比值原則52.單純形法的主要步驟Step1. 標(biāo)準(zhǔn)化，找初始基可行解設(shè)第 l 行使 最小，則第 l 行對應(yīng)的基變量x l稱為換出變量，第 l 行稱為主元行，alk 稱為主元。 Step4.迭代過程迭代過程以主元alk為中心進(jìn)行，即要將主元 alk變?yōu)?，主列上其它元素變?yōu)?，得到一個新的單純形表，同時得到一個新的基可行解。轉(zhuǎn)回Step2。6設(shè)第 l 行使 最小，則第 l 行對應(yīng)的基變量x l稱為3. 單純形表及其格式73. 單純形表及其格式7 max f =40 x1+ 50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 0例1 用單純形法求解下列

4、LP問題 max f =40 x1+ 50 x2 x1+2x x1 +2x2 +x3 =30 3x1 +2x2 +x4 =60 2x2 + +x5 =24 x1 , , x5 0 max f =40 x1+ 50 x2+0 x3 +0 x4+0 x5標(biāo)準(zhǔn)化 x1 +2x2 +x3 建立初始單純形表 xj x1 x2 x3 x4 x5bx3 1 2 1 0 030 x4 3 2 0 1 060 x5 0 2 0 0 124 40 50 0 0 0 0基變量*30/2=1560/2=3024/2=1240 50 0 0 0000建立初始單純形表 xj x1 x2第一步迭代 xj x1 x2 x3

5、x4 x5bx3 1 0 1 0 -16x4 3 0 0 1 -136x2 0 1 0 0 0.512 40 0 0 0 -25 -600基變量6/1=636/3=12_40 50 0 0 00050第一步迭代 xj x1 x2 第二步迭代 xj x1 x2 x3 x4 x5bx1 1 0 1 0 -16x4 0 0 -3 1 218x2 0 1 0 0 0.512 0 0 -40 0 15-840基變量18/2=912/0.5=24_40 50 0 0 040050第二步迭代 xj x1 x2 第三步迭代 xj x1 x2 x3 x4 x5bx1 1 0 -0.5 0.5 015x5 0 0

6、 -1.5 0.5 19x2 0 1 0.75 -0.25 07.5 0 0 -17.5 -7.5 0-975基變量該問題的最優(yōu)解為：X=(15, 7.5, 0, 0, 9)T40 50 0 0 040050第三步迭代 xj x1 x2 例2 用單純形法求解下列LP問題例2 用單純形法求解下列LP問題 xj x1 x2 x3 x4 x5bx3 -2 1 1 0 04x4 1 -1 0 1 02x5 -3 1 0 0 13 1 1 0 0 0 0基變量 1 1 0 0 00000-12893-2002-1-2x11該問題具有無界解 xj x1 x2 x例2 用單純形法求解下列LP問題max f

7、=x1+ x2+2x3 -x4 x1 +x3 - x4 =1 -x1 +x2 +2x4 =0 x1 , , x4 0 例2 用單純形法求解下列LP問題max f =x1+ xmax f =x1+ x2+2x3 -x42 -x4 xj x1 x2 x3 x4bx3x2 1 0 1 -1 -1 1 0 210 0 0 0 -1-2基變量max f =x1+ x2+2x3 -x42 -x4 xj x1 x2 x3 x4bx1x2 1 0 1 -1 0 1 1 111 0 0 0 -1-2此問題具有無窮多最優(yōu)解 max f =2 xj x1 x2 總結(jié)：解的判別1、最優(yōu)解的判別： 若X（x1x2.xn

8、）T為對應(yīng)于基B的一個基可行解，且所有j 0，則X為最優(yōu)解。2、無窮多最優(yōu)解的判別： 若X（x1x2.xn）T為一個基可行解，存在所有j 0，又存在某一非基變量xk對應(yīng)的判別數(shù)k = 0,則此LP問題有無窮多解。3、無界解的判別： 若X（x1x2.xn）T為一個基可行解，其中某個非基變量xk對應(yīng)的判別數(shù)k 0，且對應(yīng)的系數(shù)矩陣aik 0,則此LP問題具有無界解。（或稱無最優(yōu)解，最優(yōu)解 無窮）總結(jié)：解的判別1、最優(yōu)解的判別：4 .人工變量的引入及其解法 當(dāng)約束條件為“”型，引入剩余變量和人工變量由于所添加的剩余變量的系數(shù)為1，不能構(gòu)成初始基變量，為此引入一個人為的變量（注意，此時約束條件已為“=

9、”型），以便取得初始基變量，故稱為人工變量由于人工變量在原問題的解中是不能存在的，應(yīng)盡快被迭代出去，因此人工變量在目標(biāo)函數(shù)中對應(yīng)的系數(shù)應(yīng)具有懲罰性，稱為罰系數(shù)。罰系數(shù)的取值視解法而定兩種方法大M法兩階段法204 .人工變量的引入及其解法 當(dāng)約束條件為“”型（1）兩階段法：（1）兩階段法：作輔助問題解題過程：第一階段：求解輔助問題當(dāng)進(jìn)行到最優(yōu)表時，若 =0, 則得到原問題的一個基本可行解，轉(zhuǎn)入第二階段。 若 0, 則判定原問題無可行解。max = -y1 - y2- -ym作輔助問題解題過程：第一階段：求解輔助問題當(dāng)進(jìn)行到最優(yōu)表時， 從第一階段得到的基本可行解開始，繼續(xù)用單純形法進(jìn)行迭代，直到找

10、出原問題的最優(yōu)解或判斷具有無界解。第二階段: 從第一階段得到的基本可行解開始，繼續(xù)用單純形法進(jìn)行例3 用兩階段法求解下列LP問題例3 用兩階段法求解下列LP問題引入人工變量x6 , x7構(gòu)造下列輔助問題：引入人工變量x6 , x7構(gòu)造下列輔助問題：xj x1 x2 x3 x4 x5 x6 x7B-1bx4x6x7 1 -2 1 1 0 0 0 -4 1 2 0 -1 1 0 -2 0 1 0 0 0 11131- -6 1 3 0 -1 0 04-f 3 -1 -1 0 0 0 00 x300-2130-11000-311011xj x1 x2 x3 xj x1 x2 x3 x4 x5 x6

11、x7B-1bx4x6x7 3 -2 0 1 0 0 -1 0 1 0 0 -1 1 -2 -2 0 1 0 0 0 11011- 0 1 0 0 -1 0 -31-f 1 -1 0 0 0 0 11x300-2112-1x20-2-50000-11-12-12xj x1 x2 x3 xj x1 x2 x3 x4 x5B-1bx4x2x3 3 0 0 1 -2 0 1 0 0 -1 -2 0 1 0 01211-f 1 0 0 0 -12x11/3-2/34102/3-4/30-1/3-1/3-29得到原問題的最優(yōu)解為：X*=（4 1 9 0 0）T f * =2xj x1 x2 x3 （2）

12、大M法:Mx6 Mx7(M為任意大的正數(shù))（2） 大M法:Mx6 Mx7(M為任意大的正數(shù))xj x1 x2 x3 x4 x5 x6 x7B-1bx4x6x7 1 -2 1 1 0 0 0 -4 1 2 0 -1 1 0 -2 0 1 0 0 0 11131-f3 6M -1+M -1+3M 0 -M 0 04M3 -1 -1 0 0 -M -M0-M-Mxj x1 x2 x3 xj x1 x2 x3 x4 x5 x6 x7B-1bx4x6x3 3 -2 0 1 0 0 -1 0 1 0 0 -1 1 -2 -2 0 1 0 0 0 11011-f 1 -1+M 0 0 -M 0 -3M+1M

13、+13 -1 -1 0 0 -M -M0-M-1xj x1 x2 x3 xj x1 x2 x3 x4 x5 x6 x7B-1bx4x2x3 3 0 0 1 -2 2 -5 0 1 0 0 -1 1 -2 -2 0 1 0 0 0 11211-f 1 0 0 0 -1 -M+1 -M-123 -1 -1 0 0 -M -M0-1-1xj x1 x2 x3 xj x1 x2 x3 x4 x5 B-1bx1x2x3 1 0 0 1/3 -2/3 0 1 0 0 -1 0 0 1 2/3 -4/3 419-f 0 0 0 -1/3 -1/3 -23 -1 -1 0 0 3-1-1得到原問題的最優(yōu)解為：

14、X*=（4 1 9 0 0）T f * =2xj x1 x2 x3 練習(xí)：標(biāo)準(zhǔn)化：34練習(xí)：標(biāo)準(zhǔn)化：34大M法的一些說明 大M法實(shí)質(zhì)上與原單純形法一樣，M可看成一個很大的常數(shù)人工變量被迭代出去后就不會再成為基變量當(dāng)檢驗(yàn)數(shù)都滿足最優(yōu)條件，但基變量中仍有人工變量，說明原線性規(guī)劃問題無可行解大M法手算很不方便因此提出了兩階段法計(jì)算機(jī)中常用大M法兩階段法手算可能容易大M法的一些說明 大M法實(shí)質(zhì)上與原單純形法一樣，M可看成一個單純型法的一些具體問題 a.關(guān)于無界解問題可行區(qū)域不閉合(缺約束條件)單純型表中入變量 x j* 對應(yīng)的列中所有36單純型法的一些具體問題 a.關(guān)于無界解問題可行區(qū)域 b.關(guān)于多重

15、解問題多個基可行解都是最優(yōu)解，這些解在同一個超平面上，且該平面與目標(biāo)函數(shù)等值面平行最優(yōu)單純形表中有非基變量的檢驗(yàn)數(shù)為0最優(yōu)解的線性組合仍是最優(yōu)解，即 X=k1X1+k2X2，k1+k2=137 b.關(guān)于多重解問題多個基可行解都是最優(yōu)解，這些解 c.關(guān)于無可行解問題約束條件互相矛盾，無可行域單純形表迭代到最優(yōu)解時，人工變量仍在基變量中 38 c.關(guān)于無可行解問題約束條件互相矛盾，無可行域38 d.關(guān)于退化問題退化問題的原因很復(fù)雜當(dāng)單純形表中同時有多個基變量可選作出變量時退化的嚴(yán)重性在于可能導(dǎo)致死循環(huán)，克服死循環(huán)的方法有“字典序”法39 d.關(guān)于退化問題退化問題的原因很復(fù)雜39 一、判斷題1、線性

16、規(guī)劃問題的每一個基解對應(yīng)可行域的一個頂點(diǎn)。2、圖解法與單純形法，雖然求解的形式不同，但從幾何上理解，兩者是一致的。3、線性規(guī)劃問題存在最優(yōu)解，則最優(yōu)解一定對應(yīng)可行域邊界上的一個點(diǎn)。4、若x1、x2分別是某一線性規(guī)劃問題的最優(yōu)解，則x1 x1+2x2也是該線性規(guī)劃問題的最優(yōu)解，其中12為正的實(shí)數(shù)。5、對一個有n個變量、m個約束的標(biāo)準(zhǔn)形的線性規(guī)劃問題，其可行域的頂點(diǎn)恰好為Cnm 一、判斷題1、線性規(guī)劃問題的每一個基解對應(yīng)可行域的6、單純形法迭代的過程就是從一個基可行解（頂點(diǎn)）到另一個基可行解（頂點(diǎn)）的過程。7、用單純形方法，正的判別數(shù)對應(yīng)的變量都可以作為換入變量。8、線性規(guī)劃問題的數(shù)學(xué)模型增加約束條件，可行域范圍一般縮小，減少約束條件，可行域范圍一般擴(kuò)大。6、單純形法迭代的過程就是從一個基可行解（頂點(diǎn)）到另一個基可2、計(jì)算題 下表是求極大化線性規(guī)劃問題的單純形表，表中無人工變量，a1 ，a2，a3，d，c1，c2為待定常數(shù)，試說明這些常數(shù)滿足什么條件，能使以下結(jié)論成立：2、計(jì)算題 下表是求極大化線性規(guī)劃問題的單純形表，表中無xj x1 x2 x3 x4 x5 x6B-1bx3x4x6 4 a1 1 0 a2 0 -1 -3 0 1 -1 0 a3 -5 0 0 -4 1 d23-f c1 c2 0 0 -3 0 xj x1