运筹学答案熊伟中.docx
- 文档编号:2664031
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:38
- 大小:556.75KB
运筹学答案熊伟中.docx
《运筹学答案熊伟中.docx》由会员分享,可在线阅读,更多相关《运筹学答案熊伟中.docx(38页珍藏版)》请在冰点文库上搜索。
运筹学答案熊伟中
习题四
4.1工厂生产甲、乙两种产品,由A、B二组人员来生产。
A组人员熟练工人比较多,工作效率高,成本也高;B组人员新手较多工作效率比较低,成本也较低。
例如,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:
两组都尽可能少加班,如必须加班由A组优先加班
建立此生产计划的数学模型。
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已知某实际问题的线性规划模型为
假定重新确定这个问题的目标为:
P1:
z的值应不低于1900
P2:
资源1必须全部利用
将此问题转换为目标规划问题,列出数学模型。
【解】数学模型为
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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 答案 熊伟中