《運(yùn)籌學(xué)教程》第三章習(xí)題答案

1.影子價(jià)格是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而做的估價(jià)。它是一種邊際價(jià)格，其值相當(dāng)于在資源得到最有效利用的生產(chǎn)條件下，資源每變化一個(gè)單位時(shí)目標(biāo)函數(shù)的增量變化。又稱效率價(jià)格。影子價(jià)格是指社會(huì)處于某種最優(yōu)狀態(tài)下，能夠反映社會(huì)勞動(dòng)消耗、資源稀缺程度和最終產(chǎn)品需求狀況的價(jià)格，是社會(huì)對(duì)貨物真實(shí)價(jià)值的度量。只有在完善的市場(chǎng)條件下才會(huì)出現(xiàn)，然而這種完善的市場(chǎng)條件是不存在的，因此現(xiàn)成的影子價(jià)格也是不存在的。市場(chǎng)價(jià)格是物品和服務(wù)在市場(chǎng)上銷售的實(shí)際價(jià)格，是由供求關(guān)系決定的。2.證明：當(dāng)原問題約束條件右端變?yōu)閎i′時(shí)，原問題變?yōu)椋?/p>

maxz=∑CiXjs.t.

∑aijXi≤bi′(i=1,2,3,……,m)Xj≥0

(j=1,2,3,……,n)對(duì)偶問題為：

minp=∑bi′yis.t.

∑aijyi≥Ciyi≥0(i=1,2,3,……,m)(j=1,2,3,……,n)設(shè)，當(dāng)bi變?yōu)閎i′原問題有最優(yōu)解（X1′X2′X3′……Xn-1′Xn′）時(shí)，對(duì)偶問題的最優(yōu)解為（y1′y2′y3′……yn-1′yn′）,則有：又因?yàn)楫?dāng)原問題有最優(yōu)解時(shí)，對(duì)偶問題也有最優(yōu)解，且相等，則有：所以3（1）.minp=6y12y2s.t.

-y12y2≥-33y13y2≥4y1,y2≥0(2)解：令X2=X2′-X2〞，X4=X4′-X4〞，X2′，X2〞，X4′，X4〞≥0，原式化為：maxz=2X12X2′-2X2〞-5X32X4′-2X4〞s.t.

2X1-X2′X2〞3X33X4′-3X4〞≤-5-2X1X2′-X2〞-3X3-3X4′3X4〞≤5-6X1-5X2′5X2〞X3-5X4′5X4〞≤-610X1-9X2′9X2〞6X34X4′-4X4〞≤12X1,X2′，X2〞，X3,X4′，X4〞≥0則對(duì)偶規(guī)劃為：.minp=-5y1′5y1〞-6y212y3s.t.

2y1′-2y1〞-6y210y3≥2-y1′y1〞-5y2-9y3≥2y1′-y1〞5y29y3≥-23y1′-3y1〞y26y3≥-53y1′-3y1〞-5y24y3≥2-3y1′3y1〞5y2-4y3≥-2即：minp=-5y1′5y1〞-6y212y3s.t.

2y1′-2y1〞-6y210y3≥2-y1′y1〞-5y2-9y3=23y1′-3y1〞y26y3≥-53y1′-3y1〞5y24y3=2令y1〞-y1′=y1，得：minp=5y1-6y212y3s.t.

-2y1-6y210y3≥2y1-5y2-9y3=2-3y1y26y3≥-5-3y1-5y24y3=24、試用對(duì)偶理論討論下列原問題與他們的對(duì)偶問題是否有最優(yōu)解。(1)解：其對(duì)偶問題為：由圖中可知，對(duì)偶問題無解，根據(jù)對(duì)偶理論，原問題也無解。（2）解：其對(duì)偶問題為：從圖中可知，當(dāng)（）=（0，-2）時(shí)，目標(biāo)函數(shù)有最優(yōu)值，=-12，根據(jù)對(duì)偶理論，原問題最優(yōu)值與對(duì)偶問題相同，為=-12。5.考慮如下線性規(guī)劃（1）寫出對(duì)偶線性規(guī)劃；（2）用單純形法解對(duì)偶規(guī)劃，并在最優(yōu)表中給出原規(guī)劃的最優(yōu)解；（3）說明這樣做比直接求解原規(guī)劃的好處。解：（1）對(duì)偶線性規(guī)劃為：（2）將原規(guī)劃的對(duì)偶規(guī)劃化為標(biāo)準(zhǔn)形式：得到其初始單純形表，經(jīng)過兩次旋轉(zhuǎn)運(yùn)算后得到最優(yōu)表，最優(yōu)解為，最優(yōu)值為，因此原規(guī)劃的最優(yōu)解為，最優(yōu)值為。（3）這樣做的好處是不用引入人工變量，對(duì)偶規(guī)劃中的約束條件均為非大于號(hào)，可以直接運(yùn)用單純形法?；A(chǔ)變量y1y2y3y4y5y6y7y8常數(shù)項(xiàng)y5110010002y6011001003y7001100101y8100100015-p-7-8-6-500000y2110010002y6-1010-11001y7001100101y8100100015-p10-6-5800016y2110010002y6-100-1-11-100y3001100101y8100100015-p10018060226、用對(duì)偶單純形方法，求解下面問題。（1）minf=5X13X24X32X13X22X3≥64X13X25X3≥10X1，X2，X3≥0（2）maxZ=-X1-3X2-3X32X1-3X2X3≥4X12X22X3≤82X2-X3≤2X1，X2，X3≥0解：（1）先將此問題化成下列形式：maxZ=-5X1-3X2-4X3-2X1-3X2-2X3X4=-6-4X1-3X2-5X3X5=-10Xi≥0（i=1,2,3,4,5）建立此問題的初始單純形表并進(jìn)行運(yùn)算如下：Cj-5-4-300CBXBbX1X2X3X4X50X4-6-2-3-2100X5-10-4-3-501-5-4-3005/414/5Cj-5-4-300CBXBbX1X2X3X4X50X4-2-2/5-9/501-2/5-4X325/43/510-1/5-9/5-3/500-4/59/21/31/2Cj-5-4-300CBXBbX1X2X3X4X5-3X210/92/910-5/92/9-4X34/32/3011/3-1/3-5/300-1/3-2/3原問題的對(duì)偶規(guī)劃問題為：MaxP=6Y1Y22Y14Y2≤53Y13Y2≤32Y15Y2≤4Y1，Y2≥0最終表中b列數(shù)字全為非負(fù)，檢驗(yàn)數(shù)全為非正，所以得出原問題最優(yōu)解與最優(yōu)值分別為：X*=（0，10/9，4/3）Tf*=3×（10/9）4×（4/3）=26/3對(duì)偶問題的最優(yōu)解與最優(yōu)值分別為：Y*=（1/3，2/3）TP*=6×（1/3）10×（2/3）=26/3=f*(2)先將此問題化成下列形式：maxZ=-X1-3X2-2X3-2X13X2-X3X4=-4X12X22X3X5=82X2-X3X6=2Xi≥0（i=1,2,3,4,5,6）建立此問題的初始單純形表并進(jìn)行運(yùn)算如下：Cj-1-3-2000CBXBbX1X2X3X4X5X60X4-4-23-11000X581220100X6202-1001-1-3-20001/22Cj-1-3-2000CBXBbX1X2X3X4X5X6-1X121-3/21/2-1/2000X5607/23/21/2100X6202-10010-9/2-3/2-1/200原問題的對(duì)偶規(guī)劃問題為：MinP=-4Y18Y22Y3-2Y1Y2≥-13Y12Y22Y3≥-3-Y12Y2-Y3≥-2Y1，Y2，Y3≥0最終表中b列數(shù)字全為非負(fù)，檢驗(yàn)數(shù)全為非正，所以得出原問題最優(yōu)解與最優(yōu)值分別為：X*=（2，0，0）TZ*=-1×2=-2對(duì)偶問題的最優(yōu)解與最優(yōu)值分別為：Y*=（1/2，0,0）TP*=-4×（1/2）=-2=Z*7．已知線性規(guī)劃問題：寫出其對(duì)偶問題，并求一個(gè)對(duì)偶問題的可行解。解：其對(duì)偶問題為在可行域中任取可行解：。8、考慮下面線性規(guī)劃maxZ=2X13X22X12X2X3=12X12X2X4=84X1X5=164X2X6=12Xj≥0，j=1,2,…,6其最優(yōu)單純形表如表3-7所示，試分析如下問題：（1）當(dāng)C2=5時(shí)，求新最優(yōu)解。（2）當(dāng)b3=4時(shí)，求新最優(yōu)解。（3）增加一個(gè)約束2X12.4X2≤12，對(duì)最優(yōu)解有何影響。表3-7基變量X1X2X3X4X5X6X30001-1-1/40X1410001/40X64000-21/21X220101/2-1/80-14000-3/2-1/80解：由最優(yōu)單純形表所示結(jié)果及靈敏度變動(dòng)思想求解最優(yōu)解不變的C2變動(dòng)范圍：（-3/2）/（1/3）≤△C2≤（-1/8）/（-1/8）-3≤△C2≤1即0≤C2≤4而題設(shè)條件為：新C2=5，超出變動(dòng)范圍，故最優(yōu)解發(fā)生變動(dòng)，需重新求解。C2值發(fā)生變動(dòng)后，影響的值，故新的值分別為：=（-3/2）-(1/2)×（5-3）=-5/2=（-1/8）-(-1/8)×（5-3）=1/8繼續(xù)上述最優(yōu)單純形表的計(jì)算：Cj250000CBXBbX1X2X3X4X5X60X30001-1-1/402X1410001/40160X64000-21/2185X220101/2-1/80000-5/21/80Cj250000CBXBbX1X2X3X4X5X60X32001-201/22X1210010-1/20X58000-4125X23010001/4000-20-1/4新最優(yōu)解和最優(yōu)值分別為：X*=（2，3）TZ*=2×25×3=19（2）由最優(yōu)單純形表所示結(jié)果及靈敏度變動(dòng)思想求解最優(yōu)解不變的b3變動(dòng)范圍：（-4）/（1/2）≤△b3≤0/（-1/4）-8≤△b3≤0即8≤b3≤16而題設(shè)條件為：新b3=4，超出變動(dòng)范圍，故最優(yōu)解發(fā)生變動(dòng)，需重新求解。b3發(fā)生變動(dòng)后

1

-1

-1/4

0

0

30

0

1/4

0

0

-3△b3’=B-1b=

0

-2

1/2

1

-12

=

-60

1/2

-1/8

0

0

3/2

0

3

34

-3

1b3’=b△b3’=

4

-6

=

-22

3/2

7/2繼續(xù)上述最優(yōu)單純形表的計(jì)算：Cj230000CBXBbX1X2X3X4X5X60X33001-1-1/402X1110001/400X6-2000-21/213X27/20101/2-1/80000-3/2-1/803/4Cj230000CBXBbX1X2X3X4X5X60X340010-1/2-1/22X1110001/400X410001-1/4-1/23X23010001/40000-1/2-3/4新最優(yōu)解和最優(yōu)值分別為：X*=（1，3）TZ*=2×13×3=11(3)加入新的約束條件2X12.4X2≤12，將其變?yōu)橄铝行问剑?X12.4X2X7≤12

X7≥0加入新約束條件后繼續(xù)上述最優(yōu)單純形表的計(jì)算：Cj2300000CBXBbX1X2X3X4X5X6X70X30001-1-1/4002X1410001/4000X64000-21/2103X220101/2-1/8000X71222.400001000-3/2-1/800Cj2300000CBXBbX1X2X3X4X5X6X70X30001-1-1/4002X1410001/4000X64000