【正文】 3y2 + 0y3 ? 40 2y1+2y2 + 2y3 ? 50 y1 , y2 , y3 ?0 線性規(guī)劃的對(duì)偶理論 36 China University of Mining and Technology 運(yùn) 籌 學(xué) 性質(zhì) 1 對(duì)稱性定理 ：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題 min W= Y b . YA ≥ C Y ≤ 0 max Z=C X . AX≤b X ≥0 三、 對(duì)偶原理 線性規(guī)劃的對(duì)偶理論 37 China University of Mining and Technology 運(yùn) 籌 學(xué) min z′= CX . AX≥b X ≥0 maxw′= Yb . YA≤C Y ≥0 min w=Yb . YA≥C Y ≥0 max z=CX . AX≤b X ≥0 對(duì)偶的 定義 對(duì)偶的 定義 簡(jiǎn)要證明： 線性規(guī)劃的對(duì)偶理論 38 China University of Mining and Technology 運(yùn) 籌 學(xué) 性質(zhì) 2 弱對(duì)偶原理 (弱對(duì)偶性 )： 設(shè) 和 分別是問(wèn)題 (P)和(D)的可行解，則必有 0X 0Y? ?? ???njmiiijj byxcbYCX1 100 即：推論 1: 原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界；反之，對(duì)偶問(wèn)題任意可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界。 這也是對(duì)偶問(wèn)題的 無(wú)界性 。 線性規(guī)劃的對(duì)偶理論 推論 3： 在一對(duì)對(duì)偶問(wèn)題（ P）和（ D）中，若一個(gè)可行（如 P），而另一個(gè)不可行（如 D），則該可行的問(wèn)題目標(biāo)函數(shù)值無(wú)界。 ，弱對(duì)偶定理成立。 且原問(wèn)題的目標(biāo)函數(shù)值為 對(duì)偶問(wèn)題的目標(biāo)函數(shù)值為 故 )4,3,2,1(0 202 32 20322 ..432m a x432143214321???????????????????jxxxxxxxxxtsxxxxZj121212121212m in 20 20 2 1 2 2. . 2 3 3 3 2 4 , 0W y yyyyys t y yyyyy??????????? ?????????線性規(guī)劃的對(duì)偶理論 43 China University of Mining and Technology 運(yùn) 籌 學(xué) 例：利用對(duì)偶性質(zhì)判斷下面問(wèn)題有無(wú)最優(yōu)解 121 2 31 2 3m a x 2 2. . 2 3 1 0( 1 , 2 , 3 )jZ x xx x xs t x x xxj??? ? ? ? ??? ? ? ??????例 6 解：此問(wèn)題的對(duì)偶問(wèn)題為 1212121212m in 2 2 1 2. . 3 0 , 0W y yyyyystyyyy??? ? ???????? ??? ??不能成立，因此對(duì)偶問(wèn)題不可行。 TX )0,0,0(?為可行解 線性規(guī)劃的對(duì)偶理論 44 China University of Mining and Technology 運(yùn) 籌 學(xué) 性質(zhì) 3 最優(yōu)性定理： 如果 是原問(wèn)題的可行解， 是其對(duì)偶問(wèn)題的可行解，并且 : 0X 0YwzBYCX ?? :00 即則 是原問(wèn)題的最優(yōu)解， 是其對(duì)偶問(wèn)題的最優(yōu)解。 還可推出另一結(jié)論： 若一對(duì)對(duì)偶問(wèn)題中的任意一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等；若一個(gè)問(wèn)題無(wú)最優(yōu)解，則另一問(wèn)題也無(wú)最優(yōu)解。 線性規(guī)劃的對(duì)偶理論 46 China University of Mining and Technology 運(yùn) 籌 學(xué) 證明： 當(dāng) X*為原問(wèn)題的一個(gè)最優(yōu)解， B為相應(yīng)的最優(yōu)基，通過(guò)引入松弛變量 Xs，將問(wèn)題 (P)轉(zhuǎn)化為標(biāo)準(zhǔn)型 ?????????0,.0sssXXbIXAXtsXCXZM a x令 ??????????s**XXX?C CB CN 0 解 基系數(shù) 基變量 XB XN Xs CB XB I B1N B1 B1b σ 0 CN CBB1N CBB1 CBB1b C X A CCBB1A ? ? ? ? ? ? 0BCABCCIABC0C 11 B1BB ?????? ?? ????YbBCbYW 1B ??? ??bBCCXZ 1B ??? ??說(shuō)明 Y*可行 ?? ? WZ線性規(guī)劃的對(duì)偶理論 47 China University of Mining and Technology 運(yùn) 籌 學(xué) 問(wèn)題 :（ 1）由性質(zhì) 4可知，對(duì)偶問(wèn)題最優(yōu)解的表達(dá)式 Y*=? （ 2）求 Y*是否有必要重新求解 (D)? 1?? BC B—不必。 C CB CN 0 解 基系數(shù) 基變量 XB XN Xs CB XB I B1N B1 B1b σ 0 CN CBB1N CBB1 CBB1b s1B BCY* ???? ?線性規(guī)劃的對(duì)偶理論 48 China University of Mining and Technology 運(yùn) 籌 學(xué) 性質(zhì) 5 互補(bǔ)松弛性 ：設(shè) X0和 Y0分別是 P問(wèn)題 和 D問(wèn)題 的可行解，則它們分別是最優(yōu)解的充要條件是： ?????000ss0XYXY其中： Xs、 Ys為松弛變量 。 緊約束與松約束 線性規(guī)劃的對(duì)偶理論 50 China University of Mining and Technology 運(yùn) 籌 學(xué) 證 : (必要性） 原問(wèn)題 對(duì)偶問(wèn)題 ???????0X,XbXAXCXZM axss???????0Y,YcYYAYbWM i nss? ?AXbX s ?? ? ?cYAY s ??YbYXY A X s ?? CXXYYAX s ??0XYYX ss ??線性規(guī)劃的對(duì)偶理論 51 China University of Mining and Technology 運(yùn) 籌 學(xué) Max Z=CX . AX+XS=b X, XS ≥0 Min W=Yb . YAYS=C W, WS ≥0 XTYS=0 YTXS=0 m n = Y YS AT I C n = A XS I b n m m X 原始問(wèn)題和對(duì)偶問(wèn)題變量、松弛變量的維數(shù) 線性規(guī)劃的對(duì)偶理論 52 China University of Mining and Technology 運(yùn) 籌 學(xué) y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 對(duì)偶問(wèn)題的變量 對(duì)偶問(wèn)題的松弛變量 原始問(wèn)題的變量 原始問(wèn)題的松弛變量 xjym+j=0 yixn+i=0 (i=1,2,…, m。 線性規(guī)劃的對(duì)偶理論 54 China University of Mining and Technology 運(yùn) 籌 學(xué) 已知線性規(guī)劃 ????????????????3,2,1,0162210243m a x321321321jxxxxxxxxxxzj的最優(yōu)解是 X＊ =(6,2,0)T,求其對(duì)偶問(wèn)題的最優(yōu)解 Y＊ 。 線性規(guī)劃的對(duì)偶理論 56 China University of Mining and Technology 運(yùn) 籌 學(xué) 已知線性規(guī)劃 的對(duì)偶問(wèn)題的最優(yōu)解為 Y＊ =(0,2)，求原問(wèn)題的最優(yōu)解。 ∵ y2=2≠0 ∴ x5＝ 0 又 ∵ y4=1≠0 ∴ x2＝ 0 將 x2， x5分別帶入原問(wèn)題約束方程中，得： 解方程組得： x1=5,x3=1, 所以原問(wèn)題的最優(yōu)解為 X＊ =(5,0,1)，最優(yōu)值 z=12 線性規(guī)劃的對(duì)偶理論 58 China University of Mining and Technology 運(yùn) 籌 學(xué) 試用對(duì)偶原理求解線性規(guī)劃問(wèn)題 ** 341255,yy??1 2 3 4 51 2 3 4 51 2 3 4 5m i n 2 3 5 2 32 3 42 3 30, 1 , 2, 3, 4, 5jz x x x x xx x x x xx x x x xxj? ? ? ? ?? ? ? ? ? ??? ? ? ? ??????已知其對(duì)偶規(guī)劃的最優(yōu)解為 練習(xí) 線性規(guī)劃的對(duì)偶理論 62 China University of Mining and Technology 運(yùn) 籌 學(xué) ? 對(duì)偶規(guī)劃可以用線性規(guī)劃的單純形法求解。 ?互補(bǔ)松弛條件就可以解決由原問(wèn)題的最優(yōu)解直接求出對(duì)偶問(wèn)題的最優(yōu)解。 由對(duì)偶問(wèn)題得基本性質(zhì)可得： 1. 影子價(jià)格的數(shù)學(xué)分析： ????????????0 D 0 m i nm a x YCYAXbAXPYbW C X Z???????miiinjjj ybxcz11影子價(jià)格 69 China University of Mining and Technology 運(yùn) 籌 學(xué) 2. 影子價(jià)格的經(jīng)濟(jì)意義 1）影子價(jià)格是一種邊際價(jià)格 在其它條件不變的情況下，單位資源數(shù)量的變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化。即： )2,1(** miybZ ii?????影子價(jià)格 影子價(jià)格是針對(duì)某一具體約束條件而言 ,因此影子價(jià)格可理解為目標(biāo)函數(shù)最優(yōu)值對(duì)資源的一階偏導(dǎo)數(shù) 70 China University of Mining and T