包装物流系统优化方法

专业：包装工程E-mail:[e-mail]包装物流技术第5章包装物流系统优化方法5.1概述5.2多段图问题5.3节约里程法5.4背包问题（货物配载问题）5.50/1背包问题5.6矩阵连乘积问题5.7凸多边形最优三角剖分•物流系统规划所关注的问题是如何合理、有效地利用或配置各种资源（劳动力、材料、设备、资金），使实现预定目标所需的费用最小（或资源最少），或者所获得的收益最大。•物流系统的规划一般都可以用优化模型来表达。其基本思想是在满足一定的约束条件下，使预定的目标值达到最优。•物流系统规划的数学基础主要是运筹学理论，常用的方法包括线性规划、整数规划、动态规划等。5.1概述多阶段决策问题：求解的问题可以划分为一系列相互联系的阶段，在每个阶段都需要做出决策，且一个阶段决策的选择会影响下一个阶段的决策，从而影响整个过程的活动路线，求解的目标是选择各个阶段的决策是整个过程达到最优。12k+1Nx0x1x2xkxk+1xN-1xNu0u1ukuN-1如图所示，对于中间的任意一段，例如第k+1段作出相应的“决策”(或控制)uk后，才能确定该段输入状态与输出状态间的关系，即从xk变化到xk+1的状态转移规律。在选择好每一段的“决策”(或控制)uk以后，那么整个过程的状态转移规律从x0经xk一直到xN也就被完全确定。全部“决策”的总体，称为“策略”。DynamicProgramming动态规划动态最优的核心是最优性原理。它首先将一个多阶段决策问题转化为一系列单阶段决策问题，然后从最后一段状态开始逆向递推到初始段状态为止的一套求解最优策略的完整方法。最优性原理：一个过程的最优策略具有这样的性质，即无论其初始状态及其初始决策如何，其以后诸决策对以第一个决策所形成的状态作为初始状态而言，必须构成最优策略。BACII’IIII’动态规划算法的依据是最优化原理(最优子结构性质)一个最优化策略具有这样的性质，不论过去的状态和决策如何，余下的决策必须相对于前一决策所产生的状态构成最优决策序列。简言之，一个最优化策略的子策略总是最优的，问题的最优解可以通过其子问题的最优解构成。无后效性：在多段决策过程中，每一段(如第k+1段)的输出状态(xk+1)都仅仅与该段的决策(uk)及该段的初始状态(xk)有关；而与其前面各段的决策及状态的转移规律无关。（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。（2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。（3）确定决策并写出状态转移方程：状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。（4）写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。动态规划算法的基本步骤常见的动态规划问题（1）多段图问题（配送路径优化问题）（2）节约里程问题（配送路径优化问题）（3）背包问题（货物配装、装箱问题）（4）矩阵连乘积问题（5）数字三角形问题（6）最长不下降子序列（7）最长公共子序列（8）最大子段和（9）多边形游戏（10）资源分配问题……….5.2多段图问题123458761110912st97324227111118654356524V1V2V3V4V5•多段图G＝(V,E)是—个有向图。•它具有如下特性：–图中的结点被划分成k≥2个不相交的集合Vi,1≤i≤k,其中V1和Vk分别只有一个结点s(源点)和t(汇点)。–图中所有的边u,v均具有如下性质：若u∈Vi，则v∈Vi+1,1≤i≤k,且每条边u,v均附有成本c(u,v)。–从s到t的一条路径成本是这条路径上边的成本和。–多段图问题(multistagegraphproblem)是求由s到t的最小成本路径。•证明最优化原理对多段图成立：–假设s,v2,v3,…,vk-1,t是一条由s到t的最短路径–再假设从源点s开始，已作出了到结点v2的决策，因此v2就是初始决策所产生的状态–如果把v2看成是原问题的一个子问题的初始状态，解决这个子问题就是找出一条由v2到t的最短路径–这条最短路径显然是v2,v3,…,vk-1,t–如果不是，设v2,q3,…,qk-1,t由v2到t的一条更短路径，则s,v2,q3,…,qk-1,t是一条比路径s,v2,v3,…,vk-1,t更短的由s到t的路径。这与假设矛盾，因此最优性原理成立。（一）多段图问题的最优化原理证明（二）求解多段图问题的动态规划算法（1）递推公式法（多段图向前处理的算法）设P(i,j)是一条从Vi中的节点j到汇点t的最小成本路径，COST(i,j)表示这条路径的成本，根据向前处理方法有：)},1(),({min)ji,(,1liCOSTljcCOSTEljVli边的成本例子中5段图的实现计算步骤：•COST(4,9)=4•COST(4,10)=2•COST(4,11)=5123458761110912st97324227111118654356524V1V2V3V4V5COST(3,6)=min{6+COST(4,9),5+COST(4,10)}=7COST(3,7)=min{4+COST(4,9),3+COST(4,10)}=5COST(3,8)=min{5+COST(4,10),6+COST(4,11)}=7123458761110912st97324227111118654356524V1V2V3V4V5COST(2,2)=min{4+COST(3,6),2+COST(3,7),1+COST(3,8)}=7COST(2,3)=min{2+COST(3,6),7+COST(3,7)}=9COST(2,4)=min{11+COST(3,8)}=18COST(2,5)=min{11+COST(3,7),8+COST(3,8)}=15123458761110912st97324227111118654356524V1V2V3V4V5COST(1,1)=min{9+COST(2,2),7+COST(2,3),3+COST(2,4),2+COST(2,5)}=16123458761110912st97324227111118654356524V1V2V3V4V5•例子中5段图的计算步骤：–在计算每一个COST(i,j)的同时，记下每个状态(结点j)所做出的决策（即，使c(j,l)+cost(i+1,l)取最小值的l值），设它为D(i,j)，则可容易地求出这条最小成本路径。–D(3,6)=10D(3,7)=10D(3,8)=10D(2,2)=7–D(2,3)=6D(2,4)=8D(2,5)=8D(1,1)=2123458761110912st97324227111118654356524V1V2V3V4V5–设这条最小成本路径是s＝l,v2,v3,…,vk-1,t=12。则可得知：–v2＝D(1,1)＝2，v3=D(2,D(1,1))=D(2,2)=7和v4＝D(3,D(2,D(1,1)))＝D(3,D(2,2))=D(3,7)＝10所以最短路径的结点序列为：s-2-7-10-t。123458761110912st97324227111118654356524V1V2V3V4V5123458761110912st97324227111118654356524V1V2V3V4V542575791815716（2）图上作业法1）逆向法（12----1）123458761110912st97324227111118654356524V1V2V3V4V5151416911107329162）正向法（1-----12）假如由一家配送中心(DistributeCenter)向两个用户A、B送货，配送中心到两客户的最短距离分别是L1和L2，A和B间的最短距离为L12，A、B的货物需求量分别是Q1和Q2,且(Q1+Q2)小于运输装载量Q。图1节约法基本原理示意图如果改用一辆车对两客户进行巡回送货,则只需一个车次,总路程为:如果配送中心分别送货,那么需要两个车次,总路程为:ADCBL1L2L12212LLL（）1122LLLL5.3节约里程法（一）问题的提出12-12LLLLADCBL1LXL12X节约法基本原理示意图利用里程节约法确定配送路线的主要出发点有：（1）配送方的运输能力（2）配送方与客户之间的距离和各客户之间的相对距离（3）制定使配送车辆总的周转量达到或接近最小的配送方案DC45612361079653861130604050204056873131286用户30需求量10两点之间距离的距离利用节约里程法求出最优配送路线，假设配送中心的车辆运力足够，每辆车的载重极限为70t。（3）具体问题第一步计算配送中心到客户间的最短距离,画出距离表序号DC123456150266037107048—1130569—12806566—1330Q304050204060第二步，根据最短距离表，利用节约法计算出用户间的节约里程,并由大到小排列,编制节约里程顺序表序号DC123456150266037107048—1130569—12806566—1330Q304050204060序号DC12345615026503726048—3120562—1606545—080Q304050204060第二步，根据最短距离表，利用节约法计算出用户间的节约里程,并由大到小排列,编制节约里程顺序表节约里程顺序表序号路径节约里程序号路径节约里程13-41291-5225-68101-3232-36113-5144-56124-6051-251-462-652-571-643-682-43第三步根据节约里程顺序表和配送中心的约束条件，绘制配送路线。（1）选择最节约里程的路径3-4约束条件50+20≤70二者不能在与其他客户共线，在上表中去掉与3、4相关的路径（2）选择下一条节约里程的路径5-640+60≥70二者不能共线（3）选择下一条节约里程的路径1-230+40≤70二者不能在与其他客户共线，在上表中去掉与1、2相关的路径（4）无可选的节约里程路径，客户5、6只能单独送货。总路径：DC—3—4—DCDC—1—2—DCDC—5—DCDC—6—DC总路程：7+3+8=185+6+6=176+6=125+5=10节约里程：12500序号路径节约里程序号路径节约里程13~41291~5225-68101~3232~36113~5144~56124~6051~251~462~652~571~643~682~43第三步根据节约里程顺序表和配送中心的约束条件，绘制配送路线。（1）选择最节约里程的路径3-4约束条件12050+20≤120二者还能在与其他客户共线，在上表中寻找与3、4相关的路径选择下一条节约里程的路径2-350+20+40≤120（2）选择下一条节约里程的路径5-640+60≤120二者不能在与其他客户共线，在上表中去掉与5、6相关的路径（4）无可选的节约里程路径，客户1只能单独送货。总路径：DC—2—3—4—DCDC—5—6—DCDC—1—DC总路程：6+7+3+8=246+3+5=145+5=10节约里程：1880不能在与其他客户共线，在上表中去掉与2、3、4相关的路径序号路径节约里程序号路径节约里程13~41291~5225-68101~3232~36113~5144~56124~6051~251~462~652~571~643~682~43节约法的缺点（1）利用节约法选择配送路线过于强调节约路程，而没考虑行程中的时间因素,在许多情况下，时间更能决定物流配送的成本与服务质量；（2）利用节约法选择配送路线不能对客户的需求进行灵活多变的处理。客户的需求倾向于个性化，小批量、多品种、多批次，而节约法更适合需求稳定或是需求的时间不紧迫,这显然不能满足现代多变得市场环境。（3）节约法计算的配送路线并不一定是总路程最短。有一个徒步旅行者，其可携带物品重量的限度为a公斤，设有n种物品可供他选择装入包中。已知每种