运筹学部分章节习题答案

2.1用图解法求解下列线性规划问题，并指出各问题具有唯一最优解、无穷多最优解、无界

解还是无可行解。

maxz=2x,+x2

4内+3当<12

(1)2x+x<8

s.t.t2

4.%-x2<8

xpx2>0

4X1+3X2=12

所以：maxz=2x—+1=一

42

所以有唯一解

max=3x1+lx2

-XI+2X2<4

⑵311+2X2<14

xt-x2<4

为,看20

解:

X2

5

------>Xt——

(-x.+2x,=4

八।2解得：2

3XI+2X=1413

2x^=—

一4

513

所以:maxz=3x—+2x一=14

24

因为直线3再+2X2=0与直线3$+2々=14平行,

所以有无穷多最优解，maxz=14

maxz=2AJ+3x2

X-X<2

(3)12

-3X1+x2<4

X),x2>0

解：

maxz=Xj+x2

X]-x>0

(4)2

3*-x2<-3

xpx2>0

解:

2.2将卜列线性规划问题化为标准形式

minz=32+2x2-x3

minz=2xt-2x2+3x3

2x)-X32一3

一X]+%+5=4

(1)s.t.(2)^1+x3<1

-2x)+x2-<6s.t.

-2Xf+3X2-x3=-2

X1<0,x2>0,与无约束

X120,々无约束，右«0

解：(1)令X]——X]—O巧=13‘一"3''("3'，兀3''20)

则上述形式可化为:

M

maxz=2x('+2x2-3(x3'-x3)

M—2+(X3'_彳3'')=4

,,

2xt'+x2-(x3'-x3)+x4=6

，，，，

X,,X2,X3,X3,X4>0

minz=3X]+2x2-x3

24一匕之—3

(2)x1+<1

-2玉+3X2-x3=-2

xx>0,工2无约束，/VO

解：令尤；二一心0)

则上述形式可化为:

,M1

maxz=-3再-2(x2-x2)-x3

—2(/3")—'+"4=3

(X,'_X-,")—/'+%5=]

2xt-3(x2-x2")-A3*=2

,,,

XI,X2,X2,X3',X4,A5>0

2.3.在下列线性规划问题中，找出所有基解，指出哪些是基可行解并分别代入目标函数,

比较找出最优解。

maxz=3]+5x2

X1+刀3=4

(1)2X2+匕=12

3%1+2X2+X5=18

xy>0(7=1,2,34)

10500

CBXBXiX2X3X4b0

0x3341093

0X4[5J20188/5

10500

0Xa0[14/5]1/3-1/521/53/2

10Xi12/501/58/54

010-216

5x2015/14-3/143/2

10Xi10-1/72/71

00-5/14-25/1435/2

所以，最优解目标函数值为maxz=35/2

3

户=(《,(),0)r/

(2)

maxz=1OOX1+2OOx2

x1+x2<500

x,<200

2—+6X2<1200

xpx2>0

解：化为线性标准形式有:

maxz=1OOX]+200x2

*

X]+工2+X3--500

%1+x4=20C)

2M+6X2+x5=1200

jrpx2,x3,x4,x5>0

100200000

b

CBXBX1x2x3X4x5e

0X311100500500

+

0X410010200

0001200200

x52[5]1

100200000

0X32/3010-1/6300450

0X4[1]0010200200

2001/3001/6200600

x21

100/3000-100/340000

0X3001-2/3-1/6500/3

100X110010200

200010-1/31/6400/3

x2

0000-100/3140000/

3

山…口小口站心以140000丈CM40°5()0八八、

所以，最优目标函数值为maxz=---------x*=(200,-----,-----,0,0)

333

2.5.分别用大M法和两阶段法求解下列线性规划问题，并指事问题的解属于哪一类:

maxz=3x)+2x2

xi+2X2<7

(I)%1—X2>1

x,+x2>2

xl9x2>0

解：化为标准形式：

maxz=3内+2x2-Mx6-Mx7

X1+2X2+工3=7

X]-X2-X4+X6=}

X1+x2-x5+x7=2

XpX2,X3,X4,X5,X6,X7>0

32000-M-M

b

CBXBX.x2X3x4x5x6x7

0200007

x311

-MX6[1J-10-10101

-Mx71100-1012

3+2M20-M00

003006

X311-1

3X11-10-10101

-MX70[2]01-1-111

05+2M03+2M-M-3-2M0

000-1/2[3/2]1/2-39/2

X31

3X1100-1/2-1/21/21/23/2

2x20101/2-1/2-1/21/21/2

0001/2-M5/2-1/2-M-5/2-M

0X5002/3-1/311/3-26

3X1101/3-2/302/3-3/21

0

2x2001/3[1/3]-1/3-1/21

0001/2-M5/2-1/2-M-5/2-M

000005

X511-1

3X112100007

0

0X40311-106

0-4-300-M-M21

所以Z*=21x*=(7,0,0,6,5,0,0)

⑵

maxz=2xt-x2-x3

3为+2X2+.>18

2x+x<4

<}2

x]+x2-x3=5

X,占,与20

解：化为标准形式：

minz=%十七

32+2X2+x3-x4+x6=18

2X1+x2+x5=4

X1+x2-x3+=5

xpx2,x3,x4,x5,x6x7>0

0000011

b

CBXBX1x2x3x4X5x6X7

1X6321-101018

0X5[2]1001004

1X711-100015

-4-301000

1X601/21-1-3/21012

0X11[1/2]001/2002

1X701/2-10-1/2013

0-102-20-1

1X6-101-1-21010

0x221001004

1X7-10-10-1012

200130011

因为最优目标函数值=11工0,所以，此线性规划问题无可行解

(3)

maxz=-xi+x2

4/1+3X2>12

3X]-x2<6

x2>2

xpx2>0

解：

(4)

minz=X]+3x2+4x3+3x4

3x,+6X2+七+2X4>15

,6X]+3X2+2X3+乙>12

解:

2.6线性规划问题〃如'znCX,AX=b,X20,如X*是该问题的最优解，又'＞（）为某

一常数，分别讨论下列情况时最优解的变化：

（2）目标函数变为maxz=】CX：

（3）目标函数变为morz=（C+^）X；

（4）目标函数变为/MXZ=±X,约束条件变为AX=^b。

解：（1）最优解不变，最优值变为人倍。

（2）不确定

（3）最优解变为1倍，最优值不变

2

2.7下表是一个求极大值线性规划的单纯形表，其中心，心，死是松弛变量。

表2.13

Cj22

CBXBX\X2X3X4与X6b

X512-12

2X2-11-21

X\2a-1-a+84

Gj-1

（I）把表中缺少的项目填上适当的数或式子。

（2）要使上表成为最优表，。应满足什么条件？

（3）何时有无穷多最优解？

（4）何时无最优解？

（5）何时应以右替换内？

解：⑴

000001

b

CBXBX1X2X3X4x5x6

0X600121-12

21-110-21

x20

1Xi102a-10-a+84

004-2a-10a-4

（2）要使表2-14称谓最优表，a应满足条件

4-2a<0

s.t.<2WaW4

«-4<0

(3)a=2或a=4

IT-a户

-a+8<0

（5）

4一。〉0

，2。>（）

—2>一4

112a

2.6线性规划问题加以z=CX,AX=b,X20,如X*是该问题的最优解，又、>0为某

一常数，分别讨论下列情况时最优解的变化：

（1）目标函数变为maxz=4CX：

（2）目标函数变为marz=（C+）X：

（3）目标函数变为，MXZ=£X,约束条件变为H='b。

解：

2.7下表是一个求极大值线性规划的单纯形表，其中X4,冷，死是松弛变量。

表2.13

22

CBXBX\X2X3X4与X6b

X512-12

2X2-11-21

X\2a-1-a+84

Gj-1

（I）把表中缺少的项目填上适当的数或式子。

（2）要使上表成为最优表，。应满足什么条件？

（3）何时有无穷多最优解？

（4）何时无最优解？

（5）何时应以右替换内？

解：

2.8战斗机是一种重要的作战工具，但要使战斗机发挥作用必须有足够的驾驶员。因此

生产出来的战斗机除一部分直接用于战斗外，需抽一部分用于培训驾驶员。已知每年生产的

战斗机数量为卬。=/「•,〃），又每架战斗机每年能培训出k名驾驶员，问应如何分配每年

生产出来的战斗机，使在〃年内生产出来的战斗机为空防作出最大贡献？

解：

2.9.某石油管道公司希望知道，在下图所示的管道网络中可以流过的最大流量是多少

及怎样输送，弧上数字是容量限制。请建立此问题的线性规划模型，不必求解。

2.10.一家酒店24小时都需要安排服务员上班，在各时间段中所需要的服务员数量见

表

班次时间所需人数

16:00-10:0060

210:00-14:0070

314:00-18:0060

418:00-22:0050

522:00-2:0020

62:00-6:0030

设服务员分别在各时间区段一开始时上班，并连续工作八小时，问该酒店至少配备多少名服

务员。列出此问题的线性规划模型。

解：

2.11某班有男生30人，女生20人，周日去植树。根据经验，一天男生平均每人挖坑

20个，或栽树30棵，或给25棵树浇水；女生平均每人挖坑10个，或栽树20棵，或给15

棵树浇水。问应怎样安排.才能使植树（包括挖坑、栽树、浇水）最多？请建立此问题的线

性规划模型，不必求解。

解：设

男生女生

挖坑XIIXI2

栽树X21X22

浇水X31X32

共计植树Z

maxz

Ml+X2\+X3I-30

X[2+X22+X32-20

20xn+10xl2>z

z

“30X2|+20工22-

25%+15X32>z

>0J=1,2,3;/=1,2

2.12某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果

中A、8、C三种原料的含量要求、各种原料的单位成本、各种原料每月的限制用量、三种

牌号糖果的单位加工费及售价如表1所示。问该厂每月生产这三种牌号糖果各多少千克，才

能使该厂获利最大？试建立这个问题的线性规划模型。

表2.15

甲乙丙原料成本限制用量

A60%以上15%以上2.002000

B1.502500

C20%以下60%以下50%以下1.001200

加工费0.500.400.30

售价3.402.852.25

解：设

甲乙丙

AXIIX12XI3

BX21X22X23

CX31X32X33

产量X41X42X43

)x)

maxZ=2.9X41+2.45x42+1.95.r43-2(^1+x12+XI3)-1.5(JT21+x22+々3一(工31+?>2+工33

+x}2+x]3<2000

x2]+x22+x23<2500

x++x<

31x32331200

x}l-0.6X4I>0

x]2-0.15X42>0

x31-0.2X41<0

x32-O.6X42-0

x33-O.5X43-0

Ml+X2\+叫一％=0

$2++X32-82=0

为3+工23+%33-工43二°

勺>0,z=l,2,3,4;j=1,2,3

2.13.某商店制定7—12月进货售货计划，已知商店仓库容量不得超过500件，6月底

已存货200件，以后每月初进货一次，假设各月份此商品买进售出单价如下表所示，问各月

进货售货各多少，才能使总收入最多？请建立此问题的线性规划模型，不必求解。

月份78910II12

买进单价282425272323

售出单价292426282225

解:

2.14某农场要购买一批拖拉机以完成每年三季的工作量：春种330公顷，夏管130公顷，秋

收470公顷。可供选择的拖拉机型号、单台投资额及工作能力如下表所示。

拖拉机型号单台投资单台工作能力（公顷）

（元）春种夏管秋收

东方红5000301741

丰收4500291443

跃进4400321642

胜利5200311844

问配购哪几种拖拉机各几台，才能完成上述每年工作量且使总投资最小？（建立线性规划模

型，不需求解）

解

2.15某疗养院营养师要为某类病人拟订本周菜单。可供选择的蔬菜及其费用和所含营养

成分的数量，以及这类病人每周所需各种养分的最低数量如卜.表所示:

分每份所含养分数量（亳克）每份的费用

蔬菜铁磷维生素A维生素C烟酸（元）

青豆0.451041580.30.15

胡萝卜0.4528906530.350.15

花菜1.055()2550530.60.24

卷心菜0.42575270.150.06

甜菜0.5221550.250.18

土豆057523580.80.10

每周养分最低需求量60325175002455.0

另外为了口味的需求，规定一周内所用的卷心菜不多于2份，其它蔬菜不多于4份。若病人

每周需14份蔬菜，问选用每种蔬菜各多少份？（要求建立数学模型，不需求解）

解：

2.16对某厂I,II,III三种产品下一年各季度的合同预订数如下表所示。

季度

产品1234

I1500100020001200

II1500150012001500

III10002(X)015(X)2500

该三种产品1季度初无库存，要求在4季度末各库存150件。已知该厂每季度生产工时

为1500（）小时，生产I、II、HI产品每件分别需时2、4.3小时。因更换工艺装备，产品I

在2季度无法生产。规定当产品不能按期交货时，产品I,II每件每迟交一个季度赔偿20

元，产品III赔偿10元；又生产出来产品不在本季度交货的，每件每季度的库存费用为5元。

问：该厂应如何安排生产，使总的赔偿加库存的费用为最小（要求建立数学模型，不需求解）。

解：

2.17某公司有三项工作需分别招收技工和力工来完成。第一项工作可由一个技工单独

完成，或由一个技工和两个力工组成的小组来完成,第二项工作可由一个技工或一个力工单

独去完成。第三项工作可由五个力工组成的小组完成，或由一个技工领着三个力工来完成。

己知技工和力工每周工资分别为100元和80元，他们每周都工作48小时，但他们每人实际

的有效工作小时数分别为42和36。为完成这三项工作任务，该公司需要每周总有效工作小

时数为：第一项工作10000小时。第二项工作20000小时，第三项工作30000小时。又能招

收到的工人数为技工不超过400人，力工不超过800人。试建立数学模型，确定招收技工和

力工各多少人。使总的工资支出为最少（建立数学模型，不需求解）。

解：

3.1写出下列线性规划的对偶规划。

（1）maxz=3xi+2x3—4x4

2X1—X2+%3+%42—3

3x1+2x2-X3+X4<S

x\-X2+2x4-5

x.X\>0,X2<0,X3,X4无约束

解:

mmw=-3y[+Sy2+5y3

2y+3%+为23

_y+2y2-y3Vo

s.t.<y_%=2

3y+%+2y3=-4

yWO,%2。，为无约束

⑵minz=5斗+2x2-3x3

2%1—3%2+—2

%+2X2+3X3=3

s.t.<

3%+3X2+x3<5

玉VO,工2无约束，X3之0

解:

maxw=-2yl+y2+3^3>5

-2y+2%+3%=2

4y+3%+%«-3

j无约束，y3so

3.2判断下列说法是否正确，并说明原因。

（1）如果线性规划的原问题存在可行解，其对偶问题也一定存在可行解。

答：不一定。对偶问题可能存在唯一解或无界解。

（2）如果线性规划的原问题无可行解，则其对偶问题•定存在无界解。

答：错。其对偶问题可能存在无可行解或无界解。

（3）线性规划的原问题的任一可行解的函数值一定不大于其对偶问题的任一可行解的函数

值。

答：正确。

（4）任何线性规划问题存在唯一的对偶问题。

答：正确。

3.3试运用对偶理论证明下面的线性规划问题存在无界解。

maxz=3玉+2x2+2x3

2x}-3%+4X3<7

s.tA4%j-x2+2X3<5

%,々，七-0

minw=ly1+5%

‘2%+4y2>3

-3yr-2y2>2

s.tA

解:4y+2%22

画图可得其对偶函数无可行解。

,•根据推论得，原函数也无可行解。

3.4设有如下线性规划问题：

maxz=2x1-x2+x3

2xl-x2+3X3<2

3x1+4%+X3>5

x2-x3=2

<O,x2>0,尤3无约束

①写出其对偶问题；

②利用对偶理论证明原问题目标函数值z一<(

解：①对偶规划为

minw=2y+5%+2%

2y+3%W2

s.tA一凶+4%+%2—1

3y+%-%=1

y2。,%«0，>3无约束

②以'1为Y轴，,2为x轴建立直角坐标系并画出出①中对偶规划所表示的区域,

当=I，,2=U时，此时对偶规划所表示的区域有最大值点，此时，3-，

Vi—1,—0,Vo=2

即当“2'^3时，对偶规划取得最大值为6,又

牧

CX<bYy门乂

原问题目标函数值Z<6。

35给出如下线性规划问题:

maxz

%+3X2+x3<6

s.tA一为+2X2<4

x>O,(j=1,2,3)

<J

要求：①写出其对偶问题；②已知原问题最优解为X=(6，°，°),试运用互不松弛

定理求出对偶问题的最优解。

解：①

minvv=6y+4%

X-

3M+2%2-1

s.t.<

y+2%21

yx>^y2>o

②

•.•原问题的最优解为r=（6,0,0）

•/x}二6〉0

Xv-6<4,/.%=0

・二X=2

y*=（2,0）

3.6有一个求利润最大的生产计划问题，其最优单纯形表如下所示。

ClC2b

3000

XiX2

XBX3x1X5

C2011/2-1/202

x2

2

C110-1/83/80

3

0&0001-21

00~4~40

其中，，43为松弛变量，试根据表回答下述问题；

⑴求,1'，2的数值：

（2）工厂应如何安排生产，最大利润是多少？

（3）哪种资源有剩余，剩余量是多少？

（4）三种资源的影子价格是多少？

（5）在保持最优基不变的情况下，若要扩大某种资源的数量，应扩大哪一个？最多扩

大多少？并求出新的目标函数值。

(\1、1

-a—c.

2'8?4q=2

解:⑴131解得

一W

*

X

(5)人二(3/2,2,0,0,4)

Q7

z*=2x2+-xl+0=-

最大利润22

Y

(6)由原问题的最优单纯形表可得，其对偶问题的最优解7所

以由其对偶问题最优解可得，第三种资源有剩余，剩余量是4个单位;

(7)三种资源的影子价格分别为(1/4,1/4,())

(8)①当扩大第一种资源时

△b=0

O

j_

0

2~2

J_3

\x=B'AZ?=0

B88

1-21

2

3

-

XR~XH+2

4

-A+2>0

2

--A+->0

22

4+420

.\-4<2<12

⑹若最优值不变，

当9由2变成2+4,由1变成1+X,

4=-：（1+；）+：（2+7”0

检验数W.,解得一*W/lW2,即

134

%=5（1+义）一£（2+几）工。

Zo

4

-Kq«4

3,因此，若使最优基不变,横取值范围为“，的取值范围为1,3.

3.7线性规划

内+七

maxz=32x2+5

12411

-XH--X）H---&«­

3।3-336

421010

-X.H--X,H----W—

3।3-3'3

xy>0,7=1,2,3

经过单纯形算法求解，最优单纯形表3-16表示

310213/2

00-3-29

(I)当03由5增加为8时，最优解如何变化?

(2)当"1由11/6变为11/3时，最优解如何变化？当"2由10/3变为7/3时，最优解如

何变化?

11、

(3)如果原问题增加一个变量,对应。6=2,凡=

42J，请问最优解如何变

化？

解：⑴当与由5-8,则q=8-2-3X2=0

因此线性规划有无穷最优解。

-

H

-

（2）①当弓由11/6—>11/3得△/?=6

O

1一H11

2--

-XB=X*+AX=

AX=Z?-1AZ?=2X6ToK

W1O11

-1

L工

得到如下单纯形表:

32

500b

CRXB再九2元3工4元5

20112-1/217/3

x2

3王102[-1]1-1/3

00-3-1-2

21503/25

4-10-21-11/3

-10-50-3

r1T

因此，当乙由11/6变为11/3时，最优解变为X=050-0

②当口2由10/3变为7/3时,

-I2—

AXn„=BAb=-j>x>0

-11

此时最优解为x11000

1

-

4553

一

1一-2>O

⑶机会成本=YXE=[I2]x4=----所以

-44

2

应该生产。

耳y2

-i

20112-1/21/42

x2

3再102-111/43/2

00-3-1-23/4

2-11-13-3/201/2

2%6408-4416

-30-92-50

-1/31/3-1/31-1/201/6

4834/3