运输任务分配

运输调度管理——运输任务分配本次课程项目2.5任务2.5.1情境2.5.1：内贸的这票业务需要5位司机；情境2.5.2：分配的3位司机中突然生病，需要重新分配（意外）。任务1采用数学方法——建模编制优化方案任务2采用计算机软件求解最优方案任务3采用匈牙利法求解最优方案（深化能力）知识目标：1.了解运输任务分配的含义；2.理解运输任务分配的具体内容；3.掌握运输任务分配的方法。

能力目标：1.能够正确制定运输资源（车、人、任务）指派方案素质目标：善于思考、优化思维能力

、自主学习能力。浙江远大公司的内贸业务中，分配甲、乙、丙、丁、戊五个人去完成五项运输任务。每人完成各项任务时间如下表所示。要求必须每人完成一项任务，试确定总花费时间为最少的指派方案。案例任务人ABCDE甲56845乙34661丙55798丁67576戊74628

浙江远大的小食品内贸业务正在开展中，现了解到产品Q某地区有A1，A2，A3三个生产地，每天要把生产的产品运往B1，B2，B3，B4四个超市。每个产地的产量、每个超市的销量以及各产销地之间的运价如下表所示。问应如何组织调运才能达到产销平衡并使总运费最少？

B1B2B3B4产量（吨）A163255A275842A332973销量（吨）2314运输物资调配复习解:设Xij为Ai铁矿运往Bj炼铁厂的货物数量，

则目标函数为使总运费Z最少。minZ=6X11+3X12+2X13+5X14+7X21+5X22+8X23+4X24+3X31+2X32+9X33+7X34约束条件：X11+X12+X13+X14=5（满足A1矿的产量）

X21+X22+X23+X24=2（满足A2矿的产量）

X31+X32+X33+X34=3（满足A3矿的产量）

X11+X21+X31=2（满足B1厂的需求量）

X12+X22+X32=3（满足B2矿的需求量）

X13+X23+X33=1（满足B3矿的需求量）

X14+X24+X34=4（满足B4矿的需求量）

Xij>=0(i=1,2,3,j=1,2,3,4)(决策变量非负约束)

浙江远大公司的内贸业务中，分配甲、乙、丙、丁、戊五个人去完成五项运输任务。每人完成各项任务时间如下表所示。要求必须每人完成一项任务，试确定总花费时间为最少的指派方案。案例任务人ABCDE甲56845乙34661丙55798丁67576戊74628运输任务分配如何解决“工作”——“产地”“人员”——”销地“把”工作“看成是运输问题中的”产地“，它的供应量是1，即一项工作。把”人员“看成是运输问题中的”销地“，它的需求量是1，即完成一项工作。某人员完成某项工作的时间（成本）就看成是运输问题中相应的单位运费运输任务分配问题案例延伸任务人ABCDE销量甲56845乙34661丙55798丁67576戊74628产量案例求解minf(x)=5X11+6X12+8X13+4X14+5X15+3X21+4X22+6X23+6X24+X25+5X31+5X32+7X33+9X34+8X35+…+8X55约束条件：X11+X12+X13+X14+X15=1

X21+X22+X23+X24+X25=1

X31+X32+X33+X34+X35=1

X41+X42+X43+X44+X45=1

X51+X52+X53+X54+X55=1

X11+X21+X31+X41+X51=1

X12+X22+X32+X42+X52=1

X13+X23+X33+X43+X53=1

X14+X24+X34+X44+X54=1

Xij=0OR1(i=1,2,3,4,5;j=1,2,3,4,5)现有A、B、C、D、E共5个人，挑选其中4人去完成4项工作。已知每人完成各项工作的时间如表所示。规定每项工作只能由一个人去完成，每人最多承担一项工作，又假定A必须分配到一项工作，D因某种原因决定不承担第Ⅳ项工作，问应如何分配，才能使得完成4项工作总的花费时间最少？练习1人工作ABCDEⅠ1023159Ⅱ5101524Ⅲ15514715Ⅳ20151368四艘货船要从一个码头向其他的四个码头运货（分别标记为1、2、3、4）。每一艘船都能够运送到任何一个码头。但是，由于货船和货物的不同，装船、运输和卸货成本都有些不同。如同下表所示。目标是要把这四个不同的码头指派给四艘货船，使总运输成本最小。练习2码头1234货船A500400600700B600600700500C700500700600D500400600600求解方法1：Excel方法1、接受加工任务通知，并估算各小组加工不同任务的耗时定额；2、使用直观经验法进行初步判断任务的分配并计算总工时；3、采用匈牙利方法对各小组完成不同加工任务进行优化：（1）列出矩阵

求解方法2——匈牙利法（2）逐行缩减矩阵。在每一行中选择一个最小元素，然后将每一行中的各元素均减去这个最小元素。本例中各行最小元素分别是：4、1、5、5、2。

（3）检查上述矩阵，若矩阵各行各列均有“0”，则跳过此步，否则进行列约减，即每一列数据减去本列数据中的最小数。再逐列缩减矩阵。现在的矩阵每一行每一列都有0，不必对列进行简约化。

（4）检查是否可以分配。采用0元素最小覆盖线的检验法，当覆盖线的维数等于矩阵的阶数时，则最优方案已经找到。技巧：从含“0”最多的行或列开始画“盖0”线。此时只有4条覆盖线，尚未找到最优方案。（5）为增加0元素进行变换。找出没有覆盖线的行与列中的最小元素。本例是1，将不在覆盖线上的元素都减去1，而在有两条覆盖线的交点上的每一个元素都加上1，其余元素不变。

此时覆盖线的维数等于矩阵的阶数时，则最优方案已经找到。（6）重新检查覆盖线。重复（4）的做法，如下：（7）确定最优方案。按0元素所占位置进行分配，可得最优流通加工任务分配方案，即