物流系程 西南交通六彎子讲义 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