物流系程 西南交通六彎子讲义 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矩阵性质定理，因此这种 方法被称为匈牙利法