【文章內(nèi)容簡(jiǎn)介】 反映在目標(biāo)中 影子價(jià)格 = 對(duì)偶解 + 資源成本 ?按以下原則考慮經(jīng)營(yíng)策略 ： 影子價(jià)格高于市場(chǎng)價(jià)格 （ 或 ?0） 表明資源有獲利能力 ， 購(gòu)入該資源 。 影子價(jià)格低于市場(chǎng)價(jià)格 （ 或 ?0） 表明該資源無(wú)獲利能力 ， 出讓該資源 。 影子價(jià)格等于市場(chǎng)價(jià)格 （ 或 =0） 表明該資源處于平衡狀態(tài) ， 既不用買入 , 也不必賣出 。 2. 互補(bǔ)松弛定理 ?互補(bǔ)松弛定理 (又稱松緊定理 )描述了線性規(guī)劃達(dá)到最優(yōu)時(shí)，原問(wèn)題 (或?qū)ε紗?wèn)題 )變量取值和對(duì)偶問(wèn)題 (或原問(wèn)題 )約束松緊之間的對(duì)應(yīng)關(guān)系。 ? 定理 （ 互補(bǔ)松弛定理 ） 如果 X, Y分別是 P 和 D 的可行解 , 它們是 P 和 D 的最優(yōu)解的充要條件是： (C ATY)T X = 0 (b AX)T Y= 0 ? 互補(bǔ)松弛定理中還可等價(jià)表示為： yi(bi ai x) = 0 i=1 , 2 , ... , m (cj－ ypj )xj = 0 j=1 , 2 , ... , n ?互補(bǔ)松弛定理證明了最優(yōu)線性規(guī)劃的下列對(duì)應(yīng)關(guān)系： 原問(wèn)題約束為緊 ? 對(duì)偶變量 ? 0； 原問(wèn)題約束為松 ? 對(duì)偶變量 =0； 對(duì)偶約束為緊 ? 原問(wèn)題變量 ? 0； 對(duì)偶約束為松 ? 原問(wèn)題變量 =0； 原問(wèn)題變量 0 ? 對(duì)偶約束為緊約束； 原問(wèn)題變量 =0 ? 對(duì)偶約束可緊可松 。 互補(bǔ)松弛性的經(jīng)濟(jì)意義 ?若資源的影子價(jià)格大于零 (yi?0)，必為緊缺資源，約束為緊約束 (biaix=0)；否則，若該資源仍有剩余，系統(tǒng)還未達(dá)到最優(yōu)狀態(tài)，利用該資源可使目標(biāo)進(jìn)一步得到改善。 ?若資源有剩余， 約束為松 (biaix?0)，其對(duì)偶解必為零 (yi=0)，否則，若對(duì)偶解大于零，增加該資源的使用還可使目標(biāo)得到改善。 互補(bǔ)松弛性的經(jīng)濟(jì)意義 ?在最優(yōu)狀態(tài)下， 當(dāng)變量的檢驗(yàn)數(shù)小于零時(shí)（ cjypj?0），說(shuō)明生產(chǎn)該產(chǎn)品的邊際貢獻(xiàn)是負(fù)的，在最優(yōu)計(jì)劃中不該生產(chǎn)它，因此，該變量必為零（ xj=0）。 ?當(dāng)變量大于零時(shí) （ xj?0），該變量的檢驗(yàn)數(shù)（邊際貢獻(xiàn)）必為零（ cjypj=0），否則，無(wú)論邊際貢獻(xiàn)取正值或負(fù)值，相應(yīng)地增加或降低該產(chǎn)品的產(chǎn)量都可使目標(biāo)得到改善。 例 ３ .7 已知線性規(guī)劃 min z = 2x1 + 3x2 + 5x3 + 2x4 + 3x5 . x1 + x2 + 2x3 + x4 + 3x5 ? 4 2x1 x2 + 3x3 + x4 + x5 ? 3 x1 , x2 , x3 , x4 , x5 ? 0 其對(duì)偶問(wèn)題的最優(yōu)解為： y1* = , y2* = 。試用對(duì)偶理論求出它的原問(wèn)題的最優(yōu)解 對(duì)偶問(wèn)題： Max w= 4y1 + 3y2 . y1 + 2y2 ? 2 y1 y2 ? 3 2y1+ 3y2 ? 5 y1+ y2 ? 2 3y1+ y2 ? 3 y1 ? 0, y2 ? 0 代入 y1*=, y2*= 松約束 ? x2 = 0 緊約束 ? x1 ? 0 松約束 ? x3 = 0 松約束 ? x4 = 0 緊約束 ? x5 ? 0 原問(wèn)題的約束為緊約束 , 故有 : x1 + 3x5 = 4 2x1 + x5 = 3 解得： x1* = 1， x5* = 1 原問(wèn)題的最優(yōu)解為： X = (1 , 0 , 0 , 0 , 1) , z* = 5 167。 對(duì)偶單純形方法 單純形方法 始終保持原問(wèn)題的解可行 ， 檢驗(yàn)數(shù)不一定小于等于零 （ 即對(duì)偶解不可行 ） 。一旦檢驗(yàn)數(shù)小于等于零 （ 即對(duì)偶解變?yōu)榭尚薪?） ， 則問(wèn)題達(dá)到最優(yōu) 。 對(duì)偶單純形方法的基本思想： 從對(duì)偶規(guī)劃的一個(gè)可行基出發(fā)，即保證滿足 ? = C CBB1A ? 0；一旦原問(wèn)題可行，即： XB = B1b ? 0，則找到最優(yōu)解。 ??? ??NJjjijiiB xbBx ?)()(1?最優(yōu)檢驗(yàn)存在以下幾種情況： ? (1)如果 B1b?0， 該問(wèn)題已最優(yōu) ， 停止； (2) 如果 B1b存在至少一個(gè)負(fù)分量 , 且 ?i? 0 , ?i = (?i1, ?i2, ... ?in)， ?ij =(B1pj)i ， 由線性規(guī)劃的典則方程： 再由條件 (B1b)i 0和 ?i ?0， (xB)i 不可能變?yōu)檎?， 因此原問(wèn)題無(wú)可行解 。 Nrjrkkjj Jj ???? 0~?????Nrjrjjrkk Jj ??? ,0 ?????(3) 如果 B1b中存在至少一個(gè)負(fù)分量， 且每個(gè)負(fù)分量對(duì)應(yīng)的行向量 ?i存在小于零的元素，此時(shí)原問(wèn)題解不可行，仍需繼續(xù)迭代。保持對(duì)偶可行的條件可表示為： 因此可得入基變量的檢驗(yàn)條件為： rkkrjrjjjm i n?????? ??????????? 0 = 對(duì)偶單純形算法： 1. 找初始對(duì)偶可行解； 2. 最優(yōu)檢驗(yàn)： (B1b)r=min{(B1b)i i?JB } 如果 (B1b)r?0，已找到最優(yōu)解，停止。 如果 (B1b)r?0 且 ?r?0, 問(wèn)題不可行 , 停止計(jì)算。 否則選變量 xr 出基，轉(zhuǎn)到 3。 rkkrjrjjjm i n?????? ??????????? 0 = 3. 確定入基變量， 令 ?j=cjcBB1pj, 計(jì)算： 令 xk 入基。 4. 以 ?rk 為轉(zhuǎn)軸進(jìn)行旋轉(zhuǎn)迭代 得到一個(gè)新的單純形表，轉(zhuǎn)到 2。 原始單純形法 對(duì)偶單純形法初始解 原問(wèn)題可行： A x ? b, x ? 0 對(duì)偶可行： yA ? c, y ? 0最優(yōu)檢驗(yàn) 條件： ? = c c B B1A ? 0 無(wú)界：存在 ?j 0 且 B1pj ? 0 條件： x = B1b ? 0 無(wú)解：存在 ( B1b )i0 且 ?i? 0確定入基變量 xk ?k= m ax { cj cBB1pj, ? j ? J N }rkkrrjjjm i n?????? ???????????0=確定出基變量 xrrkrikikiabaabm i n ???????????? 0i=? ( B1b )r = m i n {( B1b )i i ? J B }原始與對(duì)偶單純形法的對(duì)比 例 用對(duì)偶單純形方法求解： ????????????????0,236343323m i n2121212121xxxxxxxxxxf解 : （ 1） 引入松弛變量 x3 , x4 , x5 化為標(biāo)準(zhǔn)形 ， 并在約束等式兩側(cè)同乘 1， 得到 ???????????????????????????5,2,1,0236343323m a x52142132121?jxxxxxxxxxxxxZj取 x3 , x4 , x5為基變量，此式即為典式形式，并且檢驗(yàn)數(shù)皆非正，因此可構(gòu)初始對(duì)偶單純形表 3 2 0 0 0 cB xB B 1b x1 x2 x3 x4 x5 0 x3 3 3 1 1 0 0 0 x4 6 4 ( 3 ) 0 1 0 0 x5 2 1 3 0 0 1 ? 0 0 0 0 0 0 ? 0 3 2 0 0 0 0 x3 1 5 / 3 0 1 1 / 3 0 2 x2 2 4 / 3 1 0 1 / 3 0 0 x5 4 3 0 0 1 1 ? 4 1 / 3 0 0 2 / 3 0 3 2 0 0 0 cB xB B 1b x1 x2 x3 x4 x5 0 x3 1 ( 5 / 3 ) 0 1 1 / 3 0 2 x2 2 4 / 3 1 0 1 / 3 0 0 x5 4 3 0 0 1 1 ? 4 8 /3 2 0 2 / 3 0 ? 1/ 3 0 0 2 / 3 0 3 x1 3 / 5 1 0 3 / 5 1 / 5 0 2 x2 6 / 5 0 1 4 / 5 3 / 5 0 0 x5 1 1 / 5 0 0 9 / 5 8 / 5 1 ? 2 1 / 5 0 0 1 / 5 3 /5 0 例 用對(duì)偶單純形法求解下面線性規(guī)劃 ?????????????????????4,3,2,1,012122m a x42132121jxxxxxxxxxZj解 : 構(gòu)造對(duì)偶單純形表進(jìn)行迭代， 1 1 0 0 cB xB B 1b x1 x2 x3 x4 0 x3 2 ( 2 ) 1 1 0 0 x4 1 1 1 / 2 0 1 ? 0