货郎担问题课件.ppt

《货郎担问题课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、货郎担问题小组成员：阿迪力刘帅马晓货郎担问题货郎担问题一般提法为：一个货郎从某城镇出发，经过若干个城镇一次，且仅经过一次，最后仍回到原出发的城镇，问应如何选择行走路线可使总行程最短，这是运筹学的一个著名的问题。实际中有很多问题可以归结为这类问题。哈密尔顿回路：（环球旅行问题）即从一个结点出发，经过所有结点回到出发点（结点不能重复经过）。问题描述：设v1，v2，……..，vn是已知的n个城镇，城镇vi到城镇vj的距离为dij，现求从v1出发，经各城镇一次且仅一次返回v1的最短路程。解决方案：1.穷举法？2.最短路标号法？3.指派问题？4.整数规划？5.动态规划？建立动态规

2、划模型：设S表示从v1到vi中间所可能经过的城市集合，S实际上是包含除v1和vi两个点之外的其余点的集合，但S中的点的个数要随阶段数改变。阶段：S中的点的个数状态变量（i，S）表示：从v1点出发，经过S集合中所有点一次最后到达vi。最优指标函数fk（i，S）为从v1出发，经过S集合中所有点一次最后到达vi。决策变量Pk（i，S）表示：从v1经k个中间城镇的S集合到vi城镇的最短路线上邻接vi的前一个城镇，则动态规划的顺序递推关系为：fk（i，S）=min{fk-1（j，S、{j}+dji}j属于Sf0（i，空集）=d1i（k=1，2，…,n-1,i=2,3,…n)例1

3、：已知4个城市间距离如下表，求从v1出发，经其余城市一次且仅一次最后返回v1的最短路径和距离。解：K=0由边界条件知:f0(2,空集)=d12=6f0(3,空集)=d13=7f0(4,空集)=d14=9当k=1时:从城市V1出发,经过1个城镇到达Vi的最短距离为:f1(2,{3})=f0(3,空)+d32=7+8=15f1(2,{4})=f0(4,空)+d42=9+8=14f1(3,{2})=f0(2,空)+d23=6+9=15f1(3,{4})=f0(4,空)+d43=9+5=14f1(4,{2})=f0(2,空)+d24=6+7=13f1(4,

4、{3})=f0(3,空)+d34=7+8=15当k=2时,从城市V1出发,中间经过2个城镇到达Vi的最短距离.f2(2,{3,4})=min[f1(3,{4})+d32,f1(4,{3})+d42]=min[14+8,15+5]=20P2(2,{3,4})=4f2(3,{2,4})=min[14+9,13+5]=18P2(3,{2,4})=4f2(4,{2,3})=min[15+7,15+8]=22P2(4,{2,3})=2当k=3时:从城市V1出发,中间经过3个城镇最终回到Vi的最短距离.f3(1,{2,3,4})=min[f2(2,{3,4})+d21,f2(3,

5、{2,4})+d31,f2(4,{2,3})+d41]=min[20+8,18+5,22+6]=23P3(1,{2,3,4})=3逆推回去,货郎的最短路线是12431,最短距离为23.货郎担问题当城市数目增加时,用动态规划方法求解,无论是计算量还是存储量都会大大增加,所以本方法只适用于n较小的情况.在很多货郎担问题中，经常会看到dij不等于dji的情况。这是因为：1，各城市之间可能是复线2，两地之间可能会使用不同的交通工具从而费用不同。实际中很多问题都可以归结为货郎担这类问题.如:1,物资运输路线中,汽车应该走怎样的路线使路程最短;2,工厂里在钢板上要

6、挖一些小圆孔,自动焊接机的割咀应走怎样的路线使路程最短;3,城市里有一些地方铺设管道时,管子应走怎样的路线才能使管子耗费最少,等等比如说，前面曾经遇到的排序问题，以前我们是用0-1整数规划来解决这类问题的。在这里，我们同样可以使用动态规划的方法。而且相对简单了很多。排序问题一，问题的提出:设有n个工件要在机床A,B上加工,每个工件都必须经过先A后B的两道加工工序,以ai,bi分别表示工件i(1<=i<=n)在A,B上的加工时间.问应如何在两机床上安排工件加工的顺序,使在机床A上加工第一个工件开始到在机床B上将最后一个工件加工完为止,所用的加工

7、时间最少?二,模型及其解法min(ai,bj)<=min(aj,bi)这个条件就是工件i应该排在工件j之前,即对于从头到尾的最优排序而言,它的所有前后相邻的两个工件所组成的对都必须满足以上不等式.根据这个条件,得到最优排序的规则如下:(1)先工作的加工的加工时间的工时矩阵M=a1a2…..anb1b2…..bn设有5个工件需要在机床A,B上加工,加工的顺序是先A后B,每个工件所需加工时间(单位:小时)如下表.问如何安排加工顺序可使机床连续加工完所有的加工总时间最少?以一个例题来加以说明(2)在工时矩阵M中找到最小的元素(若最小的不止一