《包装物流系统优化方法.pptVIP

包装物流技术 专 业：包装工程 E-mail: fygpack@126.com 物流系统规划所关注的问题是如何合理、有效地利用或配置各种资源（劳动力、材料、设备、资金），使实现预定目标所需的费用最小（或资源最少），或者所获得的收益最大。 物流系统的规划一般都可以用优化模型来表达。其基本思想是在满足一定的约束条件下，使预定的目标值达到最优。 物流系统规划的数学基础主要是运筹学理论，常用的方法包括线性规划、整数规划、动态规划等。 5.2 多段图问题 多段图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的一条路径成本是这条路径上边的成本和。 多段图问题(multistage graph problem)是求由s到t的最小成本路径。 （二）求解多段图问题的动态规划算法 （1）递推公式法（多段图向前处理的算法） 设P(i, j)是一条从Vi中的节点j到汇点t的最小成本路径，COST(i,j)表示这条路径的成本，根据向前处理方法有： 例子中5段图的计算步骤： 在计算每一个COST(i,j)的同时，记下每个状态(结点j)所做出的决策（即，使 c(j,l)+cost(i+1,l)取最小值的l值），设它为D(i, j)，则可容易地求出这条最小成本路径。 D(3,6)=10 D(3,7)=10 D(3,8)=10 D(2,2)=7 D(2,3)=6 D(2,4)=8 D(2,5)=8 D(1,1)=2 设这条最小成本路径是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 。 5.4 背包问题（货物配载问题） 序号 1 2 3 4 5 6 7 8 路径 3~4 5-6 2~3 4~5 1~2 2~6 1~6 2~4 节约里程 12 8 6 6 5 5 4 3 序号 9 10 11 12 路径 1~5 1~3 3~5 4~6 1~4 2~5 3~6 节约里程 2 2 1 0 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 节约法的缺点 （1）利用节约法选择配送路线过于强调节约路程，而没考虑行程中的时间因 素,在许多情况下，时间更能决定物流配送的成本与服务质量； （2）利用节约法选择配送路线不能对客户的需求进行灵活多变的处理。客户的需求倾向于个性化，小批量、多品种、多批次，而节约法更适合需求稳定或是需求的时间不紧迫,这显然不能满足现代多变得市场环境。 （3）节约法计算的配送路线并不一定是总路程最短。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？ 物品 重量（公斤/件） 每件使用价值 1 2 … j … n a1 a2 … aj … an c1 c2 … cj … cn 这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、包装箱内货物码放等。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 设xj 为第j 种物品的装件数（非负整数）则问题的数学模型如下： 用动态规划方法求解，令 fk(y) = 总重量不超过 y 公斤，包中只装有前k 种物品时的最大使用价值。 其中y ≥0， k ＝1,2,