《运筹学》教材习题答案

教材习题答案

部分有图形的答案附在各章PPT文档的后面，请留意。

第1章线性规划

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

第3章整数规划

第4章目标规划

第5章运输与指派问题

第6章网络模型

第7章网络计划

第8章动态规划

第9章排队论

第10章存储论

第11章决策论

第12章对策论

习题一

1.1讨论下列问题：

（1）在例1.1中，假定企业一周内工作5天，每天8小时，企业设备A有5台，利用率为

0.8,设备B有7台，利用率为0.85,其它条件不变，数学模型怎样变化.

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

业员，该模型如何变化.

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

述板材下料的思路.

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

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

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

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

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

表1—22

ABC资源限量

材料（kg）1.51.242500

设备（台时）31.61.21400

利润（元/件）101412

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

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

【解】设修、必、与分别为产品A、B、C的产量，则数学模型为

maxZ=IO%I+14x2+12x3

1.5%,+1.2X2+4X3<2500

3X]+1.6X2+1.2X3<1400

150<%!<250

260<x2<310

120<x3<130

x],x2,xJ>0

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

及数量如表1—23所示：

表1—23窗架所需材料规格及数量

型号A型号B

长度长度

数量（根）数量（根）

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

材料A)：1.72Bi：2.72

A2：1.33B1：2.03

需要量（套）200150

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

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

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

Bl:2.7m21110000000000300

B2:2m01003221110000450

Al:1.7m00100102103210400

A2:1.3m01120010130234600

余料0.600.30.700.30.70.610.10.900.40.8

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

设芍。.=1,2,…，14）为第/种方案使用原材料的根数，则

（1）用料最少数学模型为

14

minZ=

J=I

2%+x2++x4>300

x2+3X5+2X6+2X7+/+/+x10>450

否+玉

<+x6+2xs+/+3X]1+223N400

阳

x2+x3+2X4+x7+x9+3x10+22+3XQ+4x14>600

产jNO,J=1,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.4x13+0.8xl4

2XI+x2+xi+x4>300

x2+3X5+2X6+2X7++x9+x10>450

<x3+x6+2xg+/+3x”+2xl2+X]3>400

x,+x3+2X4+匕+/+3x10+2X12+3和+4x14>600

X/NO,J=1,2,…,14

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

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

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

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

1.4乩8两种产品，都需要经过前后两道工序加工，每一个单位产品/需要前道工序1小时

和后道工序2小时，每一个单位产品8需要前道工序2小时和后道工序3小时.可供利用

的前道工序有11小时，后道工序有17小时.

每加工一个单位产品B的同时，会产生两个单位的副产品C,且不需要任何费用，产品C

一部分可出售赢利，其余的只能加以销毁.

出售单位产品N、B、C的利润分别为3、7、2元，每单位产品C的销毁费为1元.预测表

明，产品C最多只能售出13个单位.试建立总利润最大的生产计划数学模型.

【解】设x/2分别为产品A、B的产量，有为副产品C的销售量g为副产品C的销毁量，

有X3+X4=2X2,Z为总利润，则数学模型为

maxZ=3X]+7x,+2x3-x4

X]+2X2<11

2玉+3X2417

«—2%2+X3+40

》3413

X/20,/=1,2,…,4

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

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

继续将本息投入获利；

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

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

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

最多不超过1.5万元；

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

资最多不超过1万元.

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

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

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

第1年孙X12

第2年孙工23

第3年知与4

数学模型为

maxZ=0.2X]]+0.2x2l+0.2x3l+0.5xl2+0.6x23+0.3x34

xH+xl2<30000

-1.2xu+x21+x23<30000

—1.5X|2—1.2%2i+X31+X34430000

■x]2<20000

x23<15000

x34<10000

Xy>0,z=l,---,3；y=l,---4

最优解X=（30000,0,66000,0,109200,0）；Z=84720

1.6IV发展公司是商务房地产开发项目的投资商.公司有机会在三个建设项目中投资：高层

办公楼、宾馆及购物中心，各项目不同年份所需资金和净现值见表1—24.三个项目的投资

方案是：投资公司现在预付项目所需资金的百分比数，那么以后三年每年必须按此比例追加

项目所需资金，也获得同样比例的净现值.例如，公司按10%投资项目1,现在必须支付

400万，今后三年分别投入600万、900万和100万，获得净现值450万.

公司目前和预计今后三年可用于三个项目的投资金额是：现有2500万，一年后2000万，两

年后2000万，三年后1500万.当年没有用完的资金可以转入下一年继续使用.

IV公司管理层希望设计一个组合投资方案，在每个项目中投资多少百分比，使其投资获得

的净现值最大.

表1—24

10%项目所需资金（万元）

年份

项目1项目2项目3

0400800900

1600800500

2900800200

3100700600

净现值450700500

【解】以1%为单位，计算累计投资比例和可用累计投资额，见表（2）。

表（2）

每种活动单位资源使用量（每个百分点投资的累计数）

年份

项目1项目2项目3累计可用资金（万元）

04080902500

11001601404500

21902401606500

32003102208000

净现值457050

设巧为/项目投资比例，则数学模型:

maxZ=45X(+70x2+50x3

40XI+80x,+9OOX3-2500

X

100X1+16QX2+1403<4500

<190x,+240X2+160X3<6500

200x,+310x2+220X3<8000

巧NO,/=1,2,3

最优解x=(0,16.5049,13.1067)；Z=1810.68万元

实际投资

年份项目2比例：项目3比例：

项H1比例：0累计投资（万元）

16.504913.1067

001320.3921179.6032499.995

102640.7841834.9384475.722

203961.1762097.0726058.248

305116.5192883.4747999.993

净现值01155.343655.335

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

maxZ=-2xl+x2

xi+x2>\

(1),、i

j玉-5X2>-1

2>0

minZ=-x]-3x2

2x,—x,2~2

2)

<2x1+3X2<12

%1>0,x2>0

【解】最优解X=(3/4,7/2)；最优值Z=-45/4

x1+2X2<11

一项+4X<10

⑶2

2xl-x2<7

X]-3x2<1

X”工2~0

maxZ=x1+x2

3xj+8X2<12

(4)xl+x2<2

2x}<3

x,,x2>0

【解】最优解X=(3/2,1/4)；最优值Z=7/4

minZ=%]+2X2

x[-x2>2

(5)Xj>3【解】最优解X=(3,0)；最优值Z=3

<

x2<6

x19x2>0

maxZ=+2X2

x}-x2>2

(6)%1>3

x2<6

x],x2>0

$+2X2>6

<x1+x2<2

x15x2>0

【解】无可行解。

maxZ=2.5玉+2x2

2x,+x2<8

(8)0.5再<1.5

<

%]+2X2<10

x1?x2>0

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

maxZ=x}+4X2-x3

2x]+x2+3X3<20

(1)5x-7X+4X>3

*}23

1Ox1+3X2+6X3>-5

%>0,x220,七无限制

【解】(1)令七二只一另户4，匕/6为松驰变量，则标准形式为

maxZ=x]-4X2一9+X；

2xl+4+3x；-3x；4-x4=20

5x-7X+4x；-4x；-X=3

<l25

—1O']—3%2—6X3++4=5

x]9x2,x3,x3,x4,x59x6>0

minZ=9x]-3x2+5x3

16Xj+7x?-4X3|<20

⑵Xj>5

F+8X2=-8

%)>0,x2>0,x3>0

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

r

maxZ--9%j+3x2-5x3

6Xj+7X2-4X3+x4=20

-6Xj-7X2+4X3+x5=20

-4=5

-%]_8%2=8

x19x2,x3,x4,x5?x6>0

maxZ=2x]+3x2

1<<5

⑶

<-Xi+x2=-l

x,>0,x2>0

【解】方法1:

maxZ=2%+3x2

石一£=1

%)+x=5

<4

x,-x2=1

x19x2,x3,x4>0

方法2：令X=$—1,有玉=工+1,4<5—1=4

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

x；<4

<一(X；+1)4~%2二-1

Xj,x2>0

则标准型为

maxZ=2+2x；+3x2

x[+x3=4

<—X：+々=0

x[,x2,x3>0

maxZ=min(3X1+4x29x]+x2+x3)

X)+2X2+x3<30

(4)4X1-9+2X>15

<3

9石+%+6X3>-5

X1无约束,％2、1NO

【解】令”3司+4超jVXi+Z+工3，占=再'一再〃，线性规划模型变为

maxZ=y

y<3（x{-x；）+4X2

y<x{-x：+x2+x3

x\-x：+2X2+x3<30

4（x；-x；）-x2+2X3>15

9（x；—x^）+/+6x32—5

x[,Xp%2>x3>0

标准型为

maxZ=y

y—3x；+3k—4/+%=0

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

x{-X^+2X+x+x=30

*236

4x[-4k-x2+2X3-x7=15

-9x；+9X^-X2-6X3+4=5

、再，玉，》2，*3，*4，*5，*6，工7，*82。

1.9设线性规划

maxZ=5x)+2x2

2xl+3X2+x3=50

<4x)-2X2+4=60

Xj20J=L…,4

-211「2O'

取基4=(%p3)=40、层=4],分别指出坊和&对应的基变量和非基变量，

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

【解】囱：修，冷为基变量，必，X4为非基变量，基本解为x=(15,0,20,0)T,B]是可行

基。当：尢是基变量，应用为非基变量，基本解X=(25,0,0,-40)，,B2不是可行基。

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

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

maxZ=玉+3X2

-2x,+x9<2

(1)

<2xl+3X2<12

xpx2>0

【解】图解法

单纯形法:

CO)1300

bRatio

C(i)BasisXIX2X3X4

0X3-2[11I022

0X42301124

C(j)-Z(j)13000

3X2-21102M

0X4|8|0・3160.75

co)-zo)70-306

3X2010.250.257/2

1XI10-0.3750.1253/4

C(j)-z(j)00-0.375-0.87511.25

对应的顶点:

基可行解可行域的顶点

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

X(2)=(0,2,0,6,)-(0,2)

炉=O。)'37

（牙5）

42

最优解X=(；3J7,Z=4?5

minZ=-3x1一5x2

X]+2X2<6

Q)X[+4X2<10

x,+x2<4

Xj>0,x2>0

【解】图解法

单纯形法:

C(j)-3-5000

bRatio

Basisc(i)XIX2X3X4X5

X301210063

X401|4|010102.5

X501100144

C(i)-Z(j)-3-50000

X30|0.5|01-0.5012

X2-50.25100.2502.510

X500.7500-0.2511.52

C(j)-Z(j)-1.75001.250-12.5

XI-3102-102M

X2-501-0.50.5024

X5000-1.510.5]100

co）-z（j）003.5-0.50-16

XI-310-1022

X2-50110-12

X4000-3120

C(j)-z①00201-16

对应的顶点:

基可行解可行域的顶点

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

X(2)=(0,2.5,1,0,1.5,)'(0,2.5)

X(3)=(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=3X|+4x2+x3

2xl+3X2+x3<1

(1)

V

xl+2X2+2X3<3

Xj20,/=1,2,3

【解】单纯形表：

C①34100

R.H.S.Ratio

Basisc(i)XIX2X3X4X5

X40213]11011/3

X501220133/2

341000

X2412/3111/31/301/31/2

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

C(j)-z①1/30-1/3-4/30-4/3

XI313/21/21/201/2

X5001/23/2-1/215/2

C(j)-Z(j)0-1/2-1/2-3/20-3/2

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

maxZ=2X]+X2-3X3+5x4

x}+5X2+3X3-7X4<30

(2)-x2+x3+x4<10

2x,-6X2-X3+4X4<20

Xj=

【解】单纯形表：

C①21-35000

R.H.S.Ratio

Basisc(i)XIX2X3X4X5X6X7

X50153-710030M

X603-1[1]10101010

X702-6-1|4|001205

c(j")21-35000

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

X605/2|1/2|5/4001-1/4510

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

c(j)-zG)-1/217/2-7/4000-5/4

X50320150111-1120M

X21515/2002-1/21010

X45807/2103-1/220M

C(j)-z①-430-2300-173

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

max

Z=3xl+2x2

-Xj+<4

2X2+3X3

⑶-2X<12

V3

310

玉+8X2+4X3<

xpx2,x3>0

【解】

CO)32-0.125000

R.H.S.Ratio

Basisc(i)XIX2X3X4X5X6

X40-1231004M

X50|4|0-2010123

X60384001103.3333

CG)-zo)32-0.1250000

X40022.510.25073.5

XI310-0.500.2503M

X600|8|5.50-0.75110.125

021.3750-0.7509

X40001.12510.4375-0.256.756

XI310-0.500.2503M

X2201[0.6875]0-0.09380.1250.1250.181818

C(j)-Z(j)0000-0.5625-0.259.25

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

CO)32-0.125000

R.H.S.Ratio

BasisXIX2X3X4X5X6

X400-1.6010.5909-0.45456.54556

XI310.73000.18180.09093.0909M

X3-0.12501.4510-0.13640.18180.18180.1818

0000-0.5625-0.259.25

原问题具有多重解。

177，7?

基本最优解X”)=(3,—,0,」,0)及X。)=(二,0,一,L-o)r；Z=3•，最优解的通解可表

841111114

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

X=32.72)

1111811111111

minZ=-2Xj-x2-4x3+x4

X]+2X24-x3-3X4<8

X

(4)-x2+x3+24<10

XXX

2x}+72-53-104<20

Xj>0,j=4

【解】单纯形表:

C(j)-2-1-41000

R.H.S.Ratio

BasisC(i)XIX2X3X4X5X6X7

X5012111-310088

X600-1120101010

X7027-5-1000120M

C(j)-Z(j)-2-1-41000

X3-4121-31008M

X60-1-30|5|-11020.4

X707170-2550160M

C(j)-Z①270-11400

X3-4|2/5|1/5102/53/5046/523

X41-1/5-3/501-1/51/502/5M

X7022000517035

C(j)-z①-1/52/5009/511/50

XI-211/25/2013/2023

X410-1/21/2101/205

X7001-50-22124

co)-zo)01/21/2025/20

最优解：X=(23,0,0,5,0,0,24)；最优值Z=-41

M

maxZ=3+2x2+x3

5玉+4X2+6X3<25

(5)

<8』+6X2+3X3<24

xy>0,j=1,2,3

【解】单纯形表:

c(j)32100

R.H.S.Ratio

Basisc(i)XIX2X3X4X5

X4054610255

X50|8|6301243

321000

X4000.254.1251-0.62510

XI310.750.37500.1253

C(j)-ZG)0-0.25-0.1250-0.3759

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

maxZ=5再+6x2+8x3

x}+3X2+2X3<50

(6)

x}+4X2+3X3<80

x1>0,x2>0,x3>0

【解】单纯形表:

co)56800

R.H.S.Ratio

Basisc(i)XIX2X3X4X5

X4013[2]105025

X50143018026.6667

CG)-z(j)568000

X3811/2]3/211/202550

X50-1/2-1/20-3/215M

co1-60-40-200

XI51321050

X50011-1130

C(j)-Z(j)0-9-2-50-250

最优解：X=(50,0,0,0,0,30)；最优值Z=250

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

maxZ=10Xj-5x2+x3

5占+3X+XJ=10

⑴2

—5^1+%—10%3415

xy>0,7=1,2,3

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

maxZ=10项-5X24-X3-MX5

5X1+3/+工3+15=10

{一5%+x2-10x3+x4=15

Xj>0,y=l,2,---,5

cd)10-510-M

R.H.S.Ratio

Basisc(i)XIX2X3X4X5

X5-M53101102

X40-51-101015M

C(j)-Z(j)10-51000

*BigM531000

XI1013/51/501/52

X4004-91125

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