線性規(guī)劃的對偶理論

1、線性規(guī)劃的對偶理論第二章內(nèi)容提要 對偶問題的提出 原問題與對偶問題 對偶問題的基本性質(zhì) 影子價格 對偶單純形法 靈敏度分析 參數(shù)線性規(guī)劃6/30/2022Haiyan Lu Jiangnan University2對偶問題的提出第1節(jié)對偶 對偶是指對同一事物（問題）從不同的角度（立場）出發(fā)，有兩種擬似對立的表述。 對于同一數(shù)據(jù)集(A, C, b)的線性規(guī)劃問題，可以有兩種優(yōu)化的表述。6/30/2022Haiyan Lu Jiangnan University4引例 第一章中例2（常山機器廠利用A、B、C三種設(shè)備生產(chǎn)I、II兩種產(chǎn)品，如何安排生產(chǎn)使利潤最大？）的線性規(guī)劃模型（LP1）為 假定有另

2、一四海機器廠，為擴大生產(chǎn)想租借常山機器廠擁有的設(shè)備資源，問：常山長分別以每小時什么樣的價格出租自己的設(shè)備才合算（合理）？6/30/2022Haiyan Lu Jiangnan University5引例6/30/2022Haiyan Lu Jiangnan University6原問題與對偶問題第2節(jié)原問題與對偶問題的規(guī)范形式（對稱形式）展開形式展開形式矩陣形式矩陣形式6/30/20228Haiyan Lu Jiangnan University原問題與對偶問題的規(guī)范形式原問題（原問題（max）右端項對偶問題（對偶問題（min）右端項6/30/2022Haiyan Lu Jiangnan Un

3、iversity9原問題與對偶問題的規(guī)范形式 例1 將引例中的LP2作為原問題，寫出其對偶問題。 解 6/30/2022Haiyan Lu Jiangnan University10寫出對偶問題轉(zhuǎn)化為規(guī)范形式把LP2作為原問題轉(zhuǎn)化為規(guī)范形式LP1與LP2互為對偶原問題與對偶問題的非規(guī)范形式（非對稱形式） 對于非規(guī)范形式（如原問題的約束條件中含等式約束），如何處理？6/30/2022Haiyan Lu Jiangnan University11miyynjxmibxamibxaxcznjxmibxaxcziijnjijijnjijijnjjjjnjijijnjjj, 2 , 1(*)(*), 2

4、 , 1, 0(*), 2 , 1,(*), 2 , 1,max, 2 , 1, 0, 2 , 1,max11111式的對偶變量，對應(yīng)于式的對偶變量，是對應(yīng)于設(shè)是得解為兩個不等式約束，第一步：將等式約束分設(shè)線性規(guī)劃問題原問題與對偶問題的非規(guī)范形式 對于非規(guī)范形式（如原問題的約束條件中含等式約束），如何處理？6/30/2022Haiyan Lu Jiangnan University12miynjcyaybyyyyyyymiyynjcyayaybybimijiijmiiiiiiiiiiiijmimiiijiijmimiiiii, 2 , 1, 2 , 1,min, 0, 2 , 1, 0, 2

5、, 1,)()(min111111為無約束，對偶問題理得到代入上述規(guī)劃問題并整不受約束，將可知由于令變換關(guān)系寫出對偶問題第二步：按對稱形式的原問題與對偶問題6/30/2022Haiyan Lu Jiangnan University13約束條件右端項目標函數(shù)變量的系數(shù)目標函數(shù)變量的系數(shù)約束條件右端項無約束件量條變束個個約件無約束條量束變約個個目標函數(shù)目標函數(shù)對偶問題（或原問題）原問題（或?qū)ε紗栴}）0000minmaxmmnnz原問題與對偶問題 例2 寫出下述線性規(guī)劃的對偶問題 解 方法一：將原問題化為規(guī)范形式，然后逐步求解（留作練習）；6/30/2022Haiyan Lu Jiangnan U

6、niversity14原問題與對偶問題 例2的解 方法二：按照原問題與對偶問題的對應(yīng)關(guān)系表直接寫出對偶問題：6/30/2022Haiyan Lu Jiangnan University15原問題（對偶問題）對偶問題（原問題）原問題與對偶問題 課堂練習6/30/2022Haiyan Lu Jiangnan University16無約束對偶問題為應(yīng)關(guān)系，可得原問題與對偶問題的對則按照上表中件的對偶變量分別為解：設(shè)對應(yīng)三個約束條無約束規(guī)劃原問題的對偶問題舉例說明：求下述線性3213213213121321321432143243143214321, 0, 01523322645max,; 0,;

7、0642253532minyyyyyyyyyyyyyyyyyyyxxxxxxxxxxxxxxxxxxz作業(yè) 習題二（P89） 2.1（a）6/30/2022Haiyan Lu Jiangnan University17線性規(guī)劃的對偶理論第3節(jié)對偶問題的基本性質(zhì)基于對偶的規(guī)范形式，給出對偶的下述基本性質(zhì)： 對稱性 弱對偶性 最優(yōu)性 強對偶性 無界性 對偶基本定理 互補松弛性 解的對應(yīng)關(guān)系6/30/2022Haiyan Lu Jiangnan University19對偶問題的基本性質(zhì)6/30/2022Haiyan Lu Jiangnan University20對偶問題的基本性質(zhì)6/30/202

8、2Haiyan Lu Jiangnan University21對偶問題的基本性質(zhì)6/30/2022Haiyan Lu Jiangnan University22對偶問題的基本性質(zhì)6/30/2022Haiyan Lu Jiangnan University23對偶問題的基本性質(zhì) 無界無界性性 在原問題及其對偶問題中，若其中一個問題為無界解，則另一個問題無可行解。（反之不然）證明：由弱對偶性易證。注：這個命題的逆命題不成立。實際上，當一對對偶問題中的一個問題無可行解時，另一個問題可能具有無界解，也可能無可行解。如下面的反例，這一對對偶問題均無可行解：6/30/2022Haiyan Lu Jian

9、gnan University24對偶問題的基本性質(zhì)6/30/2022Haiyan Lu Jiangnan University25對偶問題的基本性質(zhì) 對偶基本定理對偶基本定理 From the fundamental theorem of duality we see that duality is not completely symmetric. The best we can see is that: (Here OPTIMAL means having a finite optimum, and UNBOUNDED means having an unbounded optimal

10、objective value.)6/30/2022Haiyan Lu Jiangnan University26POPTIMALDOPTIMALP(D)UNBOUNDEDP(D)INFEASIBLEP(D)INFEASIBLEP(D)UNBOUNDED OR INFEASIBLE對偶問題的基本性質(zhì)6/30/2022Haiyan Lu Jiangnan University27對偶問題的基本性質(zhì)6/30/2022Haiyan Lu Jiangnan University28原問題檢驗數(shù)對偶問題對偶問題的基本性質(zhì)6/30/2022Haiyan Lu Jiangnan University29對偶

11、問題的基本性質(zhì)6/30/2022Haiyan Lu Jiangnan University30對偶問題的基本性質(zhì)6/30/2022Haiyan Lu Jiangnan University31對偶理論的應(yīng)用6/30/2022Haiyan Lu Jiangnan University32對偶理論的應(yīng)用6/30/2022Haiyan Lu Jiangnan University33影子價格第4節(jié)影子價格(Shadow Price)6/30/2022Haiyan Lu Jiangnan University35影子價格 舉例說明舉例說明本章的引例，即第一章中例2（常山機器廠利用A、B、C三種設(shè)備生產(chǎn)

12、I、II兩種產(chǎn)品，如何安排生產(chǎn)使利潤最大？）的線性規(guī)劃模型（LP1）為其對偶問題的模型（LP2）為可以用圖解法（見教材P73）直觀地分析影子價格，也可以借助單純形表來進行分析。6/30/2022Haiyan Lu Jiangnan University36影子價格6/30/2022Haiyan Lu Jiangnan University37230002310004001130100000作業(yè) 習題二 2.7(a)6/30/2022Haiyan Lu Jiangnan University38對偶單純形法第5節(jié)對偶單純形法 理論基礎(chǔ) 由對偶理論可知，用單純形法求解線性規(guī)劃問題時，在單純形表的b

13、列得到原問題的一個基可行解的同時，在檢驗數(shù)行得到對偶問題的一個基解，且兩者的目標函數(shù)值相等。 算法思想 單純形法的基本思想 在保持原問題(max)為基可行解（這時一般其對偶問題為非可行解）的基礎(chǔ)上，通過迭代，增大目標函數(shù)值，當其對偶問題的基解也為可行解時，則原問題和對偶問題均得到了最優(yōu)解。 對偶單純形法的基本思想 在（原問題）單純形表上直接求解對偶問題。 在保持對偶問題(min)為基可行解（這時一般原問題為非可行解）的基礎(chǔ)上，通過迭代，減小目標函數(shù)值，當原問題的基解也為可行解時，則對偶問題和原問題均得到了最優(yōu)解。6/30/2022Haiyan Lu Jiangnan University40對

14、偶單純形法6/30/2022Haiyan Lu Jiangnan University41對偶單純形法的計算步驟6/30/2022Haiyan Lu Jiangnan University42）。）到（重復(fù)步驟（到新的計算表。法在表中進行迭代，得為主元素，按原單純形）以（保持對偶可行）為換入變量（這樣才能確定非基變量計算若存在無可行解，停止計算。則若所有所在行的各系數(shù)在單純形表中檢驗）確定換入變量（為換出變量。對應(yīng)的基變量）確定換出變量（以下計算。數(shù)行保持非正，則進行還有一個負分量，檢驗列的數(shù)字至少計算。若則已得到最優(yōu)解，停止檢驗數(shù)行都為非正列的數(shù)字都為非負列出初始單純形表。若）根據(jù)線性規(guī)劃問

15、題，（4140min, 0, 0)., 1(3)(0)()(min2,1111lkklkkkljljjjjljljljllliiaxazcaazcaanjaxxbBbBbBbb對偶單純形法6/30/2022Haiyan Lu Jiangnan University43對偶單純形法6/30/2022Haiyan Lu Jiangnan University44對偶單純形法的優(yōu)缺點6/30/2022Haiyan Lu Jiangnan University45 優(yōu)點 初始基解可以是非可行解，當檢驗數(shù)都為非正時（對偶可行），就可進行基的變換，而不需添加人工變量，因此可以簡化計算。 對變量較少，而約束

16、條件很多的線性規(guī)劃問題，可先將其變換為對偶問題，這樣使得變量多，而約束條件很少，這時用對偶單純形法求解就會減少計算工作量。 在靈敏度分析及求解整數(shù)規(guī)劃的割平面法中，有時需要對偶單純形法，可以問題的處理得到簡化。 缺點 對于大多數(shù)線性規(guī)劃問題，很難找到原問題的一個對偶可行的初始基，因此這種方法在求解線性規(guī)劃問題時很少單獨使用。靈敏度分析第6節(jié)靈敏度分析（Sensitivity Analysis）6/30/2022Haiyan Lu Jiangnan University47靈敏度分析（Sensitivity Analysis）6/30/2022Haiyan Lu Jiangnan Univers

17、ity48靈敏度分析 步驟 將參數(shù)的改變經(jīng)計算反映到最終單純形表上； 檢查原問題是否為可行解； 檢查對偶問題是否為可行解； 按下表所列情況得出結(jié)論和決定繼續(xù)計算的步驟。 6/30/2022Haiyan Lu Jiangnan University49原問題原問題對偶問題對偶問題結(jié)論或繼續(xù)計算的步驟結(jié)論或繼續(xù)計算的步驟可行解可行解仍為問題最優(yōu)解可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進人工變量，編制新的單純形表重新計算6/30/2022Haiyan Lu Jiangnan University506/30/2022Haiyan Lu

18、Jiangnan University512300023100040013301000006/30/2022Haiyan Lu Jiangnan University5230003100040013301000006/30/2022Haiyan Lu Jiangnan University53000310004001301000006/30/2022Haiyan Lu Jiangnan University546/30/2022Haiyan Lu Jiangnan University552300023100040013301000006/30/2022Haiyan Lu Jiangnan U

19、niversity566/30/2022Haiyan Lu Jiangnan University576/30/2022Haiyan Lu Jiangnan University582132maxxxz0,12416482212121xxxxxx6/30/2022Haiyan Lu Jiangnan University5923000241000.2500400-20.5132010.5-0.125000-1.5-0.12506/30/2022Haiyan Lu Jiangnan University6043000241.25000.250040.50-20.51320.37510.5-0.1

20、2500.3750-1.5-0.12506/30/2022Haiyan Lu Jiangnan University614300023.21000.2002.400-20.4130.8010.5-0.2000-1.5-0.20增加一個變量的分析6/30/2022Haiyan Lu Jiangnan University62230002310004001330100000增加一個變量的分析6/30/2022Haiyan Lu Jiangnan University6323000423100004001433010010001增加一個變量的分析6/30/2022Haiyan Lu Jiangnan University6423000423100