運籌學 單純形法1

第4節(jié)單純形法計算步驟2/7/20231Step1化為標準型，找出初始可行基，并列出初始單純形表上述初始單純形表中，最后一行稱為檢驗數(shù)σj2/7/20232基基向量x1x2x3x4x5Z可行解圖中點B1P3P4P500816120√OB2P2P4P504016-412╳AB3P2P3P500無解B4P2P3P40321609√Q4B5P1P4P5800-161216╳CB6P1P3P54040128√Q1B7P1P3P400無解B8P1P2P54200414√Q2B9P1P2P42308013√Q3B10P1P2P343-20017╳Bx2x1O11223344Q1Q2Q3Q4ABC2/7/20233Step2：檢查非基變量所對應的檢驗數(shù)σj，若所有的σj≤0，則當前的基可行解就是最優(yōu)解，當前的目標函數(shù)值就是最優(yōu)值，停止計算。否則，轉(zhuǎn)入下一步。Step3：若存在一個σk>0，σk所對應的變量xk的系數(shù)列向量Pk≤0(即Pk中每一個分量aik≤0)，則該LP無有限最優(yōu)解，停止計算。否則，轉(zhuǎn)入下一步。Step4：進行可行基的迭代。重復以上步驟2/7/20234例7用單純形法求解例6。

maxz=2x1+3x2s.t.x1+2x2+x3=84x1+x4=164x2+x5=12xj≥0，j=1,2,…,52/7/20235練習：分別用圖解法和單純形法求解下列線性規(guī)劃問題，并指出單純形法迭代的每一步相當于圖形上哪一個頂點。MaxZ=10x1+5x23x1+4x2≤95x1+2x2≤8x1，x2≥02/7/20236解：cj10500CBXBbix1x2x3x4θ0x3934100x485201σj10500[]38/5[]0X310x18/512/501/521/5014/51-3/5x1入,x4出σj010-2[]x2入,x3出3/245X210x1σj110-1/72/73/2015/14-3/1400-5/14-25/14所以：X*=(x1,x2)T=(1,3/2)TZ*=35/2[]0:(0,0)C:(0,9/4)A:(8/5,0)B:(1,3/2)x1x2對應0對應A對應B2/7/20237回顧：單純形法求解步驟：

2/7/20238第5節(jié)單純形法的進一步討論2/7/20239第5節(jié)單純形法的進一步討論一、人工變量法（大M法）約束條件：“≤”→加一個松弛變量“≥”→減一個剩余變量后，再加一個人工變量“＝”→加一個人工變量目標函數(shù)：人工變量的系數(shù)為“－M”，即罰因子若線性規(guī)劃問題有最優(yōu)解則人工變量必為0。2/7/202310MaxZ=-3x1+x3x1+x2+x3≤4-2x1+x2-x3≥13x2+x3=9xi≥0,j=1,2,3增加人工變量后，線性規(guī)劃問題中就存在一個B為單位矩陣，后面可以根據(jù)我們前面所講的單純形法來進行求解。MaxZ=-3x1+x3-Mx6-Mx7x1+x2+x3+x4=4-2x1+x2-x3-x5+x6=13x2+x3+x7=9xi≥0,j=1,…,7標準化及變形2/7/202311練習：列出初始單純形表，并求解第2小題的最優(yōu)解P55，2.2（1）2.2/7/202312cj-30100-M-MCBXBbix1x2x3x4x5x6x7θ0x441111000-Mx61-21-10-110-Mx790310001單純形表σj-3-2M4M100[]3x2入，x6出-M041[]0x40x2-Mx7330211-10σj6M-304M+10-4M[]-x1入，x7出3M01-21-10-1101660403-311[]0x40x2-3x100001-1/21/2-1/2σj0030-M-3/2[]9x3入，x1出3/2-M+1/23011/30001/33/21102/301/2-1/21/6-[]0x40x21x300001-1/21/2-1/2σj-9/2000-M+3/4-3/4-M-1/45/2-1/2100-1/41/41/43/23/20103/4-3/41/4所以：X*=(x1,x2,x3)T=(0,5/2,3/2)TZ*=3/22/7/202313二、兩階段法第一階段暫不考慮原問題是否存在基可行解，給原問題加入人工變量，并構建一個僅含人工變量的目標函數(shù)（求極小化），人工變量的價值系數(shù)一般為1，約束條件和原問題的一樣。當?shù)谝浑A段中目標函數(shù)的最優(yōu)值＝0，即人工變量＝0，則轉(zhuǎn)入第二階段；若第一階段中目標函數(shù)的最優(yōu)值不等于0，即人工變量不等于0，則判斷原問題為無解。第二階段：將第一階段計算所得的單純形表劃去人工變量所在的列，并將目標函數(shù)換為原問題的目標函數(shù)作為第二階段的初始單純形表，進行進一步的求解。2/7/202314求解輔助問題，得到輔助問題的最優(yōu)解引進人工變量x6，x7，構造輔助問題，輔助問題的目標函數(shù)為所有人工變量之和的極小化MaxW=0?原問題沒有可行解。把輔助問題的最優(yōu)解作為原問題的初始基礎可行解用單純形法求解原問題，得到原問題的最優(yōu)解否是兩階段法的算法流程圖MaxZ=-3x1+x3x1+x2+x3≤4-2x1+x2-x3≥13x2+x3=9xi≥0,j=1,2,3MaxW=-x6-x7x1+x2+x3+x4=4-2x1+x2-x3-x5+x6=13x2+x3+x7=9xi≥0,j=1,…,72/7/202315cj00000-1-1CBXBbix1x2x3x4x5x6x7θ0x441111000-1x61-21-10-110-1x790310001(第一階段）單純形表1σj-24000[]3x2入，x6出-1041[]0x40x2-1x7330211-10σj6040-4[]－x1入，x7出301-21-10-1101660403-311[]0x40x20x100001-1/21/2-1/2σj0000-10-13011/30001/31102/301/2-1/21/6所以：已得最優(yōu)解，且人工變量為非基變量，則可去掉人工變量，得原問題的一個即可行基。2/7/202316（第二階段）單純形表2cj-30100CBXBbix1x2x3x4x5θ0x400001-1/20x23011/300-3x11102/301/2σj00303/2[]-93/2[]0X40X21x35/2-1/2100-1/400001-1/23/23/20103/4x3入，x1出σj-9/2000-3/4所以：X*=(x1,x2,x3)T=(0,5/2,3/2)TZ*=3/2

2/7/202317單純形法小結給定LP問題首先化為標準型，選取或構造一個單位矩陣作為基，求出初始基可行解，并列出初始單純形表。標準化過程按第1.3節(jié)內(nèi)容分7種情況：取值右端項等式或不等式極大或極小新加變量系數(shù)xj無約束xj≤0bi<0≤=≥minZxs

xa令xj=

xj′-xj″

xj′

≥0xj″

≥0令

xj′=-xj約束條件兩端同乘以-1加松弛變量xs加入人工變量xa減去剩余變量xs加入人工變量xa令z′=-ZminZ=-maxz′0-M2/7/202318第5節(jié)單純形法的進一步討論人工變量法（大M法）和兩階段法約束條件：“≤”→加一個松弛變量“≥”→減一個剩余變量后，再加一個人工變量“＝”→加一個人工變量若線性規(guī)劃問題有最優(yōu)解則人工變量必為0。2/7/202319目標函數(shù)極小化時解的最優(yōu)性判別；無可行解的判別；無界的判別；無窮多最優(yōu)解的判別；唯一最優(yōu)解的判別.三、單純形法計算中的幾個問題當所有非基變量的σj≥0時為最優(yōu)解；最優(yōu)解中人工變量為非0的基變量時；存在某個σk>0，且所有的aik≤0時；得最優(yōu)解時，有檢驗數(shù)為0的非基變量；得最優(yōu)解時，所有非基變量檢驗數(shù)為負；2/7/202320cj40452500CBXBbix1x2x3x4x5θ0x4100231100x512033201σj4045025100/340[3]45X225x380/31/3102/3-1/320101-11x2入，x4出σj000-5因為全σj≤0,且σ1=0,則有無窮多最優(yōu)解。

所以：其中一個最優(yōu)解為X*=(0,80/3,20,0,0)T,Z*=1700例1:0-10……思考：無窮多最優(yōu)解的一般形式？2/7/202321cj1100CBXBbix1x2x3x4θ0x3100-21100x4501-101σj1100-50[]0X31x12000-112501-101x1入，x4出σj020-1因為σ2=2,且ai2全≤0

所以：無界例2:2/7/202322例3:下表為一極大化問題對應的單純形表討論在a1,a2,a3,a4,a5,a6取何值的情況下，該表中的解為：唯一最優(yōu)解；無窮多最優(yōu)解；無界；無可行解；非最優(yōu)，繼續(xù)換基：

X3換入，x2換出x1x2x3x4x5bix110a10a2a6x20110-22x400-21a33σj00a40a5a4<0,a5<0,a6≥0a6≥0,a4≤0,a5≤0,a4=0或a5=0a6≥0,a5>0,a2≤0,a3≤0a4≤0,a5≤0,x4或x2為人工變量，a6≥0；x1為人工變量，a6>0a4>0,a4>a5;a6/a1>2→a1>0a6≥0→a1≤02/7/202323復習題：下表為一求解極大值線性規(guī)劃問題的初始單純型表及迭代后的表，為松弛變量，試求表中a~L的值及各變量下標m~t的值；2/7/202324第6節(jié)應用舉例一般而言，一個經(jīng)濟、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型。⑴.要求解問題的目標函數(shù)能用數(shù)值指標來反映，且為線性函數(shù)；⑵.存在著多種方案；⑶.要求達到的目標是在一定條件下實現(xiàn)的，這些約束可用線性等式或不等式描述。2/7/202325建模步驟：

第一步：設置要求解的決策變量。決策變量選取得當，不僅能順利地建立模型而且能方便地求解，否則很可能事倍功半。

第二步：找出所有的限制，即約束條件，并用決策變量的線性方程或線性不等式來表示。

第三步：明確目標要求，并用決策變量的線性函數(shù)來表示，確定對函數(shù)是取極大還是取極小的要求。決策變量的非負要求可以根據(jù)問題的實際意義加以確定。2/7/202326一般的產(chǎn)品計劃問題舉例例1：

某工廠生產(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小時?？晒├玫牡谝坏拦ば驗?2小時，第二道工序為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)市場預測，在計劃期內(nèi)產(chǎn)品C最大銷量為5噸。試列出線性規(guī)劃模型，決定A、B兩種產(chǎn)品的產(chǎn)量，使工廠總的利潤最大。2/7/202327數(shù)學模型：

設：x1——產(chǎn)品A的產(chǎn)量，x2——產(chǎn)品B的產(chǎn)量，x3——產(chǎn)品C的銷售量，x4——產(chǎn)品C的報廢量。依題意，可得2/7/202328例2合理下料問題?，F(xiàn)要截取2.9米、2.1米和1.5米的圓鋼各100根。而現(xiàn)在僅有一批長7.4米的棒料毛坯，問應如何下料，才能使所消耗的原材料最省。根數(shù)方案需要根數(shù)長度IIIIIIIVVVIVIIVIII2.9120101001002.1002211301001.531203104100合計7.47.37.27.16.66.56.36料頭00.10.20.30.80.91.11.4解：依題意，在排除明顯不合理的方案后?？梢粤谐?種套裁方案，前5種更合理。2/7/202329例32/7/202330練習1：練習2：P57，T2.92/7/2023312/7/202332例4.連續(xù)投資問題。P53,2-13項目第1年第2年第3年第4年第5年投資回報率投資額限制Ax1Ax2Ax3Ax4A115%Bx3B125%≤4萬元Cx2C140%≤3萬元Dx1Dx2Dx3Dx4Dx5D公債利息6%投資總額：10萬元2/7/202333練習：設某投資者有30000元可供為期四年的投資，現(xiàn)有五個投資機會可供選擇：A:可在每年年初投資，每年每元投資可獲0.2元。B:第一年年初或第三年年初投資，每兩年每元投資可獲利潤0.5元，兩年后獲利。C:第一年初投資，三年后每元投資獲利0.8元。這項投資最多不超過20000元。D:第二年年初投資，兩年后每元投資可獲利0.6元。這項投資最多不超過15000元。E:第一年年初投資，