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