销售运输最优问题及其模型.doc

销售运输最优问题及其模型 简 介 随着科技的发展 ,数学模型已广泛应用到社会生活的各个领域。随着经济的发展，道路交通运输成为了世界各国经济贸易的重要环节之一。因此，如何确定一条运输成本最低的路线，使商家获得最大利润变得尤为重要。本题就是关于销售运输最优方案的确立问题，在运输总量不变的情况下，考虑各路线运输成本的高低。在假设无分散运输的情况下，我们建立了动态规划模型，分阶段讨论运输的最优解，得出总路线的最优解，从而解决了求最短运输费用问题 ,这一模型具有广泛的实际意义。关键字：动态规划，分阶段，最少运费（1） 问题重述1、 概述 在日常生活中，我们经常遇到求最短路径或者最少运费路径的问题。其中主要考虑的就是运输成本的问题，在运输货物数量一定的条件下，综合考虑各方面因素，从而得出最佳运输方案，使运费成本最少，以保证商品产家获得最大利润。2、 解决的问题如图所示，弧上的数字为相邻两节点间的单位运费，现将总量为Q的某种产品从产地一运往销售地七，求总运费最少的运输方案。 15 20 12 8 9 10 10 14 8 12 13 （2） 问题分析由题干可知，从产地一运出的货物总量是一定的，若不考虑分散运输，则问题转化为求最短运输路径的问题，这样可以将问题简化求解。我们可将整个过程分为三个阶段，运往或为第一阶段，运往或以及运往或为第二个阶段，剩下的运输路径为第三阶段，通过比较每一阶段的子问题即最少运输费用，来得出总的路线所需的最少运输费用。 （四）模型假设 1、运输过程中不考虑分散运输类型； 2、任意相邻两点间的运输路径相等； 3、不考虑运输时间对运输成本的影响； 4、两点间货物的单位运费表示它们之间的距离。（五）模型建立与求解一、问题的分析 我们把整个过程划分3个阶段,用 K表示, K = 1 ,2 ,3 K = 1 (第一阶段) :从一级结点 结点到二级结点( ,) ;K= 2 (第二阶段) :从二级结点( ,)到三级结点( ，,) ;K= 3 (第三阶段) :从三级结点(，,)到终级结点，其中包括从4到5,5到6的路径。 从一个路径的每一结点到达下一路径的那个结点,是由阶段初的地点、 阶段未的地点所确定,图中用结点间的连线表示,再将本阶段的两地点间所需的单位运费作为两结点间的距离,标在结点间的连线上,这样就转化为求解决从地点1经地点B（2,3）、地点C（4，5，6） 至终点7的最少运输费问题就转化为寻找从一级结点至终级结点的一条最短路径问题。 求最短路径问题有两种解法:顺序递推法和逆序递推法。顺序递推法即从前向后求解,逆序递推法即从后向前求解。因为从至的最短路径与从至的最短路径相同,所以两种解法的结果是唯一确定的;并且若某一路径为最短路径,则它的任一子路径也必为最短路径。2、 模型的建立 建立相应动态规划模型来求解运输过程中的最短路径。将图形转化为： B1 15 C1 20 12 8 9 10 C2 10 14 B2 8 12 13 C3 第一阶段 第二阶段 第三阶段 阶段变量用k表示；阶段指标表示k阶段与所选择的路段相应的路长；指标函数=表示k至三阶的总路长。表示第k阶段点到终点的运输成本；递推公式=min+，k=3，2，1；每两个点间距离是一定的,用d ( i , j)表示,且 d ( i , j) = d ( j , i) 。 K = 1时,考虑第一个阶段。第一阶段的最短路程记作 ( Bi) ，i = 1,2 ,则 = 20 , = 14。 K = 2时,联合考虑前两个阶段。第一阶段、 第二阶段至Bi（2,3）结点的最短路程之和记为 ，其中i= 1 ,2,3。f 2 (C1) = min d (B1 ,C1) + f 1 (B1) ,d(B2 , C1 +f1 ( B2) = min20+15 ,14+ 10 =24 ,即从结点至 C1 结点最短路径为 B1C1, 从 结点至 C2 结点仅有一条路径 B1 C2，f 2 ( C2) =d(B1,C2)+f1( B1) =20+12=32。从结点至C2仅有B2C2一条路径，则f2(C3)=d(B2,C3)+f1(B2)=27. K = 3时,联合考虑前三个阶段。前三个阶段至结点的最短路程记作f 3（）。由图可知，从c1到有两段路径，即直接从c1至或从c1至c2后再至,通过比较可以看出前者更加节约运输成本，即运输路线为c1直接运往。同理可得，从c2直接运往为最优方案。则f3()=mind(c1,)+f2(c1),d(c2,)+f2(c2),d(c3,)+f2(c3)=min9+24,10+34,12+27=33。综合以上三阶段可得，最短路线为B2C1，即为，总运输费用最少f=f3=33。 （六）分析与讨论 动态规划模型具有静态规划模型无法比拟的优越性。如能得到全局最优方案;可以得到一组最优解;在计算时,可以利用实际知识和个人经验提高求解效率。但是它也具有一些缺点,如没有统一的标准模型;用数值方法求解时存在维数灾等。在上述问题中，我们假设了货物不可以分散运输，如果考虑这点，则问题将变得更为复杂，模型的建立也并不简单。（3） 模型的推广 本文将动态规划思想运用到求解运输问题最短路径中，其优点在于思路清晰，方法简便，理论可靠，在实际运用中取得了良好的效果。但是本文只考虑了一个发货中心的应用实例，在实际中有可能存在多个发货中心的情况，因此我们可以考虑将其进行改进或者结合启发式算法，使之更好的运用在实际中。 （八） 附录参考文献：1姜启源,等1数学模型M1北京:高等教育出版社,20032谬慧芬，邵小兵动态规划算法的原理及应用J中国科技信息，20053/view/bbe58748e45c3b3567ec8b89.html?from=rec&pos=0&weight=4&lastweight=3&count=5 杜彦娟，利用动态规划数学模型求最短路径，2011.11.12 源程序：a=0,20,14,inf,inf,inf,inf 20,0,inf,15,12,inf,inf 14,inf,0,10,inf,13,inf inf,15,10,0,8,8,9 inf,12,inf,8,0,8,10 inf,inf,13,inf,8,0,12 inf,inf,inf,inf,9,10,12;n=size(a,1);D=a;path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end; end;end;for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=