運(yùn)籌學(xué) 單純形法1

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

maxz=2x1+3x2s.t.x1+2x2+x3=84x1+x4=164x2+x5=12xj≥0，j=1,2,…,52/7/20235練習(xí)：分別用圖解法和單純形法求解下列線性規(guī)劃問(wèn)題，并指出單純形法迭代的每一步相當(dāng)于圖形上哪一個(gè)頂點(diǎn)。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對(duì)應(yīng)0對(duì)應(yīng)A對(duì)應(yīng)B2/7/20237回顧：?jiǎn)渭冃畏ㄇ蠼獠襟E：

2/7/20238第5節(jié)單純形法的進(jìn)一步討論2/7/20239第5節(jié)單純形法的進(jìn)一步討論一、人工變量法（大M法）約束條件：“≤”→加一個(gè)松弛變量“≥”→減一個(gè)剩余變量后，再加一個(gè)人工變量“＝”→加一個(gè)人工變量目標(biāo)函數(shù)：人工變量的系數(shù)為“－M”，即罰因子若線性規(guī)劃問(wèn)題有最優(yōu)解則人工變量必為0。2/7/202310MaxZ=-3x1+x3x1+x2+x3≤4-2x1+x2-x3≥13x2+x3=9xi≥0,j=1,2,3增加人工變量后，線性規(guī)劃問(wèn)題中就存在一個(gè)B為單位矩陣，后面可以根據(jù)我們前面所講的單純形法來(lái)進(jìn)行求解。MaxZ=-3x1+x3-Mx6-Mx7x1+x2+x3+x4=4-2x1+x2-x3-x5+x6=13x2+x3+x7=9xi≥0,j=1,…,7標(biāo)準(zhǔn)化及變形2/7/202311練習(xí)：列出初始單純形表，并求解第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二、兩階段法第一階段暫不考慮原問(wèn)題是否存在基可行解，給原問(wèn)題加入人工變量，并構(gòu)建一個(gè)僅含人工變量的目標(biāo)函數(shù)（求極小化），人工變量的價(jià)值系數(shù)一般為1，約束條件和原問(wèn)題的一樣。當(dāng)?shù)谝浑A段中目標(biāo)函數(shù)的最優(yōu)值＝0，即人工變量＝0，則轉(zhuǎn)入第二階段；若第一階段中目標(biāo)函數(shù)的最優(yōu)值不等于0，即人工變量不等于0，則判斷原問(wèn)題為無(wú)解。第二階段：將第一階段計(jì)算所得的單純形表劃去人工變量所在的列，并將目標(biāo)函數(shù)換為原問(wèn)題的目標(biāo)函數(shù)作為第二階段的初始單純形表，進(jìn)行進(jìn)一步的求解。2/7/202314求解輔助問(wèn)題，得到輔助問(wèn)題的最優(yōu)解引進(jìn)人工變量x6，x7，構(gòu)造輔助問(wèn)題，輔助問(wèn)題的目標(biāo)函數(shù)為所有人工變量之和的極小化MaxW=0?原問(wèn)題沒(méi)有可行解。把輔助問(wèn)題的最優(yōu)解作為原問(wèn)題的初始基礎(chǔ)可行解用單純形法求解原問(wèn)題，得到原問(wèn)題的最優(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)解，且人工變量為非基變量，則可去掉人工變量，得原問(wèn)題的一個(gè)即可行基。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單純形法小結(jié)給定LP問(wèn)題首先化為標(biāo)準(zhǔn)型，選取或構(gòu)造一個(gè)單位矩陣作為基，求出初始基可行解，并列出初始單純形表。標(biāo)準(zhǔn)化過(guò)程按第1.3節(jié)內(nèi)容分7種情況：取值右端項(xiàng)等式或不等式極大或極小新加變量系數(shù)xj無(wú)約束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é)單純形法的進(jìn)一步討論人工變量法（大M法）和兩階段法約束條件：“≤”→加一個(gè)松弛變量“≥”→減一個(gè)剩余變量后，再加一個(gè)人工變量“＝”→加一個(gè)人工變量若線性規(guī)劃問(wèn)題有最優(yōu)解則人工變量必為0。2/7/202319目標(biāo)函數(shù)極小化時(shí)解的最優(yōu)性判別；無(wú)可行解的判別；無(wú)界的判別；無(wú)窮多最優(yōu)解的判別；唯一最優(yōu)解的判別.三、單純形法計(jì)算中的幾個(gè)問(wèn)題當(dāng)所有非基變量的σj≥0時(shí)為最優(yōu)解；最優(yōu)解中人工變量為非0的基變量時(shí)；存在某個(gè)σk>0，且所有的aik≤0時(shí)；得最優(yōu)解時(shí)，有檢驗(yàn)數(shù)為0的非基變量；得最優(yōu)解時(shí)，所有非基變量檢驗(yàn)數(shù)為負(fù)；2/7/202320cj40452500CBXBbix1x2x3x4x5θ0x4100231100x512033201σj4045025100/340[3]45X225x380/31/3102/3-1/320101-11x2入，x4出σj000-5因?yàn)槿襧≤0,且σ1=0,則有無(wú)窮多最優(yōu)解。

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

所以：無(wú)界例2:2/7/202322例3:下表為一極大化問(wèn)題對(duì)應(yīng)的單純形表討論在a1,a2,a3,a4,a5,a6取何值的情況下，該表中的解為：唯一最優(yōu)解；無(wú)窮多最優(yōu)解；無(wú)界；無(wú)可行解；非最優(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復(fù)習(xí)題：下表為一求解極大值線性規(guī)劃問(wèn)題的初始單純型表及迭代后的表，為松弛變量，試求表中a~L的值及各變量下標(biāo)m~t的值；2/7/202324第6節(jié)應(yīng)用舉例一般而言，一個(gè)經(jīng)濟(jì)、管理問(wèn)題凡是滿(mǎn)足以下條件時(shí)，才能建立線性規(guī)劃模型。⑴.要求解問(wèn)題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映，且為線性函數(shù)；⑵.存在著多種方案；⑶.要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約束可用線性等式或不等式描述。2/7/202325建模步驟：

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

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

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

某工廠生產(chǎn)A、B兩種產(chǎn)品，均需經(jīng)過(guò)兩道工序，每生產(chǎn)一噸產(chǎn)品A需要經(jīng)第一道工序加工2小時(shí)，第二道工序加工3小時(shí)；每生產(chǎn)一噸產(chǎn)品B需要經(jīng)第一道工序加工3小時(shí)，第二道工序加工4小時(shí)。可供利用的第一道工序?yàn)?2小時(shí)，第二道工序?yàn)?4小時(shí)。

生產(chǎn)產(chǎn)品B的同時(shí)產(chǎn)出副產(chǎn)品C，每生產(chǎn)一噸產(chǎn)品B，可同時(shí)得到2噸產(chǎn)品C而毋需外加任何費(fèi)用；副產(chǎn)品C一部分可以盈利，剩下的只能報(bào)廢。

出售產(chǎn)品A每噸能盈利400元、產(chǎn)品B每噸能盈利1000元，每銷(xiāo)售一噸副產(chǎn)品C能盈利300元，而剩余要報(bào)廢的則每噸損失200元。經(jīng)市場(chǎng)預(yù)測(cè)，在計(jì)劃期內(nèi)產(chǎn)品C最大銷(xiāo)量為5噸。試列出線性規(guī)劃模型，決定A、B兩種產(chǎn)品的產(chǎn)量，使工廠總的利潤(rùn)最大。2/7/202327數(shù)學(xué)模型：

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