第3講 對(duì)偶理論和靈敏度分析

1、第第1章章 線性規(guī)劃線性規(guī)劃線性規(guī)劃模型及單純形法線性規(guī)劃模型及單純形法 （2 2學(xué)時(shí)）學(xué)時(shí)）單純形法續(xù)（單純形法續(xù)（2 2學(xué)時(shí)）學(xué)時(shí)）對(duì)偶理論對(duì)偶理論 （2 2學(xué)時(shí)）學(xué)時(shí)）靈敏度分析及整數(shù)規(guī)劃（靈敏度分析及整數(shù)規(guī)劃（2 2學(xué)時(shí)）學(xué)時(shí)）第第3講講 對(duì)偶理論對(duì)偶理論對(duì)偶問(wèn)題的提出對(duì)偶問(wèn)題的提出對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋-影子價(jià)格影子價(jià)格重重 點(diǎn)：對(duì)偶理論，對(duì)偶單純形法點(diǎn)：對(duì)偶理論，對(duì)偶單純形法 難難 點(diǎn)：對(duì)偶理論點(diǎn)：對(duì)偶理論基本要求：掌握對(duì)偶關(guān)系，理解對(duì)偶性質(zhì)，掌握對(duì)基本要求：掌握對(duì)偶關(guān)系，理解對(duì)偶性質(zhì)，掌握對(duì)偶單純形法，偶單純形法， 會(huì)求影子價(jià)格，會(huì)求影子價(jià)格，n引例：經(jīng)營(yíng)策略問(wèn)題。

2、甲工廠有設(shè)備和原料引例：經(jīng)營(yíng)策略問(wèn)題。甲工廠有設(shè)備和原料A A、B B 這些這些設(shè)備和原料可用于設(shè)備和原料可用于、兩種產(chǎn)品的加工，每件產(chǎn)品加兩種產(chǎn)品的加工，每件產(chǎn)品加工所需機(jī)時(shí)數(shù)，原料工所需機(jī)時(shí)數(shù)，原料A A、B B消耗量，每件產(chǎn)品的利潤(rùn)值及消耗量，每件產(chǎn)品的利潤(rùn)值及每種設(shè)備的可利用的機(jī)時(shí)數(shù)如下表?，F(xiàn)在乙廠和甲廠協(xié)每種設(shè)備的可利用的機(jī)時(shí)數(shù)如下表。現(xiàn)在乙廠和甲廠協(xié)商，打算租用甲廠的設(shè)備商，打算租用甲廠的設(shè)備購(gòu)買資源購(gòu)買資源A和和B 。問(wèn)甲廠采取。問(wèn)甲廠采取哪種經(jīng)營(yíng)策略，是自己生產(chǎn)產(chǎn)品還是出租設(shè)備、出讓原哪種經(jīng)營(yíng)策略，是自己生產(chǎn)產(chǎn)品還是出租設(shè)備、出讓原材料？如果出租設(shè)備、出讓原材料，在和乙廠協(xié)商時(shí)

3、出材料？如果出租設(shè)備、出讓原材料，在和乙廠協(xié)商時(shí)出租設(shè)備和出讓原材料租設(shè)備和出讓原材料A,BA,B的底價(jià)應(yīng)是多少？的底價(jià)應(yīng)是多少？對(duì)偶問(wèn)題的提出對(duì)偶問(wèn)題的提出 設(shè)設(shè) 備備原料原料A A原料原料B B 1 4 0 2 0 4 80臺(tái)時(shí) 160kg 120kg23盈利盈利自己生產(chǎn)：自己生產(chǎn)：0, 120 41604 802. .32zmax21212121xxxxxxt sxx原問(wèn)題原問(wèn)題引例分析：l設(shè)設(shè)y y1 1 , ,y y2 2和和y y3 3分別表示出租單位設(shè)備臺(tái)時(shí)分別表示出租單位設(shè)備臺(tái)時(shí)的租金和出讓單位原材料的租金和出讓單位原材料A,BA,B的附加額的附加額2421 yy=80y1+1

4、60y2+120y3出售資源對(duì)偶問(wèn)題l顯然商人希望總的收購(gòu)價(jià)越小越好顯然商人希望總的收購(gòu)價(jià)越小越好l工廠希望出售資源后所得不應(yīng)比生產(chǎn)產(chǎn)品所得少工廠希望出售資源后所得不應(yīng)比生產(chǎn)產(chǎn)品所得少 34231 yy3,2,1,0 iyi .ts目標(biāo)函數(shù)目標(biāo)函數(shù) min0, 120 41604 802. .32zmax21212121xxxxxxt sxx0, 120 41604 802. .32zmax21212121xxxxxxt sxx例例1400421A)3,2( C12016080b它的對(duì)偶問(wèn)題是：它的對(duì)偶問(wèn)題是：YAYA Cmin = YbYbY Y0 012016080Y)3,2(400421

5、 YY Y=（y1，y2，y3）3 , 2 , 1, 034224. .3121iyyyyytsi32112016080minyyy1 1.5.1 .5.1 原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系( (對(duì)稱形式對(duì)稱形式) )線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論0XbAXCX. .max :t sz原問(wèn)題0YCYAYb. .min :ts對(duì)偶問(wèn)題TmnmTnbbbbcccCyyyYxxxX),(),(),(),(21212121上兩式中上兩式中mnmmnnaaaaaaaaaA212222111211 0,. .min21221122222112112211112211mnmmnnnmmmm

6、mmyyycyayayacyayayacyayayatsybybyb 把把對(duì)對(duì)偶偶問(wèn)問(wèn)題題展展開(kāi)開(kāi)0,max 2112121112112211 nmnmnmmnnnxxxbbxxxaaaaaaxcxcxcz0,),(),(min21112111211212211 mnmnmmnmmmyyycccaaaaaayyyybybyb 0,. .max :21221122222112112211112211nmnmnnnnmnmnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz原問(wèn)題展開(kāi) 原關(guān)系minwnxxx21mnmmnnaaaaaaaaa212222111211對(duì)偶關(guān)系myyy

7、21 mbbb21 nccc21wzminmax maxzxy原問(wèn)題與對(duì)偶問(wèn)題的對(duì)稱形式原問(wèn)題與對(duì)偶問(wèn)題的對(duì)稱形式 標(biāo)準(zhǔn)標(biāo)準(zhǔn)( (max,max, ) )型的對(duì)偶變換型的對(duì)偶變換n目標(biāo)函數(shù)由目標(biāo)函數(shù)由 max max 型變?yōu)樾妥優(yōu)?min min 型型n對(duì)應(yīng)原問(wèn)題每個(gè)約束行有一個(gè)對(duì)偶變量對(duì)應(yīng)原問(wèn)題每個(gè)約束行有一個(gè)對(duì)偶變量 yi，i=1,2,1,2, ,m mn對(duì)偶問(wèn)題約束為對(duì)偶問(wèn)題約束為 型，有型，有 n n 行行n原問(wèn)題的價(jià)值系數(shù)原問(wèn)題的價(jià)值系數(shù) C C 變換為對(duì)偶問(wèn)題的右端項(xiàng)變換為對(duì)偶問(wèn)題的右端項(xiàng)n原問(wèn)題的右端項(xiàng)原問(wèn)題的右端項(xiàng) b b 變換為對(duì)偶問(wèn)題的價(jià)值系數(shù)變換為對(duì)偶問(wèn)題的價(jià)值系數(shù)n原問(wèn)

8、題的技術(shù)系數(shù)矩陣原問(wèn)題的技術(shù)系數(shù)矩陣 A A 轉(zhuǎn)置后成為對(duì)偶問(wèn)題的技術(shù)轉(zhuǎn)置后成為對(duì)偶問(wèn)題的技術(shù)系數(shù)矩陣系數(shù)矩陣n原問(wèn)題與對(duì)偶問(wèn)題互為對(duì)偶原問(wèn)題與對(duì)偶問(wèn)題互為對(duì)偶l對(duì)偶問(wèn)題可能比原問(wèn)題容易求解對(duì)偶問(wèn)題可能比原問(wèn)題容易求解l對(duì)偶問(wèn)題還有很多理論和實(shí)際應(yīng)用的意義對(duì)偶問(wèn)題還有很多理論和實(shí)際應(yīng)用的意義原問(wèn)題與對(duì)偶問(wèn)題的結(jié)構(gòu)關(guān)系原問(wèn)題與對(duì)偶問(wèn)題的結(jié)構(gòu)關(guān)系n原問(wèn)題與對(duì)偶問(wèn)題中的目標(biāo)函數(shù)的優(yōu)化方向相反（前原問(wèn)題與對(duì)偶問(wèn)題中的目標(biāo)函數(shù)的優(yōu)化方向相反（前者為極大，后者為極小）者為極大，后者為極?。﹏原問(wèn)題的每個(gè)約束條件對(duì)應(yīng)于對(duì)偶問(wèn)題的一個(gè)決策變?cè)瓎?wèn)題的每個(gè)約束條件對(duì)應(yīng)于對(duì)偶問(wèn)題的一個(gè)決策變量，且約束條件的資源系數(shù)

9、（右端的常數(shù)項(xiàng)）為相應(yīng)量，且約束條件的資源系數(shù)（右端的常數(shù)項(xiàng)）為相應(yīng)決策變量的價(jià)值系數(shù)決策變量的價(jià)值系數(shù)n原問(wèn)題的每個(gè)決策變量對(duì)應(yīng)于對(duì)偶問(wèn)題的一個(gè)約束條原問(wèn)題的每個(gè)決策變量對(duì)應(yīng)于對(duì)偶問(wèn)題的一個(gè)約束條件，且決策變量的價(jià)值系數(shù)為相應(yīng)約束條件的右端常件，且決策變量的價(jià)值系數(shù)為相應(yīng)約束條件的右端常數(shù)項(xiàng)數(shù)項(xiàng)n對(duì)偶問(wèn)題中的系數(shù)矩陣為原問(wèn)題中的系數(shù)矩陣的轉(zhuǎn)置對(duì)偶問(wèn)題中的系數(shù)矩陣為原問(wèn)題中的系數(shù)矩陣的轉(zhuǎn)置n原問(wèn)題約束條件中的小于等于符號(hào)對(duì)應(yīng)于對(duì)偶問(wèn)題中原問(wèn)題約束條件中的小于等于符號(hào)對(duì)應(yīng)于對(duì)偶問(wèn)題中的對(duì)偶變量取非負(fù)約束，原問(wèn)題中決策的對(duì)偶問(wèn)題非的對(duì)偶變量取非負(fù)約束，原問(wèn)題中決策的對(duì)偶問(wèn)題非負(fù)約束在對(duì)偶問(wèn)題中體現(xiàn)

10、為相應(yīng)的約束條件取大于等負(fù)約束在對(duì)偶問(wèn)題中體現(xiàn)為相應(yīng)的約束條件取大于等于符號(hào)于符號(hào) 非非標(biāo)準(zhǔn)標(biāo)準(zhǔn)型的對(duì)偶變換型的對(duì)偶變換0,510342023. .54max 21221212121xxxxxxxxtsxxz不限原線性規(guī)劃問(wèn)題例 0, 551033420223.554max)(max, 221221221221221221xxxxxxxxxxxxxxxtsxxxz型標(biāo)準(zhǔn)問(wèn)題化為0,532532443. .551020min 43214321432143214321wwwwwwwwwwwwwwwwtswwww則應(yīng)用標(biāo)準(zhǔn)型對(duì)偶變換規(guī)不限經(jīng)整理得令3213213213214332211, 0, 05

11、32443. .51020min:, yyyyyyyyytsyyywwywywy 對(duì)偶變換的規(guī)則對(duì)偶變換的規(guī)則max=5y1+4y2+6y3y1 +2y2y1 + y3-3y1+2y2+y3y1- y2+ y3=23-5 1y1 0，y2 0,y3無(wú)約束無(wú)約束對(duì)偶問(wèn)題例例3 3 寫出線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題寫出線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題minz=2x1+3x2-5x3+x4原問(wèn)題原問(wèn)題 x1+x2- 3x3 +x4 5 2x1+ 2x3 -x44 x2 + x3 +x4=6 x1 0 ,x2, x3 0, x4無(wú)約束（1）對(duì)稱性：對(duì)偶的對(duì)偶就是原始問(wèn)題min =-CXs.t. -AX -bX 0ma

12、x z=-Ybs.t. -YA -CY 0min =Ybs.t. YA C Y 0max z=CXs.t. AX bX 0對(duì)偶的定義對(duì)偶的定義對(duì)偶的定義對(duì)偶的定義1.5.2 對(duì)偶問(wèn)題的基本性質(zhì)對(duì)偶問(wèn)題的基本性質(zhì) 為了便于討論，下面不妨總是假設(shè)為了便于討論，下面不妨總是假設(shè) 0XbAX.CXmax :tsz原原問(wèn)問(wèn)題題 0YCYA.Ybmin :ts 對(duì)對(duì)偶偶問(wèn)問(wèn)題題 0YCAY0XbXA,Y,X :故有故有題的可行解題的可行解分別為原問(wèn)題和對(duì)偶問(wèn)分別為原問(wèn)題和對(duì)偶問(wèn)由于由于證證XYbYXC (2) 弱對(duì)偶性: :若若 是原問(wèn)題的可行解，是對(duì)偶是原問(wèn)題的可行解，是對(duì)偶問(wèn)題的可行解。則存在問(wèn)題的可

13、行解。則存在 XAbYY XAXCY bYYXC XA對(duì)偶問(wèn)題對(duì)偶問(wèn)題( (min)min)的任何可行解的任何可行解Y Y，其目標(biāo)函數(shù)值總是其目標(biāo)函數(shù)值總是不小于原問(wèn)題不小于原問(wèn)題( (max)max)任何可行解任何可行解X X的目標(biāo)函數(shù)值的目標(biāo)函數(shù)值 弱弱對(duì)偶定理推論對(duì)偶定理推論原問(wèn)題的任何可行解目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函原問(wèn)題的任何可行解目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下限；對(duì)偶問(wèn)題的任何可行解目標(biāo)函數(shù)值是數(shù)值的下限；對(duì)偶問(wèn)題的任何可行解目標(biāo)函數(shù)值是原問(wèn)題目標(biāo)函數(shù)值的上限原問(wèn)題目標(biāo)函數(shù)值的上限n如果原如果原( (對(duì)偶對(duì)偶) )問(wèn)題為無(wú)界解，則其對(duì)偶問(wèn)題為無(wú)界解，則其對(duì)偶( (原原) )

14、問(wèn)題無(wú)問(wèn)題無(wú)可行解可行解n如果原如果原( (對(duì)偶對(duì)偶) )問(wèn)題有可行解，其對(duì)偶問(wèn)題有可行解，其對(duì)偶( (原原) )問(wèn)題無(wú)可問(wèn)題無(wú)可行解，則原問(wèn)題為無(wú)界解行解，則原問(wèn)題為無(wú)界解n當(dāng)原問(wèn)題當(dāng)原問(wèn)題( (對(duì)偶問(wèn)題對(duì)偶問(wèn)題) )為無(wú)可行解為無(wú)可行解, ,其對(duì)偶問(wèn)題其對(duì)偶問(wèn)題( (原問(wèn)原問(wèn)題題) )或具有無(wú)界解或無(wú)可行解或具有無(wú)界解或無(wú)可行解bYYXC XA (3)強(qiáng)對(duì)偶性證：由弱對(duì)偶定理推論證：由弱對(duì)偶定理推論1 1，結(jié)論是顯然的。，結(jié)論是顯然的。 XYbYXC XY若是原問(wèn)題的可行解，是對(duì)偶問(wèn)題可行解，當(dāng)若是原問(wèn)題的可行解，是對(duì)偶問(wèn)題可行解，當(dāng) , , , , 分別是相應(yīng)問(wèn)題的最優(yōu)解分別是相應(yīng)問(wèn)題的

15、最優(yōu)解XCbY bYXC 若若bYbY 是使目標(biāo)函數(shù)取最小值的解，因此是最優(yōu)解是使目標(biāo)函數(shù)取最小值的解，因此是最優(yōu)解 Y可行解是最優(yōu)解的性質(zhì)可行解是最優(yōu)解的性質(zhì)(最優(yōu)性準(zhǔn)則定理最優(yōu)性準(zhǔn)則定理) (4) (4) 對(duì)偶對(duì)偶定理定理 若原問(wèn)題和對(duì)偶問(wèn)題兩者皆可行若原問(wèn)題和對(duì)偶問(wèn)題兩者皆可行,則兩者均則兩者均有最優(yōu)解有最優(yōu)解,且此時(shí)目標(biāo)函數(shù)值相等且此時(shí)目標(biāo)函數(shù)值相等.第第1部分部分:證明兩者均有最優(yōu)解證明兩者均有最優(yōu)解證明分兩部分證明分兩部分由于原問(wèn)題和對(duì)偶問(wèn)題均可行由于原問(wèn)題和對(duì)偶問(wèn)題均可行,根據(jù)弱根據(jù)弱對(duì)偶性對(duì)偶性,可知兩者均有界可知兩者均有界,于是均有最于是均有最優(yōu)解優(yōu)解.bYXC 第第2部分部

16、分:證明有相同的目標(biāo)函數(shù)值證明有相同的目標(biāo)函數(shù)值 設(shè)設(shè) 為原問(wèn)題的最優(yōu)解為原問(wèn)題的最優(yōu)解X它所對(duì)應(yīng)的基矩陣是它所對(duì)應(yīng)的基矩陣是B B，則其檢驗(yàn)數(shù)滿足則其檢驗(yàn)數(shù)滿足 C C C CB BB B 1 1A A 0 0 bBX1 因此有對(duì)偶問(wèn)題目標(biāo)函數(shù)值因此有對(duì)偶問(wèn)題目標(biāo)函數(shù)值而原問(wèn)題最優(yōu)解的目標(biāo)函數(shù)值而原問(wèn)題最優(yōu)解的目標(biāo)函數(shù)值為為01 YCAYBCYB，則則有有令令顯然顯然 為對(duì)偶問(wèn)題的可行解。為對(duì)偶問(wèn)題的可行解。YbBCbYB1 bBCXCzB1 證畢故由最優(yōu)解準(zhǔn)則定理可知故由最優(yōu)解準(zhǔn)則定理可知 為對(duì)偶問(wèn)題的最優(yōu)解為對(duì)偶問(wèn)題的最優(yōu)解. .Y對(duì)偶定理推論對(duì)偶定理推論n根據(jù)對(duì)偶定理第根據(jù)對(duì)偶定理第2

17、 2部分的證明部分的證明, ,可以得出可以得出: :若互為若互為對(duì)偶的線性規(guī)劃問(wèn)題中的任一個(gè)有最優(yōu)解對(duì)偶的線性規(guī)劃問(wèn)題中的任一個(gè)有最優(yōu)解, ,則另則另一個(gè)也有最優(yōu)解一個(gè)也有最優(yōu)解, ,且目標(biāo)函數(shù)值相等且目標(biāo)函數(shù)值相等. . 綜上所述綜上所述, ,一對(duì)對(duì)偶問(wèn)題的解必然是下列三種一對(duì)對(duì)偶問(wèn)題的解必然是下列三種情況之一情況之一: :n原問(wèn)題和對(duì)偶問(wèn)題都有最優(yōu)解原問(wèn)題和對(duì)偶問(wèn)題都有最優(yōu)解n一個(gè)問(wèn)題具有無(wú)界解一個(gè)問(wèn)題具有無(wú)界解, ,另一個(gè)問(wèn)題無(wú)可行解另一個(gè)問(wèn)題無(wú)可行解n原問(wèn)題和對(duì)偶問(wèn)題都無(wú)可行解原問(wèn)題和對(duì)偶問(wèn)題都無(wú)可行解 (5)互補(bǔ)松弛互補(bǔ)松弛定理定理證：由定理所設(shè)，可知有 YXSXSYYX設(shè)設(shè) , ,

18、 分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解， 為為原問(wèn)題的松弛變量的值，為對(duì)偶問(wèn)題剩余變量的原問(wèn)題的松弛變量的值，為對(duì)偶問(wèn)題剩余變量的值。值。 , , 分別是原問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解的充分分別是原問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解的充分必要條件是必要條件是0 SSYXXY0, SSXXbXXA0, SSYYCYAY分別以分別以 左乘左乘(1)(1)式，以式，以 右乘右乘(2)(2)式后，兩式相減，得式后，兩式相減，得 YXXCbYXYXYSS 0 XYXYSS若若根據(jù)最優(yōu)解判別定理，根據(jù)最優(yōu)解判別定理， 分別是原問(wèn)題和對(duì)偶問(wèn)題最優(yōu)分別是原問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解。反之亦然。解。反之亦然。YX

19、,證畢。（1）（2）0 SSYXXY即即0 XCbYXCbY max z=CXs.t.AX+XS=bX, XS 0min w=Ybs.t. AY-YS=CY, YS 0XYS=0YXS=0mn=YYSA-ICn=AXSIbnmmX原始問(wèn)題和對(duì)偶問(wèn)題變量、松弛變量的維數(shù)原始問(wèn)題和對(duì)偶問(wèn)題變量、松弛變量的維數(shù)原始問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解之間的互補(bǔ)松弛關(guān)系原始問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解之間的互補(bǔ)松弛關(guān)系maxz=CX s.t. AX+XS=b X, XS0min w=bYs.t. AY-YS=C Y, YS0maxz=CXs.t. AXb X 0min w=bYs.t. AYC Y0對(duì)偶引進(jìn)松弛變量引進(jìn)松弛變

20、量XYS=0 YXS=0X，XsY，Ysy1 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=0yixn+i=0(i=1,2,m; j=1,2,n)在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于0原始問(wèn)題的變量原始問(wèn)題的變量對(duì)偶問(wèn)題的松弛變量對(duì)偶問(wèn)題的松弛變量(6)原問(wèn)題單純形表檢驗(yàn)數(shù)行與對(duì)偶問(wèn)題解的關(guān)系原問(wèn)題單純形表檢驗(yàn)數(shù)行與對(duì)偶問(wèn)題解的關(guān)系n原問(wèn)題單純形表檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)對(duì)偶原問(wèn)題單純形表檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)基解問(wèn)題的一個(gè)基解. .顯然顯然, ,原問(wèn)題最終單純

21、形原問(wèn)題最終單純形表檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)基表檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)基可行解可行解BXNXSX1SYNBCCBN1 1 BCB02SY Y 證：標(biāo)準(zhǔn)化后的原問(wèn)題和對(duì)偶問(wèn)題的表達(dá)式為證：標(biāo)準(zhǔn)化后的原問(wèn)題和對(duì)偶問(wèn)題的表達(dá)式為：0,CXmax : SSXXbXAXz原原問(wèn)問(wèn)題題0,min :SSYYCYYAYb對(duì)偶問(wèn)題若若B B是是A A中的一個(gè)基，中的一個(gè)基，A=A=（B B，N N） 0,XCmax :SNBSNBNNBBXXXbXNXBXXCz原原問(wèn)問(wèn)題題改改寫寫為為),(0,Ybmin :212121SSSSSNSBSYYYYYYCYYNCYYB 對(duì)對(duì)偶偶問(wèn)問(wèn)題題為為原問(wèn)

22、題解為原問(wèn)題解為XB=B-1b ，BSCYYB 1N= CN-CBB-1N，Z=CBB-1b對(duì)偶問(wèn)題的約束條件：對(duì)偶問(wèn)題的約束條件：1 BCYB令令011 BBCCYBBS01 SYNSCYYN 2NBCCYBNS12 BXNXSX1SYNBCCBN1 1 BCB02SY Y 檢驗(yàn)數(shù)：檢驗(yàn)數(shù)：B= CB-CBB-1B=0，N= CN-CBB-1N，S=CBB-1原問(wèn)題單純形表檢驗(yàn)數(shù)行與對(duì)偶問(wèn)題解的關(guān)系原問(wèn)題單純形表檢驗(yàn)數(shù)行與對(duì)偶問(wèn)題解的關(guān)系結(jié)論：結(jié)論：v單純形表中的檢驗(yàn)數(shù)行和對(duì)偶問(wèn)題的解單純形表中的檢驗(yàn)數(shù)行和對(duì)偶問(wèn)題的解僅差一個(gè)符號(hào)vyi等于原問(wèn)題的第等于原問(wèn)題的第i個(gè)方程中的松弛變量所對(duì)應(yīng)的

23、檢驗(yàn)個(gè)方程中的松弛變量所對(duì)應(yīng)的檢驗(yàn) 數(shù)的負(fù)數(shù)數(shù)的負(fù)數(shù)v單純形法迭代時(shí)，原問(wèn)題解為基可行解，相應(yīng)的單純形法迭代時(shí)，原問(wèn)題解為基可行解，相應(yīng)的檢驗(yàn)數(shù)對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)解，在原問(wèn)題沒(méi)有得到檢驗(yàn)數(shù)對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)解，在原問(wèn)題沒(méi)有得到最優(yōu)解之前，對(duì)偶問(wèn)題的解為非可行解最優(yōu)解之前，對(duì)偶問(wèn)題的解為非可行解基可行解基可行解非可行解基可行解目標(biāo)函數(shù)對(duì)偶問(wèn)題原問(wèn)題YbCX YbCX 無(wú)可行解無(wú)界解原問(wèn)題為可行解時(shí)原問(wèn)題為可行解時(shí)，對(duì)偶問(wèn)題不一定，對(duì)偶問(wèn)題不一定有可行解，當(dāng)原問(wèn)有可行解，當(dāng)原問(wèn)題為最優(yōu)解，對(duì)偶題為最優(yōu)解，對(duì)偶問(wèn)題一定有最優(yōu)解問(wèn)題一定有最優(yōu)解例例4 0,12 2.zmax32132132121xxx

24、xxxxxxstxx試用對(duì)偶理論證明該線試用對(duì)偶理論證明該線性規(guī)劃問(wèn)題無(wú)最優(yōu)解。性規(guī)劃問(wèn)題無(wú)最優(yōu)解。證：證：該問(wèn)題存在可行解，該問(wèn)題存在可行解，X=（0，0，0）；）；對(duì)偶問(wèn)題為：對(duì)偶問(wèn)題為：212inyym 12.21yyst121 yy021 yy0,21 yy由第一個(gè)約束條件可知由第一個(gè)約束條件可知對(duì)偶問(wèn)題無(wú)可行解，因?qū)ε紗?wèn)題無(wú)可行解，因此，原問(wèn)題有可行解，此，原問(wèn)題有可行解，無(wú)最優(yōu)解。無(wú)最優(yōu)解。例例5： 0,332 432.32532min54321543215432154321xxxxxxxxxxxxxxxstxxxxx 試用對(duì)偶理論找出原問(wèn)題的最優(yōu)解。試用對(duì)偶理論找出原問(wèn)題的最優(yōu)解。解：解：原問(wèn)題的對(duì)偶問(wèn)題為：原問(wèn)題的