運(yùn)籌學(xué)全書習(xí)題答案

配套教材參考答案

第1章參考答案

1.1用圖解法求解下列線性規(guī)劃問題，并指出問題具有唯一最優(yōu)解、無窮最優(yōu)解還是無可行解。

(1)有唯一最優(yōu)解X*=(2,0)7,最優(yōu)值z*=4。⑵問題有無界解。

1.1(1)1.1(2)

(3)有唯一最優(yōu)解x*=(4,0)7,最優(yōu)值z*=8。

2Q

(4)有無窮多最優(yōu)解X；=(±,2)7,x；=(0,2)7,最優(yōu)值z*=T。

1.1(3)1.1(4)

1.2將下列線性規(guī)劃問題化成標(biāo)準(zhǔn)型。

maxz=-xt一尤4

maxz'-2X]+2x2-3x3+3x3

x2+x3—尤5=13

X,+x2+-x34

X]+%=10

⑴⑵

2xi+x2-x3+x3+x5=6

%!+X2-X3+X6=6

2項(xiàng)+3X2+—X4-X6-2

xt-x2+x3-x4-x710

XX,X,Xj,X,X,X>0

x.>0,；=l~7p23456

1.3用單純形法求解下述問題。

maxz=1Ox+6^2+4X3

J+々+X4=100

(1)先將問題化為標(biāo)準(zhǔn)型：1Ox,+4X+5X+x=600,然:后用單純，法法求解如下：

V235

4q+々+3Jc3+X6150

q,12，'3，1D

G一1064000

CBXBbX]X2即X4%5九6

0X4100111100

@

0X560045010

0X6150113001

°j1064000

0X44001/21-1/100

10X\6012/51/201/100

0X69003/55/20-1/101

%02-10-10

6X4200/3015/65/3-1/60

10X\100/3101/6-2/31/60

0Xe50002-101

00-8/3-10/3-2/30

問題有唯一最優(yōu)解X*=(與2200

y,0)r,最優(yōu)值z*==0

3

maxz=2芭+X2

,3x,+5X+=15

(2)先將問題化為標(biāo)準(zhǔn)型，12i用單純形y去求解。過程如下：

,=24

*6玉+2X2+x

X],工2，'3，*^4—i0

CjT10600

BBb

CXX\X2了3尢4

0了3153510

?

0X424201

0.i2100

03041-1/2

2X\411/301/6

01/30-1/3

1即3/4011/4-1/8

2X\15/410-1/125/24

00-1/12-7/24

T,最優(yōu)值z*=^。

問題有唯一最優(yōu)解X

444

1.4分別用單純形法中的大M法和兩階段法求解下列線性規(guī)劃問題。

(1)用大M法求解，過程如下：

maxz=x]—x2+x3-Mx4-Mx5

尤1+2尤2+2%3+x二6

先構(gòu)造輔助問題：4

4工1+5X2-6X3+x5=6

、X],Z，/x4,x5>0

CjT1-11-M-M

CBXBbX\%2沏X4九5

-MX4612210

-MX564?-601

°j1+5M-1+7M1-4M00

-MX418/5-3/50（22/^）1/

-1X26/54/51-6/50/

9/5-3M/50-1/5+22M/50/

1九39/11-3/2201//

-1X224/11^ZLL）10//

39/2200//

1X39/703/141//

1X\24/7111/70//

0-39/140//

由上表可知，輔助問題有最優(yōu)解，且人工變量x；=￡=o,故原問題有唯一最優(yōu)解

*,249y*33

x=（—,0,一），最優(yōu)值z=—o

777

用兩階段法求解上述問題，過程如下：

minz=x4+x5

x+2X+2X+x=6

先構(gòu)造輔助問題：}234

4項(xiàng)+5X2-6X3+%=6

x1,x2,x3,x4,x5>0

CjT000-1-1

CBXBbXiX2X4

-1XA612210

-1%564CD-601

57-400

-1X418/5-3/501/

0X26/54/51-6/50/

-3/5022/50/

0X39/11-3/2201//

0X224/117/1110//

000//

由上表可知，輔助問題有最優(yōu)解，且人工變量x；=匕=0,因此得到原問題的一個(gè)可行解，重

新計(jì)算原問題的檢驗(yàn)數(shù)，并用單純形法繼續(xù)求解。

G-1-11

0乃9/11-3/2201

024/1110

X2

39/2200

1X39/703/141

1Xi24/7111/70

0-39/140

故原問題有唯一最優(yōu)解x*=(3,O，T)7'，最優(yōu)值Z*=T。

(2)用大M法求解，過程如下：

maxz=-2xj-3x2-x3-Mx6-Mx7

x.+4X+2x,一%=8

先構(gòu)造輔助問題：c/9/

<3xj+2X2一%+七=6

xJ.>0J=l-7

CjT-2-3-100-M-M

CB

XBbX1%2X3X4x5%6%7

-MX681CD2-1010

-MX763200-101

°j-2+4M-3+6M-1+2M-M-M00

-3X221/411/2-1/40/0

-MX720-11/2-1/1

-5/4+5M/21/2-M-3/4+M/2-M/0

-3X29/5013/5-3/101/10//

-2X\4/510-2/51/5-2/5//

ai000-1/2-1/2//

由上表可知，輔助問題有最優(yōu)解，且人工變量匕=x；=0,故原問題有最優(yōu)解X*=(*|,0)T,

最優(yōu)值z*=7。又?.?b3=0,可再進(jìn)行一次迭代，以與取代4作為基變量，檢驗(yàn)數(shù)不變，因

此問題有無窮多最優(yōu)解。

G--2-3-100-M-M

CBXBbXix2X3X4X5X7

-1X3305/31-1/21/6//

-2Xi212/3-00-1/3//

%000-1/2-1/2//

用兩階段法求解上述問題，過程如下：

minz=x6+x7

x.+4X+2x,—x.+x,=8

先構(gòu)造輔助問題：'27346

<3x,+2X2-X5+X7=6

x/0"=l~7

G—I0I0I000I-1I-1

CBXBbXi即沏X4%5&Xi

Q

-1X6812-1010

-1X763200-101

462-1-100

0即21/411/2-1/40/0

-1X72<S)0-11/2-1/1

5/20-11/2-1/0

-3X29/5013/5-3/101/10//

-2X\4/510-2/51/51/5//

00000//

輔助問題有最優(yōu)解，且人工變量x；=x；=0,故原問題有基可行解X*=（，|,0）L重新計(jì)算

檢驗(yàn)數(shù)：

Cjt00000

CBXBbX\X4玲

-3X29/5013/5-3/101/10

-2X\4/510-2/51/51/5

000-1/2-1/2

4Q7

*=（1《,0），即為問題的最優(yōu)解，最優(yōu)值Z

因檢驗(yàn)數(shù)（Tj40,故x=7。Xcr3=0,可再

進(jìn)行一次迭代，以當(dāng)取代々作為基變量，檢驗(yàn)數(shù)不變，因此問題有無窮多最優(yōu)解。

（3）用大M法求解，過程如下：

maxz=-42-x2-Mx5-Mxb

3x,+x2+x5=3

先構(gòu)造輔助問題：4玉+3X-+X=6

<26

2+2X2+x4=4

x1,x2,x3,x4,x5,x6>0

CjT-4-100-M-M

CBXBbX\X2X3X4X6

①

-MX5310010

-M尤643-1001

0%44120100

%-4+7M-1+4M-M000

-4Xi111/300/0

(s)

-M雙20-10/1

0X4305/301/0

01/3+5M/3-M0/0

-4Xl3/5101/50//

-1X26/501-3/50//

o

0X41001//

001/50//

-4X}2/5100-1/5//

-19/50103/5//

X2

010011//

001/5-1/5//

由上表可知，輔助問題有最優(yōu)解，且人工變量M=x；=O,故原問題有最優(yōu)解x*=（H，l）L

最優(yōu)值Z*=17/5.

用兩階段法求解上述問題，過程如下：

minz=x54-x6

3匹+x2+x5=3

先構(gòu)造輔助問題：4%)+3X2-X3+X6=6

x1+2X2+x4=4

xpx2,x3,x4,x5,x6>0

CjT0000-1-1

c?XBbX]X2X3X4X5%6

Q

-1Xs310010

-1照643-1001

0XA4120100

74-1000

0X\111/300/0

⑥

-1九620-10/1

0X4305/301/0

05/3-10/0

0Xi3/5101/50//

0X26/501-3/50//

0%410011//

0000//

輔助問題有最優(yōu)解，且人工變量X；=x；=0,故x*=（|假,0）r是原問題的一個(gè)基可行解。重

新計(jì)算檢驗(yàn)數(shù)：

G--4-100

CBXHbXiX2X3Xi

-4Xi3/5101/50

-1X26/501-3/50

o

0X41001

001/50

-4Xi2/5100-1/5

-1X29/50103/5

0X310011

000-1/5

檢驗(yàn)數(shù)%40）=1~4,所以原問題有最優(yōu)解x*=（g2,19,l）T,最優(yōu)值z*=17/5。

(4)用大M法求解，過程如下:

maxz=IO%]+15%+12%-用毛

5x}+3X2+七+%=9

先構(gòu)造輔助問題：-5xl+6尤2+15尤3+x5=15

4-x24-x3-x64-x7=5

G-101512000-M

CBXBbX\%2X3x4九5九6X7

0X49G)311000

0X515-56150100

-Mx7521100-11

10+2M15+M12+M00-M0

10X]9/513/51/51/5000

@

0X524091100

-MXn7/50-1/53/5-2/50-11

06-M/510+3M/5-2-2M/50-M0

103/2139/8003/16-1/8000

123/209/1611/161/1600

-MXi1/20-43/800-7/16-3/80-11

°)027/8-43M/800-21/8-7M/16-5/8-3M/80-M0

由上表可知，輔助問月至有最優(yōu)解，但人工變量x；=->0,故原問題不可行。

2

用兩階段法求解上述K]題，過程如下：

nninz'=x7

+3X2+/+X4=9

XX

先構(gòu)造輔助問題：-5%j+6X24-153+5=15

2X1+九2+工?一16+七=5

xj>0J=\-l

G-000000-1

B

CXBbXiX2%3X4x5X6X7

09311000

X4

X5

-1Xi521100-11

21100-10

0Xi9/513/51/51/5000

0X52409@1100

-1X77/50-1/53/5-2/50-11

0-1/53/5-2/50-10

0X\3/2139/8003/16-1/8000

0九33/209/1611/161/1600

-1X11/20-43/800-7/16-3/80-11

0）0-43/800-7/16-3/80-I0

檢驗(yàn)數(shù)O'/W0,/=l~4,所以輔助問題有最優(yōu)解。但人工變量x；=g>0,故原問題不可行。

1.5設(shè)X,為每噸合金中礦物廣的含量（噸）。建立線性規(guī)劃模型如下:

minz=340內(nèi)+260x2+180七+230x4+190x5

25%陽+40%x2+20%X4+8%X5>28%

10%Xj+15%X3+20%X4+5%X5<15%

10%玉+5%X3+15%X5=10%

<35%<25%為+30%X2+20%X3+40%x4+17%/<55%

70%$+70%X2+40%X3+80%X4+45%x5=1

/N0,j=l~5

1.6當(dāng)G=1,c2=4,a”=3,%2=5,4=8,%]=5,&2=6,2=1°時(shí)，目標(biāo)函數(shù)最優(yōu)值

取得最小值。求解線性規(guī)劃

maxz=2+4X2

3M+5X2<8

,5尤]+6尤2?10

%],x2>0

Q

得最優(yōu)解/=（0,*,，最優(yōu)值z*=32/5。

當(dāng)G=3,。2=6,=一1,。[2=2,4=12,=2,%2=4,%=14時(shí)，目標(biāo)函數(shù)最優(yōu)值

取得最大值。求解線性規(guī)劃

maxz=3x,+6x2

一X]+2X2<12

<2x1+4々414

x],x2>0

得最優(yōu)解/=（7。）,（不唯一），最優(yōu)值z*=21。

因此原問題目標(biāo)函數(shù)最優(yōu)值的下界為32/5,上界為21。

1.7設(shè)工廠每天生產(chǎn)A、B、C三種型號的產(chǎn)品分別為不、々、七件。建立數(shù)學(xué)模型如下：

maxz=40玉+20%+30x3

711+3X2+6芻41200

,40Xj+40X2+50X3<2000

x,,x2,x3>0

1.8設(shè)該公司投資于債券的金額為Xj,建立該問題的數(shù)學(xué)模型如下：

maxz=0.065%1+0.09x2+0.045x3+0.055x4+0.5x5

Xj+x2+x3+x4+x5=30

%)+x2<18

x+x<12

V34__

x2<65%X]+65%X2

x5>20%%+20%x2

章末習(xí)題

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

minw=5y+8為+20乃

maxw=2必+3y2+5必

一%+6y2+12%>1

2M+3%+為42

⑵必+7為-9為22

⑴3M+y+4142

<2一M+3y2-9必<3

5y+7%+6%44

-5y2+9y=4

y>0,<0,y<03

3%無約束m?0,必NO

minz=Z。％

1=1

ntn

maxw=+，/?”.=1,2,…,〃J

/=1j=\i=l

⑶

ru+Vj<Cjj,i=l?-m.j=1-n

<i<Z%%=cj/=〃i+L〃i+2,???,?)

N”匕無約束，i=1~"2,/=1~〃i=l

y’NOi=l,2,…，叫

y無約束z=/?,m

2.2判斷下面說法是否正確，為什么？

⑴錯(cuò)誤。如果線性規(guī)劃的原問題存在可行解但有無界解，則其對偶問題不可行。

⑵錯(cuò)誤。如果線性規(guī)劃的對偶問題無可行解，原問題可能有無界解，也可能無可行解。

⑶錯(cuò)誤。在互為對偶的一對原問題與對偶問題中，如原問題求最小值，則其可行解的

目標(biāo)函數(shù)值一定不小于其對偶問題（求最小值）可行解的目標(biāo)函數(shù)值。

⑷正確。對偶問題可能有不同形式，但實(shí)質(zhì)上都是同一問題。

2.3給出線性規(guī)劃問題

minw-2yt+y2+2y3

y.+為+2%21

⑴其對偶問題為%一二+3-2

_M+丫2+%=1

)120,當(dāng)無約束,y3<0

⑵證明：易知y=（0,1,0）是對偶問題的一個(gè)可行解，其對應(yīng)的目標(biāo)函數(shù)值卬=1。

又觀察可知，x=（l,0,0）是原問題的一個(gè)可行解，所以原問題可行，根據(jù)弱對偶性知,

z＜w?

minw=2y+y2

-y-2y2N1

2.4證明：先寫出對偶問題:M+%21

M-乃20

*，3

顯然，/，為20時(shí)，-必-2y2＜。，這與-必-2y221矛盾。因此對偶問題無可行解。

由觀察可知x=（0,0,0）是原問題的一個(gè)可行解，故原問題有可行解而對偶問題無可行解,

由弱對偶性的推論（3）知，原問題目標(biāo)函數(shù)值無界。

maxz=4yl+3%

M+2y2<2

M->2?3

2.5先寫出對偶問題2y,+3y2<5

%+當(dāng)42

3y+%43

*，%一

>i+2y2=2

M-刈=1/5<3

2%+3為=17/5<5

將最優(yōu)解y：=4/5,y；=3/5;z=5代入各約束條件中，分別有＜%+為=7/5<2

3%+為=3

y=4/5>0

%=3/5>0

x2=0

x,=0

根據(jù)互補(bǔ)松弛性，得匕=。

%]+尤2+2工3+工4+3%5=4

2xj-x2+3X3+x4+x5=3

解得原問題的最優(yōu)解為x；=（l,0Q01）,z*=5。

minz=20)[+20y2

y+2y2>1

2M+y>2

2.6先寫出對偶問題2

2M+3%N3

3M+2y2>4

Ji，%NO

y,+2y2=1.6>1

2y}+%=2.6>2

將最優(yōu)解y：=12y；=0.2代入各約束條件中，分別有；％十；為二

3y+2y2=4

必=1.2>0

%=0.2>0

元1=0

x=0

根據(jù)互補(bǔ)松弛性，得2

x}+2X2+2X3+3X4=20

2x}+/+3X3+2X4=20

解得原問題的最優(yōu)解為x；=(0,0,4,4),z*=28。

2.7(1)因?yàn)橹挥袃蓚€(gè)主約束，故基變量有兩個(gè)，其他均為非基變量,

即約束(2)的松弛變量為非基變量。

因此約束條件(2)應(yīng)為-玉+/-匕3=6

將x：=-5,x；=0,x；=—1上式，得一玉+%—左七=5+左=6。故左=1

maxw=4M+6y2

_y_%z2

(2)

<y+%?t

%_=2

y無約束,%A。

(3)根據(jù)互補(bǔ)松弛性，％=-5<0,故-弘-32=2

又?.?y-力=2，兩式聯(lián)立解方程組得y=0,乃=-2。

2.8用對偶單純形法求解下列線性規(guī)劃問題

⑴

CL-3-4-500

CBXBbX\*3As

0A"I-8-1-2-310

0后-10-2-101

°J-3-4-500

0*-303-5/21-1/2

-3Xi5111/20-1/2

°j0-1-7/20-3/2

-4X23015/2-11/2

-3X\210-21-1

°j00-1-1-1

因此問題的最優(yōu)解為x*=(2,3,0),z*=18o

(2)

-5-2-400

CBXBbX\X2X&XA天

0XA-4-1-210

0天-10-6-3-501

0J-5-2-400

-5*4/311/32/3-1/30

0禹-20-1-21

°j0-1/3-2/3-5/30

-5Xi2/3101/3-11/3

-2X220112-1

°i00-1/3-1-1/3

因此問題的最優(yōu)解為x*=(%,2,0),z*:_2y

-/3°

2.9先用單純形法求解該線性規(guī)劃問題,得最優(yōu)E良純形表如7、?

CL-551300

a

XBbX\x2石在

5X220-11310

0在10160-2-41

Oj00-2-50

因此問題的最優(yōu)解為x*=(0,20,0),z*=lOOo

B-'b'=(10丫45、-5]

⑴。由20變?yōu)?5,因此最優(yōu)解發(fā)生變化。

1—41人90JI-90J

用對偶單純形法求解,得

C廣-55