【正文】 第二章 對偶問題及靈敏度分析 第一節(jié) 單純形法的矩陣描述 矩陣描述的目的是將單純形法用矩陣來加以解釋及有助于對偶問題的分析。 一、標準型規(guī)劃問題的矩陣描述 設線性規(guī)劃問題為： ??????0XbAXCXM ax Z? ?數(shù)系數(shù)！注意決策變量及目標函不妨假設 NBA ?? ? NNBBNBNB XCXCXXCCCXM a x Z ????????????目標函數(shù)：模型可表示為：?????????????????????????????0,0,0,),(11NBNBNBNBNBNBXXbBNXBXXXbNXBXXXbXXNB約束條件：?????????????0, )( 1111NBNBNBNBXXbBNXBXXNBCCbBCM a x Z為：典式要求的模型可表示所對應的單純形表為： CB CN XB b XB XN XB B1b I B1N Z CBB1b 0 CNCBB1N 關于檢驗數(shù)的再討論！ ①檢驗數(shù)的統(tǒng)一表示（不論是基變量還是非基變量） ②某一個變量檢驗數(shù)的表示方法 NB??? ? ? ?? ?? ?NBBNBNBBNBCCNBBCCCABCC????????????? 0 111jBjj PBCC 1???? 二、存在松弛變量模型的矩陣描述 設線性規(guī)劃問題為： ??????0XbAXCXM ax Z引入松弛變量的模型為： ????????0,0SSSXXbIXAXXCXM a x Z 注意特別強調了松弛變量在模型矩陣描述中的作用！ 在下面的矩陣描述中，松弛變量獨立表示，不歸入非基變量?？聪旅娴哪Ｐ妥兓?！ ??????????0,0SNBSNBSNNBBXXXbIXNXBXXXCXCM a x Z?????????????0,0111SNBSNBSNNBBXXXbBXBNXBXXXCXCM ax Z??????????????????0,0)(111111SNBSNBSNNSNBXXXbBXBNXBXXXCXBNXBbBCM ax Z?????????????????0,)(111111SNBSNBSBNBNBXXXbBXBNXBXXBCXNBCCbBCM ax Z約束方程 兩邊左乘 B1 把 XB代入 目標函數(shù) 目標函 數(shù)整理 ?????????????????0,)(111111SNBSNBSBNBNBXXXbBXBNXBXXBCXNBCCbBCM ax Z以此模型構造單純形表如下： CB CN 0 XB b XB XN XS XB B1b I B1N B1 Z CBB1b 0 CNCBB1N CBB1 此表的一個重要目的就是在于 B1所在的位置。 結合教材中，表 13～表 15的約束方程的系數(shù)矩陣，了解 B1的位置及作用。 表 13所對應的模型為： ?????????????????0,124164823251524132121xxxxxxxxxxxM ax Z?? ? 得到哪張表？左乘以約束條件，應該用若 1241 , ?? BPPPB第二節(jié) 對偶問題的提出 線性規(guī)劃問題具有對偶性！ 什么是對偶性？ 任何一個求最大值的線性規(guī)劃問題都有一個求最小值的線性規(guī)劃問題與之相對應。 一個叫 “ 原始問題 ” ，另一個稱為它的 “ 對偶問題 ” 。 原始問題和對偶問題所依據(jù)的數(shù)據(jù)資料是一致的！ 仍以前述模型為例說明對偶問題。 例 1 某廠計劃在下一個生產周期內生產甲、乙兩種產品，這兩種產品分別要經過兩種設備加工，有關數(shù)據(jù)如下表，問應如何安排生產計劃使總利潤最大？其依據(jù)的數(shù)據(jù)資料及模型為： 甲 乙 機器臺時 設備 A 2 4 80 設備 B 3 2 60 單件利潤 60 50 ????????????0,60238042 506021212121xxxxxxxxM ax Z 現(xiàn)在從另一個角度討論 該問題 ①為什么能夠獲利呢？ 因為有資源： A—80、 B—60 ② 不生產甲、乙產品能否獲利呢？ 把已有設備出租 ③租金或設備使用費用如何收?。? 不低于自己創(chuàng)收、承租方可以接受 ④假設設備的每臺時使用費分別為 Y Y2 根據(jù)原始數(shù)據(jù)，用于加工一件產品的設備臺時出租后的收益不應低于產品的利潤，則得到另一組約束條件： ??????????0,50246032 212121yyyyyy 但是，承租方希望其設備臺時的使用費越小越好，則必有： 21 6080 yyM in W ?? 則原問題的對偶問題為： ????????????0,50246032 608021212121yyyyyyyyM inW????????????0,60238042 506021212121xxxxxxxxM ax Z原 問 題 對 偶 問 題 第三節(jié) 線性規(guī)劃的對偶理論 一、對偶問題的定義 設原始線性規(guī)劃問題為： ??????0XbAXCXM ax Z則稱下列規(guī)劃問題為原始問題的對偶問題。 ??????0YCYAYbM inW注意： Y是行向量還是列向量；其分量的個數(shù)？ 例 2 寫出下列規(guī)劃問題的對偶問題。 ??????????????????????0,4675343232532321321321321321xxxxxxxxxxxxxxxM ax Z???????????????????????0,5643732532432321321321321321yyyyyyyyyyyyyyyM inW注意：一個方程對應一個對偶變量！ )532( ),(432 675413132321 ,CyyyYbA???????????????????????????????????????0YCAYbYM in W由對偶的定義原問題 對偶問題 二、非對稱規(guī)劃問題的對偶問題 若原始線性規(guī)劃問題為： ??????0XbAXCXM ax Z關鍵在于將原模型進行轉變如下 : ?????????0XbAXbAXCXM a xZ???????????0)2()1(XYbAXYbAXCXM a x Z變形 mmnmYYYbbbAAA 21)2()1(_12_2_ ),( ????????????????????此時則其對偶問題為； ????????0, )2()1()2()1()2()1(YYCAYAYbYbYM inW)2()1( YYY ??令??? ??無符號限制YCYAYbM inW例 3 寫出下列規(guī)劃問題的對偶問題 ??????????????0,4239253432132132121xxxxxxxxxxxM a x Z??????????00_____YAYbYM in W 分析一個一般的線性規(guī)劃問題？如何得到其對偶問題，又能夠得到什么結論！ ????????????0332211XbXAbXAbXACXM ax Z原問題（對偶問題） 對偶問題（原問題） 目標函數(shù) max 變量： n個 ≥ 0 ≤0 無約束 目標函數(shù) min 約束條件： n個 ≥ 號 ≤ 號 ＝ 約束條件： m個 ≤ 號 ≥ 號 ＝ 約束條件右端項 目標函數(shù)變量的系數(shù) 變量： m個 ≥ 0 ≤0 無約束 目標函數(shù)變量的系數(shù) 約束條件右端項 例 4 寫出下列規(guī)劃問題的對偶問題 ??????????????????????無限制321321321321321,0,05643732532432xxxxxxxxxxxxxxxM inZ????????????????????????0,0,04675343232532321321321321321yyyyyyyyyyyyyyyM ax W 三、對偶問題的基本性質 這是基于對稱型問題而言的 ：對偶問題的對偶問題是原問題 ；若 X(1)和 Y(1)分別是可行解，則 bYCX