运筹学16章参考答案

运筹学（第2版）习题答案

第1章线性规划P36-40

第2章线性规划的对偶理论P68-69

第3章整数规划P82-84

第4章目标规划P98~100

第5章运输与指派问题P134-136

第6章网络模型P164-165

第7章网络计划P185-187

第8章动态规划P208-210

第9章排队论P239-240

第10章存储论P269-270

第11章决策论Pp297-298

第12章博弈论P325-326

全书360页

习题一

1.1讨论下列问题：

（1）在例1.2中，如果设芍0=1,2,…，7）为工作了5天后星期一到星期日开始休息的营

业员，该模型如何变化.

（2）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简

述板材下料的思路.

（3）在例1.4中，若允许含有少量杂质，但杂质含量不超过1%,模型如何变化.

（4）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每

天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化.

（5）在单纯形法中，为什么说当4>0并且纵40。=1,2,，机）时线性规划具有无界解。

1.2工厂每月生产A、B,C三种产品，单件产品的原材料消耗量、设备台时的消耗量、资源

限量及单件产品利润如表1—23所示.

表1一23

ABC资源限量

材料（kg）1.51.242500

设备（台时）31.61.21400

利润（元/件）101412

根据市场需求，预测三种产品最低月需求量分别是150、260和120,最高月需求是250、310

和130.试建立该问题的数学模型，使每月利润最大.

【解】设XI、也、心分别为产品A、B、C的产量，则数学模型为

maxZ=10x,+14x2+12x3

1.5%,+1.2X2+4X3<2500

3%+1.6尤2+1-2X3<1400

1504X]<250

’260<x2<310

120<X3<130

x（,x2,x3>0

1.3建筑公司需要用6m长的塑钢材料制作A、B两种型号的窗架.两种窗架所需材料规格

及数量如表1-24所示:

表1-24窗架所需材料规格及数量

型号A型号B

长度长度

数量（根）数量（根）

每套窗架需要（m）（m）

材料Ai：1.72Bi：2.72

A2：1.33B2：2.03

需要量（套）200150

问怎样下料使得（1）用料最少；（2）余料最少.

【解】第一步：求下料方案，见下表。

方案一二三四五六七八九十十一十二十三十四需要量

Bl:2.7m211100

B2:2m000450

Al:1.7m210400

A2:1.3m234600

余料0.600.30.700.30.70.610.10.900.40.8

第二步：建立线性规划数学模型

设修。=1,2,…，14)为第，种方案使用原材料的根数，则

(1)用料最少数学模型为

14

minZ=Z%

7=1

2%+x2+x3+x4>300

x2+3X5+2X6+2X7+/+/+MoN450

■x3+x6+2xg+/+3玉1+2X12+再32400

尤2+W+2/+吃+/+3尤］0+2XI2+3X13+4XI4>600

x.>0J^l,2,,14

用单纯形法求解得到两个基本最优解

X")=(50,200,0,0,84,0,0,0,0,0,0,200,0,0);Z=534

X⑵=(0,200,100,0,84,0,0,0,0,0,0,150,0,0);Z=534

(2)余料最少数学模型为

minZ=0.6x,+0.3x3+0.7x4++0.4xl3+0.8xl4

2xt+x2+x3+x4>300

x2+3X5+2X6+2X7+4+/+MoN450

<x3+x6+2xs+/+3x”+2X12+xl3>400

+七+/+玉

x2++2X430+2XI2+3X13+4xl4>600

x/0,/=l,2,,14

用单纯形法求解得到两个基本最优解

X⑴=(0,300,0,0,50,0,0,0,0,0,0,200,0,0);Z=0,用料550根

X⑵=(0,450,0,0,0,0,0,0,0,0,0,200,0,0);Z=0,用料650根

显然用料最少的方案最优。

1.4某企业需要制定1〜6月份产品A的生产与销售计划。已知产品A每月底交货，市场需

求没有限制，由于仓库容量有限，仓库最多库存产品A1000件，1月初仓库库存200件。1〜

6月份产品A的单件成本与售价如表1-25所示。

表1-25

月份123456

产品成本（元/件）300330320360360300

销售价格（元/件）350340350420410340

（1）1〜6月份产品A各生产与销售多少总利润最大，建立数学模型；

（2）当1月初库存量为零并且要求6月底需要库存200件时，模型如何变化。

【解】设可、M0=1，2,6)分别为1〜6月份的生产量和销售量，则数学模型为

maxZ=-300玉+350y,-330x2+340%-320七+350%-360/+

420y4-360X5+410y5-300A:6+340y6

玉<800

内-必+x2V800

内—+/—必+尤34800

X|-M+%2-%+七一%+4«800

X|一M+尤2->2+工3_%+无4_>4+^K800

玉_必+工2_y2+%3_%+%_y4+/_%+入6<800

(1)一内+y4200

一玉+凶—x,+必4200

—九］+凶—x,+%一七+%«200

―玉+y-9+>2-工3+y3一》4+”〈200

―玉+X-/+>2一%3+%一Z+>4一％5+y5<200

一玉+,一马+%一*3+%一匕+%-%5+%一%6+”4200

xj,yj>0-,j=\,2,,6

(2)目标函数不变，前6个约束右端常数800改为1000,第7〜11个约束右端常数200改

为0,第12个约束“W200”改为"=—200”。

1.5某投资人现有下列四种投资机会，三年内每年年初都有3万元（不计利息）可供投资：

方案一：在三年内投资人应在每年年初投资，一年结算一次，年收益率是20%,下一年可

继续将本息投入获利；

方案二：在三年内投资人应在第一年年初投资，两年结算一次，收益率是50%,下一年可

继续将本息投入获利，这种投资最多不超过2万元；

方案三：在三年内投资人应在第二年年初投资，两年结算一次，收益率是60%,这种投资

最多不超过1.5万元；

方案四：在三年内投资人应在第三年年初投资，一年结算一次，年收益率是30%,这种投

资最多不超过1万元.

投资人应采用怎样的投资决策使三年的总收益最大，建立数学模型.

【解】是设殉为第i年投入第，项目的资金数，变量表如下

项目一项目二项目三项目四

第1年为1X12

第2年X21X23

第3年X31X34

数学模型为

maxZ=0.2;1cH+0.2x21+0.2x31+0.5xl2+0.6x23+0.3x34

X”+xl2<30000

—1.2%]+%2i+“23~30000

—

—1.5X(21.2X2|+Xj|+Xj4<30000

<%«20000

尤23"(JOO

x34<10000

XgN0,i=1,,3',j—1,4

最优解X=(30000,0,66000,0,109200,0)；Z=84720

1.6炼油厂计划生产三种成品油，不同的成品油由半成品油混合而成，例如高级汽油可以由

中石脑油、重整汽油和裂化汽油混合，辛烷值不低于94,每桶利润5元，见表1—26。

表1—26

成品油高级汽油一般汽油航空煤油一般煤油

轻油、裂化

中石脑油中石脑油轻油、裂化

油、重油、残

半成品油重整汽油重整汽油油、重油、残

油按10:4:3:1

裂化汽油裂化汽油油

调合而成

辛烷值294284

蒸汽压：公斤

/平方厘米

利润(元/桶)54.231.5

半成品油的辛烷值、气压、及每天可供应数量见表1—27。

表1—27

半成品油1中石脑油2重整汽油3裂化汽油4轻油5裂化油6重油7残油

辛烷值80115105

蒸汽压：公斤/

1.01.50.60.05

平方厘米

每天供应数量

2800

(桶)

问炼油厂每天生产多少桶成品油利润最大，建立数学模型。

解设均为第i(i=1,2,3,4)种成品油配第八/=1,2,…,7)种半成品油的数量(桶)。

总利润：

%+

Z=5(%1++玉3)+4.2(X2|+X22+X23)+3(演4+七5+演6+毛7)+15(犬44+^45+46*47)

高级汽油和一般汽油的辛烷值约束

8°x”+115网2+1()5X|3)>9484<8°x.+】1592+105和<

孙+*12+*13x2l+x22+x23

航空煤油蒸气压约束

xi4+1,5JC35+0.6^36+0.05X37<]

“34+%35+%36+%37

一般煤油比例约束

X44:X45:%：X47=10：4:3:1

即

半成品油供应量约束

xH+x21<2000

xl2+x22<1000

xi3+x23<1500

x34+<1200

X35+X45V100°

七6+%41°00

x37+x47<800

整理后得到

maxZ=5xn+5x12+5x13+4.2x21+4.2x22+4.2x23+

3X34+3%35+3X36+3元37+1.5%+1.5X45+1.5x464

-14xn+21XI2+11XI3>0

—

14X9J+21%22+1523—0

-4X21+3lx22+21冗2320

0.5X35-0.4X36-0.95X37<0

4%-10%=0

3%-4%=0

%一3%47=0

*xn+x21<2000

x12+x22<1000

x13+x23<1500

0+如(1200

必+加《100°

七6+4«1。0。

x31+X47<800

x->0;z=l,2,3,4;j=l,2,,7

1.7图解下列线性规划并指出解的形式：

maxZ=2.5%)+2x2

2工］+x2<8

(1)0.5^<1.5

x1+2X2<10

xpx2>0

【解】最优解X=(2,4)；最优值Z=13

32+8X2<12

(2)x]+x2<2

2%<3

%1,x2>0

【解】有多重解。最优解x”>=(3/2,1/2)；X<2)=(4/5,6/5)最优值Z=2

minZ=-3Xj+2x2

xx+2X2<11

-Xj+4X<10

⑶2

2%-x2<7

%-3X2<1

,x2>0

【解】最优解X=(4,1)；最优值Z=-10,有唯一最优解

minZ=4g+6x2

xy+2X2>8

(4)%1+x2<8

x2<3

Xj>0,x2>0

【解】最优解x=(2,3)；最优值Z=26,有唯一最优解

maxZ=x{+2尤2

x{-x2>2

⑸Xj>3

<

x2<6

x{,x2>0

【解】无界解。

minZ=2x1-5x2

玉+2X2>6

(6)

<x[+x2<2

xvx2>0

【解】无可行解。

3.00

1.8将下列线性规划化为标准形式

maxZ=x+4々一刍

2x]+x2+3X3<20

(1)

-7X2+4尤3>3

10x1+3X2+6X3>-5

X{NO,/2°，工3无限制

【解】(1)令元3=%3-石，工4，工5，工6为松驰变量，则标准形式为

maxZ=%+4X2-X3+X3

2x}+x2+3尤3-3X3+x4=20

5X1—7/+4X-4X-x=3

<335

一10%-3%2-6与+6x；+/=5

%,工2，工3，石，工4，/，%之°

minZ=9x)-3x2+5x3

|6x,+7%-4X3|<20

⑵%1>5

+8%2=-8

X]>0,x2>0,x3>0

【解】（2）将绝对值化为两个不等式，则标准形式为

maxZ'=—9玉+3x2-5x3

3

6玉+7X2-4尤+x4=20

-6%]-7X2+4xj+★=20

(%一4=5

——8%2=8

司，々，43，工4，工5，工62。

maxZ=2%+3x2

1<Xj<5

⑶

{_内+冗2=-]

Xj>0,x2>0

【解】方法1:

maxZ=2%+3x2

%一刍=1

Xj+x=5

<4

xl-x2=l

xpx2,x3,x4>0

方法2：令工；=石—1,有/=X+1,x；<5—1=4

maxZ=2(x：+1)+3x2

x；<4

<一(X；+1)+/=—]

xl,x2>0

则标准型为

maxZ=2+2x[+3x2

%'+演=4

<-x[+x2=0

x[,x2,x3>0

maxZ=min(3X]++x2+x3)

I1+2X2+x3<30

(4)4%j-x+2毛>15

*2

9%+々+6元32-5

网无约束,马、m32。

【解】令+4%2，y<X1+々+工3,玉=内,一内"，线性规划模型变为

maxZ=y

y<3(x[-xf)+4X2

y<x[-x^+x2+x3

x\-x；+2X24-x3<30

4(%j-xf)-x2+2%>15

9(%；—k)+.+6.之—5

尤2、冗320

标准型为

maxZ=y

y—3x；+3k-4x2+七=0

y-x{+xf-x2-x3+x5=0

x：-x；+2X2+x3+x6=30

4x{-4k-x2+2X3-x-j=15

—9x；+9k—%—6工3+4=5

1.9设线性规划

maxZ=5工1+2x2

2x1+3X2+刍=50

v4x(-2X2+x4=60

XjN0,，=L…,4

「21]「2。1工.

取基片=(耳，P3)=40、斗=4],分别指出与和层对应的基变量和非基变量，

求出基本解，并说明与、不是不是可行基.

【解】S：汨，M为基变量，X2,X4为非基变量，基本解为x=(15,0,20,0)r,Bl是可行

基。B2：加用是基变量，检用为非基变量，基本解X=(25,0,0,—40)，B?不是可行基。

1.10分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对

应于图形上的那一个极点.

maxZ=%+3X2

-2x]+X<2

(D2

2x1+3X2<12

x,,x2>0

【解】图解法

单纯形法:

C(j)1300

bRatio

C(i)BasisXIX2X3X4

0X3-2[1]1022

0X42301124

C(j)-z①13000

3X2-21102M

0X4[8]0-3160.75

c(j)-zu)70-306

3X2010.250.257/2

1XI10-0.3750.1253/4

C(j)-z①00-0.375-0.87545/4

对应的顶点:

基可行解可行域的顶点

X(1)=(0,0,2,12),(0,0)

*出=(0,2,0,6,),(0,2)

X(”=(347,0,0)-

42居42

最优解x=(23，7),z=425

424

minZ=-3x]-5x2

xl+2X2<6

Q)xt+4尤2<10

xx+x2<4

Xj>0,x2>0

【解】图解法

单纯形法:

eg)-3-5000

bRatio

BasisC(i)XIX2X3X4X5

X301210063

X40114J010102.5

X501100144

-3-50000

X30[0,5]01-0.5012

X2-50.25100.2502.510

X500.7500-0.2511.52

-1.75001.250-12.5

XI-3102-102M

X2-501-0.50.5024

X5000-1.5[0.5]100

C(j)-Z①003.5-0.50-16

XI-310-1022

X2-50110-12

X4000-3120

C(j)-Z(j)00201-16

对应的顶点:

基可行解可行域的顶点

X(l)=(0,0,6,10,4)-(0,0)

必2)=(0,2.5,1,0,1.5,)-(0,2.5)

加=(2,2,0,0,0)(2,2)

X(4,=(2,2,0,0,0)(2,2)

最优解：x=(2,2,0,0,0)；最优值z=-16

该题是退化基本可行解，5个基本可行解对应4个极点。

1.11用单纯形法求解下列线性规划

maxZ=3玉+4x2+x3

2X]+3X2+<1

(1)

X1+2无2+2x3<3

Xj>0,J=1,2,3

【解】单纯形表:

C①34100

R.H.S.Ratio

BasisC(i)XIX2X3X4X5

X402[3]11011/3

X501220133/2

C(j)-Z(j)341000

X24[2/3]11/31/301/31/2

X50-1/304/3-2/317/3M

co)-z(j)1/30-1/3-4/30-4/3

XI313/21/21/201/2

X5001/23/2-1/215/2

c»z(j)0-1/2-1/2-3/20-3/2

最优解：X=(1/2,0,0,0,5/2)；最优值Z=3/2

maxZ-2xt+x2-3x3+5JC4

xt+5JC2+3X3-7X4<30

⑵3%-x2+xi+x4<10

2x,-6X2-x3+4*4<20

X/W=l,,4

【解】单纯形表:

c(j)21-35000

R.H.S.Ratio

BasisC(i)XIX2X3X4X5X6X7

X50153-710030M

X603-1[1]10101010

X702-6-1[4]001205

C(j)-z(j)21-35000

X509/2-11/25/40107/465M

X605/2[1/2]5/4001-1/4510

X451/2-3/2-1/41001/45M

CG)-z①-1/217/2-7/4000-5/4

X50320150111-1120M

X21515/2002-1/21010

X45807/2103-1/220M

C(j)-Z(j)-430-2300-173

因为入7=3>0并且劭<0(i=l,2,3),故原问题具有无界解，即无最优解。

maxZ=3百+2x2

一%+2X2+3X3<4

⑶12

4xy-2X3<

3玉+8工2+4%3<10

xpx2,x3>0

【解】

co)32-0.125000

R.H.S.Ratio

BasisC(i)XIX2X3X4X5X6

X40-1231004M

X50[4]0-2010123

X6Z3

C(j)-Z(j)32-1/80000

X40025/211/4073.5

XI310-1/201/403M

X600[8]11/20-3/4111/8

co)-z(j)0211/80-3/409

X40009/817/16-1/427/46

XI310-1/201/403M

X2201[11/16]0-3/321/81/80.181818

CG)-Z(J)0000-9/16-1/437/4

X3进基、X2出基，得到另一个基本最优解。

c(j)32-0.125000

R.H.S.Ratio

BasisXIX2X3X4X5X6

X400-18/110113/22-5/1172/116

XI318/11002/111/1134/11M

X3-0.125016/1110-3/222/112/110.1818

C(j)-Z(j)0000-9/16-1/437/4

原问题具有多重解。

基本最优解X,l,=(3,-1,0,7—7,0)及乂⑵=(4三4,0,9£,7、?,0)r；Z=F卫，最优解的通解可表

841111114

示为X=aX">+(1-a)X⑵即

“，3411227272…小八

X=(------a,-Q,------Q,-------(7,0),(0<«<1)

1111811111111

maxZ=3%+2x2+x3

5x1+4X2+6为<25

(4)

<8%j+6X2+3X3<24

x.>0J=l,2,3

【解】单纯形表:

c(j)32100

R.H.S.Ratio

BasisC(i)XIX2X3X4X5

X4054610255

X50[8]6301243

C(j)-Z(i)321000

X4001/433/81-5/810

XI313/43/801/83

C(j)-Z(j)0-1/4-1/80-3/89

最优解：X=(3,0,0,10,0)；最优值Z=9

1.12分别用大M法和两阶段法求解下列线性规划:

maxZ=10%—5X2+x3

5%1+3X4-x=10

⑴23

-5%|+々-10%3415

>0,J=1,2,3

【解】大M法。数学模型为

maxZ=10玉一5X2+x3-Mx5

5%j+3X2+七+&=10

〈-5x[+々-1。尤3+工4=15

Xj>0,j=1,2,,5

co)10-510-M

R.H.S.Ratio

BasisC(i)XIX2X3X4X5

X5-M53101102

X40-51-101015M

co）-z（j）10-51000

*BigM531000

XI1013/51/501/52

X4004-91125

C(j)-Z(j)0-11-10-220

*BigM0000-10

最优解X=(2,0,0)；Z=20

两阶段法。

第一阶段：数学模型为

min卬=%

5%+3X2+x3+x5=10

-5X1+

〈x2-10x3+/=15

x}>0,j=l,2,,5

co)00001

R.H.S.Ratio

Basisc(i)XIX2X3X4X5

X51[5]3101102

X40-51-101015M

cu)-z(j)-5-3-100

XI013/51/501/52

X4004-91125

C(j)-Z(j)00001

第二阶段

co)10-510

R.H.S.Ratio

BasisC(i)XIX2X3X4

XI1013/51/5022

X4004-9125M

CQ)-Z(j)0-11-10

最优解X=(2,0,0)；Z=20

minZ=5苞-6x2-7x3

x,+5々-3龙3>15

⑵5X1-6%+10x<20

<3

%+工2+X3=5

x.>0J=l,2,3

【解】大M法。数学模型为

minZ=5%一6x2-7七++MAy

+5%2—-S]+4=15

5%j-6X+1()X3+5=20

<22

X1+工2+工3+4=5

所有变量非负

co)5-6-700MM

R.H.S.Ratio

Basisc(i)XIX2X3SIS2AlA3

AlM1[5]-3-1010153

S0M

A3M111000155

C(j)-Z(j)5-6-70000

*BigM-2-621000

X2-61/51-3/5-1/501/503M

S2031/5032/5-6/516/503895/16

A3M4/50[8/5]1/50-1/5125/4

C(j)-Z(j)31/50-53/5-6/506/50

*BigM-4/50-8/5-1/506/50

X2-61/210-1/801/83/815/4

S20300-212-430

X3-71/201