【正文】 0 1/6 0 15 0 5 1 0 0 1 0 2/3 0 1/6 1 x1入， x4出 σj 0 1/3 0 1/3 0 [ ] x2入， x5出 3 12 3/2 [ ] 0 X3 2 X1 1 x2 σj 7/2 1 0 0 1/4 1/2 15/2 0 0 1 5/4 15/2 3/2 0 1 0 1/4 3/2 0 0 0 1/4 1/2 所以： X*=(x1,x2,x3)T=(7/2,3/2,15/2)T Z*=17/2 2022/2/16 68 例 :(1) cj 10 5 0 0 CB XB bi x1 x2 x3 x4 θ 0 x3 9 3 4 1 0 0 x4 8 5 2 0 1 σj 10 5 0 0 [ ] 3 8/5 [ ] 0 X3 10 x1 8/5 1 2/5 0 1/5 21/5 0 14/5 1 3/5 x1入 ,x4出 σj 0 1 0 2 [ ] x2入 ,x3出 3/2 4 5 X2 10 x1 σj 1 1 0 1/7 2/7 3/2 0 1 5/14 3/14 0 0 5/14 25/14 所以： X*=(x1,x2)T=(1,3/2)T Z*=35/2 [ ] 0: (0,0) C: (0,9/4) A: (8/5,0) B:(1,3/2) x1 x2 對應(yīng)0 對應(yīng)A 對應(yīng)B 2022/2/16 69 課堂作業(yè) (1) 課后作業(yè) P43 （ 2） 2022/2/16 70 單純形法的進一步討論 一、人工變量法（大 M法） 約束條件： “ ≥” → 減一個剩余變量后，再加一個人工變量 “ ＝ ” → 加一個人工變量 目標函數(shù)： 人工變量的系數(shù)為 “ － M” ，即罰因子 若線性規(guī)劃問題有最優(yōu)解則人工變量必為 0。 2022/2/16 71 MaxZ=3x1+x3 x1+ x2+ x3≤4 2x1+ x2 x3≥1 3x2+x3=9 xi ≥0,j=1,2,3 增加人工變量后，線性規(guī)劃問題中就存在一個 B為單位矩陣， 后面可以根據(jù)我們前面所講的單純形法來進行求解。 MaxZ=3x1+x3Mx6Mx7 x1+ x2+ x3+x4 =4 2x1+ x2x3 x5+x6 =1 3x2+x3 +x7=9 xi ≥0,j=1,…,7 標準化及變形 2022/2/16 72 cj 3 0 1 0 0 M M CB XB bi x1 x2 x3 x4 x5 x6 x7 θ 0 x4 4 1 1 1 1 0 0 0 M x6 1 2 1 1 0 1 1 0 M x7 9 0 3 1 0 0 0 1 單純形表 σj 32M 4M 1 0 0 [ ] 3 x2入， x6出 M 0 4 1 [ ] 0 x4 0 x2 M x7 3 3 0 2 1 1 1 0 σj 6M3 0 4M+1 0 4M [ ] x1入， x7出 3M 0 1 2 1 1 0 1 1 0 1 6 6 0 4 0 3 3 1 1 [ ] 0 x4 0 x2 3 x1 0 0 0 0 1 1/2 1/2 1/2 σj 0 0 3 0 M3/2 [ ] 9 x3入， x1出 3/2 M+1/2 3 0 1 1/3 0 0 0 1/3 3/2 1 1 0 2/3 0 1/2 1/2 1/6 [ ] 0 x4 0 x2 1 x3 0 0 0 0 1 1/2 1/2 1/2 σj 9/2 0 0 0 M+3/4 3/4 M1/4 5/2 1/2 1 0 0 1/4 1/4 1/4 3/2 3/2 0 1 0 3/4 3/4 1/4 所以： X*=(x2,x3,x4)T=(5/2,3/2,0)T Z*=3/2 2022/2/16 73 二、兩階段法 ? 第一階段暫不考慮原問題是否存在基可行解，給原問題加入人工變量，并構(gòu)建一個僅含人工變量的目標函數(shù)（求極小化），人工變量的價值系數(shù)一般為 1，約束條件和原問題的一樣。 ? 當?shù)谝浑A段中目標函數(shù)的最優(yōu)值＝ 0，既人工變量＝ 0，則轉(zhuǎn)入第二階段；若第一階段中目標函數(shù)的最優(yōu)值不等于 0，既人工變量不等于 0，則判斷原問題為無解。 ? 第二階段：將第一階段計算所得的單純形表劃去人工變量所在的列，并將目標函數(shù)換為原問題的目標函數(shù)作為第二階段的初始單純形表，進行進一步的求解。 2022/2/16 74 求解輔助問題，得到輔助問題的最優(yōu)解 引進人工變量 x6， x7，構(gòu)造輔助問題，輔助問題的目標函數(shù)為所有人工變量之和的極小化 MaxW=0? 原問題沒有可行解。 把輔助問題的最優(yōu)解作為原問題的初始基礎(chǔ)可行解 用單純形法求解原問題，得到原問題的最優(yōu)解 否 是 兩階段法的算法流程圖 MaxZ=3x1+x3 x1+ x2+ x3≤4 2x1+ x2 x3≥1 3x2+x3=9 xi ≥0,j=1,2,3 MaxW=x6x7 x1+ x2+ x3+x4 =4 2x1+ x2x3 x5+x6 =1 3x2+x3 +x7=9 xi ≥0,j=1,…,7 2022/2/16 75 cj 0 0 0 0 0 1 1 CB XB bi x1 x2 x3 x4 x5 x6 x7 θ 0 x4 4 1 1 1 1 0 0 0 1 x6 1 2 1 1 0 1 1 0 1 x7 9 0 3 1 0 0 0 1 (第一階段）單純形表 1 σj 2 4 0 0 0 [ ] 3 x2入， x6出 1 0 4 1 [ ] 0 x4 0 x2 1 x7 3 3 0 2 1 1 1 0 σj 6 0 4 0 4 [ ] － x1入， x7出 3 0 1 2 1 1 0 1 1 0 1 6 6 0 4 0 3 3 1 1 [ ] 0 x4 0 x2 0 x1 0 0 0 0 1 1/2 1/2 1/2 σj 0 0 0 0 1 0 1 3 0 1 1/3 0 0 0 1/3 1 1 0 2/3 0 1/2 1/2 1/6 所以：已得最優(yōu)解，且人工變量為非基變量，則可去掉人工變量，得原問題的一個即可行基。 2022/2/16 76 （第二階段）單純形表 2 cj 3 0 1 0 0 CB XB bi x1 x2 x3 x4 x5 θ 0 x4 0 0 0 0 1 1/2 0 x2 3 0 1 1/3 0 0 3 x1 1 1 0 2/3 0 1/2 σj 0 0 3 0 3/2 [ ] 9 3/2 [ ] 0 X4 0 X2 1 x3 5/2 1/2 1 0 0 1/4 0 0 0 0 1 1/2 3/2 3/2 0 1 0 3/4 x3入， x1出 σj 9/2 0 0 0 3/4 所以： X*=(x2,x3,x4)T=(5/2,3/2,0)T Z*=3/2 2022/2/16 77 ? 目標函數(shù)極小化時解的最優(yōu)性判別； ? 退化解的判別； ? 無可行解的判別； ? 無界的判別； ? 無窮多最優(yōu)解的判別； ? 唯一最優(yōu)解的判別 . 三、單純形法計算中的幾個問題 當所有非基變量的 σj≥0時為最優(yōu)解； 最優(yōu)解中基變量有取值為 0的值時； 最優(yōu)解中人工變量為非 0的基變量時； 存在某個 σk0，且所有的 aik≤0時； 得最優(yōu)解時，有檢驗數(shù)為 0的非基變量； 得最優(yōu)解時，所有非基變量檢驗數(shù)為負； 2022/2/16 78 cj 40 45 25 0 0 CB XB bi x1 x2 x3 x4 x5 θ 0 x3 100 2 3 1 1 0 0 x4 120 3 3 2 0 1 σj 40 45 0 25 100/3 40 [ 3 ] 45 X2 25 x3 80/3 1/3 1 0 2/3 1/3 20 1 0 1 1 1 x2入， x3出 σj 0 0 0 5 因為 σj全 ≥0, 且 σ1=0,則有無窮多最優(yōu)解。 所以： X*=(0,80/3,20,0,0),Z*=1700 例 : ???????????????01 2 02331 0 032254540321321321321xxxxxxxxxtsxxxZ,..m a x0 10 …… 2022/2/16 79 ?????????????0x,x50xx1 0 0x2xs .t .xxm a x Z21212121cj 1 1 0 0 CB XB bi x1 x2 x3 x4 θ 0 x3 100 2 1 1 0 0 x4 50 1 1 0 1 σj 1 1 0 0 50 [ ] 0 X3 1 x1 200 0 1 1 2 50 1 1 0 1 x1入， x4出 σj 0 2 0 1 因為 σ2=2,且 ai2全 ≥0 所以：無界 例 : 2022/2/16 80 例 : 下表為一極大化問題對應(yīng)的單純形表 討論在 a1,a2,a3,a4,a5,a6取何值的情況下，該表中的解為： ?唯一最優(yōu)解； ?無窮多最優(yōu)解； ?退化解； ?無界； ?無可行解； ?X3換入， x2換出 x1 x2 x3 x4 x5 bi X1 1 0 a1 0 a2 a6 X2 0 1 1 0 2 2 x4 0 0 2 1 a3 3 σj 0 0 a4 0 a5 ? A40,a50, a6≥0 ? a6≥0,a4≤0, a5≤=0 ? a4≤0,a5≤0,a6=0 ? a6≥0,a50,a2≤0, a3≤0 ? a4≤0,a5≤0, x4或 x2為人工變量， a6≥0 ； x1為人工變量 a60 ? A40,a4a5。a6/a12→ a10 a6≥0 → a1 ≤ 0 2022/2/16 81 課后作業(yè) P43