【正文】 10112//bB福州大學公共管理學院 28 第 2步計算結束后的結果 ? ?? ?? ?? ? ? ?),(),(C,CC。x,xX。x,x,xX。P,P,PBNBTNTB003022222532412412?????價值系數(shù)非基變量基變量基福州大學公共管理學院 29 第 3步 從新的基，基變量開始 , 重復第 1步的計算步驟 . 福州大學公共管理學院 30 計算非基變量檢驗數(shù)，檢查檢驗數(shù)，確定換入變量 ? ?? ?? ? ? ?換入變量正檢驗數(shù)對應注意：535322124121000014100314210130200222x,x/,//),(,)P,PN(NBCCBNN????????????????????????????????福州大學公共管理學院 31 (3) 確定換出變量 計算： 表示選擇 0的進行計算 ? ?? ?4441328212051251212x/,/mi nPBPBbBmi nii對應????????????????????????福州大學公共管理學院 32 新的基 ? ?主元素的系數(shù)向量是換入變量??????????? ???????????????????????????412211004100214210151252513////PBx。P,P,PB福州大學公共管理學院 33 計算 B逆矩陣 ?????????????? ?????????????????18100210041181214133///E///構造?福州大學公共管理學院 34 ????????????????????????????????????????08121121204104100214210118100210041112313/////////BEB福州大學公共管理學院 35 計算非基變量的檢驗數(shù) ? ?? ?? ?已無正檢驗數(shù)注意：8123010001081211212041030200433313333/,/////),(,P,PNNBCCBNN????????????????????????????????福州大學公共管理學院 36 最優(yōu)解 ?????????????????????????????????????24412812116212841013251////bBxxxX*福州大學公共管理學院 37 目標函數(shù)的值 ? ? 1424430213??????????????,bBCzB*福州大學公共管理學院 38 第二章 對偶理論和靈敏度分析 ? 若第一章中例一關于某廠的生產計劃問題 ， 現(xiàn)有另一企業(yè)想租賃其設備 。 廠方為了在談判時心中有數(shù) ，需掌握設備臺時費用的最低價碼 ， 以便衡量對方出價 ， 對出租與否做出抉擇 。 ? 在這個問題上廠長面臨著兩種選擇：自行生產或出租設備 。 首先要弄清兩個問題： ? ① 合理安排生產能取得多大利潤 ? ? ② 為保持利潤水平不降低 ， 資源轉讓的最低價格是多少 ？ ? 問題 ① 的最優(yōu)解： x1=4， x2=2， Z*=14。 三、對偶問題的提出 福州大學公共管理學院 39 第二章 對偶理論和靈敏度分析 第二個問題：出讓定價 ? 假設出租單位設備臺時的租金和出讓單位原材料 A、 B所得利潤分別為 y y y3 ? 原本用于生產 I產品的設備臺時，如若出讓，不應低于自行生產帶來的利潤，否則寧愿自己生產。于是有 y1+4y2≥ 2 ? 同理，對 Ⅱ 產品而言，則有 2y1+4y3≥3 ? 設備臺時出讓的收益（希望出讓的收益最少值） min ?=8y1+16y2+12y3 ? 顯然還有 y1， y2， y3≥0 福州大學公共管理學院 40 第二章 對偶理論和靈敏度分析 ? 對偶問題的最優(yōu)解： y1=3/2， y2=1/8， y3=0， W* =14 ? 兩個問題的目標函數(shù)值相等，這不是偶然的，上述兩個問題實際上是一個問題的兩個方面，如果把前者稱為線性規(guī)劃原問題，則后者便是它的對偶問題，反之亦然。 ? 對偶問題的最優(yōu)解對應于原問題最優(yōu)單純型法表中，初始基變量的檢驗數(shù)的負值。 例 1的對偶問題的數(shù)學模型 min? =8y1+16y2+12y3 y1+4y2 ≥ 2 2y1 + 4y3≥ 5 y1， y2， y3≥0 . Max Z= 2x1 +3 x2 x1 +2 x2 ≤8 4x1 ≤16 4 x2 ≤12 x1 , x2 ≥0 . 福州大學公共管理學院 41 第二章 對偶理論和靈敏度分析 原問題與對偶問題的表達形式 ??????0XbAXtsCXxf..)(m a x :原問題??????0YCYAYb..)(m i n :tsyw對偶問題福州大學公共管理學院 42 第二章 對偶理論和靈敏度分析 四 線性規(guī)劃的對偶理論 （一）原問題與對偶問題的關系 標準 (max,?)型的對偶變換 ? 目標函數(shù)由 max 型變?yōu)? min 型 ? 對應原問題每個約束行有一個對偶變量 yi，i=1,2,…, m ? 對偶問題約束為 ? 型，有 n 行 ? 原問題的價值系數(shù) C 變換為對偶問題的右端項 ? 原問題的 右端項 b 變換為對偶問題的 價值系數(shù) ? 原問題的技術系數(shù)矩陣 A 轉置后成為對偶問題的技術系數(shù)矩陣 福州大學公共管理學院 43 原問題與對偶問題的關系 ??????????????????????????0,..21221122222112112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcMa x Z??????????????????????????????????0,..)(m i n21221122222112112211112211mnmmnnnmmmmmmyyycyayayacyayayacyayayatsybybybyw??????則對偶問題是 這兩個式子之間的變換關系稱為“ 對稱形式的對偶關系 ” 。 福州大學公共管理學院 44 例：寫出下面線性規(guī)劃的對偶問題： ????????????0,10251543..221212121xxxxxxtsxxM a x Z????????????0,124253..101521212121yyyyyytsyyM i n W福州大學公共管理學院 45 第二章 對偶理論和靈敏度分析 非 標準 型的對偶變換 含等式約束時，將等式約 束分解為兩個不等式 約束條件。 ?????????????????0,510342023..54)(m a x 1221212121xxxxxxxxtsxxxf不限原線性規(guī)劃問題例????????????????????????????????????????????????0, 551033420223..554)(m a x)( m a x , 221221221221221221xxxxxxxxxxxxxxxtsxxxxf型標準問題化為??????????????????????????0,532532443..551020)(m i n 43214321432143214321wwwwtswwh則應用標準型對偶變換規(guī)福州大學公共管理學院 46 第二章 對偶理論和靈敏度分析 按對稱形式變換關系可寫出它的對偶問題，如上所示。 ??????????????????????不限經(jīng)整理得令3213213213214332211,0,0532443..51020)(m i n:, yyyyyyyyytsyyyygwwywywy福州大學公共管理學院 47 原問題與對偶問題的關系，歸納如下：（原始－對偶表） 原問題（或對偶問題） 對偶問題 （或原問題） 目標函數(shù) max z 變量 n個 ≥0 ≤0 無約束 目標函數(shù) min w 約束條件 n個 ≥ ≤ ＝ 約束條件 m個 ≤ ≥ ＝ 約束條件右端項 目標函數(shù)變量的系數(shù) 變量 m個 ≥0 ≤ 0 無約束 目標函數(shù)變量的系數(shù) 約束條件右端項 福州大學公共管理學院 48 第二章 對偶理論和靈敏度分析 怎樣寫出非對稱形式的對偶問題？ ? 把一個等式約束寫成兩個不等式約束，再根據(jù)對稱形式的對偶關系定義寫出； ? 按照 原始 對偶表 直接寫出 。 福州大學公共管理學院 49 第