包装物流系统优化方法340.pptx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《包装物流系统优化方法340.pptx》由会员分享,可在线阅读,更多相关《包装物流系统优化方法340.pptx(53页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、 专 业:包装工程 E-mail:包装物流技术第第5 5章章 包装物流系统优化方法包装物流系统优化方法5.1 5.1 概述概述5.2 5.2 多段图问题多段图问题5.3 5.3 节约里程法节约里程法5.4 5.4 背包问题(货物配载问题)背包问题(货物配载问题)5.5 0/15.5 0/1背包问题背包问题5.6 5.6 矩阵连乘积问题矩阵连乘积问题5.7 5.7 凸多边形最优三角剖分凸多边形最优三角剖分物流系统规划所关注的问题是如何合理、有效地利用或配置各种资源物流系统规划所关注的问题是如何合理、有效地利用或配置各种资源(劳动力、材料、设备、资金),使实现预定目标所需的费用最小(劳动力、材料、
2、设备、资金),使实现预定目标所需的费用最小(或资源最少),或者所获得的收益最大。(或资源最少),或者所获得的收益最大。物流系统的规划一般都可以用物流系统的规划一般都可以用优化模型优化模型来表达。其基本思想是在满足来表达。其基本思想是在满足一定的约束条件下,使预定的目标值达到最优。一定的约束条件下,使预定的目标值达到最优。物流系统规划的数学基础主要是运筹学理论,常用的方法包括线性规物流系统规划的数学基础主要是运筹学理论,常用的方法包括线性规划、整数规划、动态规划等。划、整数规划、动态规划等。5.1 5.1 概述概述多阶段决策问题多阶段决策问题:求解的问题可以划分为一系列相互联系的阶段,在:求解的
3、问题可以划分为一系列相互联系的阶段,在每个阶段都需要做出决策,且一个阶段决策的选择会影响下一个阶段每个阶段都需要做出决策,且一个阶段决策的选择会影响下一个阶段的决策,从而影响整个过程的活动路线,求解的目标是选择各个阶段的决策,从而影响整个过程的活动路线,求解的目标是选择各个阶段的决策是整个过程达到最优。的决策是整个过程达到最优。如图所示,对于中间的任意一段,例如如图所示,对于中间的任意一段,例如第第k k+1+1段段作出相应的作出相应的“决策决策”(或控制或控制)u uk k后,才能确定该段后,才能确定该段输入状态输入状态与与输出状态输出状态间的关系,即从间的关系,即从x xk k变化变化到到
4、x xk k+1+1的状态转移规律。在选择好每一段的的状态转移规律。在选择好每一段的“决策决策”(”(或控制或控制)u uk k以后,那以后,那么整个过程的状态转移规律从么整个过程的状态转移规律从x x0 0经经x xk k一直到一直到x xN N也就被完全确定。全部也就被完全确定。全部“决决策策”的总体,称为的总体,称为“策略策略”。Dynamic ProgrammingDynamic Programming动态规划动态规划 动态最优的核心是动态最优的核心是最优性原理最优性原理。它首先将一个多阶段决策问题转。它首先将一个多阶段决策问题转化为一系列单阶段决策问题,然后从最后一段状态开始逆向递推
5、到初化为一系列单阶段决策问题,然后从最后一段状态开始逆向递推到初始段状态为止的一套求解最优策略的完整方法。始段状态为止的一套求解最优策略的完整方法。最优性原理:最优性原理:一个过程的最优策略具有这样的性质,即无论其初始状态及其初一个过程的最优策略具有这样的性质,即无论其初始状态及其初始决策如何,其以后诸决策对以第一个决策所形成的状态作为初始状态始决策如何,其以后诸决策对以第一个决策所形成的状态作为初始状态而言,必须构成最优策略。而言,必须构成最优策略。B BA AC CI II IIIIIIIII动态规划算法的依据是最优化原理动态规划算法的依据是最优化原理(最优子结构性质最优子结构性质)一个最
6、优化策略具有这样的性质,不论过去的状态和决策如何,余下一个最优化策略具有这样的性质,不论过去的状态和决策如何,余下的决策必须相对于前一决策所产生的状态构成最优决策序列。简言之,一的决策必须相对于前一决策所产生的状态构成最优决策序列。简言之,一个最优化策略的子策略总是最优的,问题的最优解可以通过其子问题的最个最优化策略的子策略总是最优的,问题的最优解可以通过其子问题的最优解构成。优解构成。无后效性:无后效性:在多段决策过程中,每一段在多段决策过程中,每一段(如第如第k k+1+1段段)的输出状态的输出状态(x xk k+1+1)都都仅仅与该段的决策仅仅与该段的决策(u uk k)及该段的初始状态
7、及该段的初始状态(x xk k)有关;而与其前面各段的有关;而与其前面各段的决策及状态的转移规律无关。决策及状态的转移规律无关。(1)划分阶段)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。按照问题的时间或空间特征,把问题分为若干个阶段。(2)选择状态)选择状态:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。(3)确定决策并写出状态转移方程)确定决策并写出状态转移方程:状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。(4)写出规划方程(包
8、括边界条件)写出规划方程(包括边界条件):动态规划的基本方程是规划方程的通用形式化表达式。动态规划的基本方程是规划方程的通用形式化表达式。动态规划算法的基本步骤动态规划算法的基本步骤常见的动态规划问题常见的动态规划问题(1 1)多段图问题(配送路径优化问题)多段图问题(配送路径优化问题)(2 2)节约里程问题(配送路径优化问题)节约里程问题(配送路径优化问题)(3 3)背包问题(货物配装、装箱问题)背包问题(货物配装、装箱问题)(4 4)矩阵连乘积问题)矩阵连乘积问题(5 5)数字三角形问题)数字三角形问题(6 6)最长不下降子序列)最长不下降子序列(7 7)最长公共子序列)最长公共子序列(8
9、 8)最大子段和)最大子段和(9 9)多边形游戏)多边形游戏(1010)资源分配问题)资源分配问题.5.2 多段图问题多段图问题123458761110912st97324227111118654356524V1V2V3V4V5多段图多段图G G(V,E)(V,E)是是个有向图。个有向图。它具有如下特性:它具有如下特性:图中的结点被划分成图中的结点被划分成k2k2个不相交的集合个不相交的集合V Vi i,1ik,1ik,其中其中V V1 1和和V Vk k分别分别只有一个结点只有一个结点s(s(源点源点)和和 t(t(汇点汇点)。图中所有的边图中所有的边均具有如下性质:若均具有如下性质:若uV
10、i uVi,则,则v Vv Vi+1i+1 ,1ik,1ik,且每条边且每条边均附有成本均附有成本c(u,v)c(u,v)。从从s s到到t t的一条路径成本是这条路径上边的成本和。的一条路径成本是这条路径上边的成本和。多段图问题多段图问题(multistage graph problem)(multistage graph problem)是求由是求由s s到到t t的最小成本路径。的最小成本路径。证明最优化原理对多段图成立:证明最优化原理对多段图成立:假设假设s,vs,v2 2,v,v3 3,v,vk-1k-1,t,t是一条由是一条由s s到到t t的最短路径的最短路径再假设从源点再假设从
11、源点s s开始,已作出了到结点开始,已作出了到结点v v2 2的决策,因此的决策,因此v v2 2就是初始决策就是初始决策所产生的状态所产生的状态如果把如果把v v2 2看成是原问题的一个子问题的初始状态,解决这个子问题就看成是原问题的一个子问题的初始状态,解决这个子问题就是找出一条由是找出一条由v v2 2到到t t的最短路径的最短路径这条最短路径显然是这条最短路径显然是v v2 2,v,v3 3,v,vk-1k-1,t,t如果不是,设如果不是,设v v2 2,q,q3 3,q,qk-1k-1,t,t由由v v2 2到到t t的一条更短路径,则的一条更短路径,则s,vs,v2 2,q,q3
12、3,q,qk-1k-1,t,t是一条比路径是一条比路径s,vs,v2 2,v,v3 3,v,vk-1k-1,t,t更短的由更短的由s s到到t t的路的路径。这与假设矛盾,因此最优性原理成立。径。这与假设矛盾,因此最优性原理成立。(一)多段图问题的最优化原理证明(一)多段图问题的最优化原理证明(二)求解多段图问题的动态规划算法(二)求解多段图问题的动态规划算法(1 1)递推公式法(多段图)递推公式法(多段图向前处理向前处理的算法)的算法)设设P(i,j)P(i,j)是一条从是一条从V Vi i中的节点中的节点j j到汇点到汇点t t的最小成本路径的最小成本路径,COST(i,j)COST(i,
13、j)表示这条路径的成本,根据表示这条路径的成本,根据向前处理向前处理方法有:方法有:边的成本边的成本例子中例子中5 5段图的实现计算步骤:段图的实现计算步骤:COST(4,9)=4COST(4,9)=4COST(4,10)=2COST(4,10)=2COST(4,11)=5COST(4,11)=5123458761110912st97324227111118654356524V1V2V3V4V5COST(3,6)=min6+COST(4,9),COST(3,6)=min6+COST(4,9),5+COST(4,10)5+COST(4,10)=7=7COST(3,7)=min4+COST(4,9
14、),COST(3,7)=min4+COST(4,9),3+COST(4,10)3+COST(4,10)=5=5COST(3,8)=minCOST(3,8)=min5+COST(4,10)5+COST(4,10),6+COST(4,11)=7,6+COST(4,11)=7123458761110912st97324227111118654356524V1V2V3V4V5COST(2,2)=min4+COST(3,6),COST(2,2)=min4+COST(3,6),2+COST(3,7)2+COST(3,7),1+COST(3,8)=7,1+COST(3,8)=7COST(2,3)=minCO
15、ST(2,3)=min2+COST(3,6)2+COST(3,6),7+COST(3,7)=9,7+COST(3,7)=9COST(2,4)=minCOST(2,4)=min11+COST(3,8)11+COST(3,8)=18=18COST(2,5)=min11+COST(3,7),COST(2,5)=min11+COST(3,7),8+COST(3,8)8+COST(3,8)=15=15123458761110912st97324227111118654356524V1V2V3V4V5COST(1,1)=minCOST(1,1)=min9+COST(2,2)9+COST(2,2),7+CO
16、ST(2,3)7+COST(2,3),3+COST(2,4),2+COST(2,5)=16,3+COST(2,4),2+COST(2,5)=161 12 23 34 45 58 87 76 6111110109 91212s st t97324227111118654356524V V1 1V V2 2V V3 3V V4 4V V5 5例子中例子中5 5段图的计算步骤:段图的计算步骤:在计算每一个在计算每一个COST(i,j)COST(i,j)的同时,记下每个状态的同时,记下每个状态(结点结点j)j)所做出的决所做出的决策(即,策(即,使使 c(j,l)+cost(i+1,l)c(j,l)+
17、cost(i+1,l)取最小值的取最小值的l l值值),设它为),设它为D(i,j)D(i,j),则可容易地求出这条最小成本路径。,则可容易地求出这条最小成本路径。D(3,6)=10 D(3,7)=10D(3,6)=10 D(3,7)=10D(3,8)=10D(3,8)=10D(2,2)=7D(2,2)=7D(2,3)=6D(2,3)=6 D(2,4)=8 D(2,4)=8D(2,5)=8D(2,5)=8D(1,1)=2D(1,1)=2123458761110912st97324227111118654356524V1V2V3V4V5设这条最小成本路径是设这条最小成本路径是s sl,vl,v2
18、 2,v,v3 3,v,vk-1k-1,t=12,t=12。则可得知:。则可得知:v v2 2D(1,1)D(1,1)2 2,v v3 3=D(2,D(1,1)=D(2,2)=7=D(2,D(1,1)=D(2,2)=7 和和 v v4 4D(3,D(2,D(1,1)D(3,D(2,D(1,1)D(3,D(2,2)=D(3,7)D(3,D(2,2)=D(3,7)1010所以最短路径的结点序列为:所以最短路径的结点序列为:s-2-7-10-ts-2-7-10-t 。123458761110912st97324227111118654356524V1V2V3V4V5123458761110912st
19、97324227111118654356524V1V2V3V4V542575791815716(2)图上作业法)图上作业法1 1)逆向法()逆向法(12-12-1 1)123458761110912st97324227111118654356524V1V2V3V4V5151416911107329162 2)正向法()正向法(1-121-12)假如由一家配送中心假如由一家配送中心(Distribute Center)(Distribute Center)向两个用户向两个用户A A、B B送货,配送货,配送中心到两客户的最短距离分别是送中心到两客户的最短距离分别是L1L1和和L2L2,A A和和
20、B B间的最短距离为间的最短距离为L12L12,A A、B B 的货物需求量分别是的货物需求量分别是Q1Q1和和Q2,Q2,且且(Q1+Q2)(Q1+Q2)小于运输装载量小于运输装载量Q Q。图图1 1 节约法基本原理示意图节约法基本原理示意图如果改用一辆车对两客户进行巡回送如果改用一辆车对两客户进行巡回送货货,则只需一个车次则只需一个车次,总路程为总路程为:如果配送中心分别送货如果配送中心分别送货,那么需要两那么需要两个车次个车次,总路程为总路程为:A ADCDCB BL1L1L2L2L12L125.3 5.3 节约里程法节约里程法(一)问题的提出(一)问题的提出A ADCDCB BL L1
21、 1L LX XL L1212X X节约法基本原理示意图节约法基本原理示意图利用里程节约法确定配送路线的主要出发点有:利用里程节约法确定配送路线的主要出发点有:(1 1)配送方的运输能力)配送方的运输能力(2 2)配送方与客户之间的距离和各客户之间的相对距离)配送方与客户之间的距离和各客户之间的相对距离(3 3)制定使配送车辆总的周转量达到或接近最小的配送方案)制定使配送车辆总的周转量达到或接近最小的配送方案 DC45612361079653861130604050204056873131286 6用户用户3030需求量需求量1010两点之间距离的距离两点之间距离的距离 利用节约里程法求出最优
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 包装 物流 系统 优化 方法 340
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内