【正文】 22322121yyyy解此線性方程組得 y1=1,y2=1,從而對偶問題的最優(yōu)解為： Y＊ =(1,1)，最優(yōu)值 w=26。 j=1,2,…, n) 在一對變量中，其中一個大于 0，另一個一定等于 0 線性規(guī)劃的對偶理論 53 China University of Mining and Technology 運 籌 學(xué) 性質(zhì) 5的應(yīng)用： 該性質(zhì)給出了已知一個問題最優(yōu)解求另一個問題最優(yōu)解的方法，即已知 Y＊ 求 X＊ 或已知 X＊ 求 Y＊ ???????00ssXYXY 互補松弛條件 由于變量都非負(fù)，要使求和式等于零，則必定每一分量為零，因而有下列關(guān)系： 若 Y＊ ≠0，則 Xs必為 0；若 X＊ ≠0，則 Ys必為 0 利用上述關(guān)系，建立對偶問題（或原問題）的約束線性方程組，方程組的解即為最優(yōu)解。 在線性規(guī)劃問題的最優(yōu)解中，若對應(yīng)某一約束條件的對偶變量值為非零，則該約束條件取嚴(yán)格等式 ； 另一方面，如果約束條件取嚴(yán)格不等式，則其對應(yīng)的變量一定為零。可以從原問題（ P）的單純形終表獲得。 一對對偶問題的關(guān)系，有且僅有下列三種： 1. 都有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等； 2. 兩個都無可行解； 3. 一個問題無界，則另一問題無可行解。 0X 0Y線性規(guī)劃的對偶理論 45 China University of Mining and Technology 運 籌 學(xué) 性質(zhì) 4 強 (主 )對偶性： 若原問題及其對偶問題均具有可行解， 則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。故由推論 3知原問題無界。 10?? CXZ40?? bYWbYCX ?且由推論 1知，對偶問題目標(biāo)函數(shù) W的下界為 10，原問題目標(biāo)函數(shù) Z的上界為 40。 40 China University of Mining and Technology 運 籌 學(xué) 已知原問題 (LP)， )4,3,2,1(0 202 32 20322 ..432m ax432143214321???????????????????jxxxxxxxxxtsxxxxZj試估計它的目標(biāo)函數(shù)值的界 ,并驗證弱對偶定理 . 例 5 線性規(guī)劃的對偶理論 41 China University of Mining and Technology 運 籌 學(xué) 解： 問題 (LP)的對偶問題 (DP)為 121212121212m in 20 20 2 1 2 2. . 2 3 3 3 2 4 , 0W y yyyyys t y yyyyy??????????? ?????????(DP) )4,3,2,1(0 202 32 20322 ..432m a x432143214321???????????????????jxxxxxxxxxtsxxxxZj線性規(guī)劃的對偶理論 42 China University of Mining and Technology 運 籌 學(xué) 由觀察可知 )1,1(,)1,1,1,1( ?? YX T分別是原問題和對偶問題的可行解。 若（ P）為無界解，則（ D）無可行解； 若（ D）為無界解，則（ P）無可行解。 證明： (1) 當(dāng) X和 Y為原問題和對偶問題的一個可行解 有 bAX ? CYA ?YbY A X ? CXY A X ?YbY A XCX ??原問題目標(biāo)函數(shù)值 對偶問題目標(biāo)函數(shù)值 線性規(guī)劃的對偶理論 39 China University of Mining and Technology 運 籌 學(xué) 推論 2: 在一對對偶問題（ P）和（ D）中，若其中一個問題可行但目標(biāo)函數(shù)無界，則另一個問題無可行解； 反之不成立 。 29 China University of Mining and Technology 運 籌 學(xué) Max Z=40x1+ 50x2 x1+2x2 ? 30 3x1+2x2 ? 60 2x2 ? 24 x1 , x2 ?0 y1 y2 y3 Min W = 30y1+ 60y2 + 24y3 y1+3y2 + 0y3 ? 40 2y1+2y2 + 2y3 ? 50 y1 , y2 , y3 ?0 Max W′= 30y1 60y2 24y3 y1+3y2 + 0y3 – y4 = 40 2y1+2y2 + 2y3 – y5 = 50 y1 , y2 , y3 , y4 , y5 ?0 例 4 二、 對偶問題的解 線性規(guī)劃的對偶理論 30 China University of Mining and Technology 運 籌 學(xué) Max W′= 30y1 60y2 24y3 +0(y4 + y5 )M (y6 + y7 ) y1+3y2 + 0y3 – y4 + y6 = 40 2y1+2y2 + 2y3 – y5 + y7 = 50 y1 , y2 , y3 , y4 , y5 ?0 cj 30 60 24 0 0 M M B1b θ cB yB y1 y2 y3 y4 y5 y6 y7 M y6 1 3 0 1 0 1 0 40 40/3 M y7 2 2 2 0 1 0 1 50 50/2 σj 3M30 5M60 2M24 M M 0 0 90M 線性規(guī)劃的對偶理論 31 China University of Mining and Technology 運 籌 學(xué) cj 30 60 24 0 0 M M B1b θ cB yB y1 y2 y3 y4 y5 y6 y7 60 y2 1/3 1 0 1/3 0 1/3 0 40/3 M y7 4/3 0 2 2/3 1 2/3 1 70/3 35/3 σj 4M/310 0 2M24 2M/3+20 M 5M/3+20 0 80070M/3 60 y2 1/3 1 0 1/3 0 1/3 0 40/3 40 24 y3 2/3 0 1 1/3 1/2 1/3 1/2 35/3 35/2 σj 6 0 0 12 12 M+12 M+12 1080 60 y2 0 1 1/2 1/2 1/4 1/2 1/4 15/2 30 y1 1 0 3/2 1/2 3/4 1/2 3/4 35/2 σj 0 0 9 15 15/2 M+30 M15/2 975 Ts1B 21515BCX* ?????????? ? ?線性規(guī)劃的對偶理論 32 China University of Mining and Technology 運 籌 學(xué) cj 40 50 0 0 0 B1b cB xB x1 x2 x3 x4 x5 40 x1 1 0 1/2 1/2 0 15 0 x5 0 0 3/2 1/2 1 9 50 x2 0 1 3/4 1/4 0 15/2 σj 0 0 35/2 15/2 0 975 ?????????? ? 215235BCY* s1B ? Max Z=40x1+ 50x2 x1+2x2 ? 30 3x1+2x2 ? 60 2x2 ? 24 x1 , x2 ?0 x1+2x2 +x3 = 30 3x1+2x2 +x4 =60 2x2 +x5 = 24 x1 – x5 ?0 線性規(guī)劃的對偶理論 33 China University of Mining and Technology 運 籌 學(xué) 21515900000215235*Yyyyyyxxxxx90021515*X0215235005432154321?????線性規(guī)劃的對偶理論 34 China University of Mining and Technology 運 籌 學(xué) 原問題與其對偶問題的變量與解的對應(yīng)關(guān)系： 在單純形表中，原問題的松弛變量對應(yīng)對偶問題的變量，對偶問題的剩余變量對應(yīng)原問題的變量。 3. 會用互補松弛條件來考慮一對對偶問題的界。1 China University of Mining and Technology 運 籌 學(xué) Chapter2 對偶理論 ( Duality Theory ) 單純形法的矩陣描述 對偶問題的提出 線性規(guī)劃的對偶理論 對偶問題的經(jīng)濟解釋－影子價格 對偶單純形法 靈敏度分析 (選講 ) 掌握 WinQSB軟件求解對偶規(guī)劃 本章主要內(nèi)容： √ √ √ 2 China University of Mining and Technology 運 籌 學(xué) 學(xué)習(xí)要點： 1. 理解對偶理論，掌握描述一個線性規(guī)劃問題 的對偶問題。 2. 能夠運用對偶單純形法來求解線性規(guī)劃問題。 4. 了解影子價格、靈敏度分析以及用 WinQSB求 解對偶規(guī)劃問題。 線性規(guī)劃的對偶理論 35 China University of Mining and Technology 運 籌 學(xué) XB b 原問題的變量 原問題的松弛變量 x1 x2 x3 x4 x5 x1 15 1 0 1/2 1/2 0 x5 9 0 0 3/2 1/2 1 x2 15/2 0 1 3/4 1/4 0 0 0 35/2 15/2 0 j?YB b 對偶問題 的變量 對偶問題的 剩余變量 y1 y2 y3 y4 y5 y2 15/2 0 1 1/2 1/2 1/4 y1 35/2 1 0 3/2 1/2 3/4 0 0 9 15 15/2 j?原問題最優(yōu)表 對偶問題最優(yōu)表 Max Z=40x1+ 50x2 x1+2x2 ? 30 3x1+2x2 ? 60 2x2 ? 24 x1 , x2 ?0 Min W = 30y1+ 60y2 + 24y3 y1+