【正文】 ????????????????????NNBBNNNBNBNNNBBNNNBNNBBNBNBXbBCZNBCCXNBCCbBCXCNXBCbBCXCNXBbBCXCXCXXCCCXZ???? （ 2） 將式 （ 21） 代入目標(biāo)函數(shù)的表達(dá)式 ，可得： 用非基變量表示目標(biāo)函數(shù)的表達(dá)式： （ 3） 借助一個恒等式推出用非基變量表示目標(biāo)函數(shù)的另一個等價表達(dá)式： 0)( 1 ?? ? BBB XBBCC 01 ?? ? BBBB BXBCXC代入式（ 22），并令 1?? BCB?XACbBXBCXCXNBCCbBCZ BBBBNBNB)()( 111?? ???????? ??? （ 24） 單純形乘子 2 單純形表格的矩陣形式： cj j?TBX TNXTBC BX bB 1? BB 1? NB 1?Z? bBCB 1??NBCC BN 1?? CB XB xj b CB CN 0 換個角度審視生產(chǎn)計劃問題 例：要求制定一個生產(chǎn)計劃方案，在勞動力和原材料可能供應(yīng)的范圍內(nèi)，使得產(chǎn)品的總利潤最大 。 12m a x 2 3Z x x??12121228 4 16 4 12 , 0xxxxxx????????≤≤≤≥3 對偶原理 （ 用于生產(chǎn)第 i種產(chǎn)品的資源轉(zhuǎn)讓收益不小于生產(chǎn)該種產(chǎn)品時獲得的利潤 ） 它的 對偶問題 就是一個 價格系統(tǒng) ， 使在平衡了設(shè)備資源和原材料的直接成本后 ， 所確定的 價格系統(tǒng)最具有競爭力： ???????????????0,34224..121683213221321yyyyyyytsyyyM i n W對偶變量的經(jīng)濟(jì)意義可以解釋為對工時及原材料的單位定價 ； 若工廠自己不生產(chǎn)產(chǎn)品 Ⅰ 、 Ⅱ ， 將現(xiàn)有的設(shè)備及原材料轉(zhuǎn)而接受外來加工時，那么 上述的價格系統(tǒng)能保證不虧本又最富有競爭力（包工及原材料的總價格最低） 當(dāng)原問題和對偶問題都取得最優(yōu)解時，這一對線性規(guī)劃對應(yīng)的目標(biāo)函數(shù)值是相等的： Zmax=Wmin=14 考察原問題和對偶問題的解，給作決策的管理者另一個自由度； ?怎樣通過增加更多的資源來增加利潤？ ?怎樣使用不同類型的資源來增加利潤？ 飲食與營養(yǎng)問題 例 22 采購甲、乙、丙、丁 4種食品量分別為x1， x2， x3， x4， 在保證人體所需維生素 A、B、 C前提下，使總的花費最小。 ???????????????????????0,)()(40003250175015001000..4321421432143214321xxxxCxxxBxxxxAxxxxtsxxxxM i n Z毫克維生素）（毫克維生素國際單位維生素構(gòu)建的 線性規(guī)劃模型： 換一個角度，生產(chǎn)營養(yǎng)藥丸的制藥公司力圖使?fàn)I養(yǎng)師相信，各種營養(yǎng)藥丸勿須通過多種食品的轉(zhuǎn)換就能供營養(yǎng)師調(diào)劑。 制藥公司面對的問題是 為營養(yǎng)藥丸確定單價 ，以獲得最大的收益，同時與真正的食品競爭。 于是，營養(yǎng)藥丸的單位成本 不能超過 相應(yīng)食品的市場平均價。 ?????????????????????????????0,)( 2 5 0)( 7 5 0)( 5 0 0)( 0 0 0..304 0 0 0321321321321321321yyyIVyyyI I IyyyIIyyyIyyytsyyyM a x W丁食品市價的成本合成藥丸丙食品市價的成本合成藥丸乙食品市價的成本合成藥丸甲食品市價的成本合成藥丸由此得到下面的對偶問題： 二 、 原問題和對偶問題的關(guān)系 對稱形式的對偶關(guān)系 （ 1）若原問題是 ??????????????????????????0,..21221122222112112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcMa x Z??????????????????????????????????0,..21221122222112112211112211mnnmnnnnmmmmmyyycyayayacyayayacyayayatsybybybM i n W???????? 這兩個式子的變換關(guān)系稱為“ 對稱形式的對偶關(guān)系 ” 。 (2) 其對偶問題為 （ 2） 對稱形式的對偶關(guān)系的矩陣描述 ??????0..YCYAtsbYM in W(D) ??????0..XbAXtsCXM a x Z(L) 例 23 寫出下面線性規(guī)劃的對偶問題： ????????????0,10251543..221212121xxxxxxtsxxM a x Z????????????0,124253..101521212121yyyyyytsyyM in W??????????????njxmibxatsxcM a x Zjnjijijnjjj,2,10,2,1..11???????????????miynjcyatsxbM i n Wimijiijmiii,2,1,2,1..11??符號不限，（ 1） 原問題 對偶問題 （ 特點：對偶變量符號不限 ， 系數(shù)陣轉(zhuǎn)置 ） (特點：等式約束 ) 非對稱形式的對偶關(guān)系： （ 2） 怎樣寫出非對稱形式的對偶問題 ？ ?把一個等式約束寫成兩個不等式約束 ，再根據(jù)對稱形式的對偶關(guān)系定義寫出； ?按照原始 對偶表直接寫出 ； （ 3） 原始 對偶表 原問題（或?qū)ε紗栴}） 對偶問題（或原問題） 目標(biāo)函數(shù) MaxZ 目標(biāo)函數(shù) MinW 約束條件數(shù)： m個 第 i個約束條件類型為 “ ≤” 第 i個約束條件類型為 “ ≥” 第 i個約束條件類型為“ =” 對偶變量數(shù)： m個 第 i個變量 ≥0 第 i個變量 ≤0 第 i個變量是自由變量 決策變量數(shù)： n個 第 j個變量 ≥0 第 j個變量 ≤0 第 j個變量是自由變量 約束條件數(shù)： n 第 i個約束條件類型為 “ ≥” 第 i個約束條件類型為 “ ≤” 第 i個約束條件類型為“ =” 三 、 對偶定理 對偶定理是揭示 原始問題的解與對偶問題的解之間重要關(guān)系的一系列定理 。 定理 21 對稱性定理 —— 對偶問題的對偶是原問題 。 定理 22 弱對偶定理 —— 若一對對稱形式的對偶線性規(guī)劃 ??????0..XbAXtsCXM a x Z??????0..YCYAtsbYM in W均有可行解 ， 分別為 和 ， 則 C ≤ b 。 X~ X~Y~ Y~? 關(guān)于 “ 界 ” 的結(jié)果； 極小化問題有下界 —— 推論 1 極大化問題的任意一個可行解所對應(yīng)的目標(biāo)函數(shù)值是其對偶問題最優(yōu)目標(biāo)函數(shù)值的一個下界 。 ? 極大化問題有上界 —— 推論 2 極小化問題的任意一個可行解所對應(yīng)的目標(biāo)函數(shù)值是其對偶問題最優(yōu)目標(biāo)函數(shù)值的一個上界。 ?關(guān)于最優(yōu)解無界情況與對偶問題的關(guān)系； 原始問題可行 ， 則目標(biāo)函數(shù)值上無界 對偶問題不可行 推論 4 若對偶問題可行 ， 則其目標(biāo)函數(shù)無界的充要條件是原始問題沒有可行解 。 推論 3 若原始問題可行，則其目標(biāo)函數(shù)無界的充要條件是對偶問題沒有可行解。 對偶問題可行，對偶目標(biāo)函數(shù)值無界 原始問題不可行 最優(yōu)性準(zhǔn)則定理 —— 若 、 分別為對稱形式對偶線性規(guī)劃的可行解，且兩者目標(biāo)函數(shù)的相應(yīng)值相等，即 C =b ， 則 ， 分別為原始問題和對偶問題的最優(yōu)解。 X~X~X~Y~Y~Y~定理 23 最優(yōu)性準(zhǔn)則定理 定理 24 主對偶定理 若原始問題和對偶問題兩者均可行，則兩者均有最優(yōu)解，且此時目標(biāo)函數(shù)值相同。 四、對偶最優(yōu)解 （影子價格） 的經(jīng)濟(jì)含義 對偶最優(yōu)解的經(jīng)濟(jì)解釋 討論例 11的圖解法時 ， 提出了它的對偶規(guī)劃 ， 并用圖解法求出了最優(yōu)解 。 同時提到 “ 影子價格 ” ， 確切的定義是： 一個線性規(guī)劃對偶問題的最優(yōu)解 （ 簡稱為 “ 對偶最優(yōu)解 ” ） 。 在經(jīng)濟(jì)上可以解釋 為 約束條件所付出的代價 。 當(dāng) 原問題和對偶問題都取得最優(yōu)解時 ， 這一對線性規(guī)劃對應(yīng)的目標(biāo)函數(shù)值相等 ， 即有： Zmax=CX*=2x*1+3x*2 Wmin=Y*b=8y*1+16y*2+12y*3=14 其中 X*是原問題的最優(yōu)解 ， Y*是對偶問題最優(yōu)解 。 說明 目標(biāo)函數(shù)值增加一個單位 ， 這就是 放寬一個約束條件所產(chǎn)生的附加貢獻(xiàn) 。 就是說 ， 影子價格 確定了 為得到一個附加單位的約束因素所應(yīng)花費的成本上限 。 勞動工時 ！ 因為它的變化對產(chǎn)品總利潤的影響最大 ，因此 勞動力 是 最關(guān)鍵的生產(chǎn)環(huán)節(jié) ， 若能采取有力措施增加勞動總工時 ， 則產(chǎn)品總利潤將得到較大的提高 。 在計算機(jī)求解結(jié)果中將約束條件的影子價格和變量的機(jī)會成本統(tǒng)稱為 機(jī)會成本（ opportunity cost）。 當(dāng)前最敏感的資源是什么？ 綜上 ， 影子價格 是靈敏度分析的一種形式 ， 它 通過獲取一個單位的追加的產(chǎn)品因素 ， 去 測量放寬一個約束條件的價值 ， 比較追加資源的價值和資源的實際成本 ， 就能比較有把握地作出各種可行的決策 。