運籌學(第四版)清華大學出版社《運籌學》教材編寫組-第3章

1、2021/3/10 清華大學出版社 1 二 線性規(guī)劃與目標規(guī)劃 n第第1 1章章 線性規(guī)劃與單純形法線性規(guī)劃與單純形法 n第2章 對偶理論與靈敏度分析 n第3章 運輸問題 n第4章 目標規(guī)劃 2021/3/10 清華大學出版社 2 第3章 對偶理論和靈敏度分析 n第1節(jié) 單純形法的矩陣描述 n第2節(jié) 改進單純形法 n第3節(jié) 對偶問題的提出 n第4節(jié) 線性規(guī)劃的對偶理論 n第5節(jié) 對偶問題的經(jīng)濟解釋影子價格 n第6節(jié) 對偶單純形法 n第7節(jié) 靈敏度分析 n第8節(jié)* 參數(shù)線性規(guī)劃 2021/3/10 清華大學出版社清華大學出版社 3 第1節(jié) 單純形法的矩陣描述 設線性規(guī)劃問題可以用如下矩陣形式表示

2、： 目標函數(shù) max z=CX 約束條件 AXb 非負條件 X0 2021/3/10 清華大學出版社清華大學出版社 4 第1節(jié) 單純形法的矩陣描述 將該線性規(guī)劃問題的約束條件加入松弛變量后，得到標 準型： max z=CX+0Xs AX+IXs=b X，X s0 其中I 是mm單位矩陣。 2021/3/10 清華大學出版社清華大學出版社 5 第1節(jié) 單純形法的矩陣描述 若以Xs為基變量，并標記成XB，可將系數(shù)矩陣（A，I） 分為（B，N）兩塊。B是基變量的系數(shù)矩陣，N是非基 變量的系數(shù)矩陣。并同時將決策變量也分為兩部分： 相應地可將目標函數(shù)系數(shù)C分為兩部分：CB和CN，分別 對應于基變量XB和

3、非基變量XN，并且記作 C=（CB, CN） N B X X X 2021/3/10 清華大學出版社清華大學出版社 6 第1節(jié) 單純形法的矩陣描述 若經(jīng)過迭代運算后，可表示為： 相應有 ; X X X X X X S N N S B B 2 1 1 1 非基變量： 變量可包含原基變量和松弛 基變量 非基變量 基變量 松弛變量： 其中系數(shù)矩陣 2 1 2 1 S S S X X X ; S N N; N B A 2021/3/10 清華大學出版社清華大學出版社 7 第1節(jié) 單純形法的矩陣描述 線性規(guī)劃問題可表示為： )(X, )(b XSXNBXNX )(XCXCXC XCX N SNBN SS

4、NNBB NNB 230X 22 BX 12 Czmax B 21B B 21 2211 非負條件 約束條件 目標函數(shù) 2021/3/10 清華大學出版社清華大學出版社 8 第1節(jié) 單純形法的矩陣描述 將（2-2）式移項及整理后得到： SBS NBNB sNB SNB X)IBCC( X)NBCC(bBCz ;XSBXNBbBX ;XSXNbBX 1 1 11 2 1 1 11 21 2 11 21 21 目標函數(shù)： 2021/3/10 清華大學出版社清華大學出版社 9 第1節(jié) 單純形法的矩陣描述 令非基變量=0，由上式得到： bB ; bB X )( 1 B 1 1 Cz 0 目標函數(shù)的值

5、基可行解 2021/3/10 清華大學出版社清華大學出版社 10 第1節(jié) 單純形法的矩陣描述 （1）非基變量的系數(shù)表示為： 1 B 1 B j 1 1 C-C-C 21c 1 BAB )n,j(z )NBCC( j BN 與 檢驗數(shù)也可表示為： 對應已用的檢驗數(shù)符號 2021/3/10 清華大學出版社清華大學出版社 11 第1節(jié) 單純形法的矩陣描述 （2）規(guī)則表示為： RHS值 表示選用0的分量 換入變量的系數(shù)向量 ij i ij ij i )PB( )bB( )PB( )PB( )bB( min 1 1 1 1 1 0 2021/3/10 清華大學出版社清華大學出版社 12 第1節(jié) 單純形法

6、的矩陣描述 （3）單純形表與矩陣表示的關(guān)系 )( bBC bB X X X z BCNBCC BNB B N N B BBN 72 01 10 1 1 1 1 1 1 1 1 2 1 2021/3/10 清華大學出版社清華大學出版社 13 第1節(jié) 單純形法的矩陣描述 單純形表中的數(shù)據(jù) 基變量 非基變量等式右邊 系數(shù)矩陣 檢驗數(shù) 0 1 1 BB XB bBCBCNBCC bBBNB RHSXX BBBN sN 11 1 1 11 1 1 1 2021/3/10 清華大學出版社清華大學出版社 14 小結(jié) 1）掌握矩陣的運算； 2）理解基矩陣的作用； 3）了解矩陣運算與單純表的關(guān)系。 2021/3

7、/10 清華大學出版社清華大學出版社 15 第2節(jié) 改進單純形法 求解線性規(guī)劃問題的關(guān)鍵是計算B-1 ，以下介紹一 種比較簡便的計算B-1的方法。 2021/3/10 清華大學出版社清華大學出版社 16 第2節(jié) 改進單純形法 設mn系數(shù)矩陣為A，求其逆矩陣時，可先從第1列開始。 mmmm m m aaa aaa aaa A 21 22221 11211 2021/3/10 清華大學出版社清華大學出版社 17 第2節(jié) 改進單純形法 以a11為主元素, 進行變換 )( a/a a/a a/ a a a P mm 1 1 111 1121 11 1 1 12 11 1 主元素 2021/3/10 清

8、華大學出版社清華大學出版社 18 第2節(jié) 改進單純形法 然后構(gòu)造構(gòu)造含有（1）列，而其他列都是單位列的矩陣 1/ 1/ 00/1 111 1121 11 1 aa aa a E m 2021/3/10 清華大學出版社清華大學出版社 19 第2節(jié) 改進單純形法 可得到 )( mm )( m )( m )( )( m )( aa aa aa AE;PE 11 2 1 2 1 22 1 1 1 12 111 0 0 1 0 0 1 11 21 1222 11 21 1121 a a aa a a aa 2021/3/10 清華大學出版社清華大學出版社 20 第2節(jié) 改進單純形法 )( a 1 22

9、而后以第2列的 為主元素，進行變換 )( a/a a/ a/a P )()( m )( )()( )( 2 1 1 22 1 2 1 22 1 22 1 12 2 1 2 2021/3/10 清華大學出版社清華大學出版社 21 第2節(jié) 改進單純形法 10 010 01 1 22 1 2 1 22 1 22 1 12 2 )()( m )( )()( a/a a/ a/a E 然后構(gòu)造構(gòu)造含有（2）列，而其他列都是單位列的矩陣 可得到 )( mm )( m )( m )( m )( )( a a a a a a AEE 2 2 2 2 1 2 3 2 23 2 13 12 00 10 01 20

10、21/3/10 清華大學出版社清華大學出版社 22 第2節(jié) 改進單純形法 重復以上的步驟，直到獲得 1 12 1 1 1 AAEEEm 可見EnE2E1=A-1。用這方法可以求得單純形法的基矩陣B的 逆矩陣B-1 2021/3/10 清華大學出版社清華大學出版社 23 第2節(jié) 改進單純形法 以例1為例進行計算。 124 164 82 00032 52 41 321 54321 xx xx xxx xxxxxzmax 2021/3/10 清華大學出版社清華大學出版社 24 第2節(jié) 改進單純形法 第1步：確定初始基，初始基變量;確定換入，換出變量 （1）確定初始基和初始基變量： （2）計算非基變量

11、的檢驗數(shù)，確定換入變量。 5 4 3 5430 0 1 1 1 x x x X;P,P,PB B 換入變量 對應 注意： 21 2100 1 0 32 4 0 2 0 4 1 100 010 001 00032 000 x ,x, ),(, )P,PN(NBCC BNN 2021/3/10 清華大學出版社清華大學出版社 25 第2節(jié) 改進單純形法 (3) 確定換出變量 5 1 0 1 02 1 02 min0 812 min, ,3 24 i i i B b B P B P x 對應 表示選擇0的元素 2021/3/10 清華大學出版社清華大學出版社 26 第2節(jié) 改進單純形法 （4）基變換計

12、算 將新的基 單位矩陣。計算： 243 P,P,P 41 01 211 41 0 21 4 0 2 112 / / E / / P；構(gòu)造 主元素 41 01 211 1 1 1 41 01 211 1 01 1 1 / / / / BEB 2021/3/10 清華大學出版社清華大學出版社 27 第2節(jié) 改進單純形法 （5）計算非基變量的系數(shù)矩陣 （6）計算RHS 41 0 21 4 1 1 4 1 41 01 211 1 4 1 1 1 11 / / / / NBN 3 16 2 12 16 8 41 01 211 1 1 / / bB 2021/3/10 清華大學出版社清華大學出版社 28

13、第2節(jié) 改進單純形法 第1步計算結(jié)束后的結(jié)果 ),(),(C,CC ;x ,xX ;x ,x ,xX ;P,P,PB NB T N T B 02300 11 1 1 51 243 2431 價值系數(shù) 非基變量 基變量 基 2021/3/10 清華大學出版社清華大學出版社 29 第2節(jié) 改進單純形法 計算非基變量的檢驗數(shù)，確定換入變量 換入變量 對應 注意： 51 5111 1 1 432 1 0 0 0 4 1 4100 010 2101 30002 111 x ,x/, / / ),(, )P,PN(NBCC BNN 2021/3/10 清華大學出版社清華大學出版社 30 第2節(jié) 改進單純形

14、法 確定換出變量 3 1 1 1 11 1 11 min0 2 16 min,2 14 i i i B b B P B P x 對應 2021/3/10 清華大學出版社清華大學出版社 31 第2節(jié) 改進單純形法 由此得到新的基 4100 214 2101 4100 010 2101 100 014 001 100 014 001 0 4 1 0 4 1 1 12 1 2 21 2412 / / / / BEB EP P,P,PB 2 主元素 2021/3/10 清華大學出版社清華大學出版社 32 第2節(jié) 改進單純形法 計算RHS 3 8 2 12 16 8 4100 214 2101 1 2

15、/ / bB 2021/3/10 清華大學出版社清華大學出版社 33 第2節(jié) 改進單純形法 第2步計算結(jié)束后的結(jié)果 ),(),(C,CC ;x ,xX ;x ,x ,xX ;P,P,PB NB T N T B 00302 22 2 2 53 241 2412 價值系數(shù) 非基變量 基變量 基 2021/3/10 清華大學出版社清華大學出版社 34 第2節(jié) 改進單純形法 第3步：計算非基變量（x3, x5）的檢驗數(shù) 換入變量正檢驗數(shù) 對應 注意： 53 5322 1 2 412 1 0 0 0 0 1 4100 314 2101 30200 222 x ,x/, / / ),(, )P,PN(NB

16、CC BNN 2021/3/10 清華大學出版社清華大學出版社 35 第2節(jié) 改進單純形法 確定換出變量 4 1 2 1 25 1 25 min0 83 min,4 2 1/ 4 i i i B b B P B P x 對應 2021/3/10 清華大學出版社清華大學出版社 36 第2節(jié) 改進單純形法 新的基 主元素 的系數(shù)向量是換入變量 4/1 2 2/1 1 0 0 4/100 214 2/101 ;, 5 1 2 5 2513 PB x PPPB 2021/3/10 清華大學出版社清華大學出版社 37 第2節(jié) 改進單純形法 計算B的逆矩陣 1810 0210 0411 81 21 41

17、33 / / / E / / / 構(gòu)造 08121 1212 0410 4100 214 2101 1810 0210 0411 1 23 1 3 / / / / / / / / BEB 2021/3/10 清華大學出版社清華大學出版社 38 第2節(jié) 改進單純形法 計算非基變量的檢驗數(shù) 已無正檢驗數(shù) 注意： 8123 0 1 0 0 0 1 08121 1212 0410 30200 4333 1 3 333 /,/ / / / ),(, P,PNNBCC BNN 2021/3/10 清華大學出版社清華大學出版社 39 第2節(jié) 改進單純形法 得到最優(yōu)解： 1 *1 53 2 01/ 408 2

18、1/ 2116 1/ 21/8012 4 4 2 x XxB b x 14 2 4 4 302 1 3 ,bBCz B * 目標函數(shù)的最優(yōu)值為： 2021/3/1040 P87 3.1 的（1) 作業(yè) 2021/3/10 清華大學出版社清華大學出版社 41 第3節(jié) 對偶問題的提出 v什么是對偶？ 對同一事物（或問題），從不同的角度（或立場） 提出相對的兩種不同的表述。 v例如：在平面內(nèi)，矩形的面積與其周長之間 的關(guān)系，有兩種不同的表述方法。 周長一定，面積最大的矩形是正方形。 面積一定，周長最短的矩形是正方形。 v這種表述有利于加深對事物的認識和理解。 v線性規(guī)劃問題也有對偶關(guān)系。 2021/

19、3/10 清華大學出版社清華大學出版社 42 第3節(jié) 對偶問題的提出 v對第1章例1從對偶的角度進行表述。 假設該工廠的決策者決定不生產(chǎn)產(chǎn)品、，而將其所 有資源出租或外售。這時工廠的決策者就要考慮給每種 資源如何定價的問題。設用y1，y2，y3分別表示出租單 位設備臺時的租金和出讓單位原材料A，B的附加額。 他在做定價決策時，做如下比較：若用1個單位設備臺 時和4個單位原材料A可以生產(chǎn)一件產(chǎn)品，可獲利2元， 那么生產(chǎn)每件產(chǎn)品的設備臺時和原材料出租或出讓的 所有收入應不低于生產(chǎn)一件產(chǎn)品的利潤，這就有 y1+4y22 2021/3/10 清華大學出版社清華大學出版社 43 第3節(jié) 對偶問題的提出

20、v對第1章例1從對偶的角度進行表述。 同理將生產(chǎn)每件產(chǎn)品的設備臺時和原材料出租或出讓 的所有收入應不低于生產(chǎn)一件產(chǎn)品的利潤，這就有 2y1+4y33 把工廠所有設備臺時和資源都出租或出讓，其收入為 w = 8y1+16y2+12y3 從工廠的決策者來看當然w愈大愈好；但受到接受方的 制約，從接受者來看他的支付愈少愈好，所以工廠的決 策者只能在滿足大于等于所有產(chǎn)品的利潤條件下，提出 一個盡可能低的出租或出讓價格，才能實現(xiàn)其原意，為 此需解如下的線性規(guī)劃問題： 2021/3/10 清華大學出版社清華大學出版社 44 第3節(jié) 對偶問題的提出 稱這個線性規(guī)劃問題為例1線性規(guī)劃問題(這里稱為 原問題)的

21、對偶問題。這就是從另一角度提出的線性 規(guī)劃問題。 min w=8y1+16y2+12y3 y1+4y2 2 2y1 +4y33 yi0，i=1,2,3 (2-8) 2021/3/10 清華大學出版社清華大學出版社 45 第3節(jié) 對偶問題的提出 進一步來討論它們之間的關(guān)系。 從第1節(jié)得到檢驗數(shù)的表達式是 CNCBB-1N與CBB-1 由第1章已知：當檢驗數(shù) CN CBB-1N 0 (2-9) CBB-10 (2-10) 時，表示線性規(guī)劃問題已得到最優(yōu)解。這也是最優(yōu)解 的判斷條件。 2021/3/10 清華大學出版社清華大學出版社 46 第3節(jié) 對偶問題的提出 現(xiàn)在討論這兩個條件。 v(1) 由于

22、(2-9)式，(2-10)式中都有乘子CBB-1，稱它為單純形乘 子，用符號Y= CBB-1表示。由(2-10)式，得到Y(jié)0 v(2) 對應基變量XB的檢驗數(shù)是0，CBCBB-1B=0。包括基變量 在內(nèi)的所有檢驗數(shù)可用C CBB-1A0表示。 從此可得CCBB-1A=CYA0，移項后，得到Y(jié)AC v(3) Y由(2-10)式，得到 Y= CBB-1 (2-11) 將(2-11)式兩邊右乘b，得到 Yb= CBB-1b (2-12) Yb= CBB-1b=z，因Y的上界為無限大，所以只存在最小值。 2021/3/10 清華大學出版社清華大學出版社 47 第3節(jié) 對偶問題的提出 現(xiàn)在討論這兩個條件

23、。 v(4) 從這里可以得到另一個線性規(guī)劃問題 min w=Yb YAC Y0 稱它為原線性規(guī)劃問題max z=CXAXb，X0的對偶規(guī) 劃問題 。 2021/3/10 清華大學出版社清華大學出版社 48 第3節(jié) 對偶問題的提出 對偶規(guī)劃問題 oy,y,y yy yy y,y,yY Y ,Y yyymin,Ymin T 321 31 21 321 321 342 24 0 32 4 0 2 0 4 1 1216812168 約束條件： 目標函數(shù)： 2021/3/10 清華大學出版社清華大學出版社 49 第4節(jié) 線性規(guī)劃的對偶理論 4.1 原問題與對偶問題的關(guān)系 4.2 對偶問題的基本性質(zhì) 20

24、21/3/10 清華大學出版社清華大學出版社 50 4.1 原問題與對偶問題的關(guān)系 v原問題（LP）： 1 122 1 111211 2 12 12 max . . ,0 nn n mmmnm n n zc xc xc x x aaab x st aaab x x xx 2021/3/10 清華大學出版社清華大學出版社 51 4.1 原問題與對偶問題的關(guān)系 v對偶問題(DP) 1 122m 11121 1212 12 12 min , . . ,0 m n mn mmmn n y by by b aaa y yyc cc st aaa y yy 2021/3/10 清華大學出版社清華大學出版社

25、 52 4.1 原問題與對偶問題的關(guān)系 v標準型原問題與對偶問題的關(guān)系 12 1111211 2212222 12 12 min maxzmaxzmin j n i n n mmmmnm n x xxx y yaaab yaaab yaaab ccc 原關(guān)系 對偶關(guān)系 2021/3/10 清華大學出版社清華大學出版社 53 4.1 原問題與對偶問題的關(guān)系 v例2 根據(jù)表2-3寫出原問題與對偶問題的表達式 x y x1x2b y1128 y24016 y30412 c23 2021/3/10 清華大學出版社清華大學出版社 54 4.1 原問題與對偶問題的關(guān)系 v下列形式的變換關(guān)系為對稱形式 原問

26、題 （LP） 對偶問題(DP) 0 32 24 0 124 164 82 1216832 321 31 21 21 2 1 21 32121 y,y,y yy yy x ,x x x xx yyyminxxzmax 2021/3/10 清華大學出版社清華大學出版社 55 4.1 原問題與對偶問題的關(guān)系 v非對稱形式的變換關(guān)系 原問題的約束條件中含有等式約束條件時， 按以下步驟處理。 設等式約束條件的線性規(guī)劃問題為 n ,j ,x m,i,bxa xczmax j n j ijij n j jj 210 21 1 1 2021/3/10 清華大學出版社清華大學出版社 56 4.1 原問題與對偶問

27、題的關(guān)系 v非對稱形式的變換關(guān)系 第一步：先將等式約束條件分解為兩個不等 式約束條件 1 1 11 1 max ,1,2,2 13 ,1,2,1,2, 0,1,2, ,1,2,2 14 n jj j n ijji j nn ijjiijji jj j n ijji j zc x a xbim a xbima xbim xjn a xbim 2021/3/10 清華大學出版社清華大學出版社 57 4.1 原問題與對偶問題的關(guān)系 v非對稱形式的變換關(guān)系 第二步：按對稱形式變換關(guān)系可寫出它的對 偶問題 o設yi是對應(2-13)式的對偶變量，yi是對應(2-14) 式的對偶變量，i=1,2,，m m

28、,i,y,y n,j ,cyaya ybybmin i i m i j m i iij iij m i m i ii ii 210 21 11 11 2021/3/10 清華大學出版社清華大學出版社 58 4.1 原問題與對偶問題的關(guān)系 0 21 1 1 i i i ii m i j i iij m i i ii y,y,yyy n ,j,cyya yybmin 令 將上述規(guī)劃問題的各式整理后得到 1 1 min ,1,2, 1,2, m ii i m ijij i i b y a ycjn yim 為無約束， 2021/3/10 清華大學出版社清華大學出版社 59 4.1 原問題與對偶問題的

29、關(guān)系 綜合上述，線性規(guī)劃的原問題與對偶問題的關(guān)系可表示為： maxzmin nn 0 0 m 0 0 RHS RHS m 原問題對偶問題 目標函數(shù)目標函數(shù) 約個個 束變 條量 件無約束 約個個 束變 條量 件無約束 約束條件目標函數(shù)變量的系數(shù) 目標函數(shù)變量系數(shù)約束條件的 2021/3/10 清華大學出版社清華大學出版社 60 4.1 原問題與對偶問題的關(guān)系 例3 試求下述線性規(guī)劃原問題的對偶問題 無約束 4321 3432 2431 14321 4321 00 36 2422 153 532 x,x ,x,x yxxx yxxx yxxxx xxxxzmin 2021/3/10 清華大學出版社

30、清華大學出版社 61 4.1 原問題與對偶問題的關(guān)系 由表2-4中原問題和對偶問題的對應關(guān)系，可以直接寫出上述 問題的對偶問題， 無約束 321 321 321 31 21 321 00 1 523 3 22 645 y,y,y yyy yyy yy yy yyyzmax 2021/3/10 清華大學出版社清華大學出版社 62 4.2 對偶問題的基本性質(zhì) v(1) 對稱性：對偶問題的對偶是原問題 ; v(2)弱對偶性：若X是原問題的可行解，Y是對偶問題的可行 解。則存在CXYb; v(3) 無界性：若原問題(對偶問題)為無界解，則其對偶問題 (原問題)無可行解; v(4) 可行解是最優(yōu)解時的性

31、質(zhì) ; v(5) 對偶定理：若原問題有最優(yōu)解，那么對偶問題也有最優(yōu) 解；且目標函數(shù)值相等; v(6) 互補松弛性 ; v(7) 原問題檢驗數(shù)與對偶問題解的關(guān)系。 2021/3/10 清華大學出版社清華大學出版社 63 4.2 對偶問題的基本性質(zhì) v(1) 對稱性： 對偶問題的對偶是原問題。 證明：設原問題是 max z=CX; AXb； X0 根據(jù)對偶問題的對稱變換關(guān)系，可以找到它的對偶問題是 min w=Yb; YAC； Y0 若將上式兩邊取負號，又因min w=max(-)可得到 max(w)=Yb; YA C； Y0 根據(jù)對稱變換關(guān)系，得到上式的對偶問題是 min( w)= CX； AX

32、 b; X0 又因 min(w)=max w，可得 Max w=max z=CX； AXb; X0 這就是原問題。 2021/3/10 清華大學出版社清華大學出版社 64 4.2 對偶問題的基本性質(zhì) bYXC YX 則存在 是對偶問題的可行解是原問題的可行解，若 v(2)弱對偶性 . ., 0;min: , 證畢于是得到 得到右乘上式將 所以滿足是對偶問題的可行解，因 原問題的對偶問題是 左乘上式，得到將是對偶問題的可行解，若 即以滿足約束條件是原問題的可行解，所因 設原問題是 bYXAYXC CXAYX CAYY YCYAYb bYXAY YY bXA X 0Xb;AXCX;zmax 202

33、1/3/10 清華大學出版社清華大學出版社 65 4.2 對偶問題的基本性質(zhì) 是不可能成立。,XCbY v(3) 無界性 若原問題(對偶問題)為無界解，則其對偶問題 (原問題)無可行解。 證：由性質(zhì)（2）可知， 例： 0 1 12 0 2 42 21 21 21 21 21 21 2121 y,y yy yy x ,x xx xx yyminxxzmax :DP:LP 2021/3/10 清華大學出版社清華大學出版社 66 4.2 對偶問題的基本性質(zhì) v從兩圖對比可明顯看到原問題無界， 其對偶問題無可行解 y1 y2 0 1 12 21 21 21 y,y yy yy 0 2 42 21 21

34、 21 x ,x xx xx 2021/3/10 清華大學出版社清華大學出版社 67 4.2 對偶問題的基本性質(zhì) v(4) 可行解是最優(yōu)解時的性質(zhì) 設 是原問題的可行解， 是對偶問題的可行解， 當 時， 是最優(yōu)解。 證明證明: X bY X CY ,X Y 證畢。所以是最優(yōu)解存在 ，的所有可行解同理可證明，對原問題 因而是最優(yōu)解 最小的可行解，可見是使目標函數(shù)取值所以 因都存在所有可行解 可知，對偶問題的，根據(jù)性質(zhì)證：若 是最優(yōu)解時，當 是對偶問題的可行解是原問題的可行解，設： .,XCbY X C X .bY bY ,bY X C;XC bYY bY X C .Y ,X bY X C Y .

35、 2 X 2021/3/10 清華大學出版社清華大學出版社 68 4.2 對偶問題的基本性質(zhì) .BCY ,CAY ,ABCC ,BX BB 11 0 其中即得到必存在 對應的基矩陣是原問題的最優(yōu)解，它證：設 v(5) 對偶定理 若原問題有最優(yōu)解，那么對偶問題也有最優(yōu) 解；且目標函數(shù)值相等。 是對偶問題的最優(yōu)解?？梢?由此，得到 取值是最優(yōu)解，使目標函數(shù)因原問題的 使得是對偶問題的可行解，若 Y X CbBCbY bBCX CzX bBCbY Y B B B 1 1 1 2021/3/10 清華大學出版社清華大學出版社 69 4.2 對偶問題的基本性質(zhì) 為最優(yōu)解。當且僅當，和那么 題的可行解，分

36、別為原問題和對偶問若 Y ,X ;X YXY Y ,X SS 00 v(6) 互補松弛性 00 SS SS Y ,YX,X CYYAbXAX YbminCXzmax 對偶問題原問題 題的標準關(guān)系是證：設原問題和對偶問 2021/3/10 清華大學出版社清華大學出版社 70 4.2 對偶問題的基本性質(zhì) v(6) 互補松弛性 將原問題目標函數(shù)中的系數(shù)向量C用C=YA-YS代替后，得到 z=(YA YS)X=YAX YSX (2-15) 將對偶問題的目標函數(shù)中系數(shù)列向量b，用b=AX+XS代替后， 得到 w=Y(AX+XS)=YAX+YXS (2-16) 00 162152 4 4 X Y ,XY

37、YbYAXCX Y ,X ,X CX AY bY ;0XY 0,X Y SS SS ）式可知，必有），（由（ ），則有根據(jù)性質(zhì)（ 偶問題的最優(yōu)解，又若分別是原問題和對 是最優(yōu)解。），可知由性質(zhì)（ 則若 2021/3/10 清華大學出版社清華大學出版社 71 4.2 對偶問題的基本性質(zhì) v(7) 原問題檢驗數(shù)與對偶問題解的關(guān)系 設原問題是 max z=CX; AX+XS=b; X,XS0 它的對偶問題是 min w=Yb; YA YS=C; Y,YS0 則原問題單純形表的檢驗數(shù)行對應其對偶問題的一個基解， 其對應關(guān)系見表2-5。 2021/3/10 清華大學出版社清華大學出版社 72 4.2 對

38、偶問題的基本性質(zhì) v(7) 原問題檢驗數(shù)與對偶問題解的關(guān)系 11 12 0 BNS NBB SS XXX CC B NC B YYY YS1是對應原問題中基變量XB的剩余變量， YS2是對應原問題中非基變量XN的剩余變量。 2021/3/10 清華大學出版社清華大學出版社 73 4.2 對偶問題的基本性質(zhì) v(7) 原問題檢驗數(shù)與對偶問題解的關(guān)系 證: 設B是原問題的一個可行基，于是A=(B,N)；原問題可 改寫為 max z=CBXB+CNXN BXB+NXN+XS=b XB，XN，XS0 相應地對偶問題可表示為 min w=Yb YB YS1=CB (2-17) YN YS2=CN (2-

39、18) Y，YS1,YS20 這里YS=(YS1，YS2)。 2021/3/10 清華大學出版社清華大學出版社 74 4.2 對偶問題的基本性質(zhì) v(7) 原問題檢驗數(shù)與對偶問題解的關(guān)系 當求得原問題的一個解：XB=B-1b,其相應的檢驗數(shù)為 CN CBB-1N 與 CBB-1 現(xiàn)分析這些檢驗數(shù)與對偶問題的解之間的關(guān)系：令Y=CBB-1,將 它代入(2-17)式，(2-18)式得 YS1=0, YS2=CN CBB-1N 證畢。 2021/3/10 清華大學出版社清華大學出版社 75 4.2 對偶問題的基本性質(zhì) v例4 已知線性規(guī)劃問題 max z=x1+x2 -x1+x2+x32 -2x1+

40、x2-x31 x1,x2,x30 試用對偶理論證明上述線性規(guī)劃問題無最優(yōu)解。 2021/3/10 清華大學出版社清華大學出版社 76 4.2 對偶問題的基本性質(zhì) v上述問題的對偶問題為 min w=2y1+y2 -y1-2y21 y1+ y21 y1- y20 y1，y20 由第1約束條件，可知對偶問題無可行解；原問題雖然有 可行解，但無最優(yōu)解。 2021/3/10 清華大學出版社清華大學出版社 77 4.2 對偶問題的基本性質(zhì) v例5 已知線性規(guī)劃問題 min w=2x1+3x2+5x3+2x4+3x5 x1+x2+2x3+x4+3x54 2x1-x2+3x3+x4+x53 xj0，j=1，

41、2，5 已知其對偶問題的最優(yōu)解為y1*=4/5，y2*=3/5；z=5。試 用對偶理論找出原問題的最優(yōu)解 。 2021/3/10 清華大學出版社清華大學出版社 78 4.2 對偶問題的基本性質(zhì) v例5 已知線性規(guī)劃問題 解：先寫出它的對偶問題 max z=4y1+3y2 y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1，y20 2021/3/10 清華大學出版社清華大學出版社 79 4.2 對偶問題的基本性質(zhì) v例5 已知線性規(guī)劃問題 將y1* =4/5,y2* =3/5的值代入約束條件， 得=1/53，=17/55，=7/52 它們?yōu)閲栏癫坏仁?；由互補松弛性

42、得 x2*=x3*=x4*=0。 因y1，y20；原問題的兩個約束條件應取等式，故有 x1*+3x5*=4，2x1*+x5*=3 求解后得到x1*=1,x5*=1；故原問題的最優(yōu)解為 X*=(1，0，0，0，1)T；w*=5 2021/3/1080 P88 3.3 ,3.4 作業(yè) 2021/3/10 清華大學出版社清華大學出版社 81 第5節(jié) 對偶問題的經(jīng)濟解釋 影子價格 v在單純形法的每步迭代中，目標函數(shù)取值z=CBB-1b，和檢 驗數(shù)CN CBB-1N中都有乘子Y=CBB-1，那么Y的經(jīng)濟意義是 什么? 設B是max z=CXAXb，X0的最優(yōu)基，由(2-12)式可 知 z*=CBB-1b

43、=Y*b 對z求偏導數(shù)，得 * B * YBC b z 1 由上式可知，變量yi*的經(jīng)濟意義是在其他條件不變的情況 下，單位資源變化所引起的目標函數(shù)的最優(yōu)值的變化。 2021/3/10 清華大學出版社清華大學出版社 82 第5節(jié) 對偶問題的經(jīng)濟解釋 影子價格 v第1章中例1的影價格及其經(jīng)濟解釋。 由表1-5可知 cj23000 CBXBbx1x2x3x4x5 2x141001/40 0 x5400-21/21 3x22011/2-1/80 -z-1400-3/2-1/80 y1*=1.5，y2*=0.125，y3*=0。 2021/3/10 清華大學出版社清華大學出版社 83 第5節(jié) 對偶問題

44、的經(jīng)濟解釋 影子價格 v第1章中例1的影價格及其經(jīng)濟解釋。 這說明是其他條件不變的情況下，若設備增加一臺時，該廠 按最優(yōu)計劃安排生產(chǎn)可多獲利1.5元；原材料A增加1kg，可 多獲利0.125元；原材料B增加1kg，對獲利無影響。 從圖2-1可看到，設備增加一臺時，代表該約束條件的直線由 移至，相應的最優(yōu)解由(4，2)變?yōu)?4，2.5)，目標函數(shù) z=24+32.5=15.5，即比原來的增大1.5。又若原材料A增 加1kg時，代表該約束方程的直線由移至，相應的最優(yōu) 解 從 ( 4 ， 2 ) 變 為 ( 4 . 2 5 ， 1 . 8 7 5 ) ， 目 標 函 數(shù) z = 4.25+31.87

45、5=14.125。比原來的增加0.125。原材料B增 加1kg時，該約束方程的直線由移至，這時的最優(yōu)解不 變。 2021/3/10 清華大學出版社清華大學出版社 84 第5節(jié) 對偶問題的經(jīng)濟解釋 影子價格 v第1章中例1的影價格及其經(jīng)濟解釋。 2021/3/10 清華大學出版社清華大學出版社 85 第5節(jié) 對偶問題的經(jīng)濟解釋 影子價格 vyi*的值代表對第i種資源的估價影子價格。 這種估價是針對具體工廠的具體產(chǎn)品而存在的一種特殊價 格，稱它為“影子價格”。在該廠現(xiàn)有資源和現(xiàn)有生產(chǎn)方 案的條件下，設備的每小時租費為1.5元，1kg原材料A的 出讓費為除成本外再附加0.125元，1kg原材料B可按

46、原成 本出讓，這時該廠的收入與自己組織生產(chǎn)時獲利相等。影 子價格隨具體情況而異，在完全市場經(jīng)濟的條件下，當某 種資源的市場價低于影子價格時，企業(yè)應買進該資源用于 擴大生產(chǎn)；而當某種資源的市場價高于企業(yè)影子價格時， 則企業(yè)的決策者應把已有資源賣掉?？梢娪白觾r格對市場 有調(diào)節(jié)作用。 2021/3/10 清華大學出版社清華大學出版社 86 第6節(jié) 對偶單純形法 v前節(jié)講到原問題與對偶問題的解之間的對應關(guān)系時指出： 在單純形表中進行迭代時，在b列中得到的是原問題的基 可行解，而在檢驗數(shù)行得到的是對偶問題的基解。 v通過逐步迭代，當在檢驗數(shù)行得到對偶問題的解也是基可 行解時，根據(jù)性質(zhì)(2)、(3)可知，

47、已得到最優(yōu)解。即原問題 與對偶問題都是最優(yōu)解。 v根據(jù)對偶問題的對稱性，可以這樣考慮：若保持對偶問題 的解是基可行解，即cjCBB-1Pj0，而原問題在非可行解的 基礎上，通過逐步迭代達到基可行解，這樣也得到了最優(yōu) 解。其優(yōu)點是原問題的初始解不一定是基可行解，可從非 基可行解開始迭代。 2021/3/10 清華大學出版社清華大學出版社 87 第6節(jié) 對偶單純形法 v設原問題為 max z=CX AX=b X0 又設B是一個基。不失一般性，令B=(P1，P2，Pm)，它對 應的變量為 XB=(x1，x2，,xm)。當非基變量都為零時，可 以得到XB=B-1b。若在B-1b中至少有一個負分量，設(

48、B-1b)i 0，并且在單純形表的檢驗數(shù)行中的檢驗數(shù)都為非正，即 對偶問題保持可行解，它的各分量是 (1) 對應基變量x1，x2，,xm的檢驗數(shù)是 i=ci zi=ci CBB-1Pi=0，i=1,2,m (2) 對應非基變量xm+1，xn的檢驗數(shù)是 j=cj zj=cj CBB-1Pj0，j=m+1,n 2021/3/10 清華大學出版社清華大學出版社 88 第6節(jié) 對偶單純形法 v每次迭代是將基變量中的負分量xl取出，去替換非基變量 中的xk，經(jīng)基變換，所有檢驗數(shù)仍保持非正。從原問題來 看，經(jīng)過每次迭代，原問題由非可行解往可行解靠近。當 原問題得到可行解時，便得到了最優(yōu)解。 2021/3/

49、10 清華大學出版社清華大學出版社 89 第6節(jié) 對偶單純形法 v對偶單純形法的計算步驟如下： (1) 根據(jù)線性規(guī)劃問題，列出初始單純形表。檢查b列的數(shù)字， 若都為非負，檢驗數(shù)都為非正，則已得到最優(yōu)解。停止計算。 若檢查b列的數(shù)字時，至少還有一個負分量，檢驗數(shù)保持非正， 那么進行以下計算。 (2) 確定換出變量。按min(B-1b)i(B-1b)i0(B-1b)l對應的 基變量xl為換出變量 (3) 確定換入變量。在單純形表中檢查xl所在行的各系數(shù) lj(j=1,2,，n)。若所有l(wèi)j0，則無可行解，停止 計算。若存 在lj0 (j=1,2,，n), 計算 lk kk lj lj jj ja

50、zc a a zc 0min 2021/3/10 清華大學出版社清華大學出版社 90 第6節(jié) 對偶單純形法 v對偶單純形法的計算步驟如下： 按規(guī)則所對應的列的非基變量xk為換入變量，這樣才能保持 得到的對偶問題解仍為可行解。 (4) 以lk為主元素，按原單純形法在表中進行迭代運算，得到 新的計算表。 重復步驟(1)(4)。 2021/3/10 清華大學出版社清華大學出版社 91 第6節(jié) 對偶單純形法 v例6 用對偶單純形法求解 min w=2x1+3x2+4x3 x1+2x2+x33 2x1x2+3x34 x1，x2，x30 解：解：先將此問題化成下列形式，以便得到對偶問題的初 始可行基 ma

51、x z= 2x1 3x2 4x3 x1 2x2 x3+x4 = 3 2x1+x2 3x3 +x5= 4 xj0，j=1,2,5 2021/3/10 清華大學出版社清華大學出版社 92 第6節(jié) 對偶單純形法 v例6的初始單純形表，見表2-6。 cj -2 -3 -4 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x4 x5 -3 -4 -1 -2 -2 1 -1 -3 1 0 0 1 cj-zj -2 -3 -4 0 0 從表2-6看到，檢驗數(shù)行對應的對偶問題的解是可行解。 因b列數(shù)字為負，故需進行迭代運算。 2021/3/10 清華大學出版社清華大學出版社 93 第6節(jié) 對偶單

52、純形法 v換出變量的確定： v換入變量的確定：按上述對偶單純形法計算步驟(3)，即在單 純形表中檢查xl所在行的各系數(shù)lj(j=1,2,，n)。若所有 lj0，則無可行解，停止 計算。 按上述對偶單純形法計算步驟(2)，即按min(B-1b)i(B-1b)i 0(B-1b)l對應的基變量xi為換出變量。計算 min( 3, 4)= 4 故x5為換出變量。 1 2 2 3 4 , 2 2 min 故x1為換入變量。換入、換出變量的所在列、行的交叉處“2” 為主元素。按單純形法計算步驟進行迭代，得表2-7。 2021/3/10 清華大學出版社清華大學出版社 94 第6節(jié) 對偶單純形法 cj -2

53、-3 -4 0 0 CB XB b x1 x2 x3 x4 x5 0 -2 x4 x1 -1 2 0 1 -5/2 -1/2 1/2 3/2 1 0 -1/2 -1/2 cj-zj 0 -4 -1 0 1 由表 2-7 看出，對偶問題仍是可行解，而 b 列中仍有負分量。 故重復上述迭代步驟，得表 2-8。 2021/3/10 清華大學出版社清華大學出版社 95 第6節(jié) 對偶單純形法 表2-8中，b列數(shù)字全為非負，檢驗數(shù)全為非正，故問題的 最優(yōu)解為 X*=(11/5，2/5，0，0，0)T 若對應兩個約束條件的對偶變量分別為y1和y2，則對偶問題 的最優(yōu)解為 Y*=(y1*,y2*)=(8/5,

54、1/5) 2021/3/10 清華大學出版社清華大學出版社 96 第6節(jié) 對偶單純形法 從以上求解過程可以看到對偶單純形法有以下優(yōu)點： l (1) 初始解可以是非可行解，當檢驗數(shù)都為負數(shù)時就可以進行基的變 換，這時不需要加入人工變量，因此可以簡化計算。 l (2) 當變量多于約束條件，對這樣的線性規(guī)劃問題用對偶單純形法計 算可以減少計算工作量，因此對變量較少，而約束條件很多的線性規(guī) 劃問題，可先將它變換成對偶問題，然后用對偶單純形法求解。 l (3) 在靈敏度分析及求解整數(shù)規(guī)劃的割平面法中，有時需要用對偶單 純形法，這樣可使問題的處理簡化。對偶單純形法的局限性主要是， 對大多數(shù)線性規(guī)劃問題，很

55、難找到一個初始可行基，因而這種方法在 求解線性規(guī)劃問題時很少單獨應用。 2021/3/1097 P90 3.9 的（2) 作業(yè) 2021/3/10 清華大學出版社清華大學出版社 98 第7節(jié) 靈敏度分析 v以前討論線性規(guī)劃問題時，假定ij，bi,cj都是常數(shù)。但實 際上這些系數(shù)往往是估計值和預測值。 v如市場條件一變，cj值就會變化；ij往往是因工藝條件的 改變而改變；bi是根據(jù)資源投入后的經(jīng)濟效果決定的一種 決策選擇。 v因此提出這樣兩個問題： (1)當這些系數(shù)有一個或幾個發(fā)生變化時，已求得的線性規(guī)劃問題的 最優(yōu)解會有什么變化； (2)或者這些系數(shù)在什么范圍內(nèi)變化時，線性規(guī)劃問題的最優(yōu)解或最

56、 優(yōu)基不變。 后一個問題將在第8節(jié)參數(shù)線性規(guī)劃中討論。 2021/3/10 清華大學出版社清華大學出版社 99 第7節(jié) 靈敏度分析 v顯然，當線性規(guī)劃問題中某一個或幾個系數(shù)發(fā)生變化后， 原來已得結(jié)果一般會發(fā)生變化。當然可以用單純形法從 頭計算，以便得到新的最優(yōu)解。這樣做很麻煩，而且也 沒有必要。因在單純形法迭代時，每次運算都和基變量 的系數(shù)矩陣B有關(guān)，因此可以把發(fā)生變化的個別系數(shù)，經(jīng) 過一定計算后直接填入最終計算表中，并進行檢查和分 析，可按表2-9中的幾種情況 進行處理。 原原問問題題 對對偶偶問問題題 結(jié)結(jié)論論或或繼繼續(xù)續(xù)計計算算的的步步驟驟 可行解 可行解 表中的解仍為最優(yōu)解 可行解 非

57、可行解 用單純形法繼續(xù)迭代求最優(yōu)解 非可行解 可行解用 對偶單純形法繼續(xù)迭代求最優(yōu)解 非可行解 非可行解 引進人工變量，編制新的單純形表，求最優(yōu)解 2021/3/10 清華大學出版社清華大學出版社 100 7.1 資源數(shù)量變化的分析 v資源數(shù)量變化是指資源中某系數(shù)b r發(fā)生變化，即 br=br+br。并假設規(guī)劃問題的其他系數(shù)都不變。這樣 使最終表中原問題的解相應地變化為 XB=B-1(b+b) v這里b=(0,，br,0,，0)T。只要XB0，因最終表 中檢驗數(shù)不變，故最優(yōu)基不變，但最優(yōu)解的值發(fā)生了 變化，所以XB為新的最優(yōu)解。新的最優(yōu)解的值可允許 變化范圍用以下方法確定。 2021/3/10

58、 清華大學出版社清華大學出版社 101 7.1 資源數(shù)量變化的分析 mr ir r r rmr rir rr r r a a a b ba ba ba bB bBbBbBbBbbB 11 1 11111 0 0 0 0 )( 新的最優(yōu)解的值可允許變化范圍用以下方法確定。 2021/3/10 清華大學出版社清華大學出版社 102 7.1 資源數(shù)量變化的分析 在最終表中求得的經(jīng)過變化后的 b 列的所有元素， 要求bi+airbr0，i=1,2,m。由此可得 a irbr-bi，i=1,2，m 當air0 時，br-b i/air； 當air0 時，br-b i/air；于是得到 新的最優(yōu)解的值可允

59、許變化范圍用以下方法確定。 0min0max ir ir i i rir ir i i a a b ba a b 2021/3/10 清華大學出版社清華大學出版社 103 7.1 資源數(shù)量變化的分析 例如求第1章例1中第二個約束條件b2的變化范圍。 解：可以利用第1章例1的最終計算表中的數(shù)據(jù)： 2021/3/10 清華大學出版社清華大學出版社 104 7.1 資源數(shù)量變化的分析 可計算b2： 0 0 0 8/1 2/1 4/1 2 4 4 0 0 08/12/1 12/12 04/10 2 4 4 0 0 2 22 11 b bbBbB 由上式，可得 b24/0.25=16，b24/0.5=8

60、，b22/0.125=16。所以b2的 變化范圍是8，16；顯然原b2 =16，加它的變化范圍后， b2的變化范圍是8，32。 2021/3/10 清華大學出版社清華大學出版社 105 7.1 資源數(shù)量變化的分析 2 8 0 0 0 4 0125. 05 . 0 15 . 02 025. 00 1 bB 例7 從表1-5得知第1章例1中，每設備臺時的影子價格為1.5元， 若該廠又從其他處抽調(diào)4臺時用于生產(chǎn)產(chǎn)品，。求這時該廠 生產(chǎn)產(chǎn)品，的最優(yōu)方案。 解：先計算B-1b,將結(jié)果反映到最終表1-5中，得表2-10。 cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3