管理运筹学作业答案(韩大卫)MBA.docx

第1章 线性规划基本性质

P47 1—1（2）
解：设每天从煤矿运往城市的煤为吨，该问题的LP模型为：

P48 1—2（2）

3

-1
0
（1）
（2）

解：，则该LP问题无可行解。

P48 1—2（3）

1

-5
0
（1）
（2）

Q
Z=0
Z=10
-1
P

解：目标函数等值线与函数约束（2）的边界线平行，由图可知则该LP问题为多重解（无穷多最优解）。

则（射线QP上所有点均为最优点）

P48 1—2（4）

（1）
（2）
（3）
Z=0

Q

解：由图可知Q点为最优点。
则

P48 1—3（2）

P49 1—5

解：可行域的极点与基本可行解是一一对应的。
（1）对于，不满足约束条件，即不是可行解，也就不是基本可行解，故不是该可行域的极点。
（2）对于，是可行解。此时基变量为，由此得到的基矩阵为
，所以不是基本解，也就不是基本可行解，故不是该可行域的极点。
（3）对于，是可行解。此时基变量为，由此得到的基矩阵为
，所以不是基本解，也就不是基本可行解，故不是该可行域的极点。

P50 1—8

1
2
3
4
5
6
7
8

A(2.9)
1
1
1
2
0
0
0
0
100
B(2.1)
1
2
0
0
1
0
2
3
100
C(1.2)
2
0
3
1
4
6
2
0
100
余料
0
0.3
0.9
0.4
0.5
0.2
0.8
1.1

解：设按第种截法下料根，该问题的LP模型为：

第2章 单纯形法

P70 2—1（2）

解：标准化为，容易得
第一次迭代时： 则为进基变量（此时仍为非基变量）
则为进基变量，6为主元
此时：

第二次迭代： 则为进基变量
则为进基变量，为主元

此时：
此时，则

（图解法略）

注意由方程组形式求的每个基本可行解与图解法求得的可行域的极点之间的一一对应关系。

P70 2—2（1）
解：化标准形为：

2
2
0
0

b

0

1

1
1
0

0

2

1
0
1

2
2
0
0

而它所对应的系数列向量
则该LP问题无最优解（无界解）。

补充作业：
求解下列LP问题：

解：标准化后求解过程如下：

6

3
0
0
0

b

0

60
3
1
1
1
0
0
20
0

10
（1）

2
0
1
0
10
0

20
1
1

0
0
1
20

6

3
0
0
0

0

30
0
4

1

0
30/4
6

10
1

2
0
1
0
——
0

10
0
（2）

0

1
5

0
3

0

0

0

10
0
0
1
1

6

15

1
0
1/2
0
1/2
1/2

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

0
0
-9/2
0
-9/2
-3/2

，则最优解为：

P70 2—2（4）
解：建立该LP问题的大M法辅助问题如下：

0
0

b

8
1
（4）
2

0
1
0
2

6
3
2
0
0

0
1
3

0
0

2
1/4
1
1/2

0
1/4
0
8

2
（5/2）
0

1/2

1
4/5

0

0

0
1
（3/5）

1/10
3/10

1
0

1/5

2/5

0
0
0

/2

3
0
5/3
1

1/6
1/2
/6

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

0
0
0
/2
/2

由于出现非基变量的检验数为0，故该LP问题有多重解。
则最优解为：

P71 2—2 （5）
解：目标函数化标准形为：
函数约束添加人工变量，拟采用两阶段法求解。
第一阶段：两阶段法辅助问题目标函数为：

0
0
0
0

b

2
（1）

2

1
0
0
2

6
2
1

1
0
1
0
3

7
1
1
1
1
0
0
1
7

4
1
0
1
0
0
0

0

2
1

2

1
0
0
-----

2
0
（3）

3

1
0
2/3

5
0
2

2

0
1
5/2

0
5

5

0
0

0

8/3
1
0
-1/3
0
1/3
1/3
0
-----
0

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

11/3
0
0
（11/3）
0
1/3
-2/3
1
1

0
0
11/3
0
-2/3

-5/3
0

0

3
1
0
0
0
4/11
3/11
1/11

0

3
0
1
0
1
-5/11
-1/11
7/11

0

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

0
0
0
0

由第一阶段最终单纯形表可得，故原LP问题存在可行基，转入第二阶段继续求解。

第二阶段：求解原LP问题。

1
1

b

3
1
0
0
0
-----

3
0
1
0
（1）
3
1

1
0
0
1
0
------

0
0
0
2

3
1
0
0
0

1

3
0
1
0
1

1

1
0
0
1
0

0

0
0

此时故原LP问题的最优解为：

补充作业：
求解下列LP问题：
解：建立大法的辅助问题如下：

2
1
1
0
0
0

b

4
（4）
2
2

0
0
1
1
0

20
2
4
0
0
1
0
0
10
0

16
4
8
2
0
0
1
0
4

0
0
0

2

1
1
1/2
1/2
-1/4
0
0
1/4
——
0

18
0
3

1/2
1
0
-1/2
36
0

12
0
6
0
（1）
0
1

12

0
0
0
1/2
0
0

2

4
1
2
（1/2）
0
0
1/4
0
8
0

12
0
0

0
1
-1/2
0
——
0

12
0
6
0
1
0
1

——

0

0
0
0
-1/2

1

8
2
4
1
0
0
1/2
0

0

20
2
4
0
0
1
0
0

0

12
0
6
0
1
0
1

0

0
0
0
-1/2

该LP问题有多重解。
最优解为：，
第3章 对偶原理

P92 3—1 （1）（2）（4）

（1）

（2）

（4）

P92 3—2 （6）

（6）

P93 3—6 （1）用对偶单纯形法求解LP问题
解：

0
0
0

b

0

1
0
0
0

5
1
0
0
1
0
0

（）

0
0
1

0
0
0
1/3
2

0

0
（）
1
0

0

3
0

0
1
1/3

2
1
1/3
0
0

0

0
0

1

1

6/5
0
1

0
（1/5）
0

17/5
0
0

1
2/5

8/5
1
0
1/5
0

0
0

0
0
0

6
0
5

0
1
0

1
0

1
1
0

4
1
2

0
0

0
0

0
0

该LP问题有多重解。
最优解为：

P93 3—7
解：（1）设甲、乙、丙三种产品每月的产量分别为件，建立LP模型为：

3
2
1
0
0

b

0

400
1
2
1
1
0
400
0

500
（2）
1
2
0
1
250

3
2
1
0
0

0

150
0
（3/2）
0
1

100
3

250
1
1/2
1
0
1/2
500

0
1/2

0

2

100
0
1
0
2/3

3

200
1
0
1

2/3

0
0

，则最优解为
即：每月生产甲产品200件，乙产品100件。最大总产值为800千元。
（2）对偶问题为：
由对偶性质可得：，即A设备的影子价格为1/3千元，即元350元。
故外租外厂A设备不划算。
补充作业：

1、已知线性规划问题，

其对偶问题的最优解为：，。试用对偶性质求出原问题的最优解。
解：该问题的对偶问题为：

将对偶问题的最优解代入到对偶问题的所有函数约束中去，
发现（1）（2）为严格不等式，由互补松弛性定理（或松紧定理）知 又因，由互补松弛性定理（或松紧定理）知原问题的两个约束条件应该取严格等式，综上可得： ，解得
故原问题的最优解为： ,

第5章 运输模型

P144 5—1

解：

调
拨
站
工
厂

1
2
3
4
产量

1
5 2
7.5 1
3 （10）
4.5 （2）
12
0
2
6.5 2
8 （10）
4
6 （7）
17
1.5
3
4 （10）
7
5 1
5.5 （1）
11
1
销量
10
10
10
10
40

3
6.5
3
4.5

，则该方案为非最优方案
又，则为进基变量，调整量，为离基变量。
新方案为：

调
拨
站
工
厂

1

2
3
4
产量

1
5 2
7.5 0.5
3 （3）
4.5 （9）
12
0
2
6.5 2.5
8 （10）
4 （7）
6
17
1
3
4 （10）
7
5 1
5.5 （1）
11
1
销量
10
10
10
10
40

3
7
3
4.5

，则该方案仍不是最优方案，为进基变量，调整量，为离基变量。

新方案为：

调
拨
站
工
厂

1
2
3
4
产量

1
5 1
7.5 0.5
3 （2）
4.5 （10）
12
0
2
6.5 1.5
8 （9）
4 （8）
6 0.5
17
1
3
4 （10）
7 （1）
5 2
5.5 1
11
0
销量
10
10
10
10
40

4
7
3
4.5

此时此方案为最优方案。（元）

第6章 整数规划

P171 6—2 （2）
解：先用图解法求出松弛问题的最优解为：。

无可行解

由上可知：该IP问题的最优解为，。

P171 6—2 （4）
解：将原问题转化为求
其松弛问题的最优解为

无可行解
无可行解

与相矛盾

则原IP问题无可行解。

P172 6—5

解：此题满足标准指派问题的三个条件，直接用匈牙利法求解如下：

即解矩阵为

指派方案为：机床1加工零件2，机床2加工零件3，机床3加工零件5，机床4加工零件1，机床5加工零件4，总加工费用为：（元）

P173 6—7

解：（1）该指派问题要求目标函数最大化，根据匈牙利法适用的标准指派问题三必要条件应先化为最小化问题，记

即解矩阵为

指派方案为：甲翻译德文，乙翻译日文，丙翻译法文，丁翻译俄文，戊翻译英文，
总翻译效率为：（印刷符号/小时）
（2）由于甲不能胜任翻译德文，乙不能胜任翻译日文，效益矩阵变化为：

即解矩阵为

指派方案为：甲翻译日文，乙翻译德文，丙翻译法文，丁翻译俄文，戊翻译英文，
总翻译效率为：（印刷符号/小时）
第8章 网络分析

P232 8—1

解：（1）

不连通图

（2）真子图，是的真子图。
支撑子图，是的支撑子图。
（3） 开链、简单链
开链、简单链、初等链
闭链、简单链、圈
闭链、简单链、圈
闭链、简单链、圈
开链

P233 8—5 （a）（b）（c）

解：
（a）
1
2
4
6
7
3
5

（b）
1
3
4
7
8
6
5
2

（c）
1
4
2
3
5
9
7
10
8
6

P233 8—7 （a）

解：
s
2
5
t
4
1
6
3

点到各点的最短路为：

，路长为6

，路长为2

，路长为8

，路长为6

，路长为3

P234 8—9
解：距离矩阵为
（1）各点到点的最短路

即：

最短路
最短距离

3

5

1

3

4

0

（2）点到各点的最短路

即：

最短路
最短距离

0

2

1

3

P234 8—11

解：

截量

6

7

7

5

8

则最大流量为：
该网络的最小截集为：

P235 8—12 （a）
s
1
4
3
t
2
7
6
13
3
6
4
15
4
2
3

则最大流量为
该网络的最小截集为：

P235 8—12 （b）
5
s
1
4
3
t
2
9
13
10
5
5
4
6
4
9
t
5
4

则最大流量为：
该网络的最小截集为：