線性規(guī)劃對(duì)偶理論

1、運(yùn)籌學(xué)演示課件第第 二二 章章 第二章 線性規(guī)劃的對(duì)偶理論 1 對(duì)偶問(wèn)題的提出第一章中例1(生產(chǎn)安排問(wèn)題）得LP問(wèn)題現(xiàn)有另一機(jī)械廠預(yù)備租借這個(gè)機(jī)械廠的設(shè)備資源，問(wèn)另一機(jī)械廠以每小時(shí)什么樣的價(jià)格才愿意租借設(shè)備？0,1551641222.32max21212121xxxxxxtsxxz現(xiàn)設(shè)設(shè)備A，B，C每小時(shí)的出租價(jià)格分別為 則出租廠的全部資源全部出租收入應(yīng)為 出租廠愿意出租的條件是不低于自己組織生產(chǎn)的收入。即321,yyy321151612yyy03522423213121y,y,yy yyy租借廠希望租金最少，即 得LP問(wèn)題的對(duì)偶問(wèn)題DLP321151612minyyyw321151612mi

2、nyyyw0,352242.3213121yyyyyyyts原問(wèn)題與對(duì)偶問(wèn)題的數(shù)學(xué)模型 原問(wèn)題 對(duì)偶問(wèn)題), 2 , 1(0), 2 , 1(. .max11njxmibxatsxczjnjijijnjjj矩陣表示OXbAXtsCXz.max), 2 , 1(0, 2 , 1. .min11miynjcyatsybwimijiijmiii0. .minYCYAtsYbwTTT例題的矩陣表示00151612500422.3 ,2max212121xxxxtsxxzDLPLP032502042.15,16,12min321321321yyyyyytsyyyw2 原問(wèn)題與對(duì)偶問(wèn)題 問(wèn)題與 問(wèn)題的關(guān)系

3、LPDLPDLPLPLP目標(biāo)函數(shù)極大化 目標(biāo)函數(shù)極小化 約束條件的個(gè)數(shù)為m 約束條件的個(gè)數(shù)為n變量個(gè)數(shù)為n 變量個(gè)數(shù)為m約束條件為 約束條件為 目標(biāo)函數(shù)的系數(shù)為約束條件的右端項(xiàng) 約束條件的右端項(xiàng)為目標(biāo)函數(shù)的系數(shù) 與 互為對(duì)偶問(wèn)題LPLPLPDLPDLP例1 將下面線性規(guī)劃作為原問(wèn)題，寫出其對(duì)偶規(guī)劃321151612minyyyw0,352242.3213121yyyyyyyts解：先將線性規(guī)劃問(wèn)題改寫為 321151612minyyyw0,352242.3213121yyyyyyyts故其對(duì)偶問(wèn)題為2132minxxz0,155341222.212121xxxxxxts例2 求下述線性規(guī)劃的對(duì)

4、偶問(wèn)題0, 030351546324624. .347min32132321321321xxxxxxxxxxxtsxxxz取值無(wú)約束，設(shè) 的形式，有約束寫成，然后將所有和為轉(zhuǎn)換先將303530353035,22222222211xxxxxxxxxxx0,3035530355154663246224. .3447min3221322322322132213221xxxxxxxxxxxxxxxxxxtsxxxxz第二步：令與上式中四個(gè)約束條件對(duì)應(yīng)的對(duì)偶變量分別為 ，寫出其對(duì)偶問(wèn)題。3321,yyyy0,333464556245562734. .30301524max3321332133213321

5、213321yyyyyyyyyyyyyyyyyytsyyyy第三步：再令 并將中間兩個(gè)約束條件合成等式約束，得取值無(wú)約束32132132121321, 0, 033464562734. .301524maxyyyyyyyyyyytsyyy,33311yyyyy一般線性規(guī)劃問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系 原問(wèn)題（對(duì)偶問(wèn)題） 對(duì)偶問(wèn)題（原問(wèn)題） 目標(biāo)函數(shù)max 目標(biāo)函數(shù)中變量的系數(shù) 約束條件的右端項(xiàng) 目標(biāo)函數(shù)min 約束條件的右端項(xiàng) 目標(biāo)函數(shù)中變量的系數(shù)無(wú)約束個(gè)變量00n約束條件個(gè)n個(gè)約束條件m變量無(wú)約束個(gè)00m 3 對(duì)偶問(wèn)題的基本性質(zhì)設(shè)原問(wèn)題為 對(duì)偶問(wèn)題為OXbAXtsCXz.max0. .minYC

6、YAtsYbwTTT原問(wèn)題與對(duì)偶問(wèn)題間存在如下基本性質(zhì)1.弱對(duì)偶性。如果 是原問(wèn)題的可行解 , 是其對(duì)偶問(wèn)題的可行解，則恒有 ), 2 , 1(njxj), 2 , 1(miyi.11miiijnjjybxc2.最優(yōu)性。 如果 是原問(wèn)題的可行解， 是其對(duì)偶問(wèn)題的可行解，且有 則 原問(wèn)題的最優(yōu)解， 是其對(duì)偶問(wèn)題的最優(yōu)解。),2, 1(njxj), 2 , 1(miyi.11miiijnjjybxc),2, 1(njxj), 2 , 1(miyi3.無(wú)界性。 如果原問(wèn)題（對(duì)偶問(wèn)題）具有無(wú)界解，則其對(duì)偶問(wèn)題（原問(wèn)題）無(wú)可行解。（說(shuō)明）4.強(qiáng)對(duì)偶性（或?qū)ε级ɡ恚?如果原問(wèn)題有最優(yōu)解，則其對(duì)偶問(wèn)題也一

7、定具有最優(yōu)解，且有.minmaxwz 5.互補(bǔ)松弛性。 在線性規(guī)劃問(wèn)題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；反之，如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。也即 如果 則 如果 則0iyinjjijbxa 1.0 iyinjjijbxa16.線性規(guī)劃的原問(wèn)題及其對(duì)偶問(wèn)題之間存在一對(duì)互補(bǔ)的基解基解。其中原問(wèn)題的松弛變量對(duì)應(yīng)對(duì)偶問(wèn)題的變量，對(duì)偶問(wèn)題的剩余變量對(duì)應(yīng)原問(wèn)題的變量;這些互相對(duì)應(yīng)的變量如果在一個(gè)問(wèn)題中是基變量，則在另一問(wèn)題中是非基變量；將這對(duì)互補(bǔ)的基解分別代入原問(wèn)題和對(duì)偶問(wèn)題的目標(biāo)函數(shù)有wz 例 將互為對(duì)偶問(wèn)題的線性規(guī)劃問(wèn)題LP與DLP化為

8、標(biāo) 準(zhǔn)形，得), 2 , 1(01551641222. .00032max524132154321njxxxxxxxxtsxxxxxzj0,352242. .54321531421yyyyyyyyyyyts5432100151612maxyyyyyw兩問(wèn)題最終單純形表如下：原問(wèn)題變量 原問(wèn)題松弛變量 基 3 4 3 1 0 1 0 0 -2 1 0 1 0 0 0 0 1 0 54321xxxxx241xxxjjcz b2154515151 32154yyyyy對(duì)偶問(wèn)題剩余變量 對(duì)偶問(wèn)題變量 對(duì)偶問(wèn)題變量 剩余變量 基 1 1 2 0 0 0 1 0 4 0 3 3 31yyjjcz 5432

9、1yyyyyb 21543xxxxx 原問(wèn)題松弛變量 原問(wèn)題變量5151545121注：上面兩表為兩問(wèn)題最優(yōu)單純形表，但檢驗(yàn)數(shù)取相反數(shù)。結(jié)論（1）原問(wèn)題與對(duì)偶問(wèn)題只需求解一個(gè)問(wèn)題，在單純形表中可得另一問(wèn)題最優(yōu)解。(2) 如果在單純形法某一步，原問(wèn)題與對(duì)偶問(wèn)題都得到可行解，則相應(yīng)解分別是兩問(wèn)題的最優(yōu)解。4 影子價(jià)格1。影子價(jià)格的概念單純形法中，每步迭代目標(biāo)函數(shù)其中 表示第 種資源的擁有量。對(duì)偶變量 代表一單位第 種資源在生產(chǎn)中所作貢獻(xiàn)的估計(jì)影子價(jià)格miiinjjjybxcz11nibi, 2 , 1iyii2。影子價(jià)格的數(shù)學(xué)意義與經(jīng)濟(jì)意義（1）資源的市場(chǎng)價(jià)格由市場(chǎng)決定，相對(duì)穩(wěn)定，而影子價(jià)格依賴于

10、資源的擁有與利用情況，是變數(shù)，其隨生產(chǎn)任務(wù)與產(chǎn)品的結(jié)構(gòu)的變化而變化。（2）影子價(jià)格是邊際價(jià)格。 ，表示資源每增加一個(gè)單位，在當(dāng)前情況下，目標(biāo)函數(shù)對(duì)應(yīng)的增加值。例3中， ，則 有 意即當(dāng)?shù)谝环N資源增加一個(gè)單位時(shí)，目標(biāo)值將增加一個(gè)單位。（最優(yōu)解變化）對(duì) 可作相同討論。（3）資源的影子價(jià)格是一種機(jī)會(huì)成本。市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，可買進(jìn)這種資源；反之市場(chǎng)價(jià)格高于影子價(jià)格時(shí)，可賣出這種資源。iiybzib51, 0, 1321yyy11bz32, yy（4）由互補(bǔ)松弛性質(zhì)，當(dāng) 時(shí)， ；當(dāng) 時(shí) ，表示某種資源 未充分利用時(shí)，該種 資源影子價(jià)格為零；當(dāng)影子價(jià)格不為零時(shí)，該資源已經(jīng) 完全用盡。（5）檢驗(yàn)數(shù) 的

11、經(jīng)濟(jì)意義 表示第 種產(chǎn)品一單位的產(chǎn)值，而 表示一單位該產(chǎn)品消耗各種資源影子價(jià)格的總和。即產(chǎn)品的隱含成本。（6）對(duì)線性規(guī)劃問(wèn)題求解是確定資源的最佳分配方案對(duì)對(duì)偶問(wèn)題求解是討論對(duì)資源的恰當(dāng)評(píng)價(jià)。 injjijbxa10 iy0 iyinjjijbxa1ibmiiijjjBjjyacPBCc11jcjmiiijya15 對(duì)偶單純形法對(duì)偶單純形法基本思想：保持對(duì)偶問(wèn)題的解為可行解，通過(guò)迭代，減小目標(biāo)函數(shù)值，使原問(wèn)題的解逐步成為可行解時(shí)，即為最優(yōu)解。迭代過(guò)程：將LP 問(wèn)題化為標(biāo)準(zhǔn)形式，不妨設(shè) 為對(duì)偶問(wèn)題可行基。列單純形表：表中所有 不一定為正。保持所有都為非負(fù)時(shí)則得到最優(yōu)解。對(duì)偶單純形法計(jì)算步驟mPPP

12、B,21ijjjbzc但, 0ijb迭代后，使, 0m21i，基bBc1x1mxrxnxmrccc1mrxxx1mrbbb1001010mnnnaaa211111mmrmmaaajjzc mx1001msxmsrssaaa1sn1.確定出基變量：存在小于零的 時(shí)，令 ， 為出基變量。0miniirbbbibrxjjjzc 0002.確定進(jìn)基變量：(1)確保 r 行的基變量的值為正，在 的非基變量中選取進(jìn)基變量.為主元素， 為進(jìn)基變量.rx(3)用進(jìn)基變量取代出基變量，進(jìn)行迭代(同單純形法），繼續(xù)進(jìn)行檢驗(yàn)等工作.), 2, 1(0nmmjaij rsssrjrjjjjazcaazc0minrsa

13、sx(2)確保迭代后的對(duì)偶問(wèn)題的解仍可行，令對(duì)偶問(wèn)題解的討論 當(dāng)對(duì)偶問(wèn)題存在可行解時(shí)，原問(wèn)題可能存在可行解，可能無(wú)可行解。當(dāng))n,j(abrjr2100而所有時(shí)，原問(wèn)題無(wú)可行解，此時(shí)對(duì)偶問(wèn)題有無(wú)界解。例5 用對(duì)偶單純形方法求解線性規(guī)劃問(wèn)題0,352242.3213121yyyyyyyts321151612minyyyw（說(shuō)明）初始可行基例6、用對(duì)偶單純形法求解線性規(guī)劃問(wèn)題01252632132132y,y,yyyyyy. t . s對(duì)偶問(wèn)題的初始可行基32524yy15y wmin10,12526. .543215321432yyyyyyyyyyyyts32524yy15y wmax12/32

14、/7002/152/32/ 1102/152/ 154/ 14/ 1014/54/ 12404101513/ 13/2053/ 1006/ 16/ 1103/ 124005241510125100116020005241532525454321yyyyyyyyyyybYCBBjcjjzc2y換入, 換出42) 1, 2min(y換出換出2/32/7002/152/32/ 1102/152/ 154/ 14/ 1014/54/ 12404101513/ 13/2053/ 1006/ 16/ 1103/ 124005241510125100116020005241532525454321yyyyy

15、yyyyyybYCBBjjzcjjzc2/32/7002/152/32/ 1102/152/ 154/ 14/ 1014/54/ 12404101513/ 13/2053/ 1006/ 16/ 1103/ 124005241510125100116020005241532525454321yyyyyyyyyyybYCBBjjzcjjzcjjzc最優(yōu)解最優(yōu)解不需要人工變量；不需要人工變量；當(dāng)變量多于約束時(shí)，用對(duì)偶單純形法可減少當(dāng)變量多于約束時(shí)，用對(duì)偶單純形法可減少迭代次數(shù)；迭代次數(shù)；在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法處理簡(jiǎn)化。處理簡(jiǎn)化。在初始單純形表中對(duì)

16、偶問(wèn)題是基可行解，這在初始單純形表中對(duì)偶問(wèn)題是基可行解，這點(diǎn)對(duì)多數(shù)線性規(guī)劃問(wèn)題很難做到。點(diǎn)對(duì)多數(shù)線性規(guī)劃問(wèn)題很難做到。 因此，對(duì)偶單純形法一般不單獨(dú)使用。因此，對(duì)偶單純形法一般不單獨(dú)使用。6 靈敏度分析參數(shù) 中一個(gè)或幾個(gè)變化時(shí)，變化范圍至多為多大，問(wèn)題的最優(yōu)解或最優(yōu)基不變?；痉椒ǎ?）將參數(shù)的變化反映到最終單純形表中來(lái)。具體公式: 及 jiijcba,jjPBPbBb1*1*,mi*iijjj*jjyazczc1 （2）檢查原問(wèn)題是否為可行解。 （3）檢查對(duì)偶問(wèn)題是否為可行解。 （4）據(jù)線性規(guī)劃問(wèn)題與對(duì)偶規(guī)劃問(wèn)題的最優(yōu)性檢驗(yàn)方法判斷問(wèn)題的最優(yōu)性，決定是否用單純形方法或?qū)ε紗渭冃畏椒ɡ^續(xù)進(jìn)行迭

17、代。 原問(wèn)題對(duì)偶問(wèn)題結(jié)論或繼續(xù)計(jì)算的步驟 可行解 可行解 非可行解 非可行解 可行解非可行解 可行解非可行解仍為問(wèn)題最優(yōu)解繼續(xù)用單純形法迭代求最優(yōu)解繼續(xù)用對(duì)偶單純形法迭代求最優(yōu)解引進(jìn)人工變量，編制新單純形表重新計(jì)算6-1 分析 的變化范圍jcjc的變化只引起單純形表檢驗(yàn)數(shù)的變化。例1 考察線性規(guī)劃問(wèn)題0,1551641222.32max2121212211xxxxxxtsxxz分析 和 分別在什么范圍內(nèi)變化，問(wèn)題的最優(yōu)解不變。12解：令 將 反映到原問(wèn)題的最優(yōu)單純形表中102 2+ 3 0 0 0 1 0 0 0 0 -2 1 0 1 0 0 0 0 -1 0 241xxx 基 2+ 3 0

18、4 3 35432xxxxjjzc215154515511111x121表中解為最優(yōu)的條件是05151021111由此推得 滿足要求。121jCBCb再令 將 反映到原問(wèn)題的最優(yōu)單純形表中 2 3+ 0 0 0 1 0 0 0 0 -2 1 0 1 0 0 0 0 -1 0 241xxx 基 2 3 0 4 3+ 35432xxxxjjzc215154515512221x表中解為最優(yōu)的條件是051512由此推得 滿足要求。21012bjCBC 6-2 分析 的變化范圍ibib的變化在實(shí)際問(wèn)題中表明可用資源的數(shù)量發(fā)生變化.靈敏度分析的步驟:(1)(1) 算出 ,將其加到基變量列的數(shù)字上;*ib

19、(2) (2) 由于其對(duì)偶問(wèn)題仍為可行解,故只需檢查原問(wèn)題是否仍為可行解,再按對(duì)偶單純形法進(jìn)行迭代.0,1551641222.32max21322112121xxxxxxtsxxz,2,1例 線性規(guī)劃問(wèn)題分別分析 在什么范圍內(nèi)變化，問(wèn)題的最優(yōu)基不變。3解： 先令 得原問(wèn)題的最終單純形 表為 )3 ,2, 1(0ii 2 3 0 0 0 1 0 0 0 0 -2 1 0 1 0 0 0 0 -1 0 241xxx 基 2 3 0 4 3 354321xxxxxjjzc 2151545151先分析先分析 的變化，據(jù)公式102210051005412510211111*bBb使問(wèn)題最優(yōu)基不變的條件是

20、032421311*bb由此推得 。261同理有 推得2403432155-05135445133333知6-3 增加一個(gè)變量的分析實(shí)際問(wèn)題中增加一種新產(chǎn)品，規(guī)劃問(wèn)題體現(xiàn)為增加一個(gè)變量 ；同時(shí)給出目標(biāo)函數(shù)系數(shù) 及約束條件中的系數(shù)向量。mjjjjaaaP21jxjc分析步驟： (1) 按公式 計(jì)算 在最終單 純形表中的新值。jPjjPBP1（2) 按公式 或 計(jì)算 的檢驗(yàn)數(shù)。jjjBjjYPcPBCc1jBjjPCc jx（3）將 與 填寫到最終單純形表中，若 則問(wèn)題的最優(yōu)解不變，若 ，則按單純形法繼續(xù)迭代。例 上述原問(wèn)題若增加一個(gè)變量 ，并有 及 ，試分析問(wèn)題最優(yōu)解的變化。解：解：0jjjP0

21、j6x46cTP5 ,4,261405425100541251021616PBP 2 3 0 0 0 4 1 0 0 0 0 0 -2 1 (4) 0 1 0 0 1 0 0 -1 0 1 241xxx 基 2 3 0 4 3 3654321xxxxxxjjzc 215154515111403024666PCcB將以上數(shù)值代入例題最優(yōu)單純形表 2 3 0 0 0 4 1 0 0 0 0 0 1 0 1 0 0 0 0 0 261xxx 基 2 3 4 1 3 2654321xxxxxxjjzc 21515152由于 ，繼續(xù)用單純形法迭代，得06414141212121所以得新的最優(yōu)解為.16;

22、 1, 2, 3*621zxxx6-4 增加一個(gè)約束條件的分析實(shí)際問(wèn)題中增加一個(gè)約束條件，相當(dāng)于增添一道工序。分析方法：將原問(wèn)題最優(yōu)解的值代入新增的約束條件中，如滿足則原最優(yōu)解不變，否則，將新約束反映到最終單純形表中進(jìn)行分析。例：將上例增加一個(gè)約束條件 ，分析最優(yōu)解的變化。142321 xx解：因原問(wèn)題最優(yōu)解不滿足新約束，將新約束加松弛變量得 填入最終單純形表。 1423621xxx 2 3 0 0 0 0 1 0 0 0 0 0 -2 1 0 0 1 0 0 0 3 2 0 0 0 1 0 0 -1 0 0 基 2 3 0 4 3 3 0 14jjzc 654321xxxxxx6241xxx

23、x2154515151為使 列組成單位矩陣，做初等行變換，得下表。624, 1,PPPP 基 2 3 0 4 3 3 0 -1 2 3 0 0 0 0 1 0 0 0 0 0 -2 1 0 0 1 0 0 0 0 0 0 0 1 0 0 -1 0 0 654321xxxxxx6241xxxxjjzc 515154512321對(duì)上表進(jìn)行對(duì)偶單純形法迭代得 2 3 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 基 2 0 3 3 0 jjzc 654321xxxxxx3241xxxx1581525131323231638343215231增加新

24、的約束條件后，問(wèn)題的新解為：.343, 3,38*21zxx7 參數(shù)線性規(guī)劃 研究線性規(guī)劃問(wèn)題當(dāng)參數(shù)值連續(xù)變化時(shí)，問(wèn)題的最優(yōu)解如何隨參數(shù)值的變化而變化。要求: (1) 的變化保持線性變化，即 ijbc 與iiijjjabbacc,（2）目標(biāo)函數(shù) 是 的線性函數(shù)。 z例1 求解下述參數(shù)線性規(guī)劃問(wèn)題0,1551641222.322max21212121xxxxxxtsxxz 2+2 3+ 0 0 0 1 0 0 0 0 -2 1 0 1 0 0 0 0 -1 0 241xxx 基 2+2 3 0 4 3+ 35432xxxxjjzc215154515511x解解:（步驟）（1）令 求解得最終單純形

25、表。 （2）將參數(shù)反映到最終單純形表中，得 （表 1）011最優(yōu)基不變的條件是 ;下面分別討論 1 2+2 3+ 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 251xxx 基 2+2 4 0 5 3+ 25432xxxxjjzc215154512231x25當(dāng) 時(shí)，上表中檢驗(yàn)數(shù) 。繼續(xù)迭代得11此表是 時(shí)的最優(yōu)單純形表，最優(yōu)基發(fā)生變化。0551441表 21及 的情況。 2+2 3+ 0 0 0 2 0 1 0 4 0 0 1 0 0 1 0 0 2+2 0 0 0 543xxx 基 0 6 0 16 3+ 35432xxxxjjzc2151521x25當(dāng) 時(shí)，表1中檢驗(yàn)數(shù)

26、 。繼續(xù)迭代得101553表 3jjzc243xxx543xxx0001216152 2 1 0 04 0 0 1 00 5 0 0 12+2 3+ 0 0 0133圖形表示 隨 的變化情況。 z z -3 -2 -1 0 1 26152434例2 求解參數(shù)線性規(guī)劃問(wèn)題0,1551641222.32max21212121xxxxxxtsxxz解解：計(jì)算因參數(shù) 引入基變量數(shù)值產(chǎn)生的變化。5154510051005412510211*bBb將其反映到最終單純形表（見(jiàn)29頁(yè)） 2 3 0 0 0 1 0 0 0 0 -2 1 0 1 0 0 0 0 -1 0 2 3- 0 4+ 3 3+jjzc 54321xxxxx241xxx2151515451515451表中最優(yōu)基不變的條件是當(dāng) 時(shí)，基變量 ，用對(duì)偶單純形法迭代得.155504x表1 2 3 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 2 4 0 -2 3 3+54321xxxxx231xxxjjzc 5251515321412152當(dāng) 時(shí)，表2中最優(yōu)基不變。當(dāng)時(shí)，無(wú)可行解。下面分析 時(shí)的情況，此時(shí)表1中基變量 用對(duì)偶單純形法迭代得. 5151515, 01x表 2 2 3 0 0 0 -5 0 0 1 4 0 0 1 0 1 1 0 0 -1 0 0 0 231