【正文】 任一 線性規(guī)劃 問題都存在另一與之伴隨的線性規(guī)劃問題 ，他們從不同角度對一個實際問題提出并描述 ， 組成一對互為對偶的線性規(guī)劃問題 。 第二章 線性規(guī)劃的對偶理論 167。 對偶線性規(guī)劃問題的提出 一、對偶線性規(guī)劃問題 某工廠計劃安排生產 Ⅰ 、 Ⅱ 兩種產品 ， 已知每種單位產品的利潤 、 生產單位產品所需的設備臺時及 A、 B兩種原材料的消耗 、現有原材料和設備臺時的定額如下表所示： 【 例 1】 Ⅰ Ⅱ 設 備 1 2 8臺時 原 材 料 A 4 0 16Kg 原 材 料 B 0 4 12Kg 每單位產品利潤（萬元） 2 3 ?原問題的策略 : ?問應如何安排生產才能使工廠獲利最大？ ?現在的策略 : ?假設不生產 Ⅰ 、 Ⅱ 產品 ,而是計劃將現有資源出租或出售 ,從而獲得利潤 ,這時需要考慮如何定價才合理 ? 21 32 xxf ??m a x????????????0x,x12x4 16 x48x2x.212121 設 x x2分別表示計劃生產 產品 Ⅰ 、 Ⅱ 的單位數量，由題意 原問題的模型 為： 工廠獲得最大利潤 符合資源限制 Ⅰ Ⅱ 設 備 1 2 8臺時 原 材 料 A 4 0 16Kg 原 材 料 B 0 4 12Kg 每單位產品利潤（萬元） 2 3 原問題的模型 ? 改變策略后，需要考慮如何給資源定價的問題！ 設 y y2 、 y3分別表示出租單位設備 臺時的租金和出售單位原材料 A、 B的利潤 . y1+4y2≥2 ， 2y1+4y3≥3 則： ? 工廠出租設備 、 原材料的租金要大于生產的利潤才合算 。 321 y12y16y8gm in ???工廠把所有設備臺時和資源都出租和出讓 ， 其收入為： ? 要尋找使租用者支付的租金最少的策略 。 Ⅰ Ⅱ 設 備 1 2 8臺時 原 材 料 A 4 0 16Kg 原 材 料 B 0 4 12Kg 每單位產品利潤（萬元） 2 3 新問題的模型 工廠 改變策略以后 的數學模型為： 321 y12y16y8g m i n ??????????????3,2,1,034y2y24yy.. 3121iytsi工廠獲得相應 利潤 用戶所付租金最少 321 12168m i n yyyg ??????????????3,2,1,034y2y24yy.. 3121iytsi21 32 xxf ??m a x????????????0,12416482..212121xxxxxxts 聯系在于，它們都是關于工廠生產經營的模型 ,并且使用相同的數據； 原模型和對偶模型既有聯系又有區(qū)別 區(qū)別在于 ,它們所反映的實質內容是完全不同的：前者是站在工廠 經營者 的立場上追求工廠的 銷售收入最大 ，而后者則是站在談判對手 的立場上尋求應付工廠 租金最少 的策略。 所謂 對偶規(guī)劃 ，就是與線性規(guī)劃原問題相對應并使用同一組數據按照特定方法形成的另一種反映不同性質問題的線性規(guī)劃模型。 原模型與對偶模型有很多的內在聯系和相似之處。如原問題如求目標函數最大化，對偶問題即求目標函數最小化；原問題目標函數的系數變成為對偶問題的右邊項，而原問題的約束的右邊項則變成為對偶問題目標函數的系數；對偶問題的系數矩陣是原問題系數矩陣的轉置。就象一個人對著鏡子會左右顛倒一樣，原問題與對偶問題之間存在著嚴格的對應關系。 原問題的一般模型可定義為： 二、對偶規(guī)劃的一般數學模型 n n x c x c x c Z ? ? ? ? ... max 2 2 1 1 . 1 1 2 12 1 11 ... b x a x a x a n n ? ? ? ? 2 2 2 22 1 21 ... b x a x a x a n n ? ? ? ? … … …. m n mn m m b x a x a x a ? ? ? ? ... 2 2 1 1 0 ,..., , 2 1 ? n x x x 相應的對偶問題的一般模型可定義為： m m y b y b y b S ? ? ? ? ... min 2 2 1 1 . 1 1 2 21 1 11 ... c y a y a y a m m ? ? ? ? 2 2 2 22 1 12 ... c y a y a y a m m ? ? ? ? … … … n m mn n n c y a y a y a ? ? ? ? ... 2 2 1 1 0 ,..., , 2 1 ? m y y y 上述的原問題 P和對偶問題 D還可以用矩陣形式寫為： (P) max Z= cx . Ax ≤b x ≥0 其中 ) ,.., , ( 2 1 m y y y y ? 上述的對偶模型都稱作為 對稱型對偶模型 。 而在當原問題轉化為標準型以后所建立的對偶模型則是 非對稱型的 ，如： (P) maxZ= cx . Ax =b x≥ 0 . yA y ≥ c ≥ 0 (D) min S= yb . yA≥c y為自由變量 (D) minS= yb 原問題與對偶問題的矩陣形式 問題：如何由原模型寫出對偶模型？其規(guī)律是什么 ? 三、原問題與對偶問題的對應關系 當我們討論對偶問題時必定是指一對問題，因為沒有原問題也就不可能有對偶問題。原問題和對偶問題總是相依存在的。同時，原問題和對偶問題之間也并沒有嚴格的界線，它們互為對偶，誰都可以是原問題，誰也都可以是對偶問題。 321 12168m i n yyyg ??????????????3,2,1,034y2y24yy.. 3121iytsi21 32 xxf ??m a x??????????0,12416482..212121xxxxxxts 下列的表給出了原問題模型和模型的對應關系，這些也可以看作是一個線性規(guī)劃原問題轉化為對偶問題的一般規(guī)律。 原問題線性規(guī)劃模型 對偶線性規(guī)劃模型 原問題為 maxZ的線性規(guī)劃問題對偶關