运输任务分配

1、第五节 运输任务分配物流资源分配问题也称指派问题 （assignment problem） ，属于 0-1 整数规划问题。典型的 指派问题是指： 有 n 项不同的工作要做， 恰好有 n 个人（或设备） 可以分别完成其中的一项 工作， 但由于任务性质和个人专长不同， 因而由不同的人去完成不同的工作的效率 （或所需 的资源）是不一样的。如何安排才能使工作总效率最高（或所需总资源最少）？下面介绍一种物流资源分配问题的简便算法 匈牙利法。 运用匈牙利法求最优分派的步骤如下：（一）从矩阵（ n×n）的各行（列）减去该行（列）的最小元素。（二）从所得矩阵的各列（行）减去该列（行）的最小元素，使每

2、行、每列都出现0元素。至此所得价值系数矩阵称为简约化的价值系数矩阵。（三）以最少的 m 条直线（水平的或竖直的）去覆盖简约化价值系数矩阵中的所有0元。（四）若 m=n,可从上述简约化的价值系数矩阵的0 元中找到一组位于不同行且不同列的 0 元。令这些元素对应的变量 xij =1,其余的变量 xij=0，就得到了一个最优解。若 m<n ，从未被直线覆盖的元素中找出最小元素，从所有未被覆盖的元素中将它减去， 并在所有位于水平、 垂直覆盖线相交处的元素上加上这个最小元素， 其余被覆盖的元素保持 不变，再回到步骤（三） 。【情景】* 物流公司同时接到五项运输任务，同时*物流公司拥有五个项目小组，

3、每个物流项目组都拥有独立的运输资源。 每个物流项目组都能完成所有的运输任务， 而由于资源和项目 组自身的地理位置的差异， 每个物流项目组完成每项运输任务的效率是不一样的。 此时， 运 输调度员如何安排运输任务，才能使运输效率最高。（ 案例： YSA020205 ：如何指派运输任务）某物流公司的一份说明书， 要分别译成英、 日、德、俄、 韩五种文字 （分别称为任务 A ，B，C，D，E），交甲、乙、丙、丁、戊去完成，每人完成一种。已知各人完成不同任务所需时间（小时数）如表 1-11 所示。问如何分派，才能使总用时量最少？表 1-11 完成任务时数务人任ABCDE甲56845乙34661丙5579

4、8丁67576戊74628解：该问题的价值系数矩阵为5684534661C1 5 5 7 9 86757674628按步骤（一） ，得：56843466C1 5 5 7 9675774625 -41 -18-56-58-21240123550C2 0 0 2 4 31202152406因 C 2 每列已含 0 元素，不必对列进行简约化。按步骤（三） ，得：12401 23550 C2 0 0 2 4 321202152406覆盖所有 0 元的最少直线数 m = 4, 4<5, 按步骤（四）中m<n 方案，得：C0+1 5 4 2 010426055303420312021010143C回到步骤（三）C313012450025420321306m =5=n ，回到步骤（四）中m=n 方案，得：051301124502C3004254120132413036覆盖所有 0 元的最少直线数找 0 元的顺序之一用中括号里的数字标出）684466C1579757回顾462故在该分配问题中， 最优目标函数值为 5+1+5+5