對偶理論講義精品課件

1、對偶理論講義第1頁，共69頁，2022年，5月20日，1點58分，星期三 對偶性是線性規(guī)劃問題的最重要的內(nèi)容之一。每一個線性規(guī)劃（ LP ）必然有與之相伴而生的另一個線性規(guī)劃問題，即任何一個求 maxZ 的LP都有一個求 minZ 的LP。其中的一個問題叫“原問題”，記為“P”，另一個稱為“對偶問題”，記為“D”。 例一、資源的合理利用問題 已知資料如表所示，問應(yīng)如何安排生產(chǎn)計劃使得既能充分利用現(xiàn)有資源有使總利潤最大？1810單件利潤150（設(shè)備）51C100（煤炭）32B170（鋼材）25A資源限制乙甲單件 產(chǎn) 消耗 品資源一、問 題 的 提 出第2頁，共69頁，2022年，5月20日，1點

2、58分，星期三 下面從另一個角度來討論這個問題： 假定：該廠的決策者不是考慮自己生產(chǎn)甲、乙兩種產(chǎn)品，而是將廠里的現(xiàn)有資源用于接受外來加工任務(wù)，只收取加工費。試問該決策者應(yīng)制定怎樣的收費標準（合理的）？第3頁，共69頁，2022年，5月20日，1點58分，星期三 分析問題： 1、每種資源收回的費用不能低于自己生產(chǎn)時的可獲利潤； 2、定價又不能太高，要使對方能夠接受。第4頁，共69頁，2022年，5月20日，1點58分，星期三 一般而言，W 越大越好，但因需雙方滿意，故為最好。該問題的數(shù)學模型為：第5頁，共69頁，2022年，5月20日，1點58分，星期三模型對比：第6頁，共69頁，2022年，5

3、月20日，1點58分，星期三 例二、合理配料問題，其數(shù)學模型為： 假設(shè)工廠想把這m 種營養(yǎng)成分分別制成一種營養(yǎng)丸銷售，問如何定價（以保證總收入為最多）？第7頁，共69頁，2022年，5月20日，1點58分，星期三原問題對偶問題目標函數(shù)maxmin約束條件變量數(shù)量約束條件個數(shù)約束條件個數(shù)變量數(shù)量第8頁，共69頁，2022年，5月20日，1點58分，星期三例三、23x1 x2 原問題12y1 22128y2 12816y3401612y40412對偶問題23第9頁，共69頁，2022年，5月20日，1點58分，星期三1、對稱型對偶問題：已知 P，寫出 D。二、線性規(guī)劃的對偶理論（一）、對偶問題的形

4、式第10頁，共69頁，2022年，5月20日，1點58分，星期三 例一、寫出線性規(guī)劃問題的對偶問題解：首先將原式變形第11頁，共69頁，2022年，5月20日，1點58分，星期三 注意：以后不強調(diào)等式右段項 b0，原因在對偶單純型表中只保證 而不保證 ，故 b可以是負數(shù)。第12頁，共69頁，2022年，5月20日，1點58分，星期三2、非對稱型對偶問題第13頁，共69頁，2022年，5月20日，1點58分，星期三例二、原問題第14頁，共69頁，2022年，5月20日，1點58分，星期三2、混合型對偶問題第15頁，共69頁，2022年，5月20日，1點58分，星期三例三、原問題第16頁，共69頁

5、，2022年，5月20日，1點58分，星期三對偶問題第17頁，共69頁，2022年，5月20日，1點58分，星期三綜上所述，其變換形式歸納如下：原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標函數(shù) max目標函數(shù) min約束條件m個m個變量00=無約束變量n個n個約束條件00無約束=約束條件右端項目標函數(shù)變量的系數(shù)目標函數(shù)變量的系數(shù)約束條件右端項第18頁，共69頁，2022年，5月20日，1點58分，星期三例四、線性規(guī)劃問題如下：第19頁，共69頁，2022年，5月20日，1點58分，星期三第20頁，共69頁，2022年，5月20日，1點58分，星期三練習：第21頁，共69頁，2022年，5月20

6、日，1點58分，星期三第22頁，共69頁，2022年，5月20日，1點58分，星期三min Z= - CXs.t. - AX- bX 01、對稱性定理：對偶問題的對偶是原問題。 min W= Y bs.t. YA C Y 0max Z=C Xs.t. AXb X 0對偶的定義對偶的定義max W = -Ybs.t. YA C Y 0（二）、對偶問題的性質(zhì)第23頁，共69頁，2022年，5月20日，1點58分，星期三2、弱對偶原理（弱對偶性）：設(shè) 和 分別是問題（P）和（D）的可行解，則必有 推論.若 和 分別是問題（P）和（D）的可行解，則 是（D）的目標函數(shù)最小值的一個下界； 是（P）的目標

7、函數(shù)最大值的一個上界。第24頁，共69頁，2022年，5月20日，1點58分，星期三 推論.在一對對偶問題（P）和（D）中，若其中一個問題可行但目標函數(shù)無界，則另一個問題不可行；反之不成立。這也是對偶問題的無界性。關(guān)于無界性有如下結(jié)論：問題無界無可行解無可行解問題無界對偶問題原問題無界如：（原）無可行解（對）第25頁，共69頁，2022年，5月20日，1點58分，星期三 推論.在一對對偶問題（P）和（D）中，若一個可行（如P），而另一個不可行，（如D），則該可行的問題無界。例一、試估計它們目標函數(shù)的界，并驗證弱對偶性原理。（P）第26頁，共69頁，2022年，5月20日，1點58分，星期三解：

8、（D） 由觀察可知： =（1.1.1.1）， =（1.1），分別是（P）和（D）的可行解。Z=10 ，W=40，故有 ，弱對偶定理成立。由推論可知，W 的最小值不能小于10，Z 的最大值不能超過40。第27頁，共69頁，2022年，5月20日，1點58分，星期三例二、已知試用對偶理論證明原問題無界。 解： =（0.0.0）是 P 的一個可行解，而 D 的第一個約束條件不能成立（因為y1 , y2 0)。因此，對偶問題不可行，由推論可知，原問題無界。第28頁，共69頁，2022年，5月20日，1點58分，星期三例3、已知顯然，這兩個問題都無可行解。第29頁，共69頁，2022年，5月20日，1點

9、58分，星期三 3、最優(yōu)性判別定理： 若 X* 和 Y* 分別是 P 和 D 的可行解且 CX* = Y* b，則X*. Y*分別是問題 P和D 的最優(yōu)解。 例如，在例1中，可找到 X*=（）， Y*=（1.2，0.2）,則Z=28，W=28.故X* .Y*分別是 P和D 的最優(yōu)解。第30頁，共69頁，2022年，5月20日，1點58分，星期三 4、對偶定理（強對偶性）： 若一對對偶問題 P 和 D 都有可行解，則它們都有最優(yōu)解，且目標函數(shù)的最優(yōu)值必相等。 推論.若 P 和 D 的任意一個有最優(yōu)解，則另一個也有最優(yōu)解，且目標函數(shù)的最優(yōu)值相等。 綜上所述，一對對偶問題的關(guān)系，只能有下面三種情況之

10、一出現(xiàn)：.都有最優(yōu)解，分別設(shè)為X* 和 Y*，則必有CX* =Y*b；. 一個問題無界，則另一個問題無可行解；.兩個都無可行解。第31頁，共69頁，2022年，5月20日，1點58分，星期三 5、互補松弛定理： 設(shè)X*和Y*分別是問題 P 和 D 的可行解，則它們分別是最優(yōu)解的充要條件是同時成立 一般而言，我們把某一可行點（如X*和Y* ）處的嚴格不等式約束（包括對變量的非負約束）稱為松約束，而把嚴格等式約束稱為緊約束。所以有如下推論： 設(shè)一對對偶問題都有可行解，若原問題的某一約束是某個最優(yōu)解的松約束，則它的對偶約束一定是其對偶問題最優(yōu)解的緊約束。第32頁，共69頁，2022年，5月20日，1

11、點58分，星期三例4、已知試通過求對偶問題的最優(yōu)解來求解原問題的最優(yōu)解。解：對偶問題為第33頁，共69頁，2022年，5月20日，1點58分，星期三用圖解法求出： Y*=（1 . 3）， W=11。將y*1=1， y*2=3 代入對偶約束條件，（1）（2）（5）式為緊約束，（3）（4）為松約束。令原問題的最優(yōu)解為X* = （x1.x2.x3.x4.x5），則根據(jù)互補松弛條件，必有x3 = x4 =0(1 . 3)（1）（2）（3）（4）（5）第34頁，共69頁，2022年，5月20日，1點58分，星期三 又由于y*10， y*2 0，原問題的約束必為等式，即化簡為此方程組為無窮多解 令x5 =

12、0,得到x1=1，x2=2 即X*1 =（）為原問題的一個最優(yōu)解，Z=11。 再令 x5 =2/3，得到x1=5/3，x2=0 即X*2 （）也是原問題的一個最優(yōu)解，Z=11。第35頁，共69頁，2022年，5月20日，1點58分，星期三例5、已知原問題的最優(yōu)解為X* =（），Z=12 試求對偶問題的最優(yōu)解。解：（1）（2）（3）第36頁，共69頁，2022年，5月20日，1點58分，星期三將X* =（0 . 0 . 4）代入原問題中，有下式：所以，根據(jù)互補松弛條件，必有y*1= y*2=0，代入對偶問題 （3）式， y3 =3。因此，對偶問題的最優(yōu)解為 Y*=（0 . 0 . 3），W=12

13、。第37頁，共69頁，2022年，5月20日，1點58分，星期三6、對偶問題的解利用原問題的最優(yōu)單純形表和改進單純形表求解對偶問題的最優(yōu)解。.設(shè)原問題為： maxZ=CX AX b X0引入xs ，構(gòu)建初始基變量，然后，用單純形法求解。當檢驗數(shù)滿足j0 ，則求得最優(yōu)解。此時， xs對應(yīng)的js 為- Y* ，故求對偶Y* ，只要將最優(yōu)單純形表上xs 對應(yīng)的檢驗數(shù)反號即可。CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCB B-1b0CNCB B-1NCB B-1第38頁，共69頁，2022年，5月20日，1點58分，星期三例一、第39頁，共69頁，2022年，5月20日，1

14、點58分，星期三cj1018000cBxBbx1x2x3x4x50 x317052100170/20 x410023010100/30 x515015001150/5-Z01018000cj1018000cBxBbx1x2x3x4x50 x3540/7001-23/711/710 x150/71005/7-3/718x2200/7010-1/72/7-Z-4100/7000-32/7-6/7初始表最終表第40頁，共69頁，2022年，5月20日，1點58分，星期三 由上表可知： X*=（50/7 . 200/7），Z=4100/7對偶問題的最優(yōu)解： Y*=（0 . 32/7 . 6/7），W=

15、4100/7也就是外加工時的收費標準。.設(shè)原問題： maxZ=CX AX=b X0此時，矩陣A中沒有現(xiàn)成的矩陣I，必須通過加入人工變量來湊一個單位矩陣，再用大M法或兩階段法求解。 如何求Y* ，經(jīng)分析得出如下結(jié)論： B =0 最優(yōu)基變量檢驗數(shù)向量 I =CI CB B-1 初始基變量檢驗數(shù)向量 D = CD CB B-1D 非基變量檢驗數(shù)向量 所以， Y* = CI I 第41頁，共69頁，2022年，5月20日，1點58分，星期三例二、第42頁，共69頁，2022年，5月20日，1點58分，星期三cj3-1-100-M-McBxBbx1x2x3x4x5x6x73x141001/3-2/32/

16、3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3-Z-2000-1/3-1/31/3-M2/3- Mcj-31100MMcBxBbx1x2x3x4x5x6x70 x4111-21100011Mx63-4120-1103/2Mx71-20100011-Z-3+6M1-M1-3M0M00第43頁，共69頁，2022年，5月20日，1點58分，星期三 所以， X*=（4 . 1 . 9），Z = 2 y*1= (0 4 )=1/3 y*2=(M 6 )= M(1/3M)=1/3 y*3 =(M 7 )= M(2/3 M)=2/3 Y*=（1/3 . 1/3 . 2/

17、3） W = 2 初始基變量的檢驗數(shù)4 =1/3，6 =1/3M, 7 =2/3M第44頁，共69頁，2022年，5月20日，1點58分，星期三 定義：在一對 P 和 D 中，若 P 的某個約束條件的右端項常數(shù)bi 增加一個單位時，所引起的目標函數(shù)最優(yōu)值Z* 的改變量y*i 稱為第 i 個約束條件的影子價格，又稱為邊際價格。 三、對偶問題的經(jīng)濟解釋影子價格第45頁，共69頁，2022年，5月20日，1點58分，星期三 設(shè)：B是問題 P的最優(yōu)基，由前式可知， Z*=CB B-1b = Y*b =y*1b1+ y*2b2+y*Ibi+y*mbm 當bi 變?yōu)閎i+1 時（其余右端項不變，也不影響B(tài)

18、），CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCB B-1b0CNCB B-1NCB B-1第46頁，共69頁，2022年，5月20日，1點58分，星期三 目標函數(shù)最優(yōu)值變?yōu)椋?Z*= y*1b1+ y*2b2+y*I （ bi+1 ）+y*mbm Z*= Z* Z* = y*i 也可以寫成：即y*i 表示Z*對 bi的變化率。 其經(jīng)濟意義是：在其它條件不變的情況下，單位資源變化所引起的目標函數(shù)的最優(yōu)值的變化。即對偶變量yi 就是第 i 個約束條件的影子價格。 也可以理解為目標函數(shù)最優(yōu)值對資源的一階偏導數(shù)（但問題中所有其它數(shù)據(jù)都保持不變）。第47頁，共69頁，2022

19、年，5月20日，1點58分，星期三 若第i 種資源的單位市場價格為mi ，當yi mi 時，企業(yè)愿意購進這種資源，單位純利為yimi ，則有利可圖；如果yi mi ，則企業(yè)有償轉(zhuǎn)讓這種資源，可獲單位純利miyi ，否則，企業(yè)無利可圖，甚至虧損。第48頁，共69頁，2022年，5月20日，1點58分，星期三010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123( 50/7. 200/7 )第49頁，共69頁，2022年，5月20日，1點58分，星期三多了 32/7010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123( 50/7

20、. 200/7 )x1010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 123( 55/7. 199/7 )第50頁，共69頁，2022年，5月20日，1點58分，星期三010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123( 47/7. 202/7 )多了 6/7第51頁，共69頁，2022年，5月20日，1點58分，星期三01 2 3 4 5 6 7 8 1 2 3 4 5 6 x2 x1(4 2) X*=（4 . 2 . 0 . 0. 0 . 4）Y*=（0 . 3/2 . 1/8 . 0）第52頁，共69頁，2022年，5月

21、20日，1點58分，星期三01 2 3 4 5 6 7 8 1 2 3 4 5 6 x2 x1(3 3)少了0.5第53頁，共69頁，2022年，5月20日，1點58分，星期三01 2 3 4 5 6 7 8 1 2 3 4 5 6 x2 x1(4.25 1.75)少了0.25第54頁，共69頁，2022年，5月20日，1點58分，星期三01 2 3 4 5 6 7 8 1 2 3 4 5 6 x2 x1(4 2)第55頁，共69頁，2022年，5月20日，1點58分，星期三 對偶單純形法是求解線性規(guī)劃的另一的基本方法。它是根據(jù)對偶原理和單純形法的原理而設(shè)計出來的，因此稱為對偶單純形法。不要簡

22、單理解為是求解對偶問題的單純形法。 由對偶理論可以知道，對于一個線性規(guī)劃問題，我們能夠通過求解它的對偶問題來找到它的最優(yōu)解。四、對 偶 單 純 形 法第56頁，共69頁，2022年，5月20日，1點58分，星期三 也就是說，求解原問題（P）時，可以從（P）的一個基本解（非基可行解）開始，逐步迭代，使目標函數(shù)值（Z=Y b= CB B-1b =CX）減少，當?shù)絏B=B-1b0時，即找到了（P）的最優(yōu)解，這就是對偶單純形法。 同原始單純形求法一樣，求解對偶問題（D），也可以從（D）的一個基本可行解開始，從一個基本可行解（迭代）到另一個基本可行解，使目標函數(shù)值減少。第57頁，共69頁，2022年

23、，5月20日，1點58分，星期三例一、用對偶單純形法求解：解：將模型轉(zhuǎn)化為第58頁，共69頁，2022年，5月20日，1點58分，星期三cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-10-2-2-11000 x5-12-2-3-10100 x6-14-1-1-5001(-9/-1.-12/-1. -15/-5)-Z 0-9-12-15000cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-36/5-9/5-9/5010-1/50 x5-46/5-9/5-14/5001-1/5-15x314/51/51/5100-1/5(-30/-9.-45/-14

24、.-15/-1)-Z 42-6-9000-3第59頁，共69頁，2022年，5月20日，1點58分，星期三cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14(-3/-9.-45/-9. -33/-1)-15x315/71/140101/14-3/14-Z 501/7-3/14000-45/14-33/14cj-9-12-15000cBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9-Z 72000-1/3-3

25、-7/3第60頁，共69頁，2022年，5月20日，1點58分，星期三 所以， X*=（2 . 2 . 2 . 0 . 0 . 0）， Z* =72， 原問題 Z* =72 其對偶問題的最優(yōu)解為： Y*= (1/3 . 3 . 7/3)，W*= 72第61頁，共69頁，2022年，5月20日，1點58分，星期三練習：第62頁，共69頁，2022年，5月20日，1點58分，星期三cj-2-3-400cBxBbx1x2x3x4x50 x4-3-1-2-1100 x5-4-21-301-Z -2-3-400cj-2-3-400cBxBbx1x2x3x4x50 x4-10-5/21/21-1/2-2x121-1/23/20-1/2-Z 0-4-10-1第63頁，共69頁，2022年，5月20日