管理数学之运筹学部分习题题解.doc

《管理数学》——运筹学部分参考答案
习题P47
1-1试建立下列问题的数学模型
（1）设备配购问题
某农场要购买一批拖拉机以完成每年三季的工作量：春种330公顷，夏管130公顷，秋收470公顷。可供选择的拖拉机型号、单台投资额及工作能力如下表所示。
拖拉机型号
单台投资（元）
单台工作能力（公顷）
春种
夏管
秋收
东方红
5000
30
17
41
丰收
4500
29
14
43
跃进
4400
32
16
42
胜利
5200
31
18
44
问配购哪几种拖拉机各几台，才能完成上述每年工作量且使总投资最小？
解：设购置东方红、丰收、跃进、胜利拖拉机的数量分别为台，则可建立线性规划问题的数学模型：

（2）物资调运问题
甲乙两煤矿供给A，B，C三个城市的用煤。各矿产量和各市需求如下表所示：
煤矿
日产量（吨）
城市
日需求量（吨）
甲
200
A
100

B
150
乙
250
C
200
各矿与各市之间的运输价格如下表示：
城市
煤矿
运价（元/吨）
A
B
C
甲
9
7
10
乙
8
6.5
8
问应如何调运，才能既满足城市用煤需求，又使运输的总费用最少？
解：设煤矿甲供应城市A、B、C的煤分别为，煤矿乙供应城市A、B、C的煤分别为则可建立线性规划问题数学模型：

（3）食谱问题
某疗养院营养师要为某类病人拟订本周菜单。可供选择的蔬菜及其费用和所含营养成分的数量，以及这类病人每周所需各种养分的最低数量如下表所示：
养分
蔬菜
每份蔬菜所含养分数量（毫克）
每份蔬菜
费用（元）
铁
磷
维生素A（单位）
维生素C
烟酸
青豆
0.45
10
415
8
0.3
1.5
胡萝卜
0.45
28
9065
3
0.35
1.5
花菜
1.05
50
2550
53
0.6
2.4
卷心菜
0.4
25
75
27
0.15
0.6
甜菜
05
22
15
5
0.25
1.8
土豆
0.5
75
235
8
0.8
1.0
每周养分
最低需求量
6.0
325
17500
245
5.0

另外为了口味的需求，规定一周内所用的卷心菜不多于2份，其它蔬菜不多于4份。若病人每周需14份蔬菜，问选用每种蔬菜各多少份？
解：设该类病人每周需要青豆、胡萝卜、花菜、卷心菜、甜菜、土豆分别为份，则可建立线性规划问题数学模型：

（4）下料问题
某钢筋车间要用一批长度为10米的钢筋下料制作长度为三米的钢筋90根和长度为四米的钢筋60根，问怎样下料最省？
解：首先将长度为10米的钢筋下料4米和3米的钢筋，一共有以下下料方式

需要量
4米
2
1
0
60
3米
0
2
3
90
余料
2
0
0

设分别用，，方式下料根数，则可建立线性规划问题数学模型：

习题P70
2-1 分别用图解法和单纯形法求解下述LP问题，并指出单纯形法迭代中每一基本可行解跟图解法可行域中哪一极点相互对应。

解：(1)先用图解法
-1
1
2
3
4
x1
-6
-4
-2
2
4
6
x2
3x1+4x2=9
o
5x1+2x2=8
10x1+5x2=17.5
A
B
C
可行解区域为凸多边形，在B点，处取到最大值，最大值为：。
(2)单纯形方法：引进松弛变量，化成标准形：

由于具有明显的可行基，以为基变量的基是一个明显的可行基，作出其所对应的单纯形表，并用单纯形方法进行换基迭代：
基
解

比值

9
3
4
1
0
9/3=3

8
5
2
0
1
8/5=1.6

0
-10
-5
0
0

对应的基可行解为：。与图解法中的极点相对应。不是最优基，为进基变量，为出基变量，进行换基迭代：
基
解

比值

21/5
0
14/5
1
-3/5
1.5.

8/5
1
2/5
0
1/5
4

16
0
-1
0
2

对应的基可行解为：。与图解法中的极点相对应。不是最优基，为进基变量，为出基变量，进行换基迭代：
基
解

比值

1.5
0
1
5/14
-3/14

1
1
0
-1/7
2/7

17.5
0
0
5/14
25/14

单纯形表中所有检验数均非负。最优解：。与图解法中的极点相对应。去掉松弛变量，得原问题的最优解为：。
如果用LINDO进行求解：
max 10x1+5x2
st
3x1+4x2<=9
5x1+2x2<=8
end
输出结果
LP OPTIMUM FOUND AT STEP 2
OBJECTIVE FUNCTION VALUE
1) 17.50000
VARIABLE VALUE REDUCED COST
X1 1.000000 0.000000
X2 1.500000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 0.357143
3) 0.000000 1.785714
NO. ITERATIONS= 2
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1 10.000000 2.500000 6.250000
X2 5.000000 8.333333 1.000000
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 9.000000 7.000000 4.200000
3 8.000000 7.000000 3.500000

解：先用图解法进行求解：

-1
1
2
3
4
5
6
x1
-10
-5
5
10
15
x2
5x2=15
x1+x2=5
6x1+2x2=24
2x1+x2=8.5
O
A
B
C
D

可行解区域为凸多边形，在B点，处取到最大值，最大值为：。
引进松弛变量，化成标准形：

由于具有明显的可行基，以为基变量的基是一个明显的可行基，作出其所对应的单纯形表，并用单纯形方法进行换基迭代：
基
解

比值

15
0
5
1
0
0
—

24
6
2
0
1
0
24/6=4

5
1
1
0
0
1
5/1=5

0
-2
-1
0
0
0

对应的基可行解为：。与图解法中的极点相对应。不是最优基，为进基变量，为出基变量，进行换基迭代：
基
解

比值

15
0
5
1
0
0
15/5=3

4
1
1/3
0
1/6
0
4/（1/3）=12

1
0
2/3
0
-1/6
1
1/（2/3）=1.5

8
0
-1/3
0
1/3
0

对应的基可行解为：。与图解法中的极点相对应。不是最优基，为进基变量，为出基变量，进行换基迭代：
基
解

比值

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

7/2
1
0
0
1/4
-1/2

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

8.5
0
0
0
1/4
1/2

单纯形表中所有检验数均非负。最优解：，。与图解法中的极点相对应。去掉松弛变量，得原问题的最优解为：
如果用LINDO进行求解：
max 2x1+x2
st
5x2<=15
6x1+2x2<=24
x1+x2<=5
end
输出结果：
LP OPTIMUM FOUND AT STEP 2
OBJECTIVE FUNCTION VALUE
1) 8.500000
VARIABLE VALUE REDUCED COST
X1 3.500000 0.000000
X2 1.500000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 7.500000 0.000000
3) 0.000000 0.250000
4) 0.000000 0.500000
NO. ITERATIONS= 2
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1 2.000000 1.000000 1.000000
X2 1.000000 1.000000 0.333333
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 15.000000 INFINITY 7.500000
3 24.000000 6.000000 6.000000
4 5.000000 1.000000 1.000000

习题P92
3-1 试建立下述LP问题的对偶关系表，并写出其对偶问题：

解：对偶关系表
型
型

3
1
1

2
2
3

对偶线性规划问题为：

解：对偶关系表
型
型

3
1
1

1
-1
2

1
1
-1

对偶线性规划问题为：

3-2试写出下面问题的对偶问题

对偶线性规划问题为：

习题P170
6-5 某厂拟用五台机床加工五种零件，其加工费（元）如下表所示。若每台机床只加工一种零件则应如何分配任务才能使总加工费最少？
零件
机床
零件1
零件2
零件3
零件4
零件5
1
4
1
8
4
2
2
9
8
4
7
7
3
8
4
6
6
3
4
6
5
7
6
2
5
5
5
4
3
1
解：这是最小化指派问题
首先变换效率矩阵

试求最优解

作覆盖所有零元素的最少直线集合

继续变换效率矩阵

再试求最优解

最优解：，
即：机床1加工零件1，机床2加工零件3，机床3加工零件2，机床4加工零件5，机床5加工零件4，可使加工费用最低。最低加工费用为17元。
6-7 五人翻译五种外文的速度（印刷符号/小时）如下表所示：
语种
人
英语
俄语
日语
德语
法语
甲
900
400
600
800
500
乙
800
500
900
1000
600
丙
900
700
300
500
800
丁
400
800
600
900
500
戊
1000
500
300
600
800
若规定每人专门负责一个语种的翻译工作，那么，试解答下列问题：
（1）应如何指派，使总的翻译效率最高？
（2）若甲不懂德文，乙不懂日文，其他数字不变，则应如何指派？
（3）若将效率阵中各数字都除以100，然后求解，问最优解有无变化？为什么？
解：这是最大化指派问题
用减效率矩阵中的各个元素，并变换效率矩阵

试求最优解：
作覆盖所有零元素的最少直线集合

继续变换效率矩阵

再试求最优解：
最优解：，。
即：甲翻译德语，乙翻译日语，丙翻译法语，丁翻译俄语，戊翻译英语，使总的翻译效率最高。每小时可翻译4300印刷符号。
（2）若甲不懂德文，乙不懂日文，其效率矩阵变为
，这仍是最大化指派问题
用减效率矩阵中的各个元素，并变换效率矩阵

试求最优解：

最优解：，。
即：甲翻译日语，乙翻译德语，丙翻译法语，丁翻译俄语，戊翻译英语，使总的翻译效率最高。每小时可翻译4200印刷符号。
（3）若将效率阵中各数字都除以100，然后求解，最优解没有变化。只不过将原来的效率矩阵中单位：印刷符号/小时，改为：百印刷符号/小时。求解结果是一致的。
（完）

说明：以上解答，仅供参考。
12