题六
图6－42
61图6－42示建立求部分树0－1整数规划数学模型
解边[ij]长度记cij设
数学模型：
图6－43
62图6－43示建立求v1v6短路问题0－1整数规划数学模型
解弧(ij)长度记cij设
数学模型：
63图6－43示建立求v1v6流问题线性规划数学模型
解 设xij弧（ij）流量数学模型
64求图6－41部分树图641（a）破圈法图641（b）加边法
图6－44
解图644（a）该题4解树长22中解图示
图644（b）树长20树图示
65 某乡政府计划未3年辖10村达村村间水泥公路相通目标根勘测10村间修建公路费表620示乡镇府选择修建公路路线总成低
表620
两村庄间修建公路费(万元)
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
128
105
96
85
77
138
127
131
126
114
139
112
86
75
83
148
157
85
96
89
80
132
124
105
93
88
127
148
127
136
158
98
82
117
136
97
89
105
134
146
91
105
126
89
88
解属树问题加边法图示方案
低总成743万元
66图6－45中求AHI短路短路长图(a)(b)结果进行较
图6－45
解图6－45(a)
AH短路PAH{ABFH}{ACFH}短路长22AI短路PAI{ABFI}{ACFI}短路长21
图6－45(b)：
AH短路PAH{ACGFH}短路长21AI短路PAI{ACGFI}短路长20
结果显示图图结果样
67已知某设备继续5年年年末卖掉重新购置新设备已知5年年初购置新设备价格分3538404245万元时间1～5年维护费分040914233万元试确定设备更新策略5年设备购置维护总费
解设点vj第j年年初购置新设备状态（ij）第i年年初购置新设备第j年年初弧权应费（购置费＋维护费）绘制网络图计算结果见图示
总费设备更新方案：第种方案第1年购置台设备第5年年末第二种方案第1年购置台设备第2年年末第3年年初更新第5年年末总费115万元
图6－46
68图6－46世界某6城市间航线边数字票价（百美元）Floyd算法设计意两城市间票价便宜路线表
解教师利模板求解：data＼chpt6＼ch6xls
L1
v1
v2
v3
v4
v5
v6
v1
0
88
9
56
8
6
v2
88
0
10
5
100
4
v3
9
10
0
3
48
14
v4
56
5
3
0
12
100
v5
8
100
48
12
0
9
v6
6
4
14
100
9
0
L2
v1
v2
v3
v4
v5
v6
v1
0
88
86
56
8
6
v2
88
0
8
5
13
4
v3
86
8
0
3
48
14
v4
56
5
3
0
78
9
v5
8
13
48
78
0
9
v6
6
4
14
9
9
0
L3
v1
v2
v3
v4
v5
v6
v1
0
88
86
56
8
6
v2
88
0
8
5
13
4
v3
86
8
0
3
48
12
v4
56
5
3
0
78
9
v5
8
13
48
78
0
9
v6
6
4
12
9
9
0
优票价表：
v1
v2
v3
v4
v5
v6
v1
0
88
86
56
8
6
v2
0
8
5
13
4
v3
0
3
48
12
v4
0
78
9
v5
0
9
v6
0
v1v2…v6点优路线图分：
69 设图6－46某汽车公司6零配件加工厂边数字两点间距离(km)现6工厂中选建装配车间
（1）应选工厂零配件运输方便
（2）装配辆汽车6零配件加工厂提供零件重量分050608131617吨运价2元吨公里应选工厂总运费
解(1)利题68表L3结果
v1
v2
v3
v4
v5
v6
Max
v1
0
88
86
56
8
6
88
v2
88
0
8
5
13
4
128
v3
86
8
0
3
48
12
12
v4
56
5
3
0
78
9
9
v5
8
13
48
78
0
9
128
v6
6
4
12
9
9
0
12
选第1工厂
(2)计算单件产品运价见表行计算单件产品运费见表列
v1
v2
v3
v4
v5
v6
单件产品运费
v1
0
88
86
56
8
6
8488
v2
88
0
8
5
13
4
8916
v3
86
8
0
3
48
12
8216
v4
56
5
3
0
78
9
7196
v5
8
13
48
78
0
9
8192
v6
6
4
12
9
9
0
822
运价
1
12
16
26
32
34
选第4工厂
图6－47
610 图6－47（1）求v1v10流流量（2）求割集割量
解出初始流
第轮标号：条增广链调整量等5图示
调整流量
第二轮标号：条增广链调整量等2图示
调整流量
第三轮标号：条增广链调整量等3图示
调整流量
第四轮标号：存增广链流量等45图示
取 截集{(37)(47)(69)(810)截量等45
611 3天然气田A1A2A3天然气输送2区C1C2中途2加压站B1B2天然气线图6－48示输气道单位时间通量cij单位流量费dij标弧(cij dij)求(1)流量22费流（2）费流
图6－48
解虚拟发点收点
T611－1
流量v＝22费流费271求解程参题部分答案PPT文档
T611－13
费流图流量等27总费等351
612图6－46示（1）求解旅行售货员问题（2）求解中国邮路问题
图646
解（1）旅行售货员问题
距离表C
1
2
3
4
5
6
1
∞
88
9
56
8
6
2
88
∞
10
5
∞
4
3
9
10
∞
3
48
14
4
56
5
3
∞
12
∞
5
8
∞
48
12
∞
9
6
6
4
14
∞
9
∞
C中行列分减应行列中数距离表C1
距离表C1
1
2
3
4
5
6
1
∞
32
34
0
06
04
2
28
∞
6
1
∞
0
3
4
7
∞
0
0
11
4
06
2
0
∞
72
∞
5
12
∞
0
72
∞
9
6
0
0
10
∞
32
∞
距离表C1v1v4 H1{ v1 v4 v3 v5 v6 v2 v1} C(H1)56+3+48+9+4+88352
掉第1行第四列d41∞距离表C2
距离表C2
1
2
3
5
6
2
28
∞
6
∞
0
3
4
7
∞
0
11
4
∞
2
0
72
∞
5
12
∞
0
∞
9
6
0
0
10
32
∞
距离表C2行列零H2 H1{ v1 v4 v3 v5 v6 v2 v1}总距离Hamilton回路C(H1) 352
(2)中国邮路问题虚拟条边
取回路H1＝{v1v3v4}C(H1)9+5+317C(v1v3)9> C(H1)2调整回路
回路满足短回路准图短欧拉回路中边(v1 v4)(v4 v3)重复次
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
图6－42
61图6－42示建立求部分树0－1整数规划数学模型
解边[ij]长度记cij设
数学模型：
图6－43
62图6－43示建立求v1v6短路问题0－1整数规划数学模型
解弧(ij)长度记cij设
数学模型：
63图6－43示建立求v1v6流问题线性规划数学模型
解 设xij弧（ij）流量数学模型
64求图6－41部分树图641（a）破圈法图641（b）加边法
图6－44
解图644（a）该题4解树长22中解图示
图644（b）树长20树图示
65 某乡政府计划未3年辖10村达村村间水泥公路相通目标根勘测10村间修建公路费表620示乡镇府选择修建公路路线总成低
表620
两村庄间修建公路费(万元)
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
128
105
96
85
77
138
127
131
126
114
139
112
86
75
83
148
157
85
96
89
80
132
124
105
93
88
127
148
127
136
158
98
82
117
136
97
89
105
134
146
91
105
126
89
88
解属树问题加边法图示方案
低总成743万元
66图6－45中求AHI短路短路长图(a)(b)结果进行较
图6－45
解图6－45(a)
AH短路PAH{ABFH}{ACFH}短路长22AI短路PAI{ABFI}{ACFI}短路长21
图6－45(b)：
AH短路PAH{ACGFH}短路长21AI短路PAI{ACGFI}短路长20
结果显示图图结果样
67已知某设备继续5年年年末卖掉重新购置新设备已知5年年初购置新设备价格分3538404245万元时间1～5年维护费分040914233万元试确定设备更新策略5年设备购置维护总费
解设点vj第j年年初购置新设备状态（ij）第i年年初购置新设备第j年年初弧权应费（购置费＋维护费）绘制网络图计算结果见图示
总费设备更新方案：第种方案第1年购置台设备第5年年末第二种方案第1年购置台设备第2年年末第3年年初更新第5年年末总费115万元
图6－46
68图6－46世界某6城市间航线边数字票价（百美元）Floyd算法设计意两城市间票价便宜路线表
解教师利模板求解：data＼chpt6＼ch6xls
L1
v1
v2
v3
v4
v5
v6
v1
0
88
9
56
8
6
v2
88
0
10
5
100
4
v3
9
10
0
3
48
14
v4
56
5
3
0
12
100
v5
8
100
48
12
0
9
v6
6
4
14
100
9
0
L2
v1
v2
v3
v4
v5
v6
v1
0
88
86
56
8
6
v2
88
0
8
5
13
4
v3
86
8
0
3
48
14
v4
56
5
3
0
78
9
v5
8
13
48
78
0
9
v6
6
4
14
9
9
0
L3
v1
v2
v3
v4
v5
v6
v1
0
88
86
56
8
6
v2
88
0
8
5
13
4
v3
86
8
0
3
48
12
v4
56
5
3
0
78
9
v5
8
13
48
78
0
9
v6
6
4
12
9
9
0
优票价表：
v1
v2
v3
v4
v5
v6
v1
0
88
86
56
8
6
v2
0
8
5
13
4
v3
0
3
48
12
v4
0
78
9
v5
0
9
v6
0
v1v2…v6点优路线图分：
69 设图6－46某汽车公司6零配件加工厂边数字两点间距离(km)现6工厂中选建装配车间
（1）应选工厂零配件运输方便
（2）装配辆汽车6零配件加工厂提供零件重量分050608131617吨运价2元吨公里应选工厂总运费
解(1)利题68表L3结果
v1
v2
v3
v4
v5
v6
Max
v1
0
88
86
56
8
6
88
v2
88
0
8
5
13
4
128
v3
86
8
0
3
48
12
12
v4
56
5
3
0
78
9
9
v5
8
13
48
78
0
9
128
v6
6
4
12
9
9
0
12
选第1工厂
(2)计算单件产品运价见表行计算单件产品运费见表列
v1
v2
v3
v4
v5
v6
单件产品运费
v1
0
88
86
56
8
6
8488
v2
88
0
8
5
13
4
8916
v3
86
8
0
3
48
12
8216
v4
56
5
3
0
78
9
7196
v5
8
13
48
78
0
9
8192
v6
6
4
12
9
9
0
822
运价
1
12
16
26
32
34
选第4工厂
图6－47
610 图6－47（1）求v1v10流流量（2）求割集割量
解出初始流
第轮标号：条增广链调整量等5图示
调整流量
第二轮标号：条增广链调整量等2图示
调整流量
第三轮标号：条增广链调整量等3图示
调整流量
第四轮标号：存增广链流量等45图示
取 截集{(37)(47)(69)(810)截量等45
611 3天然气田A1A2A3天然气输送2区C1C2中途2加压站B1B2天然气线图6－48示输气道单位时间通量cij单位流量费dij标弧(cij dij)求(1)流量22费流（2）费流
图6－48
解虚拟发点收点
T611－1
流量v＝22费流费271求解程参题部分答案PPT文档
T611－13
费流图流量等27总费等351
612图6－46示（1）求解旅行售货员问题（2）求解中国邮路问题
图646
解（1）旅行售货员问题
距离表C
1
2
3
4
5
6
1
∞
88
9
56
8
6
2
88
∞
10
5
∞
4
3
9
10
∞
3
48
14
4
56
5
3
∞
12
∞
5
8
∞
48
12
∞
9
6
6
4
14
∞
9
∞
C中行列分减应行列中数距离表C1
距离表C1
1
2
3
4
5
6
1
∞
32
34
0
06
04
2
28
∞
6
1
∞
0
3
4
7
∞
0
0
11
4
06
2
0
∞
72
∞
5
12
∞
0
72
∞
9
6
0
0
10
∞
32
∞
距离表C1v1v4 H1{ v1 v4 v3 v5 v6 v2 v1} C(H1)56+3+48+9+4+88352
掉第1行第四列d41∞距离表C2
距离表C2
1
2
3
5
6
2
28
∞
6
∞
0
3
4
7
∞
0
11
4
∞
2
0
72
∞
5
12
∞
0
∞
9
6
0
0
10
32
∞
距离表C2行列零H2 H1{ v1 v4 v3 v5 v6 v2 v1}总距离Hamilton回路C(H1) 352
(2)中国邮路问题虚拟条边
取回路H1＝{v1v3v4}C(H1)9+5+317C(v1v3)9> C(H1)2调整回路
回路满足短回路准图短欧拉回路中边(v1 v4)(v4 v3)重复次
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档