《運(yùn)籌學(xué)》課后習(xí)題答案 第2章 對偶原理與靈敏度分析

一、選擇題

1.2.3.4.5.6.7.8.9.10.

二、判斷題

1.2.3.4.5.6.7.8.9.10.

三、寫出下列線性規(guī)劃問題的對偶問題

=2xl+2X2+4X3(a)MaxW=2yl+3%+5%

2xl4-3X2+5X3>22y+3%+為42

3玉+x+7X<3對偶問題：3y+%+4%<2

23s.t.

xl+4X2+6尤3<55必+7%+6%?4

xpx2,x3>0y>0,y2,y3<0

(2)MaxZ=2xj-4x24-3x3(b)MinW=l2y1+10y2+15%

xt-3X2+2&<12必+0?%+為22

2X4-X>10對偶問題：3必-2%+0?%24

23s.t

x1-2X3=152必+%-2%>3

%1,x3>0,x2<0y>0,y2<0,y3/ree

(3)MaxZ=2%]+x2-3X3(c)MinW=25y+3y2+10%

西+2X2-3X3<25乂+%+%N2

%)-x+x>3對偶問題：2%-%+為<1

s.t.<23s.t.

x,+x2=103必-%+。?％=3

%>0,x2<Q,x3freeXN0,%<0,yjree

(4)Mi〃Z=X]+2X2-3X3(d)MaxW=3y+10%+8%

X1+3冗323y+()?%+2%21

2X+2X<10對偶問題：+2%+為=2

23s.t.

2xx+x2=83乂+2y2+0.%4-3

Xj<0,x2free.x3>0y>O,y2<^,yifree

四、應(yīng)用對偶單純形法求解下列線性規(guī)劃問題

()

yMinZ=x]+x2McucZ=-Xj-x2

2xj+x>4

2標(biāo)準(zhǔn)型:—2x-Z+%3=—4

s.tAx}+7X2>5-Xj-7X2+七二一5

x,,x2>0Xj,x2>0

對偶單純形法一用電子表格求解

價(jià)值系數(shù)-1.000“?0000.0000.000

基變量價(jià)值系數(shù)基變量

解答列XIX2X3X4

0X3-4.000-2.000-1.0001.0000.000

0X4-5.000-1.000-7.0000.0001.000

目標(biāo)函數(shù)相反數(shù)0.000-1.00()-1.0000.0000.000

比值：10.142857

0X3-3.286-1.8570.0001.000-0.143

-1X20.7140.1431.0000.000-0.143

目標(biāo)函數(shù)相反數(shù)0.714-0.8570.0000.000-0.143

比值：0.4614971

-1X11.7691.0000.000-0.5390.077

-1X20.4610.0001.0000.077-0.154

目標(biāo)函數(shù)相反數(shù)2.2310.0000.000-0.461-0.077

對偶單純形法求解

Cj-1-100

CBXB

bXjXIX2X3X4

0X3-4-2-110

0X4-5-1-701

0-1-100

比值：-1/-1-1/-7

0X3-23/7-13/701-1/7

-1X25/71/710-1/7

-775/7-6/700-1/7

比值：6/131

-1X123/1310-7/131/13

-1X26/13011/13-2/13

-7:29/1300-6/13-1/13

X*=(23/13,6/13,0,0)T,Z,max=-29/13f原問題X*=(23/13,6/13,0,0)T,

Zmin=29/13.

(2)A/mZ=4玉+2X2+X3MaxZ'=-4x,-2X2-

2x,+4X2+5X3>10—2xj—4x?—5玉+%=—10

3Xj-x+6x>3標(biāo)準(zhǔn)型：-3X1+-6X3+=-3

s.t.<23s.t.<

5x,+2X2+>12-5X|-2超一工3+尤6=-12

x,,x2,x3>0%］，x2，，X5，Xg>0

Cj-4-21000

CBXB

bXjXIX2X3X4X5X6

0X4-10-2-4-5100

0X5-3-31-6010

0X6-12-5-2-1001

-Z'0-4-2-1

比勺I：-4/-5-2/-2-1/-1

0X4-26/50-14/5-23/510-2/5

0X521/5011/5-27/501-3/5

-4XI12/512/51/500-1/5

-Z'48/5-2/5-1/500-4/5

比。1：1/81/232

0X326/23016/231-5/2302/23

0X5237/230137/230-27/231-3/23

-4XI50/2316/2301/230-5/23

-Z'226/230-2/5-1/500-4/5

X*=(50/23,0,26/23,0,237/23)[Z'max=-226/23X原問題X*=(50/23,0,26/23,0,

237/23)T,Zmin=226/23.

MeixZ二="2Xj-2%2—4M

2毛+3X2+5X3>2

3.3X1+x2+7%<3

s.t.

卜4X2+6W<5

>0,7=1,2,3

解：

-

MaxZ=一2芭一2X2-4尤3MaxZ二2Xj-2%2-4尤3

2%+3X2+5%3>22%+3X2+5X3-x4=2

3%+x2+7x3<3標(biāo)準(zhǔn)型：3玉+%+7七+/=3

s.t.<

%1+4元2+6X3<5%+4X2+6七+x6=5

x.>0,y=l,2,3與之0,/=1,2,3,4,5,6

Cj-2-2-4000

CbXb

bXjXIX2X3X4X5X6

0X4-2-2-3-5100

0X53317010

0X65146001

-Z'0-2-2-4

比偃1：12/34/5

-2X22/32/315/3-1/300

0X57/34/3016/31/310

0X67/3-5/30-2/38/301

Z|4/3I-2/3I0I-2/3|-2/3|00|

*277Tr4

X=(0,-,0,0,-,-)Zmax=--

五、應(yīng)用對偶理論證明如下線性規(guī)劃問題有可行解，但無最優(yōu)解

六、靈敏度分析題

'5_P

99

1,解:依題意知，X*=(-,—,0,0/,Zmax=—,B'=,:.B

99max3」2

<-99>

C=(1,2,0,0),b=(3,7)7,0=-；；/=-；

(1)若目標(biāo)函數(shù)Z=X1+2z變?yōu)閆=3X1+5z，則

'5

-9fl

9107

6N=CN-CBB"N=(0,0)—(3,5)210、

_J_1尸『5)

J99>

因此，最優(yōu)解不變，但最優(yōu)值變?yōu)閆mmaax=?9。

單純形法一目標(biāo)函數(shù)價(jià)值系數(shù)變化

價(jià)值系數(shù)3.0005.0000.0000.000

基變量價(jià)值系數(shù)基變量0

解答列XIX2X3X4

0X33.0002.0001.0001.0000.0003.000

0X47.0001.0005.0000.0001.0001.400

目標(biāo)函數(shù)相反數(shù)0.0003.0005.0000.00()0.000

0X31.6001.8000.0001.000-0.2000.889

5X21.4000.2001.0000.0000.2007.000

目標(biāo)函數(shù)相反數(shù)-7.0002.0000.0000.000-1.000

3XI0.8891.0000.0000.556-0.111

5X21.2220.0001.000-0.1110.222

目標(biāo)函數(shù)相反數(shù)-8.7780.0000.000-1.111-0.778

'50(29、

(2)當(dāng)b=(3,7)，變?yōu)閎j&ll)7'時(shí)，b=B“b=；

214

9JI9>

57W

因此，最優(yōu)解結(jié)構(gòu)不變，數(shù)值變?yōu)閄*=("，上,0,0)77

99max丁一H

單純形法一右端常數(shù)變?yōu)閎l=8,b2=ll

價(jià)值系數(shù)1.00()2.0000.0000.000

基變量價(jià)值系數(shù)基變量0

解答列XIX2X3X4

0X38.0002.0001.0001.0000.0008.000

0X411.0001.0005.0000.0001.0002.200

目標(biāo)函數(shù)相反數(shù)0.0001.00()2.0000.0000.000

1X35.8001.8000.0001.000-0.2003.222

2X22.2000.2001.0000.0000.20011.000

目標(biāo)函數(shù)相反數(shù)-4.4000.6000.0000.000-0.400

XI3.2221.00()0.0000.556-0.111

X21.5560.0001.000-0.1110.222

目標(biāo)函數(shù)相反數(shù)-6.3330.0000.000-0.333-0.333

（3）新產(chǎn)品C3=l,6=（1,B）7"，則在系數(shù)矩陣中要增加一列，對應(yīng)決策變量當(dāng)

5」

199kn1

???%=。3-。理飛=1一(1,2)[2Lj=~3-°

9)

所以最優(yōu)解和最優(yōu)值不變，該產(chǎn)品不宜生產(chǎn)。

單純形法一增加新產(chǎn)品C（單價(jià)I,al3=l,a23=3）

價(jià)值系數(shù)1.0002.0001.0000.0000.000

基變量價(jià)值系數(shù)基變量e

解答列XIX2X3X4X5

0X33.0002.0001.0001.0001.0000.0003.000

0X47.0001.0005.0003.0000.0001.0001.400

目標(biāo)函數(shù)相反數(shù)0.0001.0002.0001.0000.0000.000

1X31.6001.8000.0000.4001.000-0.2000.889

2X21.4000.2001.0000.6000.0000.2007.000

目標(biāo)函數(shù)相反數(shù)-2.8000.6000.000-0.2000.000-0.400

XI0.8891.0000.0000.2220.556-0.111

X21.2220.0001.0000.556-0.1110.222

目標(biāo)函數(shù)相反數(shù)-3.3330.0000.000-0.333-0.333-0.333

（4）若產(chǎn)品1的消耗系數(shù)由々=（2,1/'變?yōu)槎?（1,2尸則

、

’51、

,g9

=0

22)

J9

97

'5

9-9"1O'

?.PN=CLCBB」N=(0,0)—(1,2)

2

「597

故最優(yōu)解改變，但最優(yōu)值沒變，產(chǎn)品結(jié)構(gòu)無變化。

單純形法一產(chǎn)品1消耗系數(shù)變化

價(jià)值系數(shù)1.0002.0000.0000.000

基變量價(jià)值系數(shù)基變量e

解答列XIX2X4X5

0X33.0001.0001.0001.0000.0003.000

0X47.0002.0005.0000.000L0001.400

目標(biāo)函數(shù)相反數(shù)0.0001.0002.0000.00()0.000

1X31.6000.6000.0001.000-0.2002.667

2X21.4000.4001.0000.0000.2003.500

目標(biāo)函數(shù)相反數(shù)-2.8000.2000.0000.000-0.400

XI2.6671.0000.0001.667-0.333

X20.3330.0001.000-0.6670.333

目標(biāo)函數(shù)相反數(shù)-3.3330.0000.000-0.333-0.333

2.解：設(shè)甲、乙兩種產(chǎn)品的產(chǎn)量分別為占和4件。

原料A消耗花費(fèi)的錢：（2%+4Z）x1（元）。

原料B消耗花費(fèi)的錢：（3%+24）x2（元）

產(chǎn)品銷售收益：13%+16々

扣除成本后的利潤：Z=13%+16%-（2玉+4%）-2x（3玉+2x2）

MaxZ=5%+8X2

2x+4%W160

（1）利潤最大化模型為：}

3%1+2々<180

,x2>0

單純形法一用電子表格求解

價(jià)值系數(shù)5.0008.0000.0000.0000

基變量價(jià)值系數(shù)基變量

解答列XIX2X3X4

0X3160.0002.0004.0001.0000.00040

0X4180.0003.0002.0000.0001.00090

目標(biāo)函數(shù)相反數(shù)0.0005.0008.0000.0000.000

8X240.0000.5001.0000.2500.00080

0X4100.0002.0000.000-0.5001.00050

目標(biāo)函數(shù)相反數(shù)-320.0001.0000.000-2.0000.000

8X215.0000.0001.0000.375-0.250

5XI50.0001.0000.000-0.2500.500

目標(biāo)函數(shù)相反數(shù)-370.0000.0000.000-1.750-0.500

解得：最優(yōu)解X*=(50,15,0,0)、最優(yōu)值21?”=370(元)。

(2)從最優(yōu)表中可知，原料A的影子價(jià)格為y：=-q=L75(7/4),原料B的影

子價(jià)格為y；=-2=0.5(1/2),顯然原料A更珍貴。

(3)若市場上有A原料出售，企業(yè)應(yīng)該購入以擴(kuò)大生產(chǎn)。假設(shè)在保持最優(yōu)解不

變的前提下，最多購入Q(kg)。(請注意這里的逆矩陣先寫第二行再第一行)

50--2^0

4.2<200