【正文】 ：設(shè)B為L(zhǎng)P問題的最優(yōu)基，則 資源的影價(jià)=Y*=CBB1 (2)在退化情況下： 當(dāng)對(duì)偶問題有K個(gè)最優(yōu)解，則第i種資源的影價(jià)=即影價(jià)的第i個(gè)分量等于這K個(gè)對(duì)偶解中第i個(gè)分量的最小值。影子價(jià)格是在最優(yōu)決策下對(duì)資源的一種估價(jià)，沒有最優(yōu)決策就沒有影子價(jià)格，所以影子價(jià)格又稱“最優(yōu)計(jì)劃價(jià)格”，“預(yù)測(cè)價(jià)格”等等。這是因?yàn)閺淖罱K表中可看出，在最優(yōu)方案中，松馳變量x5=4，即表示在最優(yōu)生產(chǎn)方案中，原材料B尚有4個(gè)單位剩余被閑置，不產(chǎn)生任何經(jīng)濟(jì)效益。實(shí)質(zhì)上Yi*就是第i種資源邊際價(jià)值的一種表現(xiàn)，也是對(duì)第i種資源的一種估價(jià)。：舉例說明 ：①不要求模型中b≥0②先確定換出變量xL，再確定換入變量xK③ ①maxZ=CX(C≤0) ②maxZ=CX（b無(wú)限制），③當(dāng)變量個(gè)數(shù)（約束個(gè)數(shù)時(shí)，可先轉(zhuǎn)化為其對(duì)偶問題，再用單純形法或?qū)ε紗渭冃畏ń庵苓M(jìn)行靈敏度分析時(shí)，有時(shí)會(huì)用到此法 四、對(duì)偶解的經(jīng)濟(jì)含義和影子價(jià)格 *=CBB1的經(jīng)濟(jì)含義 設(shè)互為對(duì)偶的LP問題 maxZ=CX minW=Yb (原) (對(duì)) 有 Z*=CBB1b=W* (其中B為最優(yōu)基) 因此 或者說Z*=y*1b1+y*2b2+y*mbm 則其含義是：若對(duì)原問題右端常數(shù)項(xiàng)向量b中的某一常數(shù)項(xiàng)bi增加一個(gè)單位，目標(biāo)函數(shù)的最優(yōu)值Z*的變化將是Yi*。根據(jù)對(duì)偶問題的對(duì)稱性，也可以在保持對(duì)偶可行下，經(jīng)過迭代，逐步實(shí)現(xiàn)原始可行，以求得最優(yōu)解。aijy*i=cj④若229。aijX*j=bi②若229。（6）（互補(bǔ)松馳性），若X*、Y*分別是原問題的對(duì)偶問題的可行解，則X*、Y*是最優(yōu)解的充要條件是：Y*XS=0,YSX*=0(其中XS,YS分別是原問題和對(duì)偶問題的松馳變量向量)。二、對(duì)偶理論 原 始 對(duì) 偶 表原問題Max（對(duì)偶問題）對(duì)偶問題Min（原問題）約束條件數(shù)=m 變量個(gè)數(shù)=m第i個(gè)約束條件為“”第i個(gè)約束條件為“≥”第i個(gè)約束條件為“=” 第i個(gè)變量≥0 第i個(gè)變量≤0 第i個(gè)變量無(wú)限制變量個(gè)數(shù)=m 約束條件個(gè)數(shù)=n第i個(gè)變量≥0第i個(gè)變量≤0第i個(gè)變量無(wú)限制 第i個(gè)約束條件為“” 第i個(gè)約束條件為“≥” 第i個(gè)約束條件為“=”第i個(gè)約束條件的右端項(xiàng)目標(biāo)函第i個(gè)變量的系數(shù) 目標(biāo)函數(shù)第i個(gè)變量的系數(shù) 第i個(gè)約束條件的右端頂MaxZ=CX MinW=Yb設(shè) （1）（對(duì)稱性）對(duì)偶問題的對(duì)偶是原問題；（2）（弱對(duì)偶性）若是原問題的可行解，是對(duì)偶問題的可行解； 則；（3）（無(wú)界性）若原問題（對(duì)偶問題）為無(wú)界解，則其對(duì)偶問題（原問題）無(wú)可行解；（4）（最優(yōu)性準(zhǔn)則），若、分別是互為對(duì)偶問題的可行解，且C=b，則、分別是它們的最優(yōu)解；（5）（對(duì)偶定理）若互為對(duì)偶問題之一有最優(yōu)解，則另一問題必有最優(yōu)解，且它們的目標(biāo)函數(shù)值相等。0}的對(duì)偶問題于是，對(duì)稱形式下兩個(gè)互為對(duì)偶LP問題的數(shù)學(xué)模型為：MaxZ=CX MinW=Yb 與 任何一個(gè)LP問題均有一個(gè)對(duì)偶LP問題與之匹配。C又對(duì)② Y=CBB1，兩邊右乘b，有Yb=CBB1b=Z由于Y無(wú)上界，所以只有最小值，因此有MinW=Yb它是原問題 {maxZ=CX| AX163。由例1 有maxZ=cx由矩陣形式的單純形表中可知：檢驗(yàn)數(shù)的表達(dá)式為： CBB1N－CN和CBB1①② 當(dāng)表示LP問題已得到最優(yōu)解令Y=CBB1,且②有Y179。稱這兩個(gè)LP問題是互為對(duì)偶的兩個(gè)LP問題。因此有工廠的總收入為 W=8y1+16y2+12y3（2）價(jià)格應(yīng)盡量低，否則沒有競(jìng)爭(zhēng)力（此價(jià)格可成為與客戶談判的底價(jià)）租賃者考慮：希望價(jià)格越低越好，否則另找他人。3 對(duì)偶理論與靈敏度分析 一、LP的對(duì)偶問題 前已述引例1是一個(gè)在有限資源的條件下，求使利潤(rùn)最大的生產(chǎn)計(jì)劃安排問題，其數(shù)學(xué)模型為：（設(shè)備）（原材料A）（原材料B）maxZ=2x1+3x2現(xiàn)從另一角度考慮此問題。在計(jì)算機(jī)上常采用“Bland規(guī)則”：（1）取表中下標(biāo)最小的非基變量xk為換入變量，即k=min{j | sj0} （2）按q規(guī)則計(jì)算，若存在兩個(gè)相同以上最小比值時(shí)，選取下標(biāo)最小的基變量為換出變量xL，即值得慶幸的是出現(xiàn)基循環(huán)是罕見的。B1這樣迭代下去便永遠(yuǎn)得不到最優(yōu)解。B2174。sj0x500[2]121004x13110100/0x630211011Z12043400172。（2）第二階段單純形表中目標(biāo)函數(shù)系數(shù)應(yīng)將非基變量表示基變量后所得結(jié)果填入，或先直接填入原系數(shù)，再通過初等行變換使基變量的檢驗(yàn)數(shù)為0。仍以上例為例用兩階段法求解。若W=0，且所有的人工變量均為非基變量，則去掉人工變量后可得到原問題的基可行解；如果人工變量中含有為0的基變量時(shí)（即退化解），則可再進(jìn)行初等行變換將其換出，從而獲得原問題的基可行解。若W185。 ④大M法適合于手算，不適用于計(jì)算機(jī)求解。注意到：①分別在約束條件增加人工變量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à)。人工變量法常見的有大M法和兩階段法。在最終表中若不能全部被換出，則說明原問題無(wú)可行解。這樣，新問題將有一個(gè)初始基可行解（以人工變量為基變量），可用單純形法進(jìn)行迭代。所謂人工變量法是在原問題不含有初始可行基B=I的情況下，人為的對(duì)約束條件增加虛擬的非負(fù)變量（即人工變量），構(gòu)造出含有B=I的另一個(gè)LP問題后求解。即第L個(gè)分量如果在最終表中有非基變量的檢驗(yàn)數(shù)為0，則該問題有多重最優(yōu)解。換基迭代的關(guān)鍵在于將換入變量對(duì)應(yīng)的列向量用初等行變換方法變換成單位列向量。 按最小比值原則確定出基變量xL： 3176。否則轉(zhuǎn)入（3） （3）換基迭代（基變換） 1176。n)，且xk的系數(shù)列向量Pk163。 在T(B)中，若有σk0 (1163。 在T(B)中，若所有的檢驗(yàn)數(shù)σj≥0 (j=1,2,…,n) 則B為最優(yōu)基，相應(yīng)的基可行解為最優(yōu)解，停止計(jì)算。CBCNCLXBXNXLXB1B1NB1ZCBB1b0CBB1N－CNCBB1例如將例1 化成標(biāo)準(zhǔn)型后如下表T（B）：Cj23000qiCBXBx1x2x3x4x50x38121000x416400100x51204001Z023000172。因此，矩陣形式的LP模型改寫為： 174。 （3）更好表現(xiàn)一般規(guī)律的在矩陣形式的單純形表中設(shè)MaxX=CX MaxZ=CX+0XL 其標(biāo)準(zhǔn)型為 將系數(shù)矩陣(A,I)分劃為(B,N,I)，其中B為可行基，對(duì)應(yīng)于基變量向量XB,N對(duì)應(yīng)于XN，I對(duì)應(yīng)于XL,(XN,XL)為非基變量向量。目標(biāo)函數(shù)非基變量的系數(shù)則以相反數(shù)填入檢驗(yàn)數(shù)行各相應(yīng)位置。2 單純形法與計(jì)算機(jī)求解 ：求出一個(gè)初始基可行解 y停判別此基可行解是否最 優(yōu) 解 N求出使目標(biāo)函數(shù)值得到改善的基可行解 （表格形式） （1）建立初始單純形表，假定B=I，b≥0 設(shè)maxZ=c1x1+c2x2+…+xn將目標(biāo)函數(shù)改寫為：Z+c1x1+c2x2+…+xn=0把上述方程組和目標(biāo)函數(shù)方程構(gòu)成n+1個(gè)變量，m+1個(gè)方程的方程組，并寫成增廣矩陣的形式：Z x1 x2 … xm xm+1 … xn 0 1 0 … 0 1m+1 … 1n 10 0 1 … 0 2m+1 … 2n 20 0 0 … 1 mm+1 … mn m1 c1 c2 … cm cm+1 … 0以非基變量表示基變量形式代入Z中的基變量,有 令 于是因此，上述的增廣矩陣就可寫成：Z x1 x2 … xm xm+1 … xn 0 1 0 … 0 1m+1 … 1n 10 0 1 … 0 2m+1 … 2n 20 0 0 … 1 mm+1 … mn m1 0 0 … 0 …－ 再令則上述增廣矩陣可寫成下面表格形式：即初始單純形表T（B）CjC1……Cmcm+1……qiCBxBx1……xmxm+1……xnC1x111……0a1m+1……a1nC2x220……0a2m+1……a2n：：：： ：：………：Cmxmm0……1amm+1……amnZZ00……0sm+1……sn172。 ：