西南交通大学：《物流系统工程》第5章 物流系统规划(二)

物流系程 西南交通六彎子讲义 53物流分配规划 口任务分配问题的数学模型 口用匈牙利法求解分配问题

物流系统工程—— 西南交通大学电子讲义 1 5.3 物流分配规划 ❑任务分配问题的数学模型 ❑用匈牙利法求解分配问题

物流系程 第5章物示统规划 任务分配问题的数学模型 口在物流系统中或其它的管理工作中,管理人员经常面临的 个问题是:如何根据有限的资源(人力、物力、财力等) 进行工作任务分配,以达到降低成本或提高经济效益的目 的。如 令有A、B、C、D四门课程,上课的老师可以从甲、乙、丙、丁四名老 师中选择,不同的老师上不同的课程,其费用是不同的,并且规定, 每人只讲一门课程,每门课程只需要一人讲授。问:如何安排,才 能使总的上课费用最低? ◇又如:运输任务的分配问题。有η条航线的运输任务指派给η艘船去 完成,不同的船完成不同的航线其运输成本不同。要求每条船完成 条航线,并且一条航线只能由一条船去完成。如何分配任务,才 能使总的费用最小? 口这类问题是常见的任务分配问题,也叫指派问题,它的任 务是如何进行合理的任务分配,使总的费用最小\ 2

物流系统工程—— 第5章 物流系统规划 2 一. 任务分配问题的数学模型 ❑ 在物流系统中或其它的管理工作中，管理人员经常面临的 一个问题是：如何根据有限的资源(人力、物力、财力等)， 进行工作任务分配，以达到降低成本或提高经济效益的目 的。如： ❖ 有A、B、C、D四门课程，上课的老师可以从甲、乙、丙、丁四名老 师中选择，不同的老师上不同的课程，其费用是不同的，并且规定， 每人只讲一门课程，每门课程只需要一人讲授。问：如何安排，才 能使总的上课费用最低？ ❖ 又如：运输任务的分配问题。有n条航线的运输任务指派给n艘船去 完成，不同的船完成不同的航线其运输成本不同。要求每条船完成 一条航线，并且一条航线只能由一条船去完成。如何分配任务，才 能使总的费用最小？ ❑ 这类问题是常见的任务分配问题，也叫指派问题，它的任 务是如何进行合理的任务分配，使总的费用最小

物流系程 第5章物示统规划 任务分配问题的数学模型 口以运输问题的n项任务由n个司机去完成的情况为例,有n个 司机被分配完成n项运输任务,不同的司机完成任务某一项 任务的费用都不一样。要求每个司机完成其中一项任务, 每个任务只能由一名司机完成,如何分配任务,才能使总 的费用最小? c表示第机完成项生务的运输成MmZ=∑∑x i=1i=1 数); x表示第个司机去完成第项任务,其值 st ∑ 为1或0。 口当其值为1时表示第讠个司机被分配去完 成第j项任务; ∑x 口其值为0时,表示第论个司机不被分配去 完成第j项任务。 0或1 3

物流系统工程—— 第5章 物流系统规划 3 一. 任务分配问题的数学模型 ❑ 以运输问题的n项任务由n个司机去完成的情况为例，有n个 司机被分配完成n项运输任务，不同的司机完成任务某一项 任务的费用都不一样。要求每个司机完成其中一项任务， 每个任务只能由一名司机完成，如何分配任务，才能使总 的费用最小？ 0 1 1 . . 1 1 1 1 1 = 或 = = =    = = = = ij n i ij n j ij n i n i ij ij x x st x MinZ c x 令： cij表示第i个司机完成第j项任务的运输成 本（工作成本或工作时间等价值系 数）； xij表示第i个司机去完成第j项任务，其值 为1或0。 ❑当其值为1时表示第i个司机被分配去完 成第j项任务； ❑其值为0时，表示第i个司机不被分配去 完成第j项任务

物流系程 第5章物示统规划 任务分配问题的数学模型 口任务分配同题属于整数规划问题,其变量×的取值 为整数,(本例为0或1)。 口任务分配问题可以用一般的整数规划求解方法进 行求解。但是,整数规划问题的求解也是非常困 难的,到目前为止,还缺乏统一的求解方法。 口本书采用匈牙利法求解任务分配问题。 4

物流系统工程—— 第5章 物流系统规划 4 一. 任务分配问题的数学模型 ❑任务分配问题属于整数规划问题，其变量xij的取值 为整数，（本例为0或1）。 ❑任务分配问题可以用一般的整数规划求解方法进 行求解。但是，整数规划问题的求解也是非常困 难的，到目前为止，还缺乏统一的求解方法。 ❑本书采用匈牙利法求解任务分配问题

物流系程 第5章物示统规划 匈牙利法求解分配问题 口可以证明,对于分配问题,在其费用矩阵C中,各行、各 列均减去一个常数,q改变以后的最优解,仍为原问题的 最优解。 口利用这个性质,通过对c的行、列进行加减常数的计算, 把一些矩阵元素变为0,在C为0的元素上进行分解,就可 得到原问题的最优解。 口该方法应用了匈牙利数学家Koni矩阵性质定理,因此这种 方法被称为匈牙利法。 5

物流系统工程—— 第5章 物流系统规划 5 二. 匈牙利法求解分配问题 ❑ 可以证明，对于分配问题，在其费用矩阵Cij中，各行、各 列均减去一个常数，Cij改变以后的最优解，仍为原问题的 最优解。 ❑ 利用这个性质，通过对Cij的行、列进行加减常数的计算， 把一些矩阵元素变为0，在Cij为0的元素上进行分解，就可 得到原问题的最优解。 ❑ 该方法应用了匈牙利数学家Konig矩阵性质定理，因此这种 方法被称为匈牙利法

物流系程 西南交通六彎子讲义 54其他规划问题 口选址问题 口货物装配问题 口物流服务系统中的配置问题

物流系统工程—— 西南交通大学电子讲义 6 5.4 其他规划问题 ❑选址问题 ❑货物装配问题 ❑物流服务系统中的配置问题

物流系程 第5章物示统规划 选址问题 口物流调运规划问题,是一种有固定发点、固定收 点和固定道路的运输规划问题。 口还有一类运输问题,他的收货点和发货点是待定 的,这就是选址问题。这类问题在物流系统规划 中经常遇到。 口选址问题要考虑多种因素,本节只讨论选址问题 中的物流问题。分为两个问题 令单一地址选址方法; ◆图上作业法。 7

物流系统工程—— 第5章 物流系统规划 7 一. 选址问题 ❑物流调运规划问题，是一种有固定发点、固定收 点和固定道路的运输规划问题。 ❑还有一类运输问题，他的收货点和发货点是待定 的，这就是选址问题。这类问题在物流系统规划 中经常遇到。 ❑选址问题要考虑多种因素，本节只讨论选址问题 中的物流问题。分为两个问题： ❖单一地址选址方法； ❖图上作业法

物流系程 第5章物示统规划 1.单一地址选址方法 建立一个新工厂(或仓库),应合理选择厂址(或库址) 所谓选址问题,就是从多个候选厂址中选取一个最优地址 建厂,使物流费用达到最低。 问题描述:假设厂址候选地点有S个,分别用D1D2…,D 表示;原材料、燃料、零配件的供应地有m个,分别用 A1A2x…Am表示,其供应量分别用P1P2x,Pm表示;产 销售地有n个,分别用B1B2x…,Bn表示,其销售量分别为 Q1Q2x…,Q表示。 供应地 候选厂址 销售地 ⊙B A. . D2 ⊙B A ODs ⊙B 选址问题示意图 8

物流系统工程—— 第5章 物流系统规划 8 1. 单一地址选址方法 建立一个新工厂（或仓库），应合理选择厂址（或库址）。 所谓选址问题，就是从多个候选厂址中选取一个最优地址 建厂，使物流费用达到最低。 问题描述：假设厂址候选地点有s个，分别用D1 ,D2 ,…,Ds 表示；原材料、燃料、零配件的供应地有m个，分别用 A1 ,A2 ,…,Am表示，其供应量分别用P1 ,P2 ,…,Pm表示；产品 销售地有n个，分别用B1 ,B2 ,…,Bn表示，其销售量分别为 Q1 ,Q2 ,…,Qn表示

供应地 候选厂址 销售地 Ago ⊙D ⊙B 42 →⊙D2--- B B, 选址问题示意图 设c为供应地A到候选厂址D的单位运输成本; d为候选厂址D到销售地B的单位运输成本; 设选址变量为x=1,2,…,S,其中:x=0或1,1表示在D点建 ,0表示不在D点建厂

设cij为供应地Ai到候选厂址Dj的单位运输成本； djk为候选厂址Dj到销售地Bk的单位运输成本； 设选址变量为xj (j=1,2,…,s)，其中：xj=0或1，1表示在Dj点建 厂，0表示不在Dj点建厂

从供应点A到候选地D点的运输费用为:cn·P 所有的供应点到候选地D的运输费用为:∑cnP·x 从候选地D到销售地B的运输费用为:dk·Qk·x 候选地D到所有的销售地的运输费用为:∑4kQx 所有候选地的运输成本为:∑∑cnP·x1+2dkQ·x) ∴选址问题的数学模型可以表示为: miz=∑∑cP+∑4kQ小x s. t ∑ x=1或0

1 0 1 min D D B D A D 运输 c 1 1 1 1 1 1 1 1 j j k 1 j i j 或 选址问题的数学模型可以表示为： 所有候选地的运输成本为： 候选地 到所有的销售地的运输费用为： 从候选地 到销售地 的运输费用为： 所有的供应点到候选地 的运输费用为： 从供应点 到候选地 点的 费用为： = = =  +      +                    = = = = = = = = = j s j j j s j n k j k k m i i j i s j n k j k k j m i i j i j n k j k k j j k k j m i i j i j i j i j x s.t. x Z ( c P d Q ) x ( c P x d Q x ) d Q x d Q x c P x P x