运筹学部分课后习题解答

运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题

a）

12

12

12

12

min z=23

466 ..424

,0

x x

x x

s t x x

x x

+

+≥

?

?

+≥

?

?≥

?

解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都

为最优解，即该问题有无穷多最优解，这时的最优值为

min

3

z=2303

2

?+?= P47 1.3 用图解法和单纯形法求解线性规划问题

a）

12

12

12

12

max z=10x5x

349 ..528

,0

x x

s t x x

x x

+

+≤

?

?

+≤

?

?≥

?

解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点，

即

1

12

122

1

349

3

528

2

x

x x

x x x

=

?

+=

??

?

??

+==

??

?

，即最优解为*

3

1,

2

T

x

??

= ?

??

这时的最优值为

max

335

z=1015

22

?+?=

单纯形法： 原问题化成标准型为

121231241234

max z=10x 5x 349

..528,,,0x x x s t x x x x x x x +++=??

++=??≥? j c →

10

5

B C

B X

b 1x

2x

3x

4x

0 3x 9 3 4 1 0 0 4x 8 [5] 2 0 1 j j C Z -

10 5 0 0 0 3x 21/5 0 [14/5] 1 -3/5 10 1x

8/5 1 2/5 0 1/5 j j C Z -

0 1 0 -2 5 2x 3/2 0 1 5/14 -3/14 10

1x

1

1 0 -1/7

2/7

j j C Z -

-5/14 -25/14

所以有*

max 33351,,1015222T

x z ??

==?+?= ???

P78 2.4 已知线性规划问题：

1234

12

4122341231234max

24382669,,,0

z x x x x x x x x x x x x x x x x x x x =+++++≤??+≤??

++≤?

?++≤?≥??

求: (1) 写出其对偶问题；（2）已知原问题最优解为)0,4,2,2(*=X ，试根据对偶理论，直接求出对偶问题的最优解。 解：（1）该线性规划问题的对偶问题为：

1234

12

4123434131234min

86692234

11,,,0

w y y y y y y y y y y y y y y y y y y y =+++++≥??+++≥??

+≥?

?+≥?≥??

（2）由原问题最优解为)0,4,2,2(*=X ，根据互补松弛性得：

12

412343422341y y y y y y y y y ++=??

+++=??+=?

把)0,4,2,2(*=X 代入原线性规划问题的约束中得第四个约束取严格不等号，即4224890y ++=

从而有12

123322341y y y y y y +=??

++=??=?

得123443

,,1,055

y y y y ====

所以对偶问题的最优解为*43

(,,1,0)55

T y =，最优值为min 16w =

P79 2.7 考虑如下线性规划问题：

123123123123123min 6040803224342223,,0

z x x x x x x x x x x x x x x x =++++≥??++≥??

++≥??≥?

（1）写出其对偶问题；（2）用对偶单纯形法求解原问题； 解：（1）该线性规划问题的对偶问题为：

123123123123123max 2433426022403280,,0w y y y y y y y y y y y y y y y =++++≤??++≤??

++≤??≥?

（2）在原问题加入三个松弛变量456,,x x x 把该线性规划问题化为标准型：

12312341235123

6max 60408032243422230,1,,6j z x x x x x x x x x x x x x x x x j =------+=-??---+=-??

---+=-??≥=?

j c →

-60

-40

-80

B C

B X

b 1x

2x

3x

4x

5x

6x

0 4x -2 -3 -2 -1 1 0 0 0 5x -4 [-4] -1 -3 0 1 0 0 6x -3 -2 -2 -2 0 0 1 j j C Z -

-60 -40 -80 0 0 0 0 4x 1 0 -5/4 5/4 1 -1/12 0 80 1x

1 1 1/4 3/4 0 -1/4 0 0 6x -1

0 [-3/2] -1/2

0 -1/2 1 j j C Z -

-25 -35 0 -15 0 0 4x 11/6 0 0 5/3 1 1/3 -5/6 80 1x

5/6 1 0 2/3 0 -1/3 1/6 40

2x

2/3

0 1 1/3 0 1/3 -2/3 j j C Z -

-80/3

-20/3

-50/3

*max 5252230

(,,0),604080063633

T x z ==?+?+?=

P81 2.12 某厂生产A 、B 、C 三种产品，其所需劳动力、材料等有关数据见下表。要求：（a ）确定获利最大的产品生产计划；（b ）产品A 的利润在什么范围内变动时，上述最优计划不变；（c ）如果设计一种新产品D ，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？ （d ） 如果劳动力数量不增，材料不足时可从市场购买，每单位0.4 元。问该厂要不要购进原材料扩大生产，以购多少为宜。

A B C 可用量（单位）

劳动力 材 料 6 3 5 3 4 5 45 30 产品利润（元/件）

3 1 4

解：由已知可得，设j x 表示第j 种产品，从而模型为：

123123123123max 3463545

..34530,,0z x x x x x x s t x x x x x x =++++≤??

++≤??≥?

a) 用单纯形法求解上述模型为：

j c →

3

1

4

B C

B X

b 1x

2x

3x

4x

5x

0 4x 45 6 3 5 1 0 0 5x 30 3 4 [5] 0 1 j j C Z -

3

1

4 0 0 0 4x 1

5 [3] -1 0 1 -1 4 3x

6 3/5 4/5 1 0 1/5 j j C Z -

3/5 -11/5 0 0 -4/5 3 1x

5 1 -1/3 0 1/3

-1/3

4

3x

3

0 1 1 -1/5 2/5 j j C Z -

-2

-1/5 -3/5

得到最优解为*(5,0,3)T x =；最优值为max 354327z =?+?=

产品

资源

消 耗 定 额

b ）设产品A 的利润为3λ+，则上述模型中目标函数1x 的系数用3λ+替代并求解得：

j c →

3λ+

1

4 0 0

B C B X b 1x 2x

3x 4x

5x

3 1x

5 1 -1/3 0 1/3 -1/3 4

3x 3

1 1 -1/5 2/5 j j C Z -

λ

-2

-1/5 -3/5 ()j

j C

Z '-

-2+λ/3 0

-1/5-λ/3

-3/5+λ/3

要最优计划不变，要求有如下的不等式方程组成立

2031053

3053λλ

λ?-+≤??

?--≤???-+≤??

解得：3955λ-≤≤

从而产品A 的利润变化范围为：393,355??-+????,即242,455??

????

C ）设产品

D 用6x 表示，从已知可得

16661/5B c c B P σ-=-=

'1661

12833

4122555P B P -??-????????===??????

-????-??????

把6x 加入上述模型中求解得：

j c →

3

1

4

3

B C

B X b 1x

2x

3x

4x

5x

6x

3 1x

5 1 -1/3 0 1/3 -1/3 [2] 4

3x

3

1

1 -1/5

2/5

-4/5

j j C Z -

-2 0 -1/5 -3/5 1/5 3 6x 5/2 1/2 -1/6

1/6

-1/6

1 4

3x

5

2/5

13/15 1 -1/15 4/15

j j C Z -

-1/10 -59/30 0 -7/30 -17/30 0

从而得最优解*(0,0,5,0,0,5/2)T x =；最优值为max 5

45327.5272

z =?+?=> 所以产品D 值得生产。 d ）

P101 3.1已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。

表3-35

B1 B2 B3 B4 产量A1

A2

A3

10

12

2

2

7

14

20

9

16

11

20

18

15

25

5 销量 5 15 15 10

解：由已知和最小元素法可得初始方案为

B1 B2 B3 B4 产量A1

A2

A3 5

15

0 15

10

15

25

5

销量 5 15 15 10

检验：

由于有两个检验数小于零，所以需调整，调整一：

B1 B2 B3 B4 产量

产地

销地

产地

销地

产地

销地

A1 A2

A3

5

15

0 15 10

15

25

5

销量 5 15 15 10

检验：

由于还有检验数小于零，所以需调整，调整二：

B1 B2 B3 B4 产量

A1

A2

A3 5 5

10 15

10

15

25

5

销量 5 15 15 10

检验：

从上表可以看出所有的检验数都大于零，即为最优方案

最小运费为：

min 25257109151110180335

z=?+?+?+?+?+?=

表3-36

B1 B2 B3 B4 产量

A1 A2 A3 8

6

5

4

9

3

1

4

4

2

7

3

7

25

26

产地

销地产地

销地

销量

10 10 20

15

解：因为3

4

1

1

5855i j i j a b ===>=∑∑，即产大于销，所以需添加一个假想的销地，销

量为3，构成产销平衡问题，其对应各销地的单位运费都为0。 B1 B2

B3

B4

B5 产量 A1

A2 A3 8 6 5

4 9 3

1 4 4

2 7 3

0 0 0 7 25 26 销量

10 10 20 15

3

由上表和最小元素法可得初始方案为 B1 B2 B3 B4 B5 产量 A1

A2 A3 9 1 10 7 13 15 3 7 25 26 销量

10

10

20

15

3

检验：

从上表可以看出所有的检验数都大于零，即为最优方案

最小运费为：min 69513101741331503193z =?+?+?+?+?+?+?=

表3-37

B1 B2

B3

B4

B5

产量

产地 销地

产地 销地

产地

销地

A1 A2 A3 8 5

6

6

M

3

3

8

9

7

4

6

5

7

8

20

30

30

销量25 25 20 10 20

解：因为

35

11

80100

i j

i j

a b

==

=<=

∑∑，即销大于产，所以需添加一个假想的产地，产量为20，构成产销平衡问题，其对应各销地的单位运费都为0。

B1 B2 B3 B4 B5 产量

A1

A2

A3

A4

8

5

6

6

M

3

3

8

9

7

4

6

5

7

8

20

30

30

20

销量25 25 20 10 20

由上表和最小元素法可得初始方案为

B1 B2 B3 B4 B5 产量

A1

A2

A3

A4

5

20

25

20

10 15

5

20

30

30

20

销量25 25 20 10 20

检验：

由于有两个检验数小于零，所以需调整，调整一：

B1 B2 B3 B4 B5 产量

产地

销地

产地

销地

产地

销地

A1 A2 A3 A4

20

5 25 20 0 10 5 15 20 30 30 20 销量 25 25 20

10 20

检验：

由于还有检验数小于零，所以需调整，调整二： B1 B2 B3 B4 B5 产量 A1 A2 A3 A4

20 5 25 20 0 10 0 20 20 30 30 20 销量 25

25

20

10

20

检验：

从上表可以看出所有的检验数都大于零，即为最优方案

最小运费为：min 320520410653258002000305z =?+?+?+?+?+?+?+?=

P127 4.8 用割平面法求解整数规划问题。

产地

销地

a ） 12

121212

max 7936735

,0,z x x x x x x x x =+-+≤?

?

+≤?

?≥?且为整数

解：该问题的松弛问题为：

12

121212

max 7936735,0z x x x x x x x x =+-+≤??

+≤??≥?

则单纯形法求解该松弛问题得最后一单纯形表为： j c → 7 9 0 0

B C B X

b

1x 2x 3x 4x

9 2x 7/2 0 1 7/22 1/22

7

1x 9/2 1

0 -1/22 3/22 j j C Z -

-28/11 -15/11

割平面1为：234(31/2)(07/22)(01/22)x x x +=++++

3421713022222x x x ?--=-≤345711

22222x x x ?+-= 从而有 j c → 7 9 0 0 0

B C B X

b

1x 2x 3x 4x 5x

9 2x 7/2 0 1 7/22 1/22 0 7 1x 9/2 1

0 -1/22 3/22

0 5x -1/2 0

0 -7/22 -1/22 1 j j C Z -

0 0 -28/11 -15/11 0 9 2x 3

1 0 0 1 7 1x 32/7 1

0 0 1/7 -1/7 0

3x 11/7 0

0 1 1/7 -22/7 j j C Z -

-1

-8

割平面2为：145(44/7)(01/7)(16/7)x x x +=+++-+

451541640777x x x x ?--=--≤456164

777

x x x ?+-= j c →

7 9 0 0 0 3

B C B X

b

1x 2x 3x 4x 5x 6x

9

2x 3

0 1 0 0 1 0

7

1x 32/7 1

0 0 1/7 -1/7 0 0 3x 11/7 0 0 1 1/7 -22/7 0 0 6x -4/7 0

0 0 -1/7 -6/7 1

j j C Z -

0 0 0 -1 -8 0 9 2x 3 0 1 0 0 1 0 7 1x 4

1 0 0 0 -1 1 0 3x 1 0 0 1 0 -4 1 0

4x 4

0 0 0 1 6 -7 j j C Z -

-2

-7

由上表可知该问题已经达到整数解了，所以该整数解就是原问题的最优解，即

()*4,3T

x =，最优值为max 749355z =?+?=

P144 5.3 用图解分析法求目标规划模型

c ）

解:由下图可知，满足目标函数的满意解为图中的A 点。

P170 6.4 求下图中的最小树

x 1 + x 2 + d 1- - d 1+= 40

x 1 + x 2 + d 2- - d 2+= 40+10=50 x 1 + d 3- - d 3+= 24 x 2 + d 4- - d 4+= 30

min Z = P 1 d 1-+ P 2 d 2++ P 3（2d 3- +1d 4-）

s.t.

x 1 、x 2 、d 1+、d 1-、d 2+、d 2- 、d 3+、d 3- 、d 4+、d 4- ≥ 0

解：避圈法为：

得到最小树为：

P171 6.7 用标号法求下图中点1v到各点的最短路。

解：如下图所示：

P 173 6.14 用Ford-Fulkerson 的标号算法求下图中所示各容量网络中从

s

v 到

t

v 的

最大流，并标出其最小割集。图中各弧旁数字为容量ij c ，括弧中为流量ij f .

B)

解：对上有向图进行2F 标号得到

由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1，得

由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线KK 相交的弧的集合，即为

{}3451223(,),(,),(,),(,),(,),(,)s s s t t v v v v v v v v v v v v

所以从s v 到t v 的最大流为：*

12532114st

f =+++++=

C)

解：对上有向图进行2F 标号得到

由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为1，得

由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线KK 相交的弧的集合，即为{}1325(,),(,),(,)s s v v v v v v ，所以从s v 到t v 的最大流为：

*53513st f =++=

P193 7.1 根据下表给定的条件，绘制PERT网络图。

表7-8

作业代号 a1 a2 a3 b1 b2 b3 c1 c2 c3

紧前作业无 a1 a2 无 b1 b2 a1，b1 a2，b2，c1 a3，b3，c2 解：绘制的PERT网络图为：

表7-9

作业代号 A B C D E F G H I J K L M

紧前作业无无无 A,B B B F,C B E,H E,H C,D,F,J K L,I,G 解：绘制的PERT网络图为：

表7-10

作业代号 A B C D E F G H I J K L M

紧前作业无无 B C A,D D A,D E G,H I G J,K L

解：绘制的PERT网络图为：