包装物流系统优化方法.ppt

包装物流技术 专 业：包装工程 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 背包问题（货物配载问题） 3 2~4 8 3~6 4 1~6 7 2~5 5 2~6 6 1~4 5 1~2 5 0 4~6 12 6 4~5 4 1 3~5 11 6 2~3 3 2 1~3 10 8 5-6 2 2 1~5 9 12 3~4 1 节约里程 路径 序号 节约里程 路径 序号 节约法的缺点 （1）利用节约法选择配送路线过于强调节约路程，而没考虑行程中的时间因 素,在许多情况下，时间更能决定物流配送的成本与服务质量； （2）利用节约法选择配送路线不能对客户的需求进行灵活多变的处理。客户的需求倾向于个性化，小批量、多品种、多批次，而节约法更适合需求稳定或是需求的时间不紧迫,这显然不能满足现代多变得市场环境。 （3）节约法计算的配送路线并不一定是总路程最短。 有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？ c1 c2 … cj … cn 每件使用价值 a1 a2 … aj … an 重量（公斤/件） 1 2 … j … n 物品 这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、包装箱内货物码放等。 设xj 为第j 种物品的装件数（非负整数）则问题的数学模型如下： 用动态规划方法求解，令 fk(y) = 总重量不超过 y 公斤，包中只装有前k 种物品时的最大使用价值。 其中y ≥0， k ＝1,2, …, n 。所以问题就是求 fn(a) 其递推关系式为： 当 k=1 时，有： 例题：求下面背包问题的最优解 8 5 12 使用价值 3 2 5 重量（斤） 1 2 3 物品 解：a＝5 ，问题是求 f3(5) 所以，最优解为 X＝（1 . 1 . 0），最优值为 Z = 13。 5.5 0/1背包问题 给定n种物品和一个背包，物品i的重量是wi，其价值为vi，背包的容量为C。背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?如果在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或不装入背包，即不能将物品i装入背包多次，也不能只装入物品i的一部分，则称为0/