《運(yùn)籌學(xué)》教材習(xí)題答案

教材習(xí)題答案

部分有圖形的答案附在各章PPT文檔的后面，請(qǐng)留意。

第1章線性規(guī)劃

第2章線性規(guī)劃的對(duì)偶理論

第3章整數(shù)規(guī)劃

第4章目標(biāo)規(guī)劃

第5章運(yùn)輸與指派問題

第6章網(wǎng)絡(luò)模型

第7章網(wǎng)絡(luò)計(jì)劃

第8章動(dòng)態(tài)規(guī)劃

第9章排隊(duì)論

第10章存儲(chǔ)論

第11章決策論

第12章對(duì)策論

習(xí)題一

1.1討論下列問題：

（1）在例1.1中，假定企業(yè)一周內(nèi)工作5天，每天8小時(shí)，企業(yè)設(shè)備A有5臺(tái)，利用率為

0.8,設(shè)備B有7臺(tái)，利用率為0.85,其它條件不變，數(shù)學(xué)模型怎樣變化.

（2）在例1.2中，如果設(shè)刑=1,2,7）為工作了5天后星期一到星期日開始休息的營(yíng)

業(yè)員，該模型如何變化.

（3）在例1.3中，能否將約束條件改為等式：如果要求余料最少，數(shù)學(xué)模型如何變化；簡(jiǎn)

述板材下料的思路.

（4）在例1.4中，若允許含有少量雜質(zhì)，但雜質(zhì)含量不超過1%,模型如何變化.

（5）在例1.6中，假定同種設(shè)備的加工時(shí)間均勻分配到各臺(tái)設(shè)備上，要求一種設(shè)備每臺(tái)每

天的加工時(shí)間不超過另一種設(shè)備任一臺(tái)加工時(shí)間1小時(shí)，模型如何變化.

1.2工廠每月生產(chǎn)“、8、C三種產(chǎn)品，單件產(chǎn)品的原材料消耗量、設(shè)備臺(tái)時(shí)的消耗量、資源

限量及單件產(chǎn)品利潤(rùn)如表1—22所示.

表1—22

ABC資源限量

材料（kg）1.51.242500

設(shè)備（臺(tái)時(shí)）31.61.21400

利潤(rùn)（元/件）101412

根據(jù)市場(chǎng)需求，預(yù)測(cè)三種產(chǎn)品最低月需求量分別是150、260和120,最高月需求是250、310

和130.試建立該問題的數(shù)學(xué)模型，使每月利潤(rùn)最大.

【解】設(shè)修、必、與分別為產(chǎn)品A、B、C的產(chǎn)量，則數(shù)學(xué)模型為

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長(zhǎng)的塑鋼材料制作A、B兩種型號(hào)的窗架.兩種窗架所需材料規(guī)格

及數(shù)量如表1—23所示：

表1—23窗架所需材料規(guī)格及數(shù)量

型號(hào)A型號(hào)B

長(zhǎng)度長(zhǎng)度

數(shù)量（根）數(shù)量（根）

每套窗架需要（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

第二步：建立線性規(guī)劃數(shù)學(xué)模型

設(shè)芍。.=1,2,…，14）為第/種方案使用原材料的根數(shù)，則

（1）用料最少數(shù)學(xué)模型為

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

產(chǎn)jNO,J=1,2,…,14

用單純形法求解得到兩個(gè)基本最優(yōu)解

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)余料最少數(shù)學(xué)模型為

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

用單純形法求解得到兩個(gè)基本最優(yōu)解

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根

顯然用料最少的方案最優(yōu)。

1.4乩8兩種產(chǎn)品，都需要經(jīng)過前后兩道工序加工，每一個(gè)單位產(chǎn)品/需要前道工序1小時(shí)

和后道工序2小時(shí)，每一個(gè)單位產(chǎn)品8需要前道工序2小時(shí)和后道工序3小時(shí).可供利用

的前道工序有11小時(shí)，后道工序有17小時(shí).

每加工一個(gè)單位產(chǎn)品B的同時(shí)，會(huì)產(chǎn)生兩個(gè)單位的副產(chǎn)品C,且不需要任何費(fèi)用，產(chǎn)品C

一部分可出售贏利，其余的只能加以銷毀.

出售單位產(chǎn)品N、B、C的利潤(rùn)分別為3、7、2元，每單位產(chǎn)品C的銷毀費(fèi)為1元.預(yù)測(cè)表

明，產(chǎn)品C最多只能售出13個(gè)單位.試建立總利潤(rùn)最大的生產(chǎn)計(jì)劃數(shù)學(xué)模型.

【解】設(shè)x/2分別為產(chǎn)品A、B的產(chǎn)量，有為副產(chǎn)品C的銷售量g為副產(chǎn)品C的銷毀量，

有X3+X4=2X2,Z為總利潤(rùn)，則數(shù)學(xué)模型為

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

X]+2X2<11

2玉+3X2417

?—2%2+X3+40

》3413

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

1.5某投資人現(xiàn)有下列四種投資機(jī)會(huì)，三年內(nèi)每年年初都有3萬元(不計(jì)利息)可供投資：

方案■：在三年內(nèi)投資人應(yīng)在每年年初投資，一年結(jié)算一次，年收益率是20%,下一年可

繼續(xù)將本息投入獲利；

方案二：在三年內(nèi)投資人應(yīng)在第一年年初投資，兩年結(jié)算一次，收益率是50%,下一年可

繼續(xù)將本息投入獲利，這種投資最多不超過2萬元；

方案三：在三年內(nèi)投資人應(yīng)在第二年年初投資，兩年結(jié)算一次，收益率是60%,這種投資

最多不超過1.5萬元；

方案四：在三年內(nèi)投資人應(yīng)在第三年年初投資，一年結(jié)算一次，年收益率是30%,這種投

資最多不超過1萬元.

投資人應(yīng)采用怎樣的投資決策使三年的總收益最大，建立數(shù)學(xué)模型.

【解】是設(shè)修?為第i年投入第/項(xiàng)目的資金數(shù)，變量表如下

項(xiàng)目一項(xiàng)目二項(xiàng)目三項(xiàng)目四

第1年孫X12

第2年孫工23

第3年知與4

數(shù)學(xué)模型為

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

最優(yōu)解X=（30000,0,66000,0,109200,0）；Z=84720

1.6IV發(fā)展公司是商務(wù)房地產(chǎn)開發(fā)項(xiàng)目的投資商.公司有機(jī)會(huì)在三個(gè)建設(shè)項(xiàng)目中投資：高層

辦公樓、賓館及購(gòu)物中心，各項(xiàng)目不同年份所需資金和凈現(xiàn)值見表1—24.三個(gè)項(xiàng)目的投資

方案是：投資公司現(xiàn)在預(yù)付項(xiàng)目所需資金的百分比數(shù)，那么以后三年每年必須按此比例追加

項(xiàng)目所需資金，也獲得同樣比例的凈現(xiàn)值.例如，公司按10%投資項(xiàng)目1,現(xiàn)在必須支付

400萬，今后三年分別投入600萬、900萬和100萬，獲得凈現(xiàn)值450萬.

公司目前和預(yù)計(jì)今后三年可用于三個(gè)項(xiàng)目的投資金額是：現(xiàn)有2500萬，一年后2000萬，兩

年后2000萬，三年后1500萬.當(dāng)年沒有用完的資金可以轉(zhuǎn)入下一年繼續(xù)使用.

IV公司管理層希望設(shè)計(jì)一個(gè)組合投資方案，在每個(gè)項(xiàng)目中投資多少百分比，使其投資獲得

的凈現(xiàn)值最大.

表1—24

10%項(xiàng)目所需資金（萬元）

年份

項(xiàng)目1項(xiàng)目2項(xiàng)目3

0400800900

1600800500

2900800200

3100700600

凈現(xiàn)值450700500

【解】以1%為單位，計(jì)算累計(jì)投資比例和可用累計(jì)投資額，見表（2）。

表（2）

每種活動(dòng)單位資源使用量（每個(gè)百分點(diǎn)投資的累計(jì)數(shù)）

年份

項(xiàng)目1項(xiàng)目2項(xiàng)目3累計(jì)可用資金（萬元）

04080902500

11001601404500

21902401606500

32003102208000

凈現(xiàn)值457050

設(shè)巧為/項(xiàng)目投資比例，則數(shù)學(xué)模型:

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

最優(yōu)解x=(0,16.5049,13.1067)；Z=1810.68萬元

實(shí)際投資

年份項(xiàng)目2比例：項(xiàng)目3比例：

項(xiàng)H1比例：0累計(jì)投資（萬元）

16.504913.1067

001320.3921179.6032499.995

102640.7841834.9384475.722

203961.1762097.0726058.248

305116.5192883.4747999.993

凈現(xiàn)值01155.343655.335

1.7圖解下列線性規(guī)劃并指出解的形式:

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

【解】最優(yōu)解X=(3/4,7/2)；最優(yōu)值Z=-45/4

x1+2X2<11

一項(xiàng)+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

【解】最優(yōu)解X=(3/2,1/4)；最優(yōu)值Z=7/4

minZ=%]+2X2

x[-x2>2

(5)Xj>3【解】最優(yōu)解X=(3,0)；最優(yōu)值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

【解】最優(yōu)解X=(2,4)；最優(yōu)值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為松馳變量，則標(biāo)準(zhǔn)形式為

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）將絕對(duì)值化為兩個(gè)不等式，則標(biāo)準(zhǔn)形式為

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

則標(biāo)準(zhǔn)型為

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，占=再'一再〃，線性規(guī)劃模型變?yōu)?/p>

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

標(biāo)準(zhǔn)型為

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設(shè)線性規(guī)劃

maxZ=5x)+2x2

2xl+3X2+x3=50

<4x)-2X2+4=60

Xj20J=L…,4

-211「2O'

取基4=(%p3)=40、層=4],分別指出坊和&對(duì)應(yīng)的基變量和非基變量，

求出基本解，并說明巴、當(dāng)是不是可行基.

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

基。當(dāng)：尢是基變量，應(yīng)用為非基變量，基本解X=(25,0,0,-40)，,B2不是可行基。

1.10分別用圖解法和單純形法求解下列線性規(guī)劃，指出單純形法迭代的每一步的基可行解對(duì)

應(yīng)于圖形上的那一個(gè)極點(diǎn).

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

對(duì)應(yīng)的頂點(diǎn):

基可行解可行域的頂點(diǎn)

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

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

爐=O。)'37

（牙5）

42

最優(yōu)解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

對(duì)應(yīng)的頂點(diǎn):

基可行解可行域的頂點(diǎn)

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)

最優(yōu)解：X=(2,2,0,0,0)；最優(yōu)值Z=—16

該題是退化基本可行解，5個(gè)基本可行解對(duì)應(yīng)4個(gè)極點(diǎn)。

1.11用單純形法求解下列線性規(guī)劃

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

最優(yōu)解：X=(1/2,0,0,0,5/2)；最，優(yōu)值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

因?yàn)槿?=3>0并且a〃〈0(i=l,2,3),故原問題具有無界解，即無最優(yōu)解。

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進(jìn)基、X2出基，得到另一個(gè)基本最優(yōu)解。

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?

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

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

最優(yōu)解：X=(23,0,0,5,0,0,24)；最優(yōu)值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

最優(yōu)解：X=(3,0,0,9,0)；最優(yōu)值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

最優(yōu)解：X=(50,0,0,0,0,30)；最優(yōu)值Z=250

1.12分別用大河法和兩階段法求解下列線性規(guī)劃:

maxZ=10Xj-5x2+x3

5占+3X+XJ=10

⑴2

—5^1+%—10%3415

xy>0,7=1,2,3

【解】大M法。數(shù)學(xué)模型為

maxZ=10項(xiàng)-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