运筹学实用教材(第二版)宁宣熙编著课后习题答案

第一章线性规划的基本理论及其应用

1.解:建立数学模型如下:设每天应生产A、B、C三种型号的电冰箱各z”

台。

目标函数：mxaz=50工]+40工2+3013

'40Z]+40Z2+50Z342000

约束条件：17勺+3巧+6X3C150

2.解:设每天生产甲种酒（含A酒巧斤，含B酒以斤，含C酒巧斤）共与+

及+亚斤，生产乙种酒（含A酒6斤，含B酒4斤，含C酒4斤洪工4+药+

x6斤，生产丙种酒（含A酒Z7斤，含B酒之8斤，含C酒工9斤洪工7+4+工9斤。

+++

目标函数:maxz=6.8(ii+X2X3)+5.7(x4X5+X6)+4.5(x7xg+X9)

-7(X1+Z4+x7)-5(X2+Z5+18)―4(23+76+之9)

maxz=-0.2xi+1.8x2+2.8x3-1.3x4+0.7x5+1.7x6-2.5x7-0.5xg

2xi-3x2-34》。

xi+x2-4x3^0

17x4-3x5-3162。

3x4+3x5-216》0

化简为:

巧+一科30

=>

工1+j:4+叫＜2000

“2+N5+了842500

13+4+19(1200

Q0,(i=l,2,…，9)

3.用图解法解下列线性规划问题。

(1)maxz=3xi+2工?

2xi+44422

-x\+41241。

s.-1247

xi-3x2^1

口1，12)0

解:作图

-X144X2=10

可行域是OABCDE('如图)。

角顶可行解0(0,0),A(0,2.5),B(4,3.5),C(5,3),D(4,1),E(1,0)。

其中在角顶C处目标函数值最大。

:,•有唯一最优解:maxz=21;以=5,亚=3。

(2)maxz=2xi+孙

X2410

2xj+5x2460

S.t.V+12418

3xi+乃《44

解:作图

3X*X2=44

E

可行域是OABCDEo角顶可行解0(0,0),A(0,10),B(5,10)，C(10,8),

D(13,5),E(44/3,0)O

其中在角顶D处有唯--最优解:maxz=31,z；=13,皿=5。

(3)maxz=13xi+央

x\43

S.t.^Xj-1240

>0

解:作图

有可行域(如图阴影部分)但maxz无界。・,・无最优解。

(4)maxz=3孙-212

fxi+工241

s.+2x2>4

〔i"2>0

解:作图

无闭合域，此题无可行解。

4.用单纯形法解：

(1)maxz=2xi+X2

1241°

2xi+5]2460

xi+皿＜18

3xi+

X1，丁2)0

解:引进松弛变量X3，X4,X5，X6O

X2+Xj=10

2xi+5^2+^4=60

11+12+15=18

3xi+12+16=44

工R,(z=1,2,••,6)

X\n1314有16

b0

C210000

*3001100010

工402501006030

401100101818

；

Z60③100014414-j-

Zi0000000

«)*-2-10000

工3001100010▼10

139292

140001o_2

33313

®-110

小000015；

33

1144

2100044

3T

2288

巧2000

333

__L2

与一F00

003

1300010-1.50.55

1400001-6.51.59

X2101001.5-0.55

工121000-0.50.513

21000.50.531

00000.50.5最优解

二最优解为XI=13,X2=5,X3=5,X4=9,X5=X6=0O

maxz=310

(2)maxz=4xi+3x2+6x3

3xj+*2+3^3430

s.2xi+2x2+3x3<40

匹》0,£=1,2,3

解:加入松弛变量14,孙

3xj+为+343+14=30

v2孙十2x2+3^3+X5=40

,(£=1,234,5)

皿工24工415

Xb0

C43600

14031③1.03010;

13X

150223014023

7000000

-4-3-600

11

1361101030

T3

150-1①0-111010；

j62・62060

Z/-J2-1020

4220

工601

3333

123-110-1110,

2j5361170

巧-F10011最优解

・♦・最优解：了1=012=1073=3

maxz=70

5.求解线性规划minz=20xi+15x2

解：max(-z)=-20孙-15孙

2]1+工225-2xi-12<一5

-3xi+21243-3xj+2]243

s.t.j=>

Xi+1273-1]一央<―3

士,

xi，x2^022)0

加入松弛变量巧,14，工5

max(-z)=-20zi-1522+0・13+0・14+0・15

，—2xi—12+与三—5

-3xi+2x2+#4=3

•・S.tJ,用对偶单纯形法解:

一不一央+=_3

/>0(1=1,2,…5)

X11213“4

Xb

C-20-15000

*30O-1100-51

Z40-320103

0-1-1001-3

2000000

与-ci2015000

I却I。I号|="

15

__L00

zi-201T2

/

10

03—_3101

工40’22

_J_

Xs00(3)012,

巧-20-101000-50

与一与051000

\

15II。I10

1-1/2I-101-1/2I=20

x\-2010-1012

X4000-5177

X2~150110-21

町-20-155010-55

芍一弓005010

••最优解:孙=2,e=1，14=7,13=4=0

max(-z)=-55

••.minz=55

6.(1)化为标准型：

令X4=X4-X4(X4,X4^0)

max(-z)=~2x\-JC2^--M*x

■+0・27.M•元8+0・29+0,力10_

3zi+K-K+巧=25

Zl+Z2+l3+*W+元6=20

4#[+6工3-1r7+x8=5

S・t.〈,〃

2x2+3^3+2x4-2x4+X9=30.

222+373+-2K-zio+xn=2

、工1，12,13,24，14,二5，16，17，H8，19,110，111

(2)列出初始单纯形表：

Xi1213X4x了8X9

n6N7NioXII

Xb

c-2—151-10一M0-M00-M

1s03001-1100000025

*-M11I1-1010000020

X8-M40•60000-110005

工9002.32-2000010030

xii一M0232-200000-112

-5M-3M-10M-3M3M0一MM—M0M-M-27M

灯F-5M+2-3M+1-10M~5~3M-13M+100M00M0

7.求下列线性规划的对偶问题

(l)maxz=60xi+50J：2minw=401yl-6y2+25y3

x\+212440

“―2y2+山》60

-2Z|+―6对偶

2»I+N2+，3)50

11+皿<25=>

“，》2，、3.

皿，/2>0,

(2)maxz=24xj+28xminw=48yl+9y2+7y3

4xj+6x2=48

十丁2224

1149s.t.16yl+»3)28

S，T<X<7

21丁2,山>0,31无非负要求

了1，%2》0

(3)minz=2x\+以-6x3-解:将原来的约束条件转换为:

-371一工42一25

3xi+14425

N1+72+13+工4=20

币++%3+14=20

4xi+623>5

s.t・V4勺+61325=>

2x2+3Z3+21422

24222+3叫+2^4^30

_2x2_3^3-214》—30

.1],Z2，N320,l4无非负要求

%1，12，Z3)0，了4无非负要求

则其对偶问题为：maxw=-25yl+20y2+5y3+2y4-30y$

-3yl+%+41y342

*2+2%-2y$<1

s.Iyi+6y3+3%-3ys&-6

―3+,2+2y4-2第=-1

“，?3，丁4，»5'0，”无非负要求,

8.用对偶单纯形法解。minz=20x1+10x2

解：max(-z)=-20xi-10x2

(Sxi+12>6(-5xi-X2^-6

S.匕42之1+2R2>8=>s.t.{-2zi-2l2〈-8

111，力2301Z1，222

引入松弛变量w，14max(-z)=-20彳1-1032+0・13+0,14

—5x)―央+23=-6

<-2x\-2^2+A=-8

.1，Z2，*3,74°

X1N3*4

Xb

C-20-1000

工30-5-110一6

0-2@01-8；

00000

芍-F2010200

1当1=1。1好5

O__L

13001-2-21

-101104

A-10-1005-40

10005

弋005

瑁=2.5H=l。

xi—2010

4专*

1

X20得

~10•143/

与-20-102.53.75-45

町一弓002.53.75

最优解:了1=4x2=3y

max(-z)=-45

minz=45

9.(1)用单纯形法解：

加入松弛变量r4，/5，26

maxz=2xi一工2+i3+0・Z4+0・R5+0・^6

3xi-2x2+2x3+24=15

一11+12+工3+4=3

S.1

xi-x2+x3-t-x6=4

、工［，12,13，74'75,16^^°

X|12“3“4孙76

Xb6

C2-11000

Z403-22100155

X50-1110103

劭0①-1100144；

0000000

町-F-21-1000

口00

(D-110-333；

孙00020117

X|21-110014

2

-220028

弓-~ci0-11002

XI-101-11073

XS000201①7

7r

X1210010-27

2-1110-111

-1

町-900010

X2-101513024

工600020117

X1210412021

zi2-1311018

q一Cj002110

,最优解：」ri=219%2=：24一臼二=0。nnaxa:=18

M15一-21厂

(2)如果bi由3—♦4，求费的So

634.-2

-203■-130-

解：基矩阵B10-1B-1=011

-111-120-

对应于新的6列市虚）皂

13o-~20~-321

01146

.120--2.-28J

.，最优解变为[

a匚=28,32,0,0,0,6]T,即K匚1=2入央=32,巧=°

maxsV=-1X32+2X2J3=24

(3)如果1三为2O

因为H3不是:基空：ttO4C=21=1<83=2

所以最优解保:持7e0

(4)如果Ci由23更为3。则最2冬」笔纯形，表4£为

C13邛通

X

C3-11000

-101513024

孙00020117

310412021

i3-1723039

006230

Zj-Cj>Oo

二最优解不变：工1=21,12=24,工3=0。但目标函数值mazz=3X21-24

=39。

(5)[c3al3a23a33厂由[1,2,1,11变为[4,3,2,1]T

'130"3V

则对应于巧的列向量变为0112=3

.120.-1.-7-

Z3-C3=(-1X94-0X3+2X7)T-4=120

・•,最优解保持不变

%i=21,X2=24,#3=°。

maxz=18

(6)若增加一个新的约束条件2与+亚+

2X3<60

解:力口一个松弛变量与，(乃》0)2J：I+12+2巧+如=60

11X214x5X6为

b

2-110000

N2-1015130024

16000201107

勺2

1104120021

170212000.160

X2-1015130024

000201107

2104120021

X7000-11-3O-01-6；

巧2-13110018

工厂90021©00

=21J-I-1l_L|1

11-111111-3131-717

23150

“2-101_200

7777

33143

工600001

7・7T7

612135

叫21000

7777

113-A.6

00010

777

120

2-1yy00y

巧7

00yy00y

：,12=^=Xi====,mzx.z=^

j(j.(1)试用线性规划模型求解该厂最佳生产计划安排。

解;设生产椅子XJ把，生产桌子Z2张。

目标函数maxz=15xi+30x2maxz=15xj+30^2+0・(巧+工4+巧+%6)

4xi+512《2004xi+5x2+了3=200

2xi+4立242402x)+4^2+14=240

S.t."11&40=><x\+Z5=40

孙428Z2+16=28

Xj,12》0工)0,(，=1,2,…6)

i\•”2X4JT5Xb

Xbe

C15300000

13045100020040

产4024010024060

xs010001040

0*600(D000128287

2j0000000

Fj-15-300000

130④0100-56015；

丸020010-412864

必01000104040

入3001000•128

«/03000030840

与-9-15000030

1__5_

X\151b0015

44

_x3

“400010-298

5

00125

巧004

123001000128

0

町1530v40学41065

00¥00字最优解

，-Cj44

・••最优解：

X1=15,%2=28,为=4—0,14=98,4=25

maxz=1065兀。

(2)解：约束条件中限定系数b由［200,240,40,28『改变为［200,240,30,

35］TO

-4005-

2104

•・.基矩阵8=

100

-0001-

1_£

00

44

_3

10

B-1=一22

5.

01

一44

一0001.

・・・对应于6的列向量为

__5

0

-4

_3.

0

B-2

5.

1

4

01.

・•・最优生产计划改变为

[=6.25勺6把

X2-35张

rnaxz=15X6+30x351140元。

设生产面包不斤，饼干Z2斤,夹心饼工3斤,小甜饼Z4斤。

目标函数：rnaxz=0.15与+0.45x2+0.33x3+0.42x4

12xj+3^2+4-^-^3+1^*^44500

3J?2+4+&120

2xj+12x2+3^3+4144350

/Z]+'2^2+孑孙+孙4300

2xj++134250

+434100

1"2，13，14》。

用单纯形法解得最优解为:干=0,72=0,13=100,14=12.5

maxz=38.25元

。方解:设冬天买进的木材，冬天卖出可，春天卖出了2,夏天卖出了3,秋天卖

出了4；

春天买进的木材，春天卖出Z5,夏天卖出z6,秋天卖出工7；

'夏天买进的木材，夏天卖出工8,秋天卖出了9；

秋天买进的木材，秋天卖出勺0。

则每卖1万米3木材的利润表为：（万元）

卖出

冬春夏秋

买进

冬1530-0.01755-0.02745-0.037

春1035-0.01725-0.027

夏6555-0.017

秋5

，线性规划模型如下：

maxz=15xi+(30-0.017)x2+(55—0.027)x3+(45—0.037)x4+10xj

+(35-0.017)x6+(25—0.027)x7+65工8+(55—0.017)h9+5xio

工1<100

xi+巧&140

Z3+16+18&200

24+N7+19+1104160