對(duì)偶理論DualityTheoryppt課件

1、對(duì)對(duì) 偶偶 理理 論論(Duality Theory)對(duì)偶問題的提出對(duì)偶問題的提出線性規(guī)劃的對(duì)偶實(shí)際線性規(guī)劃的對(duì)偶實(shí)際對(duì)偶問題的經(jīng)濟(jì)解釋對(duì)偶問題的經(jīng)濟(jì)解釋-影子價(jià)錢影子價(jià)錢 對(duì)對(duì) 偶偶 單單 純純 形形 法法 靈靈 敏敏 度度 分分 析析 對(duì)偶性是線性規(guī)劃問題的最重要的內(nèi)容之一。每一個(gè)線性對(duì)偶性是線性規(guī)劃問題的最重要的內(nèi)容之一。每一個(gè)線性規(guī)劃規(guī)劃 LP 必然有與之相伴而生的另一個(gè)線性規(guī)劃問題，即必然有與之相伴而生的另一個(gè)線性規(guī)劃問題，即任何一個(gè)求任何一個(gè)求 maxZ 的的LP都有一個(gè)求都有一個(gè)求 minZ 的的LP。其中的一個(gè)問。其中的一個(gè)問題叫題叫“原問題，記為原問題，記為“P，另一個(gè)稱為，

2、另一個(gè)稱為“對(duì)偶問題，記為對(duì)偶問題，記為“D。 例一、資源的合理利用例一、資源的合理利用問題問題 知資料如表所示，問應(yīng)知資料如表所示，問應(yīng)如何安排消費(fèi)方案使得既如何安排消費(fèi)方案使得既能充分利用現(xiàn)有資源有使能充分利用現(xiàn)有資源有使總利潤(rùn)最大？總利潤(rùn)最大？1810單件利潤(rùn)單件利潤(rùn)150設(shè)備設(shè)備51C100煤炭煤炭32B170鋼材鋼材25A資源限制資源限制乙乙甲甲單件單件 產(chǎn)產(chǎn) 耗費(fèi)耗費(fèi) 品品資源資源一、問一、問 題題 的的 提提 出出 0, 1505( 10032 170251810max2121212121xxxxxxxxxxZ原原問問題題）數(shù)數(shù)學(xué)學(xué)模模型型： 下面從另一個(gè)角度來討論這個(gè)問題：下面

3、從另一個(gè)角度來討論這個(gè)問題： 假定：該廠的決策者不是思索本人消費(fèi)甲、乙兩種假定：該廠的決策者不是思索本人消費(fèi)甲、乙兩種產(chǎn)品，而是將廠里的現(xiàn)有資源用于接受外來加工義務(wù)，產(chǎn)品，而是將廠里的現(xiàn)有資源用于接受外來加工義務(wù)，只收取加工費(fèi)。試問該決策者應(yīng)制定怎樣的收費(fèi)規(guī)范只收取加工費(fèi)。試問該決策者應(yīng)制定怎樣的收費(fèi)規(guī)范合理的？合理的？ 分析問題：分析問題： 1 1、每種資源收回的費(fèi)用不能低于本人消費(fèi)時(shí)的可獲、每種資源收回的費(fèi)用不能低于本人消費(fèi)時(shí)的可獲利潤(rùn)；利潤(rùn)； 2 2、定價(jià)又不能太高，要使對(duì)方可以接受。、定價(jià)又不能太高，要使對(duì)方可以接受。Wyyyyyyyyyyyyyyy 32132132132132115

4、0100170 0, 18532 1025 , 以以表表達(dá)達(dá)：就就目目標(biāo)標(biāo)而而言言，用用下下式式可可有有下下式式：?jiǎn)螁蝺r(jià)價(jià)，所所以以分分別別為為三三種種資資源源的的收收費(fèi)費(fèi)設(shè)設(shè) 普通而言，普通而言，W W 越大越好，但因需雙方稱心，故越大越好，但因需雙方稱心，故321150100170minyyyW 為最好。為最好。該問題的數(shù)學(xué)模型為：該問題的數(shù)學(xué)模型為： 0,185321025150100170min321321321321yyyyyyyyyyyyW（對(duì)對(duì)偶偶問問題題） 0, 1505( 10032 170251810max2121212121xxxxxxxxxxZ原原問問題題） 0, 18

5、532 1025150100170min321321321321yyyyyyyyyyyyW（對(duì)對(duì)偶偶問問題題）模型對(duì)比：模型對(duì)比： 例二、合理配料問題，其數(shù)學(xué)模型為：例二、合理配料問題，其數(shù)學(xué)模型為： 0 min 11jmiijijnjjjxbxaxcZ 假設(shè)工廠想把這假設(shè)工廠想把這m m 種營(yíng)養(yǎng)成分分別制成一種營(yíng)養(yǎng)丸種營(yíng)養(yǎng)成分分別制成一種營(yíng)養(yǎng)丸銷售，問如何定價(jià)以保證總收入為最多？銷售，問如何定價(jià)以保證總收入為最多？ 0 max11injjiijnjiiycyaybW（對(duì)對(duì)偶偶問問題題）有有下下列列式式子子：原問題原問題對(duì)偶問題對(duì)偶問題目標(biāo)函數(shù)目標(biāo)函數(shù)maxmin約束條件約束條件變量數(shù)量變量數(shù)

6、量約束條件個(gè)數(shù)約束條件個(gè)數(shù)約束條件個(gè)數(shù)約束條件個(gè)數(shù)變量數(shù)量變量數(shù)量例三、例三、23x1 x2 原問題原問題12y1 22128y2 12816y3401612y40412對(duì)偶問題對(duì)偶問題231 1、對(duì)稱型對(duì)偶問題：知、對(duì)稱型對(duì)偶問題：知 P P，寫出，寫出 D D。 0XbAX CXmaxZ P矩矩陣陣形形式式：二、線性規(guī)劃的對(duì)偶實(shí)際二、線性規(guī)劃的對(duì)偶實(shí)際一、對(duì)偶問題的方式一、對(duì)偶問題的方式 0YCYA min YbWD 例一、寫出線性規(guī)劃問題的對(duì)偶問題例一、寫出線性規(guī)劃問題的對(duì)偶問題 0,5643 7 32 532432max321321321321321xxxxxxxxxxxxxxxZ解：

7、首先將原式變形解：首先將原式變形 0,5 64 3 7 32532432max32132132132321xxxxxxxxxxxxxxxZ 留意：以后不強(qiáng)調(diào)等式右段項(xiàng)留意：以后不強(qiáng)調(diào)等式右段項(xiàng) b0 b0，緣由在對(duì)偶，緣由在對(duì)偶單純型表中只保證單純型表中只保證 而不保證而不保證 ，故，故 b b可以是負(fù)數(shù)?？梢允秦?fù)數(shù)。0 j 01 bB 0,4675343232 532min 321321321321321yyyyyyyyyyyyyyyW對(duì)對(duì)偶偶問問題題：2 2、非對(duì)稱型對(duì)偶問題、非對(duì)稱型對(duì)偶問題 0XbAX max CXZP矩矩陣陣形形式式： 無無符符號(hào)號(hào)限限制制（無無約約束束） min Y

8、CYAYbWD例二、原問題例二、原問題 0,5643732532432max321321321321321xxxxxxxxxxxxxxxZ 無無約約束束解解：對(duì)對(duì)偶偶問問題題為為 ,467534 3 2 32 532min 321321321321321yyyyyyyyyyyyyyyW2 2、混合型對(duì)偶問題、混合型對(duì)偶問題 無無約約束束無無約約束束矩矩陣陣形形式式：23123232221211313212111332211213232131222212112121112211,0,0min,0maxYYYCAYAYAYCAYAYAYYbYbYbWDXXbXAXAbXAXAbXAXAXCXCZP

9、 例三、例三、 無無約約束束4321432142143214321, 0, 06 43 247 23 523 4 532maxxxxxxxxxxxxxxxxxxxxZ原問題原問題 無無約約束束32132131321321321,0,01 72 54 3332 2234 645minyyyyyyyyyyyyyyyyyW對(duì)偶問題對(duì)偶問題綜上所述，其變換方式歸納如下：綜上所述，其變換方式歸納如下：原問題（或?qū)ε紗栴}）原問題（或?qū)ε紗栴}）對(duì)偶問題（或原問題）對(duì)偶問題（或原問題）目標(biāo)函數(shù)目標(biāo)函數(shù) max目標(biāo)函數(shù)目標(biāo)函數(shù) min約約束束條條件件m個(gè)個(gè)m個(gè)個(gè)變變量量0000= =無約束無約束變變量量n個(gè)個(gè)n

10、個(gè)個(gè)約約束束條條件件0000無約束無約束= =約束條件右端項(xiàng)約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)約束條件右端項(xiàng)例四、線性規(guī)劃問題如下：例四、線性規(guī)劃問題如下： 無無約約束束、4321432431432143210 06 442 25 3 532min,xxx,xxxxxxxxxxxxxxxZ 無無約約束束對(duì)對(duì)偶偶問問題題：3213213213121321,0,01 4 5233 2 2 645maxyyyyyyyyyyyyyyyyW 無無約約束束、，4321432143243214321321321321321321 ,00247

11、32543 0432 4323min2 0,564 37 32532 422min.1xxxxxxxxxxxxxxxxxxxZ. xxxxxxxxxxxxxxxZ練習(xí)：練習(xí)： 無無約約束束答答案案：32132132132131321321321321321321y0,y0,y44y4y4y 37y3y3y 23yy 2y32y y 253max.2 0.yy0,y46y7y5y24yy 3y2y 3y2y 532max.1yyyWyyyWmin Z= - CXs.t. - AX- bX 01 1、對(duì)稱性定理：對(duì)偶問題的對(duì)偶是原問題。、對(duì)稱性定理：對(duì)偶問題的對(duì)偶是原問題。 min W= Y bs

12、.t. YA C Y 0max Z=C Xs.t. AXb X 0對(duì)偶的定義對(duì)偶的定義對(duì)偶的定義對(duì)偶的定義max W = -Ybs.t. YA C Y 0二、對(duì)偶問題的性質(zhì)二、對(duì)偶問題的性質(zhì)2 2、弱對(duì)偶原理弱對(duì)偶性：設(shè)、弱對(duì)偶原理弱對(duì)偶性：設(shè) 和和 分別是問題分別是問題P P和和D D的可行解，那么必有的可行解，那么必有_X_Y njmiiijjbyxcbYXC11_ ,即即 推論推論. .假設(shè)假設(shè) 和和 分別是問題分別是問題P P和和D D的可行的可行解，那么解，那么 是是D D的目的函數(shù)最小值的一個(gè)下界；的目的函數(shù)最小值的一個(gè)下界； 是是P P的目的函數(shù)最大值的一個(gè)上界。的目的函數(shù)最大值

13、的一個(gè)上界。_XCbY_X_Y 推論推論.在一對(duì)對(duì)偶問題在一對(duì)對(duì)偶問題P和和D中，假設(shè)其中，假設(shè)其中一個(gè)問題可行但目的函中一個(gè)問題可行但目的函數(shù)無界，那么另一個(gè)問題數(shù)無界，那么另一個(gè)問題不可行；反之不成立。這不可行；反之不成立。這也是對(duì)偶問題的無界性。也是對(duì)偶問題的無界性。無可行解無可行解關(guān)于無界性有如下結(jié)論：關(guān)于無界性有如下結(jié)論：?jiǎn)栴}無界問題無界無可行解無可行解問題無界問題無界對(duì)偶問題對(duì)偶問題原問題原問題 0,024 2max21212121xxxxxxxxZ無界無界如：如：原原 0,012 24min21212121yyyyyyyyW無可無可行解行解對(duì)對(duì) 推論推論.在一對(duì)對(duì)偶問題在一對(duì)對(duì)偶

14、問題P和和D中，假設(shè)一中，假設(shè)一個(gè)可行如個(gè)可行如P，而另一個(gè)不可行，如，而另一個(gè)不可行，如D，那么該，那么該可行的問題無界?？尚械膯栴}無界。例一、例一、 02023220322 432max41432143214321xxxxxxxxxxxxxZ試估計(jì)它們目的函數(shù)的界，并驗(yàn)證弱對(duì)偶性原理。試估計(jì)它們目的函數(shù)的界，并驗(yàn)證弱對(duì)偶性原理。P解：解： 0,04233322 212 2020min212121212121yyyyyyyyyyyyWD 由察看可知：由察看可知： =1.1.1.1T， =1.1，分別，分別是是P和和D的可行解。的可行解。Z=10 ，W=40，故有，故有 ，弱對(duì)偶定理成立。由推

15、論可知，弱對(duì)偶定理成立。由推論可知，W 的的最小值不能小于最小值不能小于10，Z 的最大值不能超越的最大值不能超越40。_XCbY_X_Y例二、知例二、知 0,1222max32132132121xxxxxxxxxxxZ : p 0,02122min:2121212121yyyyyyyyyyWD 試用對(duì)偶實(shí)際證明原問題無界。試用對(duì)偶實(shí)際證明原問題無界。 解：解： =0.0.0T是是 P 的一個(gè)可行解，而的一個(gè)可行解，而 D 的第的第一個(gè)約束條件不能成立由于一個(gè)約束條件不能成立由于y1 , y2 0)。因此，對(duì)偶。因此，對(duì)偶問題不可行，由推論可知，原問題無界。問題不可行，由推論可知，原問題無界。

16、_X例例3 3、知、知 0,11 max :21212121xxxxxxxxZP 0, 1 1 min :21212121yyyyyyyyWD顯然，這兩個(gè)問題都無可行解。顯然，這兩個(gè)問題都無可行解。 3 3、最優(yōu)性判別定理：、最優(yōu)性判別定理： 假設(shè)假設(shè) X X* * 和和 Y Y* * 分別是分別是 P P 和和 D D 的可行解且的可行解且 CXCX* * = Y = Y* * b b，那么那么X X* *. Y. Y* *分別是問題分別是問題 P P和和D D 的最優(yōu)解。的最優(yōu)解。 例如，在例例如，在例1 1中，可找到中，可找到 X X* *= =0.0.4.40.0.4.4T T， Y

17、Y* *= =1.21.2，0.20.2, ,那么那么Z Z* * =28 =28，W W* * =28. =28.故故X X* * .Y .Y* *分分別是別是 P P和和D D 的最優(yōu)解。的最優(yōu)解。 4 4、對(duì)偶定理強(qiáng)對(duì)偶性：、對(duì)偶定理強(qiáng)對(duì)偶性： 假設(shè)一對(duì)對(duì)偶問題假設(shè)一對(duì)對(duì)偶問題 P P 和和 D D 都有可行解，那么它們都有可行解，那么它們都有最優(yōu)解，且目的函數(shù)的最優(yōu)值必相等。都有最優(yōu)解，且目的函數(shù)的最優(yōu)值必相等。 推論推論. .假設(shè)假設(shè) P P 和和 D D 的恣意一個(gè)有最優(yōu)解，那么另的恣意一個(gè)有最優(yōu)解，那么另一個(gè)也有最優(yōu)解，且目的函數(shù)的最優(yōu)值相等。一個(gè)也有最優(yōu)解，且目的函數(shù)的最優(yōu)值相

18、等。 綜上所述，一對(duì)對(duì)偶問題的關(guān)系，只能有下面三種情綜上所述，一對(duì)對(duì)偶問題的關(guān)系，只能有下面三種情況之一出現(xiàn)：況之一出現(xiàn)：.都有最優(yōu)解，分別設(shè)為都有最優(yōu)解，分別設(shè)為X* 和和 Y*，那么必有，那么必有CX* =Y*b；. 一個(gè)問題無界，那么另一個(gè)問題無可行解；一個(gè)問題無界，那么另一個(gè)問題無可行解；.兩個(gè)都無可行解。兩個(gè)都無可行解。 5 5、互補(bǔ)松弛定理：、互補(bǔ)松弛定理： 設(shè)設(shè)X X* *和和Y Y* *分別是問題分別是問題 P P 和和 D D 的可行解，那么它們的可行解，那么它們分別是最優(yōu)解的充要條件是分別是最優(yōu)解的充要條件是剩剩余余變變量量或或或或ssssYXXYXCAYXYAXbY.00

19、)(00)( 同時(shí)成立同時(shí)成立 普通而言，我們把某一可行點(diǎn)如普通而言，我們把某一可行點(diǎn)如X*和和Y* 處的處的嚴(yán)厲不等式約束包括對(duì)變量的非負(fù)約束稱為松約嚴(yán)厲不等式約束包括對(duì)變量的非負(fù)約束稱為松約束，而把嚴(yán)厲等式約束稱為緊約束。所以有如下推論：束，而把嚴(yán)厲等式約束稱為緊約束。所以有如下推論： 設(shè)一對(duì)對(duì)偶問題都有可行解，假設(shè)原問題的某一約設(shè)一對(duì)對(duì)偶問題都有可行解，假設(shè)原問題的某一約束是某個(gè)最優(yōu)解的松約束，那么它的對(duì)偶約束一定是束是某個(gè)最優(yōu)解的松約束，那么它的對(duì)偶約束一定是其對(duì)偶問題最優(yōu)解的緊約束。其對(duì)偶問題最優(yōu)解的緊約束。例例4、知、知 032 235 95243min51543215432543

20、21xxxxxxxxxxxxxxxZ試經(jīng)過求對(duì)偶問題的最優(yōu)解來求解原問題的最優(yōu)解。試經(jīng)過求對(duì)偶問題的最優(yōu)解來求解原問題的最優(yōu)解。解：對(duì)偶問題為解：對(duì)偶問題為 0,)5(923)4(55)3(2)2(4)1(332max2121212121221yyyyyyyyyyyyyW 用圖解法求出：用圖解法求出： Y*=1 . 3， W=11。將將y*1=1， y*2=3 代入對(duì)偶約束條件，代入對(duì)偶約束條件，125式為緊約束，式為緊約束，34為松約束。為松約束。令原問題的最優(yōu)解為令原問題的最優(yōu)解為X* = x1.x2.x3.x4.x5T，那么，那么根據(jù)互補(bǔ)松弛條件，必有根據(jù)互補(bǔ)松弛條件，必有x3 = x4

21、 =0(1 . 3)12345 又由于又由于y*10， y*2 0，原問題的約束必為等式，原問題的約束必為等式，即即 322352152xxxxx 5251321xxxx化簡(jiǎn)為化簡(jiǎn)為此方程組為無窮多解此方程組為無窮多解 令令x5 =0,x5 =0,得到得到x1=1x1=1，x2=2 x2=2 即即X X* *1 =1 =1.2.0.0.01.2.0.0.0T T為原問題的為原問題的一個(gè)最優(yōu)解，一個(gè)最優(yōu)解，Z=11Z=11。 再令再令 x5 =2/3 x5 =2/3，得到，得到x1=5/3x1=5/3，x2=0 x2=0 即即X X* *2 2 5/3.0.0.0.2/35/3.0.0.0.2/

22、3T T也是原問題的一個(gè)最優(yōu)解，也是原問題的一個(gè)最優(yōu)解，Z Z* * =11 =11。例例5、知原問題的最優(yōu)、知原問題的最優(yōu)解為解為X* =0.0.4T，Z=12 試求對(duì)偶問題試求對(duì)偶問題的最優(yōu)解。的最優(yōu)解。 無無約約束束321321321321321, 0, 04 16 3253234maxxxxxxxxxxxxxxxxZ解：解： 無約束無約束321321321321321, 0, 03654 3 132 42minyyyyyyyyyyyyyyyW123將將X* =0 . 0 . 4代入原問題中，有下式：代入原問題中，有下式： 4 4 1 246 32 20532321321321xxxxx

23、xxxx所以，根據(jù)互補(bǔ)松弛條件，必有所以，根據(jù)互補(bǔ)松弛條件，必有y*1= y*2=0，代入對(duì)，代入對(duì)偶問題偶問題 3式，式， y3 =3。因此，對(duì)偶問題的最優(yōu)解為。因此，對(duì)偶問題的最優(yōu)解為 Y*=0 . 0 . 3，W=12。6 6、對(duì)偶問題的解、對(duì)偶問題的解利用原問題的最優(yōu)單純利用原問題的最優(yōu)單純形表和改良單純形表求形表和改良單純形表求解對(duì)偶問題的最優(yōu)解。解對(duì)偶問題的最優(yōu)解。. .設(shè)原問題為：設(shè)原問題為： maxZ=CX maxZ=CX AX b AX b X0 X0引入引入xs xs ，構(gòu)建初始基變量，然后，用單純形法求解。，構(gòu)建初始基變量，然后，用單純形法求解。當(dāng)檢驗(yàn)數(shù)滿足當(dāng)檢驗(yàn)數(shù)滿足j

24、0 j0 ，那么求得最優(yōu)解。此時(shí)，那么求得最優(yōu)解。此時(shí)， xs xs對(duì)對(duì)應(yīng)的應(yīng)的js js 為為- Y- Y* * ，故求對(duì)偶，故求對(duì)偶Y Y* * ，只需將最優(yōu)單純形，只需將最優(yōu)單純形表上表上xs xs 對(duì)應(yīng)的檢驗(yàn)數(shù)反號(hào)即可。對(duì)應(yīng)的檢驗(yàn)數(shù)反號(hào)即可。CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCB B-1b0CNCB B-1NCB B-1例一、例一、 0,150510032170251810max2121212121xxxxxxxxPxxZ 0,185321025150100170min321321321321yyyyyyyyyDyyyW 0 150 5 100 32

25、170 250001810max5152142132154321xxxxxxxxxxxxxxxZcj1018000cBxBbx1x2x3x4x50 x317052100170/20 x410023010100/30 x515015001150/5-Z01018000icj1018000cBxBbx1x2x3x4x50 x3540/7001-23/711/710 x150/71005/7-3/718x2200/7010-1/72/7-Z-4100/7000-32/7-6/7初初始始表表最終表最終表 由上表可知：由上表可知： X*=50/7 . 200/7T，Z* =4100/7對(duì)偶問題的最優(yōu)解：

26、對(duì)偶問題的最優(yōu)解： Y*=0 . 32/7 . 6/7，W* =4100/7也就是外加工時(shí)的收費(fèi)規(guī)范。也就是外加工時(shí)的收費(fèi)規(guī)范。. .設(shè)原問題：設(shè)原問題： maxZ=CX maxZ=CX AX=b AX=b X0 X0此時(shí)，矩陣此時(shí)，矩陣A A中沒有現(xiàn)成的矩陣中沒有現(xiàn)成的矩陣I I，必需經(jīng)過參與人工，必需經(jīng)過參與人工變量來湊一個(gè)單位矩陣，再用大變量來湊一個(gè)單位矩陣，再用大M M法或兩階段法求解。法或兩階段法求解。 如何求如何求Y Y* * ，經(jīng)分析得出如下結(jié)論：，經(jīng)分析得出如下結(jié)論： B =0 B =0 最優(yōu)基變量檢驗(yàn)數(shù)向量最優(yōu)基變量檢驗(yàn)數(shù)向量 I =CI I =CI CB B-1 CB B-

27、1 初始初始基變量檢驗(yàn)數(shù)向量基變量檢驗(yàn)數(shù)向量 D = CD D = CD CB B-1D CB B-1D 非基變量非基變量檢驗(yàn)數(shù)向量檢驗(yàn)數(shù)向量 所以，所以， Y Y* * = CI = CI I I 例二、例二、 0123241123max3131321321321xxxxxxxxxxxx P 無約束無約束32132121321321, 0, 01212324311minyyyyyyyyyyyDyyyW cj3-1-100-M-McBxBbx1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3-Z-2000

28、-1/3-1/31/3-M 2/3- Mcj3- 1- 100- M- McBxBbx1x2x3x4x5x6x70 x4111-21100011- Mx63-4120-1103/2- Mx71-20100011-Z3-6M-1+M-1+3M0-M00i 所以，所以， 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/3 W* = 2 初始基變量的檢驗(yàn)數(shù)初始基變量的檢驗(yàn)數(shù)4 =1/3，6 =1/3M, 7 =2/3M 定義：在一對(duì)定義：在一對(duì)

29、 P 和和 D 中，假設(shè)中，假設(shè) P 的某個(gè)約束條件的某個(gè)約束條件的右端項(xiàng)常數(shù)的右端項(xiàng)常數(shù)bi 添加一個(gè)單位時(shí)，所引起的目的函數(shù)添加一個(gè)單位時(shí)，所引起的目的函數(shù)最優(yōu)值最優(yōu)值Z* 的改動(dòng)量的改動(dòng)量y*i 稱為第稱為第 i 個(gè)約束條件的影子價(jià)錢，個(gè)約束條件的影子價(jià)錢，又稱為邊沿價(jià)錢。又稱為邊沿價(jià)錢。 0 D 0 minmax YCYAXbAXPYbW CX Z三、對(duì)偶問題的經(jīng)濟(jì)解釋三、對(duì)偶問題的經(jīng)濟(jì)解釋影子價(jià)錢影子價(jià)錢 設(shè)：設(shè)：B是問題是問題 P的最優(yōu)基，由前式可知，的最優(yōu)基，由前式可知， Z*=CB B-1b = Y*b =y*1b1+ y*2b2+y*Ibi+y*mbm 當(dāng)當(dāng)bi 變?yōu)樽優(yōu)閎i

30、+1 時(shí)其他右端項(xiàng)不變，也不影響時(shí)其他右端項(xiàng)不變，也不影響B(tài)，CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCB B-1b0CNCB B-1NCB B-1 目的函數(shù)最優(yōu)值變?yōu)椋耗康暮瘮?shù)最優(yōu)值變?yōu)椋?Z*= y*1b1+ y*2b2+y*I bi+1 +y*mbm Z*= Z* Z* = y*i )2 , 1(*miybZii 也可以寫成：也可以寫成：即即y*i 表示表示Z*對(duì)對(duì) bi的變化率。的變化率。 其經(jīng)濟(jì)意義是：在其它條件不變的情況下，單位資源其經(jīng)濟(jì)意義是：在其它條件不變的情況下，單位資源變化所引起的目的函數(shù)的最優(yōu)值的變化。即對(duì)偶變量變化所引起的目的函數(shù)的最優(yōu)值的變

31、化。即對(duì)偶變量yi 就是第就是第 i 個(gè)約束條件的影子價(jià)錢。個(gè)約束條件的影子價(jià)錢。 也可以了解為目的函數(shù)最優(yōu)值對(duì)資源的一階偏導(dǎo)數(shù)也可以了解為目的函數(shù)最優(yōu)值對(duì)資源的一階偏導(dǎo)數(shù)但問題中一切其它數(shù)據(jù)都堅(jiān)持不變。但問題中一切其它數(shù)據(jù)都堅(jiān)持不變。 假設(shè)第假設(shè)第i 種資源的單位市場(chǎng)價(jià)錢為種資源的單位市場(chǎng)價(jià)錢為mi ，當(dāng)，當(dāng)yi mi 時(shí)，時(shí)，企業(yè)情愿購(gòu)進(jìn)這種資源，單位純利為企業(yè)情愿購(gòu)進(jìn)這種資源，單位純利為yimi ，那么有，那么有利可圖；假設(shè)利可圖；假設(shè)yi mi ，那么企業(yè)有償轉(zhuǎn)讓這種資源，那么企業(yè)有償轉(zhuǎn)讓這種資源，可獲單位純利可獲單位純利miyi ，否那么，企業(yè)無利可圖，甚至，否那么，企業(yè)無利可圖，甚

32、至虧損。虧損。 0,150510032170251810max2121212121xxxxxxxxPxxZ010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123( 50/7. 200/7 )74132)719918()75510( Z多了多了 32/7 32/7x1010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 123( 55/7. 199/7 )74100)720018()75010( Z010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123( 50/7. 200/7 )74106)720218

33、()74710( Z010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123( 47/7. 202/7 )多了多了 6/7 6/7 對(duì)偶單純形法是求解線性規(guī)劃的另一的根本方法。對(duì)偶單純形法是求解線性規(guī)劃的另一的根本方法。它是根據(jù)對(duì)偶原理和單純形法的原理而設(shè)計(jì)出來的，它是根據(jù)對(duì)偶原理和單純形法的原理而設(shè)計(jì)出來的，因此稱為對(duì)偶單純形法。不要簡(jiǎn)單了解為是求解對(duì)偶因此稱為對(duì)偶單純形法。不要簡(jiǎn)單了解為是求解對(duì)偶問題的單純形法。問題的單純形法。 由對(duì)偶實(shí)際可以知道，對(duì)于一個(gè)線性規(guī)劃問題，我由對(duì)偶實(shí)際可以知道，對(duì)于一個(gè)線性規(guī)劃問題，我們可以經(jīng)過求解它的對(duì)偶問題來找到它的最優(yōu)解

34、。們可以經(jīng)過求解它的對(duì)偶問題來找到它的最優(yōu)解。四、對(duì)四、對(duì) 偶偶 單單 純純 形形 法法 也就是說，求解原問題也就是說，求解原問題P P時(shí)，可以從時(shí)，可以從P P的一的一個(gè)根本解非基可行解開場(chǎng)，逐漸迭代，使目的函個(gè)根本解非基可行解開場(chǎng)，逐漸迭代，使目的函數(shù)值數(shù)值Z=Y b= CB B-1b =CXZ=Y b= CB B-1b =CX減少，當(dāng)?shù)綔p少，當(dāng)?shù)絏B=B-1b0XB=B-1b0時(shí)，即找到了時(shí)，即找到了P P的最優(yōu)解，這就是對(duì)偶的最優(yōu)解，這就是對(duì)偶單純形法。單純形法。 同原始單純形求法一樣，求解對(duì)偶問題同原始單純形求法一樣，求解對(duì)偶問題D D，也可，也可以從以從D D的一個(gè)根本可行

35、解開場(chǎng)，從一個(gè)根本可行解的一個(gè)根本可行解開場(chǎng)，從一個(gè)根本可行解迭代到另一個(gè)根本可行解，使目的函數(shù)值減少。迭代到另一個(gè)根本可行解，使目的函數(shù)值減少。對(duì)偶對(duì)偶 單純形表單純形表max存在存在bi 0 至至少有一個(gè)少有一個(gè)初始表初始表 全部全部j0 迭迭代代迭代規(guī)那么堅(jiān)迭代規(guī)那么堅(jiān)持原問題可行持原問題可行解解最終表最終表全部全部 bi 0全部全部j0 在原問題解不可行，對(duì)偶在原問題解不可行，對(duì)偶問題解可行的根底上迭代，問題解可行的根底上迭代，至原問題解可行，對(duì)偶問至原問題解可行，對(duì)偶問題解也可行，也就同時(shí)到題解也可行，也就同時(shí)到達(dá)最優(yōu)。達(dá)最優(yōu)。 用對(duì)偶單純形法求解原問用對(duì)偶單純形法求解原問題時(shí)必需滿

36、足兩個(gè)條件：題時(shí)必需滿足兩個(gè)條件：1 單純形表的常數(shù)列中單純形表的常數(shù)列中至 少 有 一 個(gè) 負(fù) 的 分 量 。至 少 有 一 個(gè) 負(fù) 的 分 量 。 存在存在 bi 0 2 單純形表的檢驗(yàn)數(shù)行單純形表的檢驗(yàn)數(shù)行的全部元素不大于的全部元素不大于0。 全全部部j0 用對(duì)偶單純形法求解原問題用對(duì)偶單純形法求解原問題 maxZ = CX AX = b X 0 步驟如下：步驟如下：1假設(shè)初始表假設(shè)初始表j0，bi 0，那么目前解為最優(yōu)解。，那么目前解為最優(yōu)解。 假設(shè)初始表假設(shè)初始表j0，存在，存在bi 0 至少有一個(gè)，那么至少有一個(gè)，那么轉(zhuǎn)入下一步進(jìn)展迭代。轉(zhuǎn)入下一步進(jìn)展迭代。2選出基變量：選出基變量

37、： minbi | bi0 =b k ,那么那么k行為主元行，行為主元行，x k 出基。出基。3選入基變量：選入基變量： min j /a kj | a kj0, 那么以 x j 為入基變量，用單純形法繼續(xù)迭代，即可求出最優(yōu)解。 二基變量的價(jià)值系數(shù) Cj 發(fā)生改動(dòng)， Cj Cj=Cj+Cj (Cj可正可負(fù))，一切非基變量的檢驗(yàn)數(shù)都改動(dòng)，計(jì)算新的檢驗(yàn)數(shù)。 假設(shè)新的檢驗(yàn)數(shù)： 1j0， 原最優(yōu)解堅(jiān)持不變。 ( 2 ) j0, 那么以大于0的檢驗(yàn)數(shù)中最大的變量為入基變量，用單純形法繼續(xù)迭代，即可求出最優(yōu)解。 例：某企業(yè)利用三種資源消費(fèi)兩種產(chǎn)品的最優(yōu)方案例：某企業(yè)利用三種資源消費(fèi)兩種產(chǎn)品的最優(yōu)方案問題歸

38、結(jié)為以下線性規(guī)劃問題歸結(jié)為以下線性規(guī)劃 0,45 802903 45 max2121212121xxxxxxxxxxZ知最優(yōu)表如下。知最優(yōu)表如下。1 1確定確定x2x2的系數(shù)的系數(shù)c2c2的變化范圍，使原最優(yōu)的變化范圍，使原最優(yōu)解堅(jiān)持最優(yōu)；解堅(jiān)持最優(yōu)；2 2假設(shè)假設(shè)c2=6c2=6，求新，求新的最優(yōu)方案。的最優(yōu)方案。 一、一、 價(jià)值系數(shù)價(jià)值系數(shù)cjcj的變化分析的變化分析cj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12000-1-3 0,45 802903 45 max2121212121xxxxxxxxxxZ4 = c25

39、 05 = 52c2 0 5/2 c2 5cj5c2 000CBXBbx1x2x3x4x50 x3250012-55x1351001-1c2 x2 10 010-12000c2 - 55 - 2c2最優(yōu)解最優(yōu)解X X* *= =3535，1010，2525，0 0，0 0T T堅(jiān)持不變。堅(jiān)持不變。1Cj56000CBXBbx1x2x3x4x50 x3250012-55x1351001-16 x2 10 010-12j 0001-70 x425/2001/21-5/25x145/210-1/203/26 x2 45/2 011/20-1/2j00-1/20-9/2x1*=45/2，x2*=45/

40、2，x4*=25/2，x3*= x5*=0，z*=495/22 二、右端常數(shù)bi的變化分析1. 假設(shè)假設(shè)B-1b0 , 那么原最優(yōu)解還是最優(yōu)解，那么原最優(yōu)解還是最優(yōu)解， 即最優(yōu)基即最優(yōu)基B不變，但解的數(shù)值發(fā)生改動(dòng)。不變，但解的數(shù)值發(fā)生改動(dòng)。 XB=B-1b,其它其它 x為為02. 假設(shè)假設(shè)B-1b 0, 那么用對(duì)偶單純形法繼續(xù)求那么用對(duì)偶單純形法繼續(xù)求解。解。3確定使最優(yōu)基不變的資源限量范圍。確定使最優(yōu)基不變的資源限量范圍。 用用B-1b0計(jì)算。計(jì)算。 XB= B1b例：對(duì)于上例中的線性規(guī)劃作以下分析：例：對(duì)于上例中的線性規(guī)劃作以下分析：1 1b3b3在什么范圍內(nèi)變化，原最優(yōu)基不變？在什么范圍

41、內(nèi)變化，原最優(yōu)基不變？2 2假設(shè)假設(shè)b3=55b3=55，求出新的最優(yōu)解。，求出新的最優(yōu)解。 0,45 802903 45Z max2121212121xxxxxxxxxx二、右端常數(shù)二、右端常數(shù)bibi的變化分析的變化分析cj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12000-1-32 1- 01 1 05- 2 1最優(yōu)基：最優(yōu)基：B=P3，P1，P2B1=1 2 1- 01 1 05- 2 1 3b8090 333b280b805b - 250 3b8090B1=0 解得解得40b35040b350，即當(dāng)，即當(dāng)b340b

42、340，50 50 時(shí)，最優(yōu)基時(shí)，最優(yōu)基B B 不變不變z*=580b3+480+2b3=80+3b3333b280b805b-250*2*1*3xxx=2當(dāng)當(dāng) b3= 55 時(shí)時(shí) 333b280b805b-250 30 25 25=x2 x1x50-11/5-3/500j0-1/52/51020 4 03/5-1/5013051-2/5-1/50050-32-1-5x50-1000j -101030 x2 4 100125x152100-25x30 x4x3x2x1bXBCB0045Cj三、三、 添加一個(gè)新變量的分析添加一個(gè)新變量的分析例例2.10 續(xù)例續(xù)例2.8設(shè)企業(yè)研制了一種新產(chǎn)設(shè)企業(yè)研

43、制了一種新產(chǎn)品，對(duì)三種資源的耗費(fèi)系數(shù)列向量以品，對(duì)三種資源的耗費(fèi)系數(shù)列向量以P6表示表示P6= 。問它的價(jià)值系數(shù)。問它的價(jià)值系數(shù)c6符合什么條符合什么條件件才必需安排它的消費(fèi)？設(shè)才必需安排它的消費(fèi)？設(shè)c6=3，新的最優(yōu)，新的最優(yōu)消費(fèi)方案是什么？消費(fèi)方案是什么？2/112/36=c6CBB1P6 =c60，5，4 = c65/202/116P2 1- 01 1 05- 2 12/112/302/11=B1P6 =Cj540003CBXBbx1x2x3x4x5x60 x3250012-515x1351001-11/26 x2 10 010-120j 000-1-31/23x6250012-515x145/210-1/203/204 x2 10 010-120j00-1/2-2-1/20四、四、 添加新的約束條件的分析添加新的約束條件的分析例例2.11 假設(shè)在例假設(shè)在例2.8中，還要思索