第4節單純形法計算步驟2/7/20231Step1化為標準型，找出初始可行基，并列出初始單純形表上述初始單純形表中，最后一行稱為檢驗數σj2/7/20232基基向量x1x2x3x4x5Z可行解圖中點B1P3P4P500816120√OB2P2P4P504016-412╳AB3P2P3P500無解B4P2P3P40321609√Q4B5P1P4P5800-161216╳CB6P1P3P54040128√Q1B7P1P3P400無解B8P1P2P54200414√Q2B9P1P2P42308013√Q3B10P1P2P343-20017╳Bx2x1O11223344Q1Q2Q3Q4ABC2/7/20233Step2：檢查非基變量所對應的檢驗數σj，若所有的σj≤0，則當前的基可行解就是最優解，當前的目標函數值就是最優值，停止計算。否則，轉入下一步。Step3：若存在一個σk>0，σk所對應的變量xk的系數列向量Pk≤0(即Pk中每一個分量aik≤0)，則該LP無有限最優解，停止計算。否則，轉入下一步。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練習：分別用圖解法和單純形法求解下列線性規劃問題，并指出單純形法迭代的每一步相當于圖形上哪一個頂點。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節單純形法的進一步討論2/7/20239第5節單純形法的進一步討論一、人工變量法（大M法）約束條件：“≤”→加一個松弛變量“≥”→減一個剩余變量后，再加一個人工變量“＝”→加一個人工變量目標函數：人工變量的系數為“－M”，即罰因子若線性規劃問題有最優解則人工變量必為0。2/7/202310MaxZ=-3x1+x3x1+x2+x3≤4-2x1+x2-x3≥13x2+x3=9xi≥0,j=1,2,3增加人工變量后，線性規劃問題中就存在一個B為單位矩陣，后面可以根據我們前面所講的單純形法來進行求解。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小題的最優解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二、兩階段法第一階段暫不考慮原問題是否存在基可行解，給原問題加入人工變量，并構建一個僅含人工變量的目標函數（求極小化），人工變量的價值系數一般為1，約束條件和原問題的一樣。當第一階段中目標函數的最優值＝0，即人工變量＝0，則轉入第二階段；若第一階段中目標函數的最優值不等于0，即人工變量不等于0，則判斷原問題為無解。第二階段：將第一階段計算所得的單純形表劃去人工變量所在的列，并將目標函數換為原問題的目標函數作為第二階段的初始單純形表，進行進一步的求解。2/7/202314求解輔助問題，得到輔助問題的最優解引進人工變量x6，x7，構造輔助問題，輔助問題的目標函數為所有人工變量之和的極小化MaxW=0?原問題沒有可行解。把輔助問題的最優解作為原問題的初始基礎可行解用單純形法求解原問題，得到原問題的最優解否是兩階段法的算法流程圖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所以：已得最優解，且人工變量為非基變量，則可去掉人工變量，得原問題的一個即可行基。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節內容分7種情況：取值右端項等式或不等式極大或極小新加變量系數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節單純形法的進一步討論人工變量法（大M法）和兩階段法約束條件：“≤”→加一個松弛變量“≥”→減一個剩余變量后，再加一個人工變量“＝”→加一個人工變量若線性規劃問題有最優解則人工變量必為0。2/7/202319目標函數極小化時解的最優性判別；無可行解的判別；無界的判別；無窮多最優解的判別；唯一最優解的判別.三、單純形法計算中的幾個問題當所有非基變量的σj≥0時為最優解；最優解中人工變量為非0的基變量時；存在某個σk>0，且所有的aik≤0時；得最優解時，有檢驗數為0的非基變量；得最優解時，所有非基變量檢驗數為負；2/7/202320cj40452500CBXBbix1x2x3x4x5θ0x4100231100x512033201σj4045025100/340[3]45X225x380/31/3102/3-1/320101-11x2入，x4出σj000-5因為全σj≤0,且σ1=0,則有無窮多最優解。

所以：其中一個最優解為X*=(0,80/3,20,0,0)T,Z*=1700例1:0-10……思考：無窮多最優解的一般形式？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取何值的情況下，該表中的解為：唯一最優解；無窮多最優解；無界；無可行解；非最優，繼續換基：

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復習題：下表為一求解極大值線性規劃問題的初始單純型表及迭代后的表，為松弛變量，試求表中a~L的值及各變量下標m~t的值；2/7/202324第6節應用舉例一般而言，一個經濟、管理問題凡是滿足以下條件時，才能建立線性規劃模型。⑴.要求解問題的目標函數能用數值指標來反映，且為線性函數；⑵.存在著多種方案；⑶.要求達到的目標是在一定條件下實現的，這些約束可用線性等式或不等式描述。2/7/202325建模步驟：

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

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

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

某工廠生產A、B兩種產品，均需經過兩道工序，每生產一噸產品A需要經第一道工序加工2小時，第二道工序加工3小時；每生產一噸產品B需要經第一道工序加工3小時，第二道工序加工4小時。可供利用的第一道工序為12小時，第二道工序為24小時。

生產產品B的同時產出副產品C，每生產一噸產品B，可同時得到2噸產品C而毋需外加任何費用；副產品C一部分可以盈利，剩下的只能報廢。

出售產品A每噸能盈利400元、產品B每噸能盈利1000元，每銷售一噸副產品C能盈利300元，而剩余要報廢的則每噸損失200元。經市場預測，在計劃期內產品C最大銷量為5噸。試列出線性規劃模型，決定A、B兩種產品的產量，使工廠總的利潤最大。2/7/202327數學模型：

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