1、第二章 對偶理論與靈敏度分析2.1 對偶問題 凡是一個線性規劃都對應一個對偶線性規劃凡是一個線性規劃都對應一個對偶線性規劃2.2 對偶理論2.3 對偶單純形法 新的算法（大新的算法（大M，二階段），二階段）2.4 對偶問題的最優解2.5 靈敏度分析 對線性規劃參數動態分析對線性規劃參數動態分析2.6 影子價格2.1對偶問題 思路：（1）從應用出發引入對偶問題（2）介紹任意線性規劃對偶問題 【例】 某工廠在計劃期內要安排生產、兩種產品，已知生產單位產品所需的設備臺時及A、B兩種原材料的消耗和各種資源的限制量，如表所示。該工廠每生產一件產品可獲利2元，每生產一件產品可獲利3元，問應如何安排計劃使該

2、工廠獲利最多？資源限量設 備128臺時原材料A4016kg原材料B0412kg 對上例，假設該工廠的決策者決定不生產產品、，而將其所有資源出租或外售。這時工廠的決策者如何給每種資源定價？ 對比 例例2-12-1（營養問題）某養雞場所用的混合飼料由（營養問題）某養雞場所用的混合飼料由n n種天然飼料種天然飼料配合而成。要求在這批配合飼料中必須含有配合而成。要求在這批配合飼料中必須含有m m種不同的營養成種不同的營養成分，且第分，且第i i種營養成分的含量不低于種營養成分的含量不低于b bi i已知第已知第i i種營養成分種營養成分在每單位第在每單位第j j種天然飼料中的含量為種天然飼料中的含量為

3、a aijij. . 每單位第每單位第j j種天然飼種天然飼料的價格為料的價格為c cj j試問試問: :應如何對這應如何對這n n種飼料配方，使這批飼料種飼料配方，使這批飼料的費用最小的費用最小? ?（P）中第）中第i個約束條件，對應（個約束條件，對應（D）中第）中第i個變量；個變量；（P）中第）中第j個變量，對應（個變量，對應（D）中第）中第j個約束條件個約束條件記住矩陣表示對偶問題（對偶問題（D）的對偶問題即為原有問題（）的對偶問題即為原有問題（P），定理），定理2-1。思路：一般線性規劃均整理成（思路：一般線性規劃均整理成（P）或（）或（D）的形式，）的形式，然后求對偶規劃。然后求對偶

4、規劃。在對偶問題（在對偶問題（D）中，原有問題（）中，原有問題（P）中的等式約束對應）中的等式約束對應的變量的變量u1為自由變量；為自由變量；（P）中的自由變量）中的自由變量x2對應的約束條件為等式約束。對應的約束條件為等式約束。總結：任意一般線性規劃（總結：任意一般線性規劃（P）的對偶問題（）的對偶問題（D）定義）定義 書上書上59頁頁2-5，2-6（P）（D）以后不需要再將（以后不需要再將（P）中等式約束一拆為二，）中等式約束一拆為二，直接進行轉換！直接進行轉換！回顧書上本節內容。2.2 對偶理論 對標準型線性規劃及其對偶問題之間關系對標準型線性規劃及其對偶問題之間關系進行討論，結論對一般

5、形式的線型規劃進行討論，結論對一般形式的線型規劃（P）及其對偶問題及其對偶問題（D）同樣適用同樣適用。極大化問題可行解的目標函數極大化問題可行解的目標函數 不超過不超過極小化問題可行解的目標函數極小化問題可行解的目標函數 極大化問題可行解的目標函數極大化問題可行解的目標函數不超過不超過極小化問題可行解的目標函數極小化問題可行解的目標函數 （1）（3）書上書上64頁頁 作業： 92頁1，2，3（P）在可行域內無上界，則對偶問題不可行。其他教材中有交待，本教材這樣介紹的目的是為了給影子價格的講解作鋪墊。其他教材中有交待，本教材這樣介紹的目的是為了給影子價格的講解作鋪墊。 總結原有問題（P）和對偶問

6、題（D）之間的對應關系。 64頁表2-1。 Kp， KD ，f, z2.3對偶單純形法2.3對偶單純形法P67 對偶單純形法原理單純形法特點1.確定進基變量t (r0)2.確定出基變量k（最小比原則）3.f0不斷下降1.確定出基變量k ( 0)2.確定進基變量t（最大比原則）3.f0不斷上升（此時X不是可行解）(單純形因子是對偶問題可行解。)對偶單純形法特點B為原有可行基B為對偶可行基min0,1kiitktitbbyimyy max0,jtkjDktkjrryjIyyb 書上第67頁（2-13） 書上第68頁定理2-5 書上第68頁單純形法算法第一張表必須檢驗數非負第一張表必須檢驗數非負,

7、可正可負。可正可負。目標函數系數非負，為靈敏度分析和整數規劃問題子程序目標函數系數非負，為靈敏度分析和整數規劃問題子程序br=0 情況2.3對偶單純形法 對偶單純形法和大對偶單純形法和大M M法一樣都是求解極小化法一樣都是求解極小化LPLP的算法。與其算法名稱無關。的算法。與其算法名稱無關。 第一張表必須檢驗數非負。第一張表必須檢驗數非負。 用對偶單純形法求解的模型里用對偶單純形法求解的模型里沒有人工變沒有人工變量量，只有剩余變量和松弛變量。，只有剩余變量和松弛變量。2.4對偶問題的最優解 本節目的：在求本節目的：在求P的同時，的同時，給出給出D的最優解的最優解看書73頁，情況三 作業：93頁

8、7，82.5 靈敏度分析 目的：對線性規劃某些參數進行動態分析，為什么進行分析，怎么分析呢？目的：對線性規劃某些參數進行動態分析，為什么進行分析，怎么分析呢？jjcc 屬于72頁情況二（P）類型是個靜態問題是個靜態問題最優值的變化？最優值的變化？2.5.1參數Cs的靈敏度分析 無影響X1為非基本變量為非基本變量X2為基本變量為基本變量改變量變化范圍改變量變化范圍目標函數最優值有何變化？目標函數最優值有何變化？受到影響的是？受到影響的是？X2為基本變量為基本變量目標函數最優值有何變化？目標函數最優值有何變化？“靈敏度分析的一般公式靈敏度分析的一般公式 僅影響僅影響rs基本變量在第基本變量在第 i

9、 行行f0 和和 非基本變量的檢驗數非基本變量的檢驗數 均受到影響均受到影響如果三個均為正如果三個均為負2.5.2參數bs的靈敏度分析2.5.2參數bs的靈敏度分析 sssbbb 令 s sbbbe 在哪里？73頁2-18 B ：（A.2, A.3, A.6 ） B-1： （y4, y5, y6）請回答：最優解？最優值？請回答：最優解？最優值？ x2x3x6-4-30請回答：最優解？請回答：最優解？最優值？最優值？ -1000，用什么方法求解？，用什么方法求解？可見：對偶單純形法是靈敏度分析的子程序。可見：對偶單純形法是靈敏度分析的子程序。 作業：94頁9 （1）要求用公式法和推導法兩種辦法解題 （2）用第一種方法b1求b1請同學直接回答？請同學直接回答？最優值的變化？最優值的變化？Cs攝動bs攝動11sissi