我的運籌學(xué)課件wang-對偶理論與靈敏度分析

1、 線性規(guī)劃的對偶模型線性規(guī)劃的對偶模型 對偶性質(zhì)對偶性質(zhì) 對偶問題的經(jīng)濟(jì)解釋影子價格對偶問題的經(jīng)濟(jì)解釋影子價格 對偶單純形法對偶單純形法 靈敏度分析靈敏度分析 對偶理論是線性規(guī)劃的重要內(nèi)容之一。隨著線性規(guī)劃問題研究對偶理論是線性規(guī)劃的重要內(nèi)容之一。隨著線性規(guī)劃問題研究的深入，人們發(fā)現(xiàn)對應(yīng)于每個線性規(guī)劃問題都伴生一個相應(yīng)的線性的深入，人們發(fā)現(xiàn)對應(yīng)于每個線性規(guī)劃問題都伴生一個相應(yīng)的線性規(guī)劃問題。規(guī)劃問題。 前者是由矩陣，右端向量和價值向量定義的，稱之為原前者是由矩陣，右端向量和價值向量定義的，稱之為原問題；問題； 后者也是由相同的數(shù)據(jù)集合，和構(gòu)成的，稱之為原問題后者也是由相同的數(shù)據(jù)集合，和構(gòu)成的，

2、稱之為原問題的對偶問題。的對偶問題。 一對原問題和對偶問題是緊密關(guān)聯(lián)的，它們不但有相同的數(shù)據(jù)一對原問題和對偶問題是緊密關(guān)聯(lián)的，它們不但有相同的數(shù)據(jù)集合，相同的最優(yōu)目標(biāo)函數(shù)值，而且在求得一個線性規(guī)劃的最優(yōu)解集合，相同的最優(yōu)目標(biāo)函數(shù)值，而且在求得一個線性規(guī)劃的最優(yōu)解的同時，也同步得到對偶線性規(guī)劃的最優(yōu)解。對偶理論深刻地指示的同時，也同步得到對偶線性規(guī)劃的最優(yōu)解。對偶理論深刻地指示了原問題和對偶問題的內(nèi)在聯(lián)系，由對偶問題引伸出來的對偶解還了原問題和對偶問題的內(nèi)在聯(lián)系，由對偶問題引伸出來的對偶解還有著重要的經(jīng)濟(jì)意義，是研究經(jīng)濟(jì)學(xué)的重要概念和工具之一。有著重要的經(jīng)濟(jì)意義，是研究經(jīng)濟(jì)學(xué)的重要概念和工具之一

3、。 設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需設(shè)某工廠生產(chǎn)兩種產(chǎn)品甲和乙，生產(chǎn)中需4種設(shè)備種設(shè)備按按A，B，C，D順序加工順序加工，每件產(chǎn)品加工所需的機(jī)時數(shù)、每件產(chǎn)品的利潤，每件產(chǎn)品加工所需的機(jī)時數(shù)、每件產(chǎn)品的利潤值及每種設(shè)備的可利用機(jī)時數(shù)列于下表值及每種設(shè)備的可利用機(jī)時數(shù)列于下表 ：產(chǎn)品數(shù)據(jù)表產(chǎn)品數(shù)據(jù)表 設(shè)備設(shè)備產(chǎn)品產(chǎn)品ABCD產(chǎn)品利潤產(chǎn)品利潤（元件）（元件） 甲甲 21402乙乙 22043設(shè)備可利用設(shè)備可利用機(jī)時數(shù)（時）機(jī)時數(shù)（時） 1281612問：充分利用設(shè)備機(jī)時，工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能問：充分利用設(shè)備機(jī)時，工廠應(yīng)生產(chǎn)甲和乙型產(chǎn)品各多少件才能獲得最大利潤？獲得最大利潤？1. 解

4、：設(shè)甲、乙型產(chǎn)品各生產(chǎn)解：設(shè)甲、乙型產(chǎn)品各生產(chǎn)x1及及x2件，則數(shù)學(xué)模型為：件，則數(shù)學(xué)模型為： 0,124164821222.32max2121212121xxxxxxxxtsxxz反過來問：若反過來問：若工廠決策者工廠決策者決定決定不再自己生產(chǎn)甲、乙產(chǎn)品，而不再自己生產(chǎn)甲、乙產(chǎn)品，而是把各種設(shè)備的有限機(jī)時數(shù)是把各種設(shè)備的有限機(jī)時數(shù)租讓給租讓給其他工廠使用，這時工廠其他工廠使用，這時工廠的決策者應(yīng)該的決策者應(yīng)該如何確定各種設(shè)備的租價如何確定各種設(shè)備的租價，才是最佳決策？，才是最佳決策？在市場競爭的時代，廠長的最佳決策顯然應(yīng)符合兩條：在市場競爭的時代，廠長的最佳決策顯然應(yīng)符合兩條：（1）不吃虧原

5、則不吃虧原則。把設(shè)備租出去所獲得的租金不應(yīng)低于利用這把設(shè)備租出去所獲得的租金不應(yīng)低于利用這些設(shè)備自行生產(chǎn)所獲得的利潤些設(shè)備自行生產(chǎn)所獲得的利潤。由此原則，便構(gòu)成了新規(guī)劃的不。由此原則，便構(gòu)成了新規(guī)劃的不等式約束條件。等式約束條件。 （2）競爭性原則競爭性原則。即在上述不吃虧原則下，盡量降低機(jī)時總收。即在上述不吃虧原則下，盡量降低機(jī)時總收費，以便爭取更多用戶。費，以便爭取更多用戶。設(shè)設(shè)A、B、C、D設(shè)備的機(jī)時價分別為設(shè)備的機(jī)時價分別為y1、y2、y3、y4，則新的線性，則新的線性規(guī)劃數(shù)學(xué)模型為：規(guī)劃數(shù)學(xué)模型為： 0,340222042.1216812min4321432143214321yyyy

6、yyyyyyyytsyyyy把同種問題的兩種提法所獲得的數(shù)學(xué)模型用表把同種問題的兩種提法所獲得的數(shù)學(xué)模型用表2表示，將會發(fā)表示，將會發(fā)現(xiàn)一個有趣的現(xiàn)象?，F(xiàn)一個有趣的現(xiàn)象。原問題與對偶問題對比表原問題與對偶問題對比表A（y1） B（y2）C（y3） D（y4） 甲（甲（x1） 21402乙（乙（x2） 220431281612 min max z 對偶性是線性規(guī)劃問題的最重要的內(nèi)容之一。每一個線性規(guī)劃（對偶性是線性規(guī)劃問題的最重要的內(nèi)容之一。每一個線性規(guī)劃（ LP ）必然有與之相伴而生的另一個線性規(guī)劃問題，即任何一個求必然有與之相伴而生的另一個線性規(guī)劃問題，即任何一個求 maxZ 的的LP都都有

7、一個求有一個求 minZ 的的LP。其中的一個問題叫。其中的一個問題叫“原問題原問題”，記為，記為“P”，另一個，另一個稱為稱為“對偶問題對偶問題”，記為，記為“D”。2. 0,124164821222.32max2121212121xxxxxxxxtsxxz 0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy原問題原問題-P對偶問題對偶問題-D23x1x2原問題原問題12y122128y212816y3401612y40412對偶問題對偶問題23（1）對稱形式）對稱形式特點：目標(biāo)函數(shù)求極大值時，所有約束條件為特點：目標(biāo)函數(shù)求極大值

8、時，所有約束條件為號，變號，變量非負(fù)量非負(fù);目標(biāo)函數(shù)求極小值時，所有約束條件為目標(biāo)函數(shù)求極小值時，所有約束條件為號，變量非號，變量非負(fù)負(fù).0XbAXCXmaxZ ：PTT : minA YCY0TDWY b原問題原問題對偶問題對偶問題目標(biāo)函數(shù)目標(biāo)函數(shù)maxmin約束條件約束條件變量數(shù)量變量數(shù)量約束條件個數(shù)約束條件個數(shù)約束條件個數(shù)約束條件個數(shù)變量數(shù)量變量數(shù)量例例2.1 寫出線性規(guī)劃問題的對偶問題寫出線性規(guī)劃問題的對偶問題 0,5643 7 32 532432max321321321321321xxxxxxxxxxxxxxxZ解：首先將原問題變形為對稱形式解：首先將原問題變形為對稱形式 0,5 6

9、4 3 7 32532432max32132132132321xxxxxxxxxxxxxxxZ 注意：注意：以后不強(qiáng)調(diào)等以后不強(qiáng)調(diào)等式右段項式右段項 b b00，原因在對，原因在對偶單純型表中只保證偶單純型表中只保證 而不保證而不保證 ，故，故 b b可以是負(fù)數(shù)?？梢允秦?fù)數(shù)。0 j 01 bB 0,4675343232 532min 321321321321321yyyyyyyyyyyyyyyW對對偶偶問問題題：(2) 非對稱型對偶問題非對稱型對偶問題若給出的線性規(guī)劃不是對稱形式，可以先化成對稱形式若給出的線性規(guī)劃不是對稱形式，可以先化成對稱形式再寫對偶問題。再寫對偶問題。也可直接也可直接按教

10、材表按教材表2-2中的對應(yīng)關(guān)系中的對應(yīng)關(guān)系寫出非對寫出非對稱形式的對偶問題稱形式的對偶問題。原問題原問題（或?qū)ε紗栴}）（或?qū)ε紗栴}）對偶問題對偶問題（或原問題）（或原問題）目標(biāo)函數(shù)目標(biāo)函數(shù) max目標(biāo)函數(shù)目標(biāo)函數(shù) min約約束束條條件件m個個m個個變變量量0000= =無約束無約束變變量量n個個n個個約約束束條條件件0000無約束無約束= =b b約束條件右端項約束條件右端項目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)C C目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項約束條件右端項例例2.2 寫出下列線性規(guī)劃問題的對偶問題寫出下列線性規(guī)劃問題的對偶問題. 0,5643732532432max32

11、1321321321321xxxxxxxxxxxxxxxZ解：原問題的對偶問題為解：原問題的對偶問題為123123123123123m in2352323435764,Wyyyyyyyyyyyyyyy 無約束無約束例例2.3 寫出下列線性規(guī)劃問題的對偶問題寫出下列線性規(guī)劃問題的對偶問題. 無無約約束束4321432142143214321, 0, 06 43 247 23 523 4 532maxxxxxxxxxxxxxxxxxxxxZ解：原問題的對偶問題為解：原問題的對偶問題為 無無約約束束32132131321321321,0,01 72 54 3332 2234 645minyyyyyy

12、yyyyyyyyyyyW例例2.4無約束、，4321432143243214321321321321321321 , 002473254334324323min20,5643732532422min. 1xxxxxxxxxxxxxxxxxxxZ. xxxxxxxxxxxxxxxZ 無約束無約束答案：答案：32132132132131321321321321321321y0,y0,y44y4y4y 37y3y3y 23yy 2y32y y 253max. 2 0.yy0,y46y7y5y24yy 3y2y 3y2y 532max. 1yyyWyyyW性質(zhì)性質(zhì)1 1 對稱性定理對稱性定理：對偶問題

13、的對偶是原問題：對偶問題的對偶是原問題minZ=-CXs.t.-AX -bX0minW=Ybs.t.AYCY0maxZ=CXs.t.AX bX0對偶的定義對偶的定義對偶的定義對偶的定義maxW=-Ybs.t.-AY-CY 0性質(zhì)性質(zhì)2 2 弱對偶原理弱對偶原理( (弱對偶性弱對偶性) )：設(shè)設(shè) 和和 分別是問題分別是問題(P)(P)和和(D)(D)的可行解，則必有的可行解，則必有0X0Y njmiiijjbyxcbYCX1100即即：推論推論1: 原問題任一可行解的目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值原問題任一可行解的目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值的下界；反之，對偶問題任意可行解的目標(biāo)函數(shù)值是其

14、原問題目的下界；反之，對偶問題任意可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。標(biāo)函數(shù)值的上界。推論推論2: 在一對對偶問題（在一對對偶問題（P）和（）和（D）中，若其中一個問題可行）中，若其中一個問題可行但目標(biāo)函數(shù)無界，則另一個問題無可行解（但目標(biāo)函數(shù)無界，則另一個問題無可行解（如果原問題沒有上界，如果原問題沒有上界，即即maxZ+，則對偶問題不可行。如果對偶問題沒有下界，即，則對偶問題不可行。如果對偶問題沒有下界，即minW-，則原問題不可行，則原問題不可行 ）；）；反之不成立反之不成立(即無可行解的原因即無可行解的原因有二）有二）。這也是對偶問題的無界性。這也是對偶問題的無界性。 0,0

15、24 2max21212121xxxxxxxxZ無界無界（原）（原） 0,012 24min21212121yyyyyyyyW無可無可行解行解（對）（對）關(guān)于無界性有如下結(jié)論：關(guān)于無界性有如下結(jié)論：問題無界問題無界無可行解無可行解無可行解無可行解問題無界問題無界對偶問題對偶問題原問題原問題例例2.5推論推論3 3：在一對對偶問題（在一對對偶問題（P）和（）和（D）中，若一個可行（如）中，若一個可行（如P），而另一個不可行（如），而另一個不可行（如D），則該可行的問題目標(biāo)函數(shù)），則該可行的問題目標(biāo)函數(shù)值無界。值無界。 02023220322 432max41432143214321xxxxxxx

16、xxxxxxZ試估計它們目標(biāo)函數(shù)的界，并驗證弱對偶性原理。試估計它們目標(biāo)函數(shù)的界，并驗證弱對偶性原理。（P）例例2.6解：解： 0,04233322 212 2020min212121212121yyyyyyyyyyyyW（D） 由觀察可知：由觀察可知： =（1.1.1.1），）， =（1.1），分別），分別是（是（P）和（）和（D）的可行解。）的可行解。Z=10 ，W=40，故有，故有 ，弱對偶定理成立。由推論，弱對偶定理成立。由推論可知，可知，W 的的最小值不能小于最小值不能小于10，Z 的最大值不能超過的最大值不能超過40。_XCbY_X_Y性質(zhì)性質(zhì)3 最優(yōu)性定理最優(yōu)性定理：如果如果 是

17、原問題的可行解，是原問題的可行解， 是其對偶是其對偶問題的可行解，并且問題的可行解，并且:0X0Ywz:00即即BYCX 則則 是原問題的最優(yōu)解，是原問題的最優(yōu)解， 是其對偶問題的最優(yōu)解。是其對偶問題的最優(yōu)解。0X0Y 例如例如:在一對對偶問題（在一對對偶問題（P）和（）和（D）中，可找到）中，可找到 X*=（0.0.4.4），）， Y*=（1.2，0.2）,且且Z=W=28 ，則則X*，Y*分別是分別是 P和和D 的最優(yōu)解。的最優(yōu)解。性質(zhì)性質(zhì)4 強(qiáng)對偶性強(qiáng)對偶性：若原問題及其對偶問題均具有可行解，則兩若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。者均具有

18、最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。-1BY=CB（還可推出另一結(jié)論：若（還可推出另一結(jié)論：若（LP）與（）與（DP）都有可行解，則兩者都）都有可行解，則兩者都有最優(yōu)解，若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。）有最優(yōu)解，若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。）推論推論 若原問題有一個對應(yīng)于基的最優(yōu)解，那么此時的單純?nèi)粼瓎栴}有一個對應(yīng)于基的最優(yōu)解，那么此時的單純形乘子是對偶問題的一個最優(yōu)解。形乘子是對偶問題的一個最優(yōu)解。根據(jù)這個推論我們根據(jù)這個推論我們可以在原問題的最優(yōu)單純形表中直接找可以在原問題的最優(yōu)單純形表中直接找到對偶問題的最優(yōu)解到對偶問題的最優(yōu)解，即松弛變量檢驗數(shù)的相反數(shù)，即松

19、弛變量檢驗數(shù)的相反數(shù) 。 -1BY=C B對偶問題可改寫為原問題的檢驗數(shù)對應(yīng)對偶問題的一個基本解。原問題的檢驗數(shù)對應(yīng)對偶問題的一個基本解。證明：設(shè)是原問題的一個可行基，證明：設(shè)是原問題的一個可行基，且且則原問題可以寫為則原問題可以寫為BBNNBNSBNSmaxZ=C X+C XBX+NX+X =bX ,X,X01212SSBNSSminW=YbY(B,N)-(Y ,Y )=(C ,C )Y,Y ,Y01212SBSNSSminW =YbYB-Y=CYN-Y=CY,Y,Y0其中其中 分別為原問題決策變量中基變量和非基變量所對應(yīng)的對偶約束分別為原問題決策變量中基變量和非基變量所對應(yīng)的對偶約束的剩余

20、變量。的剩余變量。 對偶問題也可等價表示為：對偶問題也可等價表示為：12SSY ,YA=(B,N)對原問題可行基，對原問題可行基，可得可行解可得可行解對應(yīng)于的檢驗數(shù)分別為對應(yīng)于的檢驗數(shù)分別為。不難驗證，不難驗證，為對偶問題的一個基本解。為對偶問題的一個基本解。-1BX =B bBNSX ,X ,X-1-1NBB0,C -C B N,-C B12-1-1BSSNBY=C B ,Y =0,Y =-(C -C B N)例例 利用單純形表求原問題的最優(yōu)解，并由最優(yōu)單純利用單純形表求原問題的最優(yōu)解，并由最優(yōu)單純形表推出對偶問題的最優(yōu)解。形表推出對偶問題的最優(yōu)解。解：原問題線性規(guī)劃模型為：解：原問題線性規(guī)

21、劃模型為：引入松弛變量，引入松弛變量，化標(biāo)準(zhǔn)形得化標(biāo)準(zhǔn)形得: :12123124125jmaxZ=32x +30 x3x +4x +x =365x +4x +x =409x +8x +x =76x0,j=1.51212121212maxZ=32x +30 x3x +4x365x +4x409x +8x76x0,x0345x ,x ,x32282 1 0 -2/3 0 1/34/3X132 0 0 1/3 1 -2/33/4X404/2 1 0 0 2 -14X1324/3 0 0 1 3 -24X308/4/5 1 4/5 0 1/5 08X13212/8/5 0 8/5 1 -3/5 012

22、X3040/5 5 4 0 1 040X4036/3 3 4 1 0 036X30 0 0 -7/6 0 -19/6Z 0 1 3/4 0 -1/48X230 0 0 0 7/2 -11/2278Z 0 1 0 -9/4 5/45X230 0 22/5 0 -32/5 0256Z4/4/5 0 4/5 0 -9/5 14X50 32 30 0 0 00Z76/9 9 8 0 0 176X50 X1 X2 X3 X4 X5bXBCB 32 30 0 0 0 C32282由最優(yōu)表可知，原問題最優(yōu)解由最優(yōu)表可知，原問題最優(yōu)解同時不難得到同時不難得到原問題的最優(yōu)基原問題的最優(yōu)基由強(qiáng)對偶定理的推論可得此

23、時的單純形乘子由強(qiáng)對偶定理的推論可得此時的單純形乘子 為對偶問題的最優(yōu)解為對偶問題的最優(yōu)解, ,即松弛變量檢驗數(shù)即松弛變量檢驗數(shù)的相反數(shù)。的相反數(shù)。 4, 12034B=(P P,P 121B03331044C3230000CBXBbX1X2X3X4X603230X4X1X23/44/38001/31-2/310-2/301/3013/40-1/4Z00-7/60-19/6*43X =(,8,0,0)34322822maxZ=282312123124125jmaxZ=32x +30 x3x +4x +x =365x +4x +x =409x +8x +x =76x0,

24、j=1.5*-1B719Y =C B(,0,)66性質(zhì)性質(zhì)5 互補(bǔ)松弛性互補(bǔ)松弛性：設(shè)設(shè)X0和和Y0分別是分別是P問題問題 和和 D問題問題 的可行的可行解，則它們分別是最優(yōu)解的充要條件是：解，則它們分別是最優(yōu)解的充要條件是： 000ss0XYXY其中：其中：Xs、Ys為松弛變量（為松弛變量（松馳變量松馳變量*對偶變量對偶變量=0）性質(zhì)性質(zhì)5的應(yīng)用：的應(yīng)用：該性質(zhì)給出了已知一個問題最優(yōu)解求另一個問題最優(yōu)該性質(zhì)給出了已知一個問題最優(yōu)解求另一個問題最優(yōu)解的方法解的方法，即已知，即已知Y求求X或已知或已知X求求Y 00ssXYXY互補(bǔ)松弛條件互補(bǔ)松弛條件由于松弛變量都非負(fù)，要使求和式等于零，則必定每

25、一分量為由于松弛變量都非負(fù)，要使求和式等于零，則必定每一分量為零，因而有下列關(guān)系：零，因而有下列關(guān)系：若若Y0，則，則Xs必為必為0；若；若X0，則，則Ys必為必為0利用上述關(guān)系，建立對偶問題（或原問題）的約束線性方程組，利用上述關(guān)系，建立對偶問題（或原問題）的約束線性方程組，方程組的解即為最優(yōu)解。方程組的解即為最優(yōu)解。例例2.7已知線性規(guī)劃已知線性規(guī)劃 3 , 2 , 1, 0162210243max321321321jxxxxxxxxxxzj的最優(yōu)解是的最優(yōu)解是X=(6,2,0)T,求其對偶問題的最優(yōu)解求其對偶問題的最優(yōu)解Y。解：寫出原問題的對偶問題，即解：寫出原問題的對偶問題，即 0,1

26、422321610min2121212121yyyyyyyyyyw1212312412512345min1016232241,0wyy yyy yy y yy yyyyyy 標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化設(shè)對偶問題最優(yōu)解為設(shè)對偶問題最優(yōu)解為Y(y1，y2),由互補(bǔ)松弛性定理可知，由互補(bǔ)松弛性定理可知，X和和 Y滿足：滿足：00 ssXYXY即：即：0),)(,(0),)(,(5421321543 TTxxyyxxxyyy因為因為X1=60，X2=20，所以，所以對偶問題的第一、二個約束的對偶問題的第一、二個約束的松弛變量等于零松弛變量等于零，即，即y30，y40，帶入方程中：，帶入方程中： 422322121y

27、yyy解此線性方程組得解此線性方程組得y1=1,y2=1,從而對偶問題的最優(yōu)解為：從而對偶問題的最優(yōu)解為：Y=(1,1)，最優(yōu)值，最優(yōu)值w=26。例例2.8 已知線性規(guī)劃已知線性規(guī)劃 無約束無約束321321321321, 0, 06422minxxxxxxxxxxxxz的對偶問題的最優(yōu)解為的對偶問題的最優(yōu)解為Y=(0,-2)，求原問題的最優(yōu)解。，求原問題的最優(yōu)解。解解: 對偶問題是對偶問題是 021264max2121212121yyyyyyyyyyw無約，無約，標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化 121231241252341max462120,0，5wyyyyy yy y yy +y yyyyy無約束無約束設(shè)

28、對偶問題最優(yōu)解為設(shè)對偶問題最優(yōu)解為X(x1，x2 ，x3)T ,由互補(bǔ)松弛性定理由互補(bǔ)松弛性定理可知，可知，X和和 Y滿足：滿足：0),)(,(0),)(,(5421321543 TTxxyyxxxyyy將將Y =(0,-2)帶入由方程可知，帶入由方程可知，y3y50，y41。 y2=-20 x50又又y4=10 x20將將x2，x5分別帶入原問題約束方程中，得：分別帶入原問題約束方程中，得： 643131xxxx解方程組得：解方程組得：x1=-5,x3=-1, 所以原問題的最優(yōu)解為所以原問題的最優(yōu)解為X=(-5,0,-1)，最優(yōu)值，最優(yōu)值z=-12原問題與對偶問題解的對應(yīng)關(guān)系小結(jié)原問題與對偶

29、問題解的對應(yīng)關(guān)系小結(jié)對應(yīng)關(guān)系對應(yīng)關(guān)系原問題原問題最優(yōu)解最優(yōu)解無界解無界解無可行解無可行解對偶問題對偶問題最優(yōu)解最優(yōu)解(Y,Y)(N,N)無界解無界解(Y,Y)無可行解無可行解(Y,Y)無法判斷無法判斷1. 影子價格的數(shù)學(xué)分析：影子價格的數(shù)學(xué)分析：0D0minmaxYCYAXbAXPbYW CX Z定義：在一對定義：在一對 P 和和 D 中，若中，若 P 的某個約束條件的右端項常的某個約束條件的右端項常數(shù)數(shù)bi （第第i種資源的擁有量種資源的擁有量）增加一個單位時，所引起目標(biāo)）增加一個單位時，所引起目標(biāo)函數(shù)最優(yōu)值函數(shù)最優(yōu)值z* 的改變量稱為的改變量稱為第第 i 種資源的影子價格種資源的影子價格，

30、其值等，其值等于于D問題中對偶變量問題中對偶變量yi*。由強(qiáng)對偶定理可知，如果原問題有最優(yōu)解，那么對偶由強(qiáng)對偶定理可知，如果原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，而且它們的目標(biāo)函數(shù)值相等，即有：問題也有最優(yōu)解，而且它們的目標(biāo)函數(shù)值相等，即有：其中是線性規(guī)劃原問題約束條件的右端其中是線性規(guī)劃原問題約束條件的右端數(shù)據(jù)向量，它代表各種資源的擁有量。數(shù)據(jù)向量，它代表各種資源的擁有量。為對偶問題最優(yōu)解，它為對偶問題最優(yōu)解，它代表在資源最優(yōu)代表在資源最優(yōu)利用條件下對各種單位資源的估價利用條件下對各種單位資源的估價，這種估計不是資源的市場，這種估計不是資源的市場價格，而是根據(jù)資源在生產(chǎn)中所作出的貢獻(xiàn)（如創(chuàng)

31、造利潤、產(chǎn)價格，而是根據(jù)資源在生產(chǎn)中所作出的貢獻(xiàn)（如創(chuàng)造利潤、產(chǎn)值等）而作出估價。值等）而作出估價。*X*Y*1122mmZ=CX =Y b=y by by b12mb=(b ,b ,b )T*12mY =(y ,y ,y )2. 影子價格的經(jīng)濟(jì)意義影子價格的經(jīng)濟(jì)意義1）影子價格是一種邊際價格）影子價格是一種邊際價格在其它條件不變的情況下，單位資源數(shù)量的變化所引在其它條件不變的情況下，單位資源數(shù)量的變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化。即對偶變量起的目標(biāo)函數(shù)最優(yōu)值的變化。即對偶變量yi 就是第就是第 i 種資源種資源的影子價格。即：的影子價格。即： )2 , 1(*miybZii 2）影子價格是一

32、種機(jī)會成本）影子價格是一種機(jī)會成本在市場經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場價格低于影子在市場經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場價格低于影子價格時，企業(yè)應(yīng)買進(jìn)這種資源用于擴(kuò)大生產(chǎn)；相反當(dāng)某價格時，企業(yè)應(yīng)買進(jìn)這種資源用于擴(kuò)大生產(chǎn)；相反當(dāng)某種資源的市場價格高于影子價格時，企業(yè)應(yīng)賣出這種資種資源的市場價格高于影子價格時，企業(yè)應(yīng)賣出這種資源。隨著資源的買進(jìn)賣出，企業(yè)資源的影子價格也將隨源。隨著資源的買進(jìn)賣出，企業(yè)資源的影子價格也將隨之發(fā)生變化，一直到影子價格與市場價格保持同等水平之發(fā)生變化，一直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。時，才處于平衡狀態(tài)。影子價格的大小客觀地反映了各種不同資源在系統(tǒng)內(nèi)

33、的影子價格的大小客觀地反映了各種不同資源在系統(tǒng)內(nèi)的稀缺程度稀缺程度。如果第。如果第i i種資源供大于求，即在達(dá)到最優(yōu)解時，種資源供大于求，即在達(dá)到最優(yōu)解時，該種資源沒有用完，或松弛變量，由互補(bǔ)松弛定理，該種資源沒有用完，或松弛變量，由互補(bǔ)松弛定理，在對偶最優(yōu)解中，第在對偶最優(yōu)解中，第ii種資源的影子價格。反之種資源的影子價格。反之如果第如果第ii種資源的影子價格種資源的影子價格 ，那么由互補(bǔ)松弛定理，那么由互補(bǔ)松弛定理，原問題的第原問題的第i i個約束為嚴(yán)格等式，即，這表明第個約束為嚴(yán)格等式，即，這表明第ii種資種資源已經(jīng)用完，成為稀缺資源。源已經(jīng)用完，成為稀缺資源。 *Yiu0*iy0iu0

34、*iy03）影子價格在資源利用中的應(yīng)用）影子價格在資源利用中的應(yīng)用4）影子價格對單純形表計算的解釋）影子價格對單純形表計算的解釋單純形表中的檢驗數(shù)單純形表中的檢驗數(shù) miiijjjBjjyacPBCc11其中其中c cj j表示第表示第j j種產(chǎn)品的價格種產(chǎn)品的價格; ; 表示生產(chǎn)該種產(chǎn)品所消耗表示生產(chǎn)該種產(chǎn)品所消耗的各項資源的影子價格的總和的各項資源的影子價格的總和, ,即產(chǎn)品的即產(chǎn)品的隱含成本隱含成本。 miiijya1當(dāng)產(chǎn)值大于隱含成本時，即當(dāng)產(chǎn)值大于隱含成本時，即 ，表明生產(chǎn)該項產(chǎn)品有，表明生產(chǎn)該項產(chǎn)品有利，可在計劃中安排；否則利，可在計劃中安排；否則 ，用這些資源生產(chǎn)別的，用這些資源

35、生產(chǎn)別的產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。0 j 0 j 12123124125jmaxZ=32x +30 x3x +4x +x =365x +4x +x =409x +8x +x =76x0,j=1.5設(shè)備設(shè)備每噸產(chǎn)品的加工臺時每噸產(chǎn)品的加工臺時 可供臺時數(shù)可供臺時數(shù) 甲甲 乙乙 A AB BC C 3 35 59 9 4 44 48 8 3636404076 76 利潤（元利潤（元/ /噸）噸） 32 32 30 30 例例4*X=(,8)3T2maxZ=2823719*Y =(,0,)66對偶最優(yōu)解對偶最優(yōu)解其中為設(shè)備其中為設(shè)備A A的影子價格，的影子價

36、格，在資源最優(yōu)利用的條件下，設(shè)備在資源最優(yōu)利用的條件下，設(shè)備A A每增加每增加一個單位臺時，可以使總利潤增加元。一個單位臺時，可以使總利潤增加元。若設(shè)備可供臺時數(shù)，則若設(shè)備可供臺時數(shù)，則*17y =67623*X=(,8)34T5maxZ=2836 對偶單純形法是求解線性規(guī)劃的另一個基本方法。它是對偶單純形法是求解線性規(guī)劃的另一個基本方法。它是根據(jù)對偶原理和單純形法原理而設(shè)計出來的，因此稱為對根據(jù)對偶原理和單純形法原理而設(shè)計出來的，因此稱為對偶單純形法。不要簡單理解為是求解對偶問題的單純形法。偶單純形法。不要簡單理解為是求解對偶問題的單純形法。 找出一個對偶問題的可行基，找出一個對偶問題的可行

37、基，保持對偶問題為可行解保持對偶問題為可行解的的條件下，條件下，(即必須保持所有的檢驗數(shù)非正，同時取消原問題必即必須保持所有的檢驗數(shù)非正，同時取消原問題必須可行的要求，即須可行的要求，即取消常數(shù)列的非負(fù)限制取消常數(shù)列的非負(fù)限制)，判，判斷斷XB是否可行是否可行（XB=b為非負(fù)），有最優(yōu)解。否則，通過變換基解，直到找為非負(fù)），有最優(yōu)解。否則，通過變換基解，直到找到原問題基可行解（即到原問題基可行解（即XB為非負(fù)），這時原問題與對偶問題為非負(fù)），這時原問題與對偶問題同時達(dá)到可行解。同時達(dá)到可行解。找出一個找出一個DP的可行基的可行基LP是否可行是否可行（XB 0）保持保持DP為可行解情況下轉(zhuǎn)移到為

38、可行解情況下轉(zhuǎn)移到LP的另一個基本解的另一個基本解最優(yōu)解最優(yōu)解是是否否循循環(huán)環(huán)結(jié)束結(jié)束例例2.9 用對偶單純形法求解：用對偶單純形法求解： )3.2.1(0145 1232102215129min321321321321jxxxxxxxxxxxxxZj解解:（1）將模型轉(zhuǎn)化為求最大化問題，約束方程化為等式求將模型轉(zhuǎn)化為求最大化問題，約束方程化為等式求出一組基本解，因為對偶問題可行（求出一組基本解，因為對偶問題可行（求max問題）。問題）。 014 5 12 3210 2215129max61632153214321321xxxxxxxxxxxxxxxxZcj-9-12-15000bcBxBx1

39、x2x3x4x5x60 x4-2-2-1100-100 x5-2-3-1010-120 x6-1-1-5001-14j-9-12-150000icj-9-12-15000bcBxBx1x2x3x4x5x60 x4-9/5-9/5010-1/5-36/50 x5-9/5-14/5001-1/5-46/5-15x31/51/5100-1/514/5(-30/-9,-45/-14,-15/-1)-6-9000-342icj-9-12-15000bcBxBx1x2x3x4x5x60 x4-9/14001-9/14-1/14-9/7-12x29/14100-5/141/1423/7(-3/-9,-45/

40、-9,-33/-1)-15x31/140101/14-3/1415/7-3/14000-45/14-33/14ij j cj-9-12-15000cBxBx1x2x3x4x5x6b-9x1100-14/911/92-12x20101-102-15x30011/90-2/92000-1/3-3-7/3j 原問題的最優(yōu)解為：原問題的最優(yōu)解為：X*=（2 , 2 , 2 , 0 , 0 , 0），），Z* =72 由定理由定理4，其對偶問題的最優(yōu)解為：，其對偶問題的最優(yōu)解為：Y*= （1/3 , 3 , 7/3），），W*= 72 對偶單純形法應(yīng)注意的問題：對偶單純形法應(yīng)注意的問題： 用對偶單純形法

41、求解線性規(guī)劃是一種求解方法，而不是去求對偶用對偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對偶問題的最優(yōu)解問題的最優(yōu)解 初始表中一定要滿足對偶問題可行，也就是說檢驗數(shù)滿足最優(yōu)判初始表中一定要滿足對偶問題可行，也就是說檢驗數(shù)滿足最優(yōu)判別準(zhǔn)則別準(zhǔn)則 最小比值中最小比值中 的絕對值是使得比值非負(fù)，在極小化問題的絕對值是使得比值非負(fù)，在極小化問題 j j00，分母分母a aij ij0 0 這時必須取絕對值。在極大化問題中，這時必須取絕對值。在極大化問題中， j j00，分母，分母a aij ij00， 總滿足非負(fù)，這時絕對值符號不起作用，可以去掉。如總滿足非負(fù)，這時絕對值符號不起作用，可以去掉。

42、如在本例中將目標(biāo)函數(shù)寫成在本例中將目標(biāo)函數(shù)寫成ijja 這里這里 j j 0 0在求在求 k k時就可以不帶絕對值符號。時就可以不帶絕對值符號。32134maxxxxz ijja 對偶單純形法與普通單純形法的對偶單純形法與普通單純形法的換基順序不一樣換基順序不一樣，普通單純形法，普通單純形法是先確定進(jìn)基變量后確定出基變量，是先確定進(jìn)基變量后確定出基變量，對偶單純形法是先確定出基變對偶單純形法是先確定出基變量后確定進(jìn)基變量量后確定進(jìn)基變量； 普通單純形法的最小比值是普通單純形法的最小比值是 其目的是保證下一其目的是保證下一個原問題的基本解可行，個原問題的基本解可行，對偶單純形法的最小比值對偶單純

43、形法的最小比值是是 0minikikiiaab其目的是保證下一個對偶問題的基本解可行其目的是保證下一個對偶問題的基本解可行 0minljljjjaa 對偶單純形法在確定出基變量時，若不遵循對偶單純形法在確定出基變量時，若不遵循 規(guī)則，任選一個小于零的規(guī)則，任選一個小于零的b bii對應(yīng)的基變量出基，不影響計算結(jié)果，對應(yīng)的基變量出基，不影響計算結(jié)果，只是迭代次數(shù)可能不一樣。只是迭代次數(shù)可能不一樣。 0|min iilbbb-1BX =B b 一個標(biāo)準(zhǔn)形式的線性規(guī)劃問題可由約束矩陣，右端項向一個標(biāo)準(zhǔn)形式的線性規(guī)劃問題可由約束矩陣，右端項向量量b b，和價值向量完全確定，假如一個線性規(guī)劃問題對于給，

44、和價值向量完全確定，假如一個線性規(guī)劃問題對于給定的數(shù)據(jù)集合，定的數(shù)據(jù)集合，b b，有最優(yōu)解，則最優(yōu)解。最，有最優(yōu)解，則最優(yōu)解。最優(yōu)目標(biāo)函數(shù)值，其中為最優(yōu)基。優(yōu)目標(biāo)函數(shù)值，其中為最優(yōu)基。 但是線性規(guī)劃問題所對應(yīng)的數(shù)據(jù)集合，但是線性規(guī)劃問題所對應(yīng)的數(shù)據(jù)集合，b b，常常是通，常常是通過預(yù)測或估計所得到的統(tǒng)計數(shù)據(jù)，在實際使用中，不免會有一過預(yù)測或估計所得到的統(tǒng)計數(shù)據(jù)，在實際使用中，不免會有一定的誤差。而且隨著市場環(huán)境，工藝條件和資源數(shù)量的改變，定的誤差。而且隨著市場環(huán)境，工藝條件和資源數(shù)量的改變，這些數(shù)據(jù)完全可能發(fā)生變化。因此這些數(shù)據(jù)完全可能發(fā)生變化。因此有必要來分析一下當(dāng)這些數(shù)有必要來分析一下當(dāng)這

45、些數(shù)據(jù)發(fā)生波動時，對目前的最優(yōu)解，最優(yōu)值或者最優(yōu)基會產(chǎn)生什據(jù)發(fā)生波動時，對目前的最優(yōu)解，最優(yōu)值或者最優(yōu)基會產(chǎn)生什么影響，這就是所謂的靈敏度分析。么影響，這就是所謂的靈敏度分析。 -1BZ=C B b靈敏度分析主要討論如下二類問題：靈敏度分析主要討論如下二類問題：線性規(guī)劃的數(shù)據(jù)集合在什么范圍內(nèi)波動將不影響最優(yōu)解或最優(yōu)線性規(guī)劃的數(shù)據(jù)集合在什么范圍內(nèi)波動將不影響最優(yōu)解或最優(yōu)基？基？ 若最優(yōu)解發(fā)生變化，應(yīng)如何用最簡單的方法找到新的最優(yōu)解。若最優(yōu)解發(fā)生變化，應(yīng)如何用最簡單的方法找到新的最優(yōu)解。為討論方便，以下列出標(biāo)準(zhǔn)型線性規(guī)劃問題最優(yōu)單純形表的一般形為討論方便，以下列出標(biāo)準(zhǔn)型線性規(guī)劃問題最優(yōu)單純形表的一

46、般形式，式，其中其中B B為線性規(guī)劃問題的最優(yōu)基為線性規(guī)劃問題的最優(yōu)基：CC1 C2 Cn CB XB b x1 x2 xn CB1 XB1 B-1b B-1A=B-1(P1，P2，Pn) CB2 XB2 : : CBm XBm Z CBB-1b C-CBB-1A 11mjjijijBjica xcC B P 1jjP =BP1bBb線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(biāo)準(zhǔn)形式11max.1,2,0,1,2,LLnjjjnijjijjZc xa xbs timxjnm ax.0ZC XA Xbs tX令：令：例例1-11-1：某企業(yè)利用三種資源生產(chǎn)兩種產(chǎn)品的最優(yōu)計劃問題歸：某企業(yè)利用三種資源生

47、產(chǎn)兩種產(chǎn)品的最優(yōu)計劃問題歸結(jié)為下列線性規(guī)劃結(jié)為下列線性規(guī)劃 0,45 802903 45 max2121212121xxxxxxxxxxZ問題：問題：（1 1）確定）確定x x2 2的系數(shù)的系數(shù)c c2 2的變的變化范圍，使原最優(yōu)解保持最化范圍，使原最優(yōu)解保持最優(yōu)；優(yōu)；（2 2）若）若c c2 2=6=6，求新的最優(yōu)，求新的最優(yōu)計劃。計劃。 1212312412512m a x5439 028 04 5,0 Zxxxxx xx x x x xxxcj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12j000-1-3最 優(yōu) 表最 優(yōu)

48、 表如下：如下：4 = c25 05 = 52c2 0 5/2 c2 5cj5c2 000CBXBbx1x2x3x4x50 x3250012-55x1351001-1c2 x2 10 010-12j000c2 - 55 - 2c2最優(yōu)解最優(yōu)解X*=（35，10，25，0，0）保持不變。保持不變。（1）（2）Cj56000CBXBbx1x2x3x4x50 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/2用單純形法求解得。用單純

49、形法求解得。x1*=45/2，x2*=45/2，x4*=25/2，x3*= x5*=0，z*=405/2原料（公斤）原料（公斤）產(chǎn)品（萬件）產(chǎn)品（萬件）供應(yīng)量供應(yīng)量A B C DA B C D甲甲乙乙3 2 10 43 2 10 40 0 2 1/20 0 2 1/218183 3利潤（萬元利潤（萬元/ /萬件）萬件）9 8 50 199 8 50 19問應(yīng)該怎樣組織生產(chǎn)，才能使總利潤最大，問應(yīng)該怎樣組織生產(chǎn)，才能使總利潤最大，若產(chǎn)品或的利潤產(chǎn)若產(chǎn)品或的利潤產(chǎn)生波動，波動范圍多大時，原最優(yōu)解保持不變生波動，波動范圍多大時，原最優(yōu)解保持不變？解解：設(shè)生產(chǎn)，四種產(chǎn)品設(shè)生產(chǎn)，四種產(chǎn)品各萬件，則此問題

50、的各萬件，則此問題的線性規(guī)劃模型為：線性規(guī)劃模型為：1234x ,x ,x ,x123412341342jmaxZ=9x +8x +50 x +19x3x +2x +10 x +4x182x +x3x0,j=1,2,3,4標(biāo)準(zhǔn)化，引入松弛變量標(biāo)準(zhǔn)化，引入松弛變量x x5 5,x,x6 6， 利用單純形表求解：利用單純形表求解：-4 -2/3 0 0 -13/3 -10/388Z2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/321X4X319500 2 0 2 -3 -1084Z261 2/3 0 1/2 1/3 -5/3 0 0 1 1/4 0 1/213/

51、2X1X39509 8 0 13/2 0 -2575Z1-3 2 0 3/2 1 -5 0 0 1 1/4 0 1/233/2X5X30509 8 50 19 0 00Z9/53/23 2 10 4 1 0 0 0 2 1/2 0 1183X5X600X1 X2 X3 X4 X5 X6BXBCB9 8 50 19 0 0C即最優(yōu)生產(chǎn)方案是生產(chǎn)產(chǎn)品即最優(yōu)生產(chǎn)方案是生產(chǎn)產(chǎn)品1 1萬件，產(chǎn)品萬件，產(chǎn)品2 2萬件，萬件，不生產(chǎn)不生產(chǎn), ,兩種產(chǎn)品。可得最大利潤為兩種產(chǎn)品。可得最大利潤為8888萬元。萬元。 *X =(0,0,1,2) ,maxZ=88TC 9 8 50 19 0 0CBXBBX1 X2

52、 X3 X4 X5 X 61950X4X321 2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/3Z88 -4 -2/3 0 0 -13/3 -10/3最優(yōu)表：最優(yōu)表：(1)1)若產(chǎn)品的利潤，有改變量。因為為非基變量，若產(chǎn)品的利潤，有改變量。因為為非基變量，推得推得 44或（萬元）時或（萬元）時原最優(yōu)解不變，最優(yōu)利潤值（萬元）也原最優(yōu)解不變，最優(yōu)利潤值（萬元）也不變。不變。1c91c1x-1BZ =C B b=881c13*X =(0,0,1,2)T( () )若產(chǎn)品的利潤若產(chǎn)品的利潤 ，有改變量。因為為基變量，有改變量。因為為基變量，推得推得3c503c3x

53、35c22 原最優(yōu)解不變，原最優(yōu)解不變，最優(yōu)利潤值最優(yōu)利潤值（萬元）（萬元）347.5c52-1B332Z =C B b=(19,50+ c )=88+ c1 1c即當(dāng)即當(dāng)時時XB= B1b例例2 2：對于上例中的線性規(guī)劃作下列分析：對于上例中的線性規(guī)劃作下列分析：（1 1）b b3 3在什么范圍內(nèi)變化，原最優(yōu)基不變？在什么范圍內(nèi)變化，原最優(yōu)基不變？（2 2）若）若b b3 3=55=55，求出新的最優(yōu)解。，求出新的最優(yōu)解。 0,45 802903 45Z max2121212121xxxxxxxxxxcj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14

54、 x2 10 010-12000-1-321-01105-21最優(yōu)基：最優(yōu)基：B=I=（P3，P1，P2）B1=最優(yōu)解：最優(yōu)解：X*=（35，10，25，0，0）（1）XB=B1b= 2 1- 01 1 05- 2 190803b80802333bb250 - 5b90803b=0 B1解得解得40b350，即當(dāng)，即當(dāng)b340，50 時，最優(yōu)基時，最優(yōu)基B 不變不變z*=5（80b3）+4（80+2b3） =80+3b3333b280b805b-250*2*1*3xxx=（2）當(dāng)當(dāng) b3= 55 時時 80802333250-5bbb 30 25 25=x2 x1x50-11/5-3/500j

55、0-1/52/51020 4 03/5-1/5013051-2/5-1/50050-32-1-5x50-1000j -101030 x2 4 100125x152100-25x30 x4x3x2x1bXBCB0045Cj最優(yōu)解：最優(yōu)解：X*=（30，20，0，0，5）1212312412512m a x5439 028 04 5,0 Zxxxxx xx x x x xxxcj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12j000-1-3最 優(yōu) 表最 優(yōu) 表如下：如下：三、增加一個變量三、增加一個變量 的分析的分析jx例例3 3

56、：（續(xù)例：（續(xù)例1 1）設(shè)企業(yè)研制了一種新產(chǎn)品，）設(shè)企業(yè)研制了一種新產(chǎn)品，對三種資源的消耗系數(shù)列向量以對三種資源的消耗系數(shù)列向量以P6表示表示P6= = 。問它。問它的價值系數(shù)的價值系數(shù)c c6 6符合什么條件才必須安排它的符合什么條件才必須安排它的生產(chǎn)？設(shè)生產(chǎn)？設(shè)c c6 6=3=3，新的最優(yōu)生產(chǎn)計劃是什么？，新的最優(yōu)生產(chǎn)計劃是什么？3/ 211/ 2 6=c6CBB1P6 =c6（0，5，4） = c65/202/116P21-01105-212/112/302/11=B1P6 =Cj540003CBXBbx1x2x3x4x5x60 x3250012-515x1351001-11/24x2

57、 10 010-120j 000-1-31/23x6250012-515x145/210-1/203/204 x2 10 010-120j00-1/2-2-1/201212312412512m a x5439 028 04 5,0 Zxxxxx xx x x x xxxcj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12j000-1-3最 優(yōu) 表最 優(yōu) 表如下：如下：四、四、 增加新的約束條件的分析（直接添加到最終單純形表中）增加新的約束條件的分析（直接添加到最終單純形表中）例例4: 4: 假設(shè)在例假設(shè)在例1 1中，還要考慮一個

58、新的資源約束：中，還要考慮一個新的資源約束： 4x4x1 1+2x+2x2 2150150121212121212max543902804215045,0 zxxxxxx x xxxxx12123124125122516346max54394028045,00215 zxxxxx xx x x x x x x xxx xxxx標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化cj540000CBXBbx1x2x3x4x5x60 x3250012-505x1351001-104 x2 10 010-1200 x6150420001000-1-30Cj540000CBXBbx1x2x3x4x5x60 x3250012-505x1351

59、001-104x210010-1200 x6 150 420001j 000-1-300 x3250012-505x1351001-104x210010-1200 x6 -10 000-201j000-3-300 x3150010-515x1301000-11/24x21501002-1/20 x4 5 00010-1/2j0000-3-1/21212312412512m a x5439 028 04 5,0 Zxxxxx xx x x x xxxcj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12j000-1-3最 優(yōu) 表最 優(yōu) 表如下：如下：1. c1. cj j和和b bi i同時變化的情況同時變化的情況五、五、 其它變化情況的分析其它變化情況的分析例例5: 5: 在例在例1 1中，假定中，假定c c2 2由由4 4上升為上升為6 6，b b3 3增加到增加到5555，試問最優(yōu)，試問最優(yōu)解將會發(fā)生什么變化？解將會發(fā)生什么變化？1212121212max5439028045,0 zxxxxxx x xx x21-01105-21B1= B