包装物流系统优化方法

专业：包装工程包装物流技术第5章包装物流系统优化方法5.1概述5.2多段图问题5.3节约里程法5.4背包问题（货物配载问题）5.50/1背包问题5.6矩阵连乘积问题5.7凸多边形最优三角剖分物流系统规划所关注的问题是如何合理、有效地利用或配置各种资源（劳动力、材料、设备、资金），使实现预定目标所需的费用最小（或资源最少），或者所获得的收益最大。物流系统的规划一般都可以用优化模型来表达。其基本思想是在满足一定的约束条件下，使预定的目标值达到最优。物流系统规划的数学基础主要是运筹学理论，常用的方法包括线性规划、整数规划、动态规划等。5.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)表示这条路径的成本，根据向前处理方法有：边的成本例子中5段图的实现计算步骤：COST(4,9)=4COST(4,10)=2COST(4,11)=5123458761110912st97324227111118654356524V1V2V3V4V5COST(3,6)=min{6+COST(4,9),5+COST(4,10)}=7COST(3,7)=min{4+COST(4,9),3+COST(4,10)}=5COST(3,8)=min{5+COST(4,10),6+COST(4,11)}=7123458761110912st97324227111118654356524V1V2V3V4V5COST(2,2)=min{4+COST(3,6),2+COST(3,7),1+COST(3,8)}=7COST(2,3)=min{2+COST(3,6),7+COST(3,7)}=9COST(2,4)=min{11+COST(3,8)}=18COST(2,5)=min{11+COST(3,7),8+COST(3,8)}=15123458761110912st97324227111118654356524V1V2V3V4V5COST(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)=10 D(3,8)=10 D(2,2)=7D(2,3)=6 D(2,4)=8 D(2,5)=8 D(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）假如由桶一家配跃送中心楼(Di奋str弊ibu有te独Cen娱ter盾)向皮两个用摔户A、连B送货想，配送醋中心到圆两客户月的最短瓶距离分捷别是L贫1和L寇2，A常和B间迟的最短师距离为恒L12阿，A远、B者的货物乞需求量个分别是耻Q1和条Q2,疮且(亿Q1+厅Q2堪)小椅于运输巾装载量衡Q。图1芝节约法基练本原理示纠意图如果改精用一辆激车对两固客户进嚼行巡回傻送货,丘则只需玻一个车糠次,总恨路程为昼:如果配送诵中心分别季送货,那夏么需要两凑个车次,聚总路程为搁:ADCBL1L2L125.3颤节约免里程法（一）呜问题的作提出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+2校0≤70二者不披能在与桐其他客散户共线，在上表帜中去掉与右3、4相呼关的路径（2）选砍择下一条浅节约里程驶的路径5-640+牢60≥70二者不访能共线（3）治选择下伪一条节很约里程地的路径1-230+个40≤翠70二者不能驰在与其他享客户共线，在上表坐中去掉与赛1、2相图关的路径（4）惹无可选婶的节约椅里程路肃径，客户5、孤6只能单遥独送货。总路径晚：DC童—3—稿4—D防CDC—1叉—2—D谱CDC—5决—DCDC—6伪—DC总路程：师7+3+芹8=185+6+瓦6=176+6烛=125+5=野10节约里昂程：1完2500序号路径节约里程序号路径节约里程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种物品可贷供他选择值装入包中祝。已知每条种物品的服重量及使婆用价值（源作用），絮问此人应责如何选择忌携带的物折品（各几滤件），使盯所起作用授（使用价形值）最大投？物品12…j…n重量（公斤/件）a1a2…

aj…

an每件使用价值c1c2…cj…

cn这就是背锈包问题。姨类似的还喝有工厂里翼的下料问唤题、运输堂中的货物晨装载问题时、包装箱扑内货物码岔放等。5.4女背包圾问题（泉货物配缺载问题崇）设xj为第j种物品尺的装件乡丰数（非瞒负整数挽）则问杜题的数似学模型浊如下：用动态规您划方法求陷解，令fk(y)=总重迟量不超过y公斤，包宫中只装有销前k种物品步时的最佣大使用盆价值。其中y≥0，k＝1,2,…,n。所以问题醉就是求fn(a)其递推关壳系式为：当k=1庆时，有舞：例题：求茫下面背包国问题的最舞优解物品123重量（斤）325使用价值8512解：a＝5养，问题沿是求f3(5)所以，最看优解为X＝（1肺.1秩.游0），最优值为Z=13名。5.5莲0/1潮背包问题给定n种物品和消一个背包责，物品i的重量是wi，其价值蒸为vi，背包扁的容量背为C。背包敢问题是集如何选棋择装入到背包的浊物品，辣使得装扛入背包染中物品遭的总价冲值最大惭?如果府在选择闷装入背腾包的物均品时，轿对每种朗物品i只有两种仓选择：装普入背包或杯不装入背丝式包，即不刑能将物品i装入背包巡寿多次，也沾不能只装掌入物品i的一部分浆，则称为翁0/1背宅包问题。在0/1起背包问题耍中，物品i或者被拒装入背击包，或历者不被球装入背璃包，设xi表示物品i装入背不包的情乖况，则泡当xi=0时哥，表示织物品i没有被改装入背蜓包，xi=1时，丈表示物品i被装入背薪包。根据谋问题的要湖求，有如叮下约束条码件和目标择函数：问题归变结为寻递找一个骂满足约达束条件累，并使饭目标函钻数达到贩最大的江解向量X=(x1,x2,…,xn)。首先证明0/1背包问题满足最优性原理。设(x1,x2,…,xn)是所给0/1背包问题的一个最优解，则(x2,…,xn)是下面一个子问题的最优解：如若不然，设(y2,…,yn)是上述子问题的一个最优解，则，且。同时，，这说明(x1,y2,…,yn)是所给0/1背包问题比(x1,x2,…,xn)更优的解，从而导致矛盾。0/1井背包问钩题可以潮看作是浸决策一悔个序列故(x1,x2,…班,xn)，对蜡任一变脱量xi的决策是缸决定xi=1还抛是xi=0。赔在对xi-1决策后，灿已确定了害(x1,…,活xi-1)，在概决策xi时，问么题处于鸣下列两跨种状态焰之一：a.背包槽容量不足根以装入物暑品i，则叙xi=0，背蒜包不增加益价值；b.背包型容量可以晃装入物品至i，则xi=1，背鉴包的价值椅增加了vi。这两种退情况下造背包价暂值的最椅大者应档该是对xi决策后全的背包毕价值。舍令V(i,j)表示在义前i(1≤i≤n)个物品舌中能够装宽入容量为j（0≤j≤C）的背录包中的并物品的总最大值心，则可举以得到仁如下动蛾态规划躺函数：V(i,0)阵=V(0,j)=0钉（述1）表明：稼把前面妻i个物会品装入尚容量为扯0的背刻包和把至0个物忧品装入蝴容量为掘j的背搂包，得丝式到的价煤值均为腾0。第一个阁式子表苹明：如拒果第i菜个物品投的重量沉大于背胆包的容芬量，则里装入前持i个物败品得到按的最大美价值和味装入前挣i-1另个物品算得到的掀最大价晕值是相府同的，镇即物品慨i不能卫装入背炕包；第家二个式跌子表明妙：如果倍第i个纸物品的廊重量小即于背包抵的容量狗，则会盲有以下佩两种情骆况：（屋1）如浊果把第夹i个物宪品装入蛋背包，拒则背包级中物品食的价值耽等于把队前i-友1个物院品装入茄容量为清j-wi的背包分中的价幅值加上戴第i个练物品的烛价值vi；（2）茶如果第i演个物品没当有装入背沟包，则背监包中物品碍的价值就刘等于把前惰i-1个鸣物品装入歇容量为j解的背包中摸所取得的计价值。显拿然，取二瓶者中价值指较大者作敢为把前i本个物品装扔入容量为坡j的背包饮中的最优播解。第一阶段，只装入拜前1个物盾品，确定阅在各种情烈况下的背更包能够得呀到的最大草价值；第二阶灿段，只装入敢前2个物怒品，确定羞在各种情息况下的背依包能够得饶到的最大慌价值；依尤此类推，甩直到第n个阶段。最后，V(n,C)便是在扮容量为C的背包慕中装入n个物品美时取得裂的最大安价值。息为了确白定装入遵背包的和具体物鼓品，从V(n,C)的值向裹前推，如微果V(n,C)>V(n-1,C)，表明粗第n个物品鲁被装入啦背包，旨前n-1个览物品被观装入容羽量为C-wn的背包中格；否则，箩第n个物品没冬有被装入仅背包，前