运筹学答案熊伟中.docx
《运筹学答案熊伟中.docx》由会员分享，可在线阅读，更多相关《运筹学答案熊伟中.docx（38页珍藏版）》请在冰点文库上搜索。
运筹学答案熊伟中
习题四
4.1工厂生产甲、乙两种产品，由Ａ、Ｂ二组人员来生产。
Ａ组人员熟练工人比较多，工作效率高，成本也高；Ｂ组人员新手较多工作效率比较低，成本也较低。
例如，A组只生产甲产品时每小时生产10件，成本是50元有关资料如表4.21所示。
表4.21
产品甲
产品乙
效率（件/小时）
成本（元/件）
效率（件/小时）
成本（元/件）
A组
10
50
8
45
B组
8
45
5
40
产品售价（元/件）
80
75
二组人员每天正常工作时间都是8小时，每周5天。
一周内每组最多可以加班10小时，加班生产的产品每件增加成本5元。
工厂根据市场需求、利润及生产能力确定了下列目标顺序：
P1：
每周供应市场甲产品400件，乙产品300件
P2：
每周利润指标不低于500元
P3：
两组都尽可能少加班，如必须加班由Ａ组优先加班
建立此生产计划的数学模型。
4.1【解】解法一：
设x1,x2分别为A组一周内正常时间生产产品甲、乙的产量，x3,x4分别为A组一周内加班时间生产产品甲、乙的产量；x5,x6分别为B组一周内正常时间生产产品甲、乙的产量，x7,x8分别为B组一周内加班时间生产产品甲、乙的产量。
总利润为
生产时间为
A组：
B组：
数学模型为：
解法二：
设x1,x2分别为A组一周内生产产品甲、乙的正常时间，x3,x4分别为A组一周内生产产品甲、乙的加班时间；x5,x6分别为B组一周内生产产品甲、乙的正常时间，x7,x8分别为B组一周内生产产品甲、乙的加班时间。
数学模型请同学们建立。
4.2设xij为Ai到Bj的运量，数学模型为
4.3双击下图，打开幻灯片。
4.4已知某实际问题的线性规划模型为
假定重新确定这个问题的目标为：
Ｐ1：
ｚ的值应不低于1900
Ｐ2：
资源１必须全部利用
将此问题转换为目标规划问题，列出数学模型。
【解】数学模型为
4.5已知目标规划问题
（1）分别用图解法和单纯形法求解；
（2）分析目标函数分别变为①、②两种情况时（②中分析w1、w2的比例变动）解的变化。
①
②
【解】
（1）图解法（双击下图，打开幻灯片）
（1）单纯形法
Cj
0
0
P1
P4
0
P2
5P3
0
3P3
0
b
CB
基
x1
x2
d1－
d1+
d2－
d2+
d3－
d3+
d4－
d4+
P1
d1－
1
2
1
－1
6
0
d2－
1
2
1
－1
9
5P3
d3－
1
－2
1
－1
4
3P3
d4－
[1]
1
－1
2
表
（1）
Cj－Zj
P1
－1
－2
1
P2
1
P3
－5
7
5
3
P4
1
P1
d1－
[1]
1
－1
－2
2
2
0
d2－
1
1
－1
－2
2
5
5P3
d3－
1
1
－1
2
－2
8
0
x2－
1
1
－1
2
表
（2）
Cj－Zj
P1
－1
1
2
－2
P2
1
P3
－5
7
5
－7
10
P4
1
0
x1
1
1/2
－1/2
1/2
－1/2
0
0
13/2
P4
d1+
－1
1
1
－1
3
3P3
d4－
－1/4
1/4
1/4
－1/4
1
－1
3/4
0
x2
1
1/4
－1/4
－1/4
5/4
表（5）
Cj－Zj
P1
1
P2
1
P3
3/4
－3/4
17/4
3/4
3
P4
1
1
1
（b）
单纯形法，利用上表（5）的结果，引入参数w1、w2进行灵敏度分析，得到下表。
Cj
0
0
P1
P4
0
P2
w1P3
0
w2P3
0
b
CB
基
x1
x2
d1－
d1+
d2－
d2+
d3－
d3+
d4－
d4+
0
x1
1
1/2
－1/2
1/2
－1/2
0
0
13/2
P4
d1+
－1
1
1
－1
3
w2P3
d4－
－1/4
1/4
[1/4]
－1/4
1
－1
3/4
0
x2
1
1/4
－1/4
－1/4
5/4
表
（1）
Cj－Zj
P1
1
P2
1
P3
w2/4
－w2/4
w1-w2/4
w2/4
w2
P4
1
1
1
0
x1
1
1
－1
－2
2
5
P4
d1+
－1
1
1
－1
3
w1P3
d3－
－1
1
1
－1
4
－4
3
0
x2－
1
1
－1
2
表
（2）
Cj－Zj
P1
1
P2
1
P3
w1
－w1
w1
w2－4w1
4w1
P4
1
－1
1
（1）由表
（1）知，当w1－w2/4>0，即
时，满意解为：
X＝（13/2，5/4）
（2）由表
（2）知，当w2－4w1>0，即
时，满意解为：
X＝（5，2）
（3）当
时，表
（1）和表
（2）都是满意解。
习题五
5.2用元素差额法直接给出表5-53及表5-54下列两个运输问题的近似最优解．
表5-53
B1
B2
B3
B4
B5
Ai
A1
19
16
10
21
9
18
A2
14
13
5
24
7
30
A3
25
30
20
11
23
10
A4
7
8
6
10
4
42
Bj
15
25
35
20
5
表5-54
B1
B2
B3
B4
Ai
A1
5
3
8
6
16
A2
10
7
12
15
24
A3
17
4
8
9
30
Bj
20
25
10
15
【解】表5-53。
Z=824
表5-54Z=495
5.3求表5-55及表5-56所示运输问题的最优方案．
（1）用闭回路法求检验数（表5-55）
表5-55
B1
B2
B3
B4
Ai
A1
10
5
2
3
70
A2
4
3
1
2
80
A3
5
6
4
4
30
bj
60
60
40
20
（2）用位势法求检验数（表5-56）
表5-56
B1
B2
B3
B4
Ai
A1
9
15
4
8
10
A2
3
1
7
6
30
A3
2
10
13
4
20
A4
4
5
8
3
43
bj
20
15
50
15
【解】
（1）
（2）
5.4求下列运输问题的最优解
（1）C1目标函数求最小值；
（2）C2目标函数求最大值
1545204060305040
（3）目标函数最小值,B1的需求为30≤b1≤50,B2的需求为40，B3的需求为20≤b3≤60,A1不可达A4，B4的需求为30．
【解】
（1）
（2）
（3）先化为平衡表
B11
B12
B2
B31
B32
B4
ai
A1
4
4
9
7
7
M
70
A2
6
6
5
3
3
2
20
A3
8
8
5
9
9
10
50
A4
M
0
M
M
0
M
40
bj
30
20
40
20
40
30
180
最优解：
5.5
（1）建立数学模型
设xij（I=1,2,3;j=1,2）为甲、乙、丙三种型号的客车每天发往B1，B2两城市的台班数，则
（2）写平衡运价表
将第一、二等式两边同除以40，加入松驰变量x13,x23和x33将不等式化为等式，则平衡表为：
B1
B2
B3
ai
甲
乙
丙
80
60
50
65
50
40
0
0
0
5
10
15
bj
10
15
5
为了平衡表简单，故表中运价没有乘以40，最优解不变
（3）最优调度方案：
即甲第天发5辆车到B1城市，乙每天发5辆车到B1城市，5辆车到B2城市，丙每天发10辆车到B2城市，多余5辆，最大收入为
Z=40（5×80+5×60+5×50+10×40）=54000（元）
5.6
（1）设xij为第i月生产的产品第j月交货的台数，则此生产计划问题的数学模型为
（2）化为运输问题后运价表（即生产费用加上存储费用）如下，其中第5列是虚设销地费用为零，需求量为30。
1
2
3
4
5
ai
1
2
3
4
1
M
M
M
1.15
1.25
M
M
1.3
1.4
0.87
M
1.45
1.55
1.02
0.98
0
0
0
0
65
65
65
65
bj
50
40
60
80
30
（3）用表上作业法，最优生产方案如下表：
1
2
3
4
5
ai
1
2
3
4
50
15
25
60
10
5
65
30
65
65
65
65
Bi
50
40
60
80
30
上表表明：
一月份生产65台，当月交货50台；二月份交货15台,二月份生产35台，当月交货25台，四月份交货10台；三月份生产65台，当月交货60台，四月份交货5台，4月份生产65台当月交货。
最小费用Z=235万元。
5.7假设在例5.15中四种产品的需求量分别是1000、2000、3000和4000件，求最优生产配置方案．
【解】将表5-35所示的单件产品成本乘以需求量，为计算简便，从表中提出公因子1000．
产品1
产品2
产品3
产品4
工厂1
58
138
540
1040
工厂2
75
100
450
920
工厂3
65
140
510
1000
工厂4
82
110
600
1120
用匈牙利法得到最优表
第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2；
总成本
Z＝1000×（58＋920＋510＋110）＝1598000
注：
结果与例5.15的第2个方案相同，但并不意味着“某列（行）同乘以一个非负元素后最优解不变”结论成立。
5.8求解下列最小值的指派问题，其中第
（2）题某人要作两项工作，其余3人每人做一项工作．
（1）
【解】最优解
（2）
【解】虚拟一个人，其效率取4人中最好的，构造效率表为
1
2
3
4
5
甲
26
38
41
52
27
乙
25
33
44
59
21
丙
20
30
47
56
25
丁
22
31
45
53
20
戊
20
30
41
52
20
最优解：
甲～戊完成工作的顺序为3、5、1、2、4，最优值Z=165
最优分配方案：
甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。
5.9求解下列最大值的指派问题：
（1）
【解】最优解
（2）
【解】最优解
第5人不安排工作。
表5-58成绩表（分钟）
游泳
自行车
长跑
登山
甲
20
43
33
29
乙
15
33
28
26
丙
18
42
38
29
丁
19
44
32
27
戊
17
34
30
28
5.10学校举行游泳、自行车、长跑和登山四项接力赛，已知五名运动员完成各项目的成绩（分钟）如表5-58所示．如何从中选拔一个接力队，使预期的比赛成绩最好．
【解】设xij为第i人参加第j项目的状态，则数学模型为
接力队最优组合
乙
长跑
丙
游泳
丁
登山
戊
自行车
甲淘汰。
预期时间为107分钟。
习题六
图6－39
6.1如图6－39所示，建立求最小部分树的0－1整数规划数学模型。
【解】边[i，j]的长度记为cij，设
数学模型为：
图6－40
6.2如图6－40所示，建立求v1到v6的最短路问题的0－1整数规划数学模型。
【解】弧（i，j）的长度记为cij，设
数学模型为：
6.3如图6－40所示，建立求v1到v6的最大流问题的线性规划数学模型。
【解】设xij为弧（i,j）的流量，数学模型为
6.4求图6－41的最小部分树。
图6-41（a）用破圈法,图6-41（b）用加边法。
图6－41
【解】图6-41（a），该题有4个解，最小树长为21，其中一个解如下图所示。
图6-41（b），最小树长为20。
最小树如下图所示。
6.5某乡政府计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。
根据勘测，10个村之间修建公路的费用如表6-20所示。
乡镇府如何选择修建公路的路线使总成本最低。
表6-20
两村庄之间修建公路的费用（万元）
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
12.8
10.5
9.6
8.5
7.7
13.8
12.7
13.1
12.6
11.4
13.9
11.2
8.6
7.5
8.3
14.8
15.7
8.5
9.6
8.9
8.0
13.2
12.4
10.5
9.3
8.8
12.7
14.8
12.7
13.6
15.8
9.8
8.2
11.7
13.6
9.7
8.9
10.5
13.4
14.6
9.1
10.5
12.6
8.9
8.8
【解】属于最小树问题。
用加边法，得到下图所示的方案。
最低总成本74.3万元。
6.6在图6－42中，求A到H、I的最短路及最短路长，并对图（a）和（b）的结果进行比较。
图6－42
【解】图6－42（a）:
A到H的最短路PAH={A,B,F,H},{A,C,F,H}最短路长22；A到I的最短路PAI={A,B,F,I},{A,C,F,I}最短路长21。
对于图6－42（b）：
A到H的最短路PAH={A,C,G,F,H},最短路长21；A到I的最短路PAI={A,C,G,F,I},最短路长20；
结果显示有向图与无向图的结果可能不一样。
6.7已知某设备可继续使用5年，也可以在每年年末卖掉重新购置新设备。
已知5年年初购置新设备的价格分别为3.5、3.8、4.0、4.2和4.5万元。
使用时间在1～5年内的维护费用分别为0.4、0.9、1.4、2.3和3万元。
试确定一个设备更新策略，使5年的设备购置和维护总费用最小。
【解】设点vj为第j年年初购置新设备的状态，（i，j）为第i年年初购置新设备使用到第j年年初，弧的权为对应的费用（购置费＋维护费），绘制网络图并计算，结果见下图所示。
总费用最小的设备更新方案为：
第一种方案，第1年购置一台设备使用到第5年年末；第二种方案，第1年购置一台设备使用到第2年年末，第3年年初更新后使用到第5年年末。
总费用为11.5万元。
图6－43
6.8图6－43是世界某6大城市之间的航线，边上的数字为票价（百美元），用Floyd算法设计任意两城市之间票价最便宜的路线表。
【解】教师可利用模板求解：
data\chpt6\ch6.xls
L1
v1
v2
v3
v4
v5
v6
v1
0
8.8
9
5.6
8
6
v2
8.8
0
10
5
100
4
v3
9
10
0
3
4.8
14
v4
5.6
5
3
0
12
100
v5
8
100
4.8
12
0
9
v6
6
4
14
100
9
0
L2
v1
v2
v3
v4
v5
v6
v1
0
8.8
8.6
5.6
8
6
v2
8.8
0
8
5
13
4
v3
8.6
8
0
3
4.8
14
v4
5.6
5
3
0
7.8
9
v5
8
13
4.8
7.8
0
9
v6
6
4
14
9
9
0
L3
v1
v2
v3
v4
v5
v6
v1
0
8.8
8.6
5.6
8
6
v2
8.8
0
8
5
13
4
v3
8.6
8
0
3
4.8
12
v4
5.6
5
3
0
7.8
9
v5
8
13
4.8
7.8
0
9
v6
6
4
12
9
9
0
最优票价表：
v1
v2
v3
v4
v5
v6
v1
0
8.8
8.6
5.6
8
6
v2
0
8
5
13
4
v3
0
3
4.8
12
v4
0
7.8
9
v5
0
9
v6
0
v1、v2、…、v6到各点的最优路线图分别为：
6.9设图6－43是某汽车公司的6个零配件加工厂，边上的数字为两点间的距离（km）。
现要在6个工厂中选一个建装配车间。
（1）应选那个工厂使零配件的运输最方便。
（2）装配一辆汽车6个零配件加工厂所提供零件重量分别是0.5、0.6、0.8、1.3、1.6和1.7吨，运价为2元/吨公里。
应选那个工厂使总运费最小。
【解】
（1）利用习题6.8表L3的结果
v1
v2
v3
v4
v5
v6
Max
v1
0
8.8
8.6
5.6
8
6
8.8
v2
8.8
0
8
5
13
4
12.8
v3
8.6
8
0
3
4.8
12
12
v4
5.6
5
3
0
7.8
9
9
v5
8
13
4.8
7.8
0
9
12.8
v6
6
4
12
9
9
0
12
选第1个工厂最好。
（2）计算单件产品的运价，见下表最后一行。
计算单件产品的运费，见下表最后一列。
v1
v2
v3
v4
v5
v6
单件产品运费
v1
0
8.8
8.6
5.6
8
6
84.88
v2
8.8
0
8
5
13
4
89.16
v3
8.6
8
0
3
4.8
12
82.16
v4
5.6
5
3
0
7.8
9
71.96
v5
8
13
4.8
7.8
0
9
81.92
v6
6
4
12
9
9
0
82.2
运价
1
1.2
1.6
2.6
3.2
3.4
选第4个工厂最好。
图6－44
6.10如图6－44，
（1）求v1到v10的最大流及最大流量；
（2）求最小割集和最小割量。
【解】给出初始流如下
第一轮标号：
得到一条增广链，调整量等于5，如下图所示
调整流量。
第二轮标号：
得到一条增广链，调整量等于2，如下图所示
调整流量。
第三轮标号：
得到一条增广链，调整量等于3，如下图所示
调整流量。
第四轮标号：
不存在增广链，最大流量等于45，如下图所示
取
，最小截集{（3,7）,（4,7）,（6,9）,（8,10），最小截量等于45。
6.11将3个天然气田A1、A2、A3的天然气输送到2个地区C1、C2，中途有2个加压站B1、B2，天然气管线如图6－45所示。
输气管道单位时间的最大通过量cij及单位流量的费用dij标在弧上（cij,dij）。
求
（1）流量为22的最小费用流；
（2）最小费用最大流。
图6－45
【解】虚拟一个发点和一个收点
T6.11－1
得到流量v＝22的最小费用流，最小费用为271。
求解过程参看第4章PPT文档习题答案。
T6.11－13
最小费用最大流如下图，最大流量等于27，总费用等于351。
6.12如图6－43所示，
（1）求解旅行售货员问题；
（2）求解中国邮路问题。
图6-43
【解】
（1）旅行售货员问题。
距离表C
1
2
3
4
5
6
1
∞
8.8
9
5.6
8
6
2
8.8
∞
10
5
∞
4
3
9
10
∞
3
4.8
14
4
5.6
5
3
∞
12
∞
5
8
∞
4.8
12
∞
9
6
6
4
14
∞
9
∞
在C中行列分别减除对应行列中的最小数，得到距离表C1。
距离表C1
1
2
升级会员 