【正文】 初始基可行解 （ 一 ） 人工變量法 若對(duì) LP模型標(biāo)準(zhǔn)化后 ， 不具有 B=I時(shí) ， 如何辦 ？ 此時(shí)可采用人工變量法得到初始基可行解 。 所謂人工變量法是在原問題不含有初始可行基 B=I的情況下 ， 人為的對(duì)約束條件增加虛擬的非負(fù)變量 （ 即人工變量） ， 構(gòu)造出含有 B=I的另一個(gè) LP問題后求解 。 當(dāng)增加的人工變量全部取值為 0時(shí) ， 才與原問題等價(jià) 。 這樣 ， 新問題將有一個(gè)初始基可行解 （ 以人工變量為基變量 ） ， 可用單純形法進(jìn)行迭代 。 經(jīng)迭代后 ， 若人工變量全部被換成非基變量 ， 即人工變量全部出基 ， 則得到原問題的一個(gè)基可行解 。 在最終表中若人工變量不能全部被換出 ， 則說明原問題無可行解 。 因此 ， 該法的關(guān)鍵在于將人工變量全部換出 。 60 （ 1 ）大 M 法 （通過下例簡略介紹其方法與步驟） 例，用大 M 法求解 M i n Z = x1+1 .5x2 ??????????0,233212121xxxxxx解： M i nZ = x1+1 .5x2+0 . x3+0 . x4+M x5+M x6 ????????????????0,0,0,23365432164215321xxxxxxxxxxxxxx其中 x3,x4為松馳變量， x5,x6為人工變量， M 為任意大的正數(shù)。 人工變量法常見的有大 M法和兩階段法。 61 注意到： ① 分別在約束條件中增加人工變量 x5,x6是為了構(gòu)成 “ 人工基 ” ② 對(duì)于 Min的目標(biāo)函數(shù)采用 (+M)， 而對(duì)于 Max的目標(biāo)函數(shù)則采用 (M)作為人工變量的系數(shù) ,是強(qiáng)加于人工變量的一種懲罰 ,其目的是為了強(qiáng)制人工變量由基變量轉(zhuǎn)為非基變量 ， 使之恢復(fù)原問題 ， 或與原問題等價(jià) 。 ③ 對(duì)于 minZ判別最優(yōu)性準(zhǔn)則應(yīng)是 Cj－ Zj≤0。 ④ 大 M法適合于計(jì)算機(jī)計(jì)算 ， 不適用于手工求解 。 所以本題求解過程略 。 62 （ 2） 兩階段法 第一階段：不考慮原問題是否存在基可行解；給原 LP問題的約束條件加入人工變量，構(gòu)造僅含人工變量的目標(biāo)函數(shù)并要求實(shí)現(xiàn)最小化（即使原 LP問題目標(biāo)函數(shù)是求最大化）的輔助問題： MinW=xn+1+…+x n+m ???????????????????????????????????????????0,111222121111111mnmmnnmnmnnnnnnxxbxxaxabxxaxabxxaxa 然后用單純形法求解（ 1）。若 W?0，則原問題無可行解，停止計(jì)算。若 W=0，且所有的人工變量均為非基變量，則去掉人工變量后可得到原問題的基可行解；如果人工變量中含有為 0的基變量時(shí)（即退化解），則可再進(jìn)行初等行變換將其換出，從而獲得原問題的基可行解。 （ 1） 63 第二階段：在第一階段所得的基可行解的基礎(chǔ)上 ， 將最終表中的人工變量列刪去 ， 同時(shí)將人工目標(biāo)函數(shù)行換為原問題的目標(biāo)函數(shù)作為第二階段計(jì)算的初始表 。 仍以上例為例用兩階段法求解 。 MinZ=x1++0x3+0x4 ?????????????0,0,2334321421321xxxxxxxxxx MinW=x5+x6 輔助問題： ????????????????0,0,0,23365432164215321xxxxxxxxxxxxxx原問題： 用單純形法求解的迭代表如下： 64 cj 0 0 0 0 1 1 CB XB b x1 x2 x3 x4 x5 x6 1 1 x5 x6 3 2 1 3 1 0 1 0 1 1 0 1 0 1 W 5 2 4 1 1 0 0 cj 0 0 0 0 1 1 CB XB b x1 x2 x3 x4 x5 x6 0 1 x2 x6 1 1 1/3 1 1/3 0 1/3 0 2/3 0 1/3 1 1/3 1 W 1 2/3 0 1/3 1 4/3 0 65 cj 0 0 0 0 1 1 CB XB b x1 x2 x3 x4 x5 x6 0 0 x2 x1 1/2 3/2 0 1 1/2 1/2 1/2 1/2 1 0 1/2 3/2 1/2 3/2 W 0 0 0 0 0 1 1 上述表中目標(biāo)函數(shù)值 W=0，且人工變量已全部出基，得到原問題的一個(gè)可行基 B=（ P2， P1）和一個(gè)基可行解 X=（ X2， X1） =（ 1/2， 3/2）。去掉人工變量列，并將目標(biāo)函數(shù)行換為原目標(biāo)函數(shù)行得： cj 0 0 0 0 CB XB b x1 x2 x3 x4 1 x2 x1 1/2 3/2 0 1 1/2 1/2 1 0 1/2 3/2 Z 9/4 0 0 1/4 3/4 66 上表中最后一行所有檢驗(yàn)數(shù)均非正 （ 因?yàn)槭乔髽O小化問題 ） ， 所以上述表已是原問題的最優(yōu)表 。 從表中可知原問題的最優(yōu)解為 X1=1/2， X2=3/2， 最優(yōu)目標(biāo)函數(shù)值為Z=9/4。 注意：第二階段在填單純形表時(shí) ， 檢驗(yàn)數(shù)行的值是將原目標(biāo)函數(shù)中的基變量用非基變量表示 （ x 1 = 3 / 2 1/2x3+3/2x4， x2=1/2+1/2x31/2x4） 后所得結(jié)果填入 ， 或直接通過表中數(shù)字關(guān)系計(jì)算而得 。 67 總 結(jié) 一、線性規(guī)劃模型的建立 確定決策變量 確定目標(biāo)函數(shù) 確定約束條件 二、線性規(guī)劃模型的求解 1）找到初始可行基解，建立初始單純形表 2）判斷最優(yōu)：所有檢驗(yàn)數(shù)大于等于 0時(shí)最優(yōu) 3）換基迭代：以負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的變量進(jìn)基，按最小元素法確定出基變量。 普通單純形法 人工變量法 1）在原問題上加入人工變量化為輔助問題 ,用單純形法求解輔助問題 2）刪去人工變量和改換目標(biāo)函數(shù) ,求解原問題 68 練習(xí)：求解下列線性規(guī)劃問題 ???????????????0,6242..2max32121321321xxxxxxxxtsxxxZ其最優(yōu)表為： cj 1 2 1 0 0 CB XB b x1 x2 x3 x4 x5 1 2 x3 x2 1 3 3/2 0 1 1 1/2 1/2 1 0 0 1/2 Z 7 7/2 0 0 1 1/2 69 補(bǔ)充：矩陣形式的單純形表 ??????0XbAX.CXzmax加入松馳變量化為標(biāo)準(zhǔn)形 設(shè) C=（ CB,CN),A=(B,N), ???????XXXNB代入 (2)得 : ???????0XbXAX.CXzmaxS(2) ?????????????????????????0X,XbXXX)NB(.XX)CC(zmaxNBSNBNBNB?????????0X,XbX)XNXB(.)XCXC(zmaxNBSNBNNBB70 將基變量從目標(biāo)函數(shù)中消除 ?????????0X,XbX)XNXB(.)XCXC(zmaxNBSNBNNBB??????????? ?0X,XbBXBXNBX.)XCXC(zmaxNB1SN1BNNBB1?????????????????0X,XbBXBXBX.XC)XBXNBbB(CzmaxNB1SN1BNNSN11B11?????????????????0X,XbBXBXNBX.XBCX)CNBC(bBCzmaxNB1SN1BSBN11B11NB建立對(duì)應(yīng)于基 B的矩陣形式的單純形表 T（ B）： 71 C CB CN CS b XB XN XS XB B1b I B1N B1 Z C BB1b 0 C BB1NCN CB B1 ? B1A CBB1AC ?????????????????0X,XbBXBXNBX.XBCX)CNBC(bBCzmaxNB1SN1BSBN11B11NBb X XB B1b B1A Z C BB1b C BB1AC 化簡為如下簡單的表格形式 : 72 167。 對(duì)偶理論與靈敏度分析 一、 LP的對(duì)偶問題 課本 P6的生產(chǎn)計(jì)劃問題是一個(gè)在有限資源的條件下 ， 求使利潤最大的生產(chǎn)計(jì)劃安排問題 ， 其數(shù)學(xué)模型為： ????????????0,)(2623)(2432.34Zmaxxxxxxxxx21212121工時(shí)約束材料約束現(xiàn)從另一角度考慮此問題。假設(shè)有客戶提出要求，租賃工廠的工時(shí)和購買工廠的材料，為其加工生產(chǎn)別的產(chǎn)品，由客戶支付工