运筹学部分课后习题解答.doc

运筹学部分课后习题解答
P47 1.1 用图解法求解线性规划问题
a）
解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为最优解，即该问题有无穷多最优解，这时的最优值为

P47 1.3 用图解法和单纯形法求解线性规划问题
a）
解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点，即，即最优解为
这时的最优值为

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

10
5
0
0

b

0

9
3
4
1
0
0

8
[5]
2
0
1

10
5
0
0
0

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

8/5
1
2/5
0
1/5

0
1
0
-2
5

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

1
1
0
-1/7
2/7

0
0
-5/14
-25/14
所以有

P78 2.4 已知线性规划问题：

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

（2）由原问题最优解为，根据互补松弛性得：

把代入原线性规划问题的约束中得第四个约束取严格不等号，即
从而有
得
所以对偶问题的最优解为，最优值为

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

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

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

-60
-40
-80
0
0
0

b

0

-2
-3
-2
-1
1
0
0
0

-4
[-4]
-1
-3
0
1
0
0

-3
-2
-2
-2
0
0
1

-60
-40
-80
0
0
0
0

1
0
-5/4
5/4
1
-1/12
0
80

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

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

0
-25
-35
0
-15
0
0

11/6
0
0
5/3
1
1/3
-5/6
80

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

2/3
0
1
1/3
0
1/3
-2/3

0
0
-80/3
0
-20/3
-50/3

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

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

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

3
1
4
0
0

b

0

45
6
3
5
1
0
0

30
3
4
[5]
0
1

3
1
4
0
0
0

15
[3]
-1
0
1
-1
4

6
3/5
4/5
1
0
1/5

3/5
-11/5
0
0
-4/5
3

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

3
0
1
1
-1/5
2/5

0
-2
0
-1/5
-3/5
得到最优解为；最优值为
b）设产品A的利润为，则上述模型中目标函数的系数用替代并求解得：

1
4
0
0

b

3

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

3
0
1
1
-1/5
2/5

-2
0
-1/5
-3/5

0
-2+/3
0
-1/5-/3
-3/5+/3
要最优计划不变，要求有如下的不等式方程组成立
解得：
从而产品A的利润变化范围为：,即

C）设产品D用表示，从已知可得

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

3
1
4
0
0
3

b

3

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

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

0
-2
0
-1/5
-3/5
1/5
3

5/2
1/2
-1/6
0
1/6
-1/6
1
4

5
2/5
13/15
1
-1/15
4/15
0

-1/10
-59/30
0
-7/30
-17/30
0
从而得最优解；最优值为
所以产品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
0

10

15
25
5
销量
5
15
15
10

检验：

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

B1
B2
B3
B4
产量
A1
A2
A3

5
15
0

15

10
0
15
25
5
销量
5
15
15
10

检验：

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

B1
B2
B3
B4
产量
A1
A2
A3

5
5
10

15

10

0
15
25
5
销量
5
15
15
10

检验：

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

表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，构成产销平衡问题，其对应各销地的单位运费都为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

检验：

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

表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

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

B1
B2
B3
B4
B5
产量
A1
A2
A3
A4
8
5
6
0
6
M
3
0
3
8
9
0
7
4
6
0
5
7
8
0
20
30
30
20
销量
25
25
20
10
20

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

B1
B2
B3
B4
B5
产量
A1
A2
A3
A4

5

20

25

20

0

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

检验：

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

P127 4.8 用割平面法求解整数规划问题。
a）
解：该问题的松弛问题为：

则单纯形法求解该松弛问题得最后一单纯形表为：

7
9
0
0

b

9

7/2
0
1
7/22
1/22
7

9/2
1
0
-1/22
3/22

0
0
-28/11
-15/11
割平面1为：

从而有

7
9
0
0
0

b

9

7/2
0
1
7/22
1/22
0
7

9/2
1
0
-1/22
3/22
0
0

-1/2
0
0
-7/22
-1/22
1

0
0
-28/11
-15/11
0
9

3
0
1
0
0
1
7

32/7
1
0
0
1/7
-1/7
0

11/7
0
0
1
1/7
-22/7

0
0
0
-1
-8
割平面2为：

7
9
0
0
0
3

b

9

3
0
1
0
0
1
0
7

32/7
1
0
0
1/7
-1/7
0
0

11/7
0
0
1
1/7
-22/7
0
0

-4/7
0
0
0
-1/7
-6/7
1

0
0
0
-1
-8
0
9

3
0
1
0
0
1
0
7

4
1
0
0
0
-1
1
0

1
0
0
1
0
-4
1
0

4
0
0
0
1
6
-7

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

P144 5.3 用图解分析法求目标规划模型
x1 + x2 + d1- - d1+= 40
x1 + x2 + d2- - d2+= 40+10=50
x1 + d3- - d3+= 24
x2 + d4- - d4+= 30
min Z = P1 d1-+ P2 d2++ P3（2d3- +1d4-）
s.t.
x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 、d4+、d4- ≥ 0
c）

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

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

的满意解。
解：由下图可知，满足的满意解为区域CDOA；
满足的满意解为闭区域MCDOM；
满足的满意解为图中的阴影部分，即为图中的凸多边形OABCDO 。

P170 6.4 求下图中的最小树

解：避圈法为：

得到最小树为：

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

解：如下图所示：

P 173 6.14 用Ford-Fulkerson的标号算法求下图中所示各容量网络中从到的最大流，并标出其最小割集。图中各弧旁数字为容量，括弧中为流量.
B)

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

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

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

所以从到的最大流为：

C)

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

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

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

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网络图为：