第5章 运输问题与指派问题

1、OROR课件课件v但是：但是：从约束条件入手 导导 学学-回顾回顾OROR课件课件运 筹 帷 幄 之 中决 胜 千 里 之 外OROR课件课件运输问题运输问题 5 指派问题指派问题TP & AP1 运输问题及其数学模型2 求解方法表上作业法3 特殊运输问题的求解（1） 指派问题及其数学模型（2） 求解方法匈牙利法（3） 特殊指派问题的求解 导导 学学-主要内容主要内容OROR课件课件重点重点难点难点TP & AP运输与指派问题模型及其特征算法原理特殊问题的处理两算法的思想及其实现 导导 学学-重点与难点重点与难点OROR课件课件 运输问题和指派问题是一种特殊特殊的LP问题，要求

2、了解两问题的基本特征；掌握两问题的求解算法原理及计算过程；学会对它们的特殊形式的处理。TP & AP 导导 学学-本章要求本章要求OROR课件课件TP & AP 设某种物资有m个产地：A1,A2,Am；产量分别为：a1,a2,am个单位；n个销地：B1,B2,Bn；销量分别为：b1,b2,bn个单位；假设产销总量是平衡的，即单位运价：Ai Bj：cij问：如何调运这种物资才能使总的运费最小？njjmiiba11OROR课件课件单位运价表与平衡表（合表）单位运价表与平衡表（合表）TP & AP产 地 B1 B2 Bn 产 量 A1 A2 . Am . C11 C21 cm

3、 1 C12 C21 cm 2 C1n C2n cm n a1 a2 am 销 量 b1 b2 bn 销 地 单位运价产销量（平衡）OROR课件课件模型模型TP & AP设：xij为AiBj的运量OROR课件课件TP & AP【简例】已知有关资料如下表算法的提出：观测模型的特征要求建立总运费最小的模型。OROR课件课件模型模型TP & AP约束条件个数为 m+n，但只有m+n-1 个是线性无关元素只有0和1，每列只有两个1OROR课件课件算法思想算法思想TP & AP 与单纯形法一样，最优解在基本可行解中产生。但基于模型的特征，初始基本可行解是通过分析单位运价表

4、，首先满足局部最优，然后通过调整（迭代）使整体达到最优。平衡表OROR课件课件算法步骤及要点算法步骤及要点TP & AP初始调运方案检验数ij0 ?YN调整：找到新的调运方案特征特征：解变量（基变量）个数为 m+n-1；以解变量为顶点不构成折现闭回路。方法方法：最小元素法、差值法方法：闭回路法、位势法方法：闭回路法OROR课件课件折现闭回路：折现闭回路：TP & AP产 地 B 1 B 2 B 3 B 4 A 1 X 11 X 12 X 13 X 14 A 2 X 21 X 22 X 23 X 24 A 3 X 31 X 32 X 33 X 34 销 地 顶点: x11,x12

5、,x32,x31顶点：x12,x13,x33,x34,x24,x22v定理：以m+n-1个变量构成的基本可行解的充要条件是它不含折现闭回路。OROR课件课件最小元素法最小元素法TP & AP基本思想：“”或称“”3 42 345Z=139543247422100OROR课件课件差值法差值法伏格尔（伏格尔（Vogel) 法法TP & AP基本思想：在考虑最大差值的基础上，就近供应就近供应差值（行、列）次小元素最小元素Z=239543247125883 25 2854 13 15OROR课件课件闭回路法闭回路法TP & AP 基本原理基本原理：以任一非基变量为顶点，其它顶点

6、为基变量，所构成的闭回路是唯一的。3 42 345471323OROR课件课件TP & AP位势法位势法 基本原理基本原理：由于找闭回路带来的麻烦，根据对偶理论，设两组变量（对偶变量）ui和vj，及基变量的检验数等于0，建立一组参数方程：OROR课件课件TP & AP3 42 345vjui令 u1 = 00-5-56977-47-1323OROR课件课件TP & AP3 42 345-47-1313闭回路法闭回路法基本思想基本思想：确定换入、换出变量。在闭回路上采用“奇加偶减”调整运量xij，闭回路以外xij不变。315?OROR课件课件TP & AP 45

7、3153 vjui0297-5-57411-1323560 40 363 5vjui027-58-464101432S=83OROR课件课件TP & AP目标取极大（MaxZ）：用ij 0 进行最优性检验。供过于求（产销）：加虚销点加虚销点，且Ci虚0 ，销量为产销之差 【例】供不应求（销产）：加虚产点加虚产点，且C虚j = 0 ，产量为销产之差 【例】 OROR课件课件TP & AP2115OROR课件课件TP & AP2125OROR课件课件TP & AP问题的提出问题的提出 设有n个人，需要分派他们去做n件工作。；由于每人的专长不同，各人做任一种工作的效率

8、可能不同，因而创造的价值也不同。问如何安排，才能使创造的？OROR课件课件TP & AP【例】现有4辆装载不同货物的待卸车，派班员要分派给4个装卸班组，每个班组卸一辆车。由于各个班组的技术专长不同，各个班组卸不同车辆所需时间（小时）如下表。问派班员应如何分配卸车任务，才能使卸车所花的总时间最少？待卸车装卸组cijOROR课件课件TP & AP待卸车装卸组否则01jixij bjai11111111OROR课件课件TP & AP算法的提出：观测模型的特征特殊的运输问题OROR课件课件TP & APcijnn不同行（列）减去最小元素 bijnn？OROR课件课件TP

9、 & AP设：i，j 分别是系数矩阵cij 行和列减去的最小元素。则 bij=cij- i - j 因为bij0，xij0 则上式为bij所对应的最优目标值0。cij所对应的最优目标值为行、列减去的最小元素之和。OROR课件课件TP & AP算法步骤算法步骤YN行（列）减去该行（列）的最小元素【例1】bij中存在不同行、不同列的0元素bij= (0)时，xij=1; 否则，xij=0变换系数矩阵【例2】OROR课件课件TP & AP 562345345632143444cij -1-2-3-23401120134100323 -23201100132100123 bij

10、44 (0)(0)(0)(0) Z=1+2+5+2=1+2+3+2+2=10【例1】OROR课件课件TP & AP 5432564577858791044cij -7-5-4-2-1 bij44 【例2】2210020112300023 (0)3210120122301023(0)(0)-1-111100020201200024(0)(0)(0)(0)1100020201200024(0)(0)(0)(0)或：关键关键：能覆盖所有0元素的最少直线数最少直线数？如何画如何画 ？OROR课件课件TP & AP Z=20【例2】或：OROR课件课件TP & AP【例2】画法画法：在没有（0）的行行打号对打号的行上的所有有0元素的列列打号再对打号的列上有（0）的行行打号有新的打号的行列行列吗？YN对没有打号的行行画横线对所有打号的列画纵线OROR课件课件TP & A