运筹学全书习题答案

配套教材参考答案

第1章参考答案

1.1用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解还是无可行解。

(1)有唯一最优解X*=(2,0)7,最优值z*=4。⑵问题有无界解。

1.1(1)1.1(2)

(3)有唯一最优解x*=(4,0)7,最优值z*=8。

2Q

(4)有无穷多最优解X；=(±,2)7,x；=(0,2)7,最优值z*=T。

1.1(3)1.1(4)

1.2将下列线性规划问题化成标准型。

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项+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)先将问题化为标准型：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

问题有唯一最优解X*=(与2200

y,0)r,最优值z*==0

3

maxz=2芭+X2

,3x,+5X+=15

(2)先将问题化为标准型，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,最优值z*=^。

问题有唯一最优解X

444

1.4分别用单纯形法中的大M法和两阶段法求解下列线性规划问题。

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

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

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

先构造辅助问题：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//

由上表可知，辅助问题有最优解，且人工变量x；=£=o,故原问题有唯一最优解

*,249y*33

x=（—,0,一），最优值z=—o

777

用两阶段法求解上述问题，过程如下：

minz=x4+x5

x+2X+2X+x=6

先构造辅助问题：}234

4项+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//

由上表可知，辅助问题有最优解，且人工变量x；=匕=0,因此得到原问题的一个可行解，重

新计算原问题的检验数，并用单纯形法继续求解。

G-1-11

0乃9/11-3/2201

024/1110

X2

39/2200

1X39/703/141

1Xi24/7111/70

0-39/140

故原问题有唯一最优解x*=(3,O，T)7'，最优值Z*=T。

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

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

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

先构造辅助问题：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//

由上表可知，辅助问题有最优解，且人工变量匕=x；=0,故原问题有最优解X*=(*|,0)T,

最优值z*=7。又•.•b3=0,可再进行一次迭代，以与取代4作为基变量，检验数不变，因

此问题有无穷多最优解。

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

先构造辅助问题：'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//

辅助问题有最优解，且人工变量x；=x；=0,故原问题有基可行解X*=（，|,0）L重新计算

检验数：

Cjt00000

CBXBbX\X4玲

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

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

000-1/2-1/2

4Q7

*=（1《,0），即为问题的最优解，最优值Z

因检验数（Tj40,故x=7。Xcr3=0,可再

进行一次迭代，以当取代々作为基变量，检验数不变，因此问题有无穷多最优解。

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

maxz=-42-x2-Mx5-Mxb

3x,+x2+x5=3

先构造辅助问题：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//

由上表可知，辅助问题有最优解，且人工变量M=x；=O,故原问题有最优解x*=（H，l）L

最优值Z*=17/5.

用两阶段法求解上述问题，过程如下：

minz=x54-x6

3匹+x2+x5=3

先构造辅助问题：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//

辅助问题有最优解，且人工变量X；=x；=0,故x*=（|假,0）r是原问题的一个基可行解。重

新计算检验数：

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

检验数%40）=1~4,所以原问题有最优解x*=（g2,19,l）T,最优值z*=17/5。

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

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

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

先构造辅助问题：-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

由上表可知，辅助问月至有最优解，但人工变量x；=->0,故原问题不可行。

2

用两阶段法求解上述K]题，过程如下：

nninz'=x7

+3X2+/+X4=9

XX

先构造辅助问题：-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

检验数O'/W0,/=l~4,所以辅助问题有最优解。但人工变量x；=g>0,故原问题不可行。

1.5设X,为每吨合金中矿物广的含量（吨）。建立线性规划模型如下:

minz=340内+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当G=1,c2=4,a”=3,%2=5,4=8,%]=5,&2=6,2=1°时，目标函数最优值

取得最小值。求解线性规划

maxz=2+4X2

3M+5X2<8

,5尤]+6尤2«10

%],x2>0

Q

得最优解/=（0,*,，最优值z*=32/5。

当G=3,。2=6,=一1,。[2=2,4=12,=2,%2=4,%=14时，目标函数最优值

取得最大值。求解线性规划

maxz=3x,+6x2

一X]+2X2<12

<2x1+4々414

x],x2>0

得最优解/=（7。）,（不唯一），最优值z*=21。

因此原问题目标函数最优值的下界为32/5,上界为21。

1.7设工厂每天生产A、B、C三种型号的产品分别为不、々、七件。建立数学模型如下：

maxz=40玉+20%+30x3

711+3X2+6刍41200

,40Xj+40X2+50X3<2000

x,,x2,x3>0

1.8设该公司投资于债券的金额为Xj,建立该问题的数学模型如下：

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

章末习题

2.1写出下列线性规划问题的对偶问题

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判断下面说法是否正确，为什么？

⑴错误。如果线性规划的原问题存在可行解但有无界解，则其对偶问题不可行。

⑵错误。如果线性规划的对偶问题无可行解，原问题可能有无界解，也可能无可行解。

⑶错误。在互为对偶的一对原问题与对偶问题中，如原问题求最小值，则其可行解的

目标函数值一定不小于其对偶问题（求最小值）可行解的目标函数值。

⑷正确。对偶问题可能有不同形式，但实质上都是同一问题。

2.3给出线性规划问题

minw-2yt+y2+2y3

y.+为+2%21

⑴其对偶问题为%一二+3-2

_M+丫2+%=1

)120,当无约束,y3<0

⑵证明：易知y=（0,1,0）是对偶问题的一个可行解，其对应的目标函数值卬=1。

又观察可知，x=（l,0,0）是原问题的一个可行解，所以原问题可行，根据弱对偶性知,

z＜w»

minw=2y+y2

-y-2y2N1

2.4证明：先写出对偶问题:M+%21

M-乃20

*，3

显然，/，为20时，-必-2y2＜。，这与-必-2y221矛盾。因此对偶问题无可行解。

由观察可知x=（0,0,0）是原问题的一个可行解，故原问题有可行解而对偶问题无可行解,

由弱对偶性的推论（3）知，原问题目标函数值无界。

maxz=4yl+3%

M+2y2<2

M->2«3

2.5先写出对偶问题2y,+3y2<5

%+当42

3y+%43

*，%一

>i+2y2=2

M-刈=1/5<3

2%+3为=17/5<5

将最优解y：=4/5,y；=3/5;z=5代入各约束条件中，分别有＜%+为=7/5<2

3%+为=3

y=4/5>0

%=3/5>0

x2=0

x,=0

根据互补松弛性，得匕=。

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

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

解得原问题的最优解为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：=12y；=0.2代入各约束条件中，分别有；％十；为二

3y+2y2=4

必=1.2>0

%=0.2>0

元1=0

x=0

根据互补松弛性，得2

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

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

解得原问题的最优解为x；=(0,0,4,4),z*=28。

2.7(1)因为只有两个主约束，故基变量有两个，其他均为非基变量,

即约束(2)的松弛变量为非基变量。

因此约束条件(2)应为-玉+/-匕3=6

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

maxw=4M+6y2

_y_%z2

(2)

<y+%«t

%_=2

y无约束,%A。

(3)根据互补松弛性，％=-5<0,故-弘-32=2

又•.・y-力=2，两式联立解方程组得y=0,乃=-2。

2.8用对偶单纯形法求解下列线性规划问题

⑴

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

因此问题的最优解为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

因此问题的最优解为x*=(%,2,0),z*:_2y

-/3°

2.9先用单纯形法求解该线性规划问题,得最优E良纯形表如7、•

CL-551300

a

XBbX\x2石在

5X220-11310

0在10160-2-41

Oj00-2-50

因此问题的最优解为x*=(0,20,0),z*=lOOo

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

⑴。由20变为45,因此最优解发生变化。

1—41人90JI-90J

用对偶单纯形法求解,得

C广-55