管理运筹学专题3Word下载.docx
《管理运筹学专题3Word下载.docx》由会员分享，可在线阅读，更多相关《管理运筹学专题3Word下载.docx（24页珍藏版）》请在冰点文库上搜索。
B
C
D
E
10
7
5
3
11
4
6
8
方法提示（以下方法供参考，但不限于这些方法，问题6至问题9必须完成）：
1．枚举法：
可产生最优解，但如果配送点很多时（如10个点），此方法不行。
2．动态规划：
假设无后效性，可得到一个满意解。
由于问题本身实际有后效性，所以不一定能产生最优解。
3．指派问题解法（匈牙利算法）：
当出现小范围回路时需对上述路线表做一定的调整，而且调整的方式很多，需讨论。
4．用图论的方法来求解此问题。
5．节约法（一种启发式算法）：
可得到满意解，不一定是最优解。
6．当B、C、D、E各处货物需求量分别为6.1吨、13.8吨、6.8吨、12.7吨时，配送车辆最大载货量为5吨，试用不同方法探求配送方案，并进行对比分析。
7．由于客户需求的变化，B、C、D、E各处货物需求量分别为6.8吨、13.8吨、6.1吨、12.7吨时，配送车辆最大载货量为5吨，试用不同方法探求配送方案，并进行对比分析。
8．对问题6，运输费用为1.6元/吨·
公里，每次装车、卸车费用各30元，空车（载货量少于0.5吨时按空车计收运费）返程费按0.8元/公里计算，试论证采用多大载货量（载货量有5吨、8吨、10吨、12吨、20吨几种规格）的车辆效果最好？
9．对问题6，运输费用为1.6元/吨·
公里，每次装车、卸车费用各30元，空车（载货量少于0.5吨时按空车计收运费）返程费按0.8元/公里计算，试论证采用多大载货量（载货量允许为任意值）的车辆效果最好？
三、案例求解
3.1、LINGO软件求解
MODEL:
SETS:
!
初始设置;
CITY/1..5/:
U;
U（i）为地点编号;
LINK（CITY,CITY）:
DIST,X;
DIST为两地间距离;
ENDSETS
数据区;
DATA:
DIST=99911745
10999458
7499978
5679993
3883999;
ENDDATA
N=@SIZE（CITY）;
模型的大小;
MIN=@SUM（LINK:
DIST*X）;
目标函数为点距之和最小的路径;
@FOR（CITY（K）:
@SUM（CITY（I）|I#NE#K:
X（I,K））=1;
对于线路中每一个地点只有一条路指向这个地点;
@SUM（CITY（J）|J#NE#K:
X（K,J））=1;
从这个城市出发只有一条路可以离开;
@FOR（CITY（J）|J#GT#1#AND#J#NE#K:
如果连接cityk和cityj,则cityj=cityk+1;
U（J）>
=U（K）+X（K,J）-
（N-2）*（1-X（K,J））+
（N-3）*X（J,K））;
）;
@FOR（LINK:
@BIN（X））;
@FOR（CITY（K）|K#GT#1:
U（K）<
=N-1-（N-2）*X（1,K）;
U（K）>
=1+（N-2）*X（K,1））;
END
最短路：
U
（1）0.0000000.000000
U
（2）2.0000000.000000
U（3）1.0000000.000000
U（4）3.0000000.000000
U（5）4.0000000.000000
A→C→B→D→E→A
路长：
7+4+5+3+3=22
3.2、枚举法求解
建立所有路线表：
路线
路程
总路程
ABCDEA
11+4+7+3+3
28
ACBDEA
7+4+5+3+3
22
ABCEDA
11+4+8+3+5
31
ACBEDA
7+4+8+3+5
27
ABDCEA
11+5+7+8+3
34
ACDBEA
7+7+6+8+3
ABDECA
11+5+3+8+7
ACDEBA
7+7+3+8+10
35
ABECDA
11+8+8+7+5
39
ACEBDA
7+8+8+5+5
33
ABEDCA
11+8+3+7+7
36
ACEDBA
7+8+3+6+10
ADBCEA
4+6+4+8+3
25
AEBCDA
5+8+4+7+5
29
ADBECA
4+6+8+8+7
AEBDCA
5+8+5+7+7
32
ADCEBA
4+7+8+8+10
37
AECDBA
5+8+7+6+10
ADCBEA
4+7+4+8+3
26
AECBDA
5+8+4+5+5
ADECBA
4+3+8+4+10
AEDBCA
5+3+6+4+7
ADEBCA
4+3+8+4+7
AEDCBA
5+3+7+4+10
由上表可以得出最短路线为：
A—C—B—D—E—A，此时的总路程为7+4+5+3+3=22（公里），所以我们通过枚举法得出最短配送路线为：
A—C—B—D—E—A，其最短总路程为22公里。
根据计算结果可知，出现了两条回路：
①ADEA，②BCB，最短路程为3+4+4+3+3+1=18公里。
当前所求得的最佳路线方案并非是一个完整的封闭回路，而是分成了两条封闭的支路，不满足我们所要求的最佳完整封闭回路。
接下来，我们要拆分其中一条回路，需找新的更合理的最优路线。
通常选择较短路线入手，即第②条线路，可以设置人为障碍，使得从B到C的路线不可以被选择（或者从C到B的路线不可以被选择），相当于人为宣布了此路不通，寻找新的路线方案替代原有回路。
同时，可以确定，无论找到什么样的路线方案，得到的新的总路程不会小于目前的总路程结果（18公里）。
设置一：
B到C的距离为M
最佳路线：
ACBDEA，最短路程为3+4+7+3+3+2=22公里。
设置二：
C到B的距离为M
最佳路线之一：
AEDBCA，最短路程为3+6+4+3+3+1+4+1+1-1=25公里，大于设置一的22公里。
因此，最短配送路线为ACBDEA，总路程为22公里。
3.4、EXCEL求解
出发地
抵达地
路程图
999
初始数据设置
出现了两条回路：
①ADEA，②BCB
加入限制条件
BC不通
CB不通
图形可描述现实世界中许多状态变化，图形表达事物是现代科学技术中的一种重要手段。
图形不仅形象直观，而且可以结合数据，可以数形结合便于汁算，因此图论内容是相当现实和必需的。
旅行售货员问题是一个经典的组合优化问题，其实质是在一个带权的完全无向图中，找一个权值最小的回路。
解法
步骤1在完全图中任选一点作为起始点，找出一个与始点最近的点，形成一条边的初始路，然后逐点的扩充这条路。
步骤2设X表示最新加入到这条路上的顶点，从不在路上的所有顶点中，选一个与X最临近的点，把连接于点X的边加到这条路上，重复这一步，直到图中所有的顶点都完全包含
在路中。
步骤3把起始点和最后加入的顶点之间的边放入，得到回路。
步骤如图：
最邻近算法例图
改进算法：
但在实际中随着问题规模的增大用如上的近似算法解决问题是相当困难的，因为随着问题规模的增大，近似的程度也会增大，问题规模越大和精确解的相差就越大。
因为这是一个离散的问题，对上述的算法进行改进，运用类似三角剖分的方法对于该问题做如下的近似算法。
步骤1首先找到所有边中权最小的一条边，然后以这条边为起始边用类似三角剖分的办法找到权和最小的三角形，删除最大的边。
步骤2从下一个点出发继续按照步骤1的方法往下做，在这个过程中如果遇到不符合的情况则要按照邻近算法选择权最小的一条路径，然后以这条路的下一个顶点按照步骤1继续做。
在最后的几个顶点中，如果按照上面步骤回到源点那么操作完成。
但是如果没有形成回路，那么对最后2到3个顶点用近似邻近算法找到回路。
步骤3对已经找到的边的权相加得到的就是旅行售货员问题的一个解。
图1
在图1中，选点a作为源点，找到以此点为出发点的最小权边ae，并以此为三角形一边找到权和最小的三角形aed并删除最大权边ad（如图2），则以顶点a和e为出发点分别找到最小权边以及最小权和三角形abc和bcd，接着分别比较这两个三角形的两条权较小的边权之和有bc+ac<
bc+bd，则选择c-b-d为通路，删除ab和cd（如图3），此时连接a与c，得到回路，确定方向为a-c-b-de-a（如图4）。
将得到的边权和相加7+4+5+3+3=22，此时经检验这个结果是最小回路。
图2
图3
图4
图4即为最优路线。
配送路线为ACBDEA，总路程为22公里。
四、约束条件下的配送方案
4.1、车辆载重5t
因为B、C、D、E地需求量为6.1吨、13.8吨、6.8吨、12.7吨，总需求量为39.4吨，而配送车辆的最大载货量为5吨，因此，一共需要8车次。
此时可有两种方案进行选择：
1、由8辆车组成一个车队，一起出发，行进相同的路线，然后一起返回，因为此种情况下，每到一个地点都可能会有车返回，因此，最优路线可能不是上边求出的路线；
2、对目的地进行一定的组合，然后把8辆车进行分配，或者由N辆车运送8车次。
下面我们对这两个方案进行分析：
1、一起出发的情况，用枚举法：
1
2
98
42
45
18
203
回1，余7
回2，余5
回2，余3
回3
49
16
205
回3，余2
回2
40
63
234
回1，余6
回3，余3
210
62
61
24
245
227
166
回2,余5
46
190
70
38
181
回3，余4
回2，余2
回3,余4
回1，余3
152
60
156
157
回2，余6
回1，余5
169
52
189
回2，余4
176
57
20
回1，余2
14
177
58
41
69
173
23
50
56
153
由上表可知，如果一个车队一起出发，那么最优路线一共有两条，ADECBA和AEDBCA，总路程为152公里。
显然，让整个车队一起配送这个方案，并不是最优的。
2、因为BCDE各地的需求是零散的，不可能用一个车次运完，因此，可以根据每地需求的情况进行适当的分组，分开进行配送。
由题中所给的数据，结合需求量、载货量，我们可以分析出基本路线：
①A与B之间需要往返一次：
S1=11+10=21
②A与C之间需要往返两次：
S2=7*7*2=28
③A与D之间需要往返一次：
S3=4+5=9
④A与E之间需要往返两次：
S4=8*2=16
∴B\C\D\E之间的需求剩余量为：
1.1
3.8
1.8
2.7
∴⑤最优路径为A——>
C——>
B——>
A;
A——>
D——>
E——>
S5=21+10=31
∴S总=21+28+9+16+31=105公里<
152公里
因此，对目的地进行一定的组合，由N辆车运送8车次的方案2是最优选择。
于是为了简便，以下的分析我们都假设只用一辆车进行配送。
4.1.1需求变化后的情况
1——④的总路程不变，需求剩余量变为：
由上题的枚举可以算出最优路程以及其距离：
⑤最优路径为A——>
S5=22+18=40公里
∴S总=21+28+9+16+40=114公里
4.2、费用限制下的配送方案
当载货量为5吨时，参见问题6可知，最优路线为①A与B之间往返一次；
②A与C之间往返两次；
③A与D之间往返一次；
④A与E之间往返两次；
⑤A——>
A，A——>
A。
A——>
B30*2+5*10*1.6+0.8*10=148
C（30*2+7*5*1.6+0.8*7）*2=243.2
D30*2+5*5*1.6+0.8*5=104
E（30*2+3*5*1.6+0.8*3）*2=172.8
此时车载4.9吨30*2+7*4.9*1.6+4*1.6*1.1+30+0.8*11=160.72
A
此时车载4.5吨30*2+4.5*5*1.6+3*1.6*1.8+30+0.8*5=138.64
∴共计费用967.36元
当车载量为10吨时：
A与C之间需要往返一次30*2+1.6*10*7+0.8*7=177.6
A与E之间需要往返一次30*2+1.6*10*3+0.8*5=112
6.1
6.8
B地与C地需求量之和为：
9.9吨；
D地与E地需求量之和为9.5吨；
故路线为：
最优路径为A——>
此时车载量为9.9吨30*2+9.9*7*1.6+4*6.1*1.6+30+0.8*11=248.72
此时车载量为9.5吨30*2+9.5*4*1.6+3*2.7*1.6+30+0.8*3=166.16
∴共计费用为：
704.48元
当载货量为20吨时，则
13.8
12.7
19.9吨；
D地与E地需求量之和为19.5吨；
此时车载19.9吨30*2+19.9*7*1.6+6.1*4*1.6+30+0.8*11=360.72
此时车载19.5吨30*2+19.5*5*1.6+6.8*3*1.6+30+0.8*5=282.64
643.36元
综上，采用20吨的载货量的车辆效果最好。
4.2.1车载无限制下的配送
根据4.2的分析A——>
共计费用为：
故实际车载为19.9t时，车辆利用率最高，效果最好。
[1]李军.非对称距离的旅行商问题的构造算法[J].运筹与管理，2000,9.
[2]许金星,吴素萍.旅行售货员问题的图论近似算法[J].计算机工程与应用,2009,45.
[3]徐国松.Lingo软件在运输问题中的应用[J].管理科学.
[4]霍佳震,张磊.求解配送＼收集旅行商问题的启发式算法[J].同济大学学报,2006.
[5]邱家学.中国邮递员问题的EXCEL求解[J].科学实践.
六、附录
会议纪要：
第一次会议：
时间：
2010年6月4日晚21点
地点：
思东八层
参加人员：
刘景华周界村夏蕾罗炜罡邓文涛关明亮刘庚
记录人：
刘景华
会议的主题及内容：
本次案例相比于前2次的案例有了很大的提高,案例本身具有灵活性,可以用多种方法进行求解,本次案例没有固定的要求,对于案例的丰富性与准确性有了更深层次的要求.这次是我们小组第一次会议,主要完成的是明确本次案例的问题和初步的分工.
具体分工如下，关明亮邓文涛负责枚举法相关问题的解答，夏蕾，罗炜罡负责匈牙利法的相关讨论，周界村选择动态规划法及节约法进行处理，刘庚负责图论解答方法。
本人将解题资料发至组员邮箱，作为参考，方便解题。
并尝试用数学软件解题，初步计划使用LINGO和EXCEL进行求解。
并由我及时将大家的方案进行汇总，帮助大家解题。
第二次会议：
2010年6月6日下午16：
00
思东大厅
本次会议的内容是核对大家的最短路解题结果。
由于枚举法是最不易出错的，所以以枚举法的结果作为参照。
夏蕾组负责的匈牙利法解题正确，同时和我所负责的EXCEL解题结果一样，出现两条回路，经过人工调整得到最优解。
LINGO的解法正确。
大家针对6,7,8,9题提出自己思路答案，对于无法提出思路的问题再进行讨论，由于第七题和第六题想类似，所以我们将讨论的重点放在第八题和第九题上。
会议进行中，周界村和夏蕾同学针对邓文涛和关明亮枚举法发车的方式有不同见解，并提出散车运输成本会更低，运输过程和方式也更灵活化。
同时鼓励周界村对动态规划和节约法进行尝试建立模型。
第三次会议：
2010年6月8日晚22点
刘庚
在本次会议的最后组员对各题目都有了完整的思路并基本写出了题目的简要步骤，大家进行了核查修正了有遗漏的问
升级会员 