OROR课件课件 回 顾到目前为止，针对规划问题所建立的算到目前为止，针对规划问题所建立的算到目前为止，针对规划问题所建立的算到目前为止，针对规划问题所建立的算法有一个共同的特征：法有一个共同的特征：法有一个共同的特征：法有一个共同的特征：v但是：但是：在决策的实践中，有些问题约束条件存在决策的实践中，有些问题约束条件存在决策的实践中，有些问题约束条件存在决策的实践中，有些问题约束条件存在一定的在一定的在一定的在一定的特殊性特殊性特殊性特殊性，按常规办法，按常规办法，按常规办法，按常规办法有可能有可能有可能有可能出出出出现严重退化而导致问题现严重退化而导致问题现严重退化而导致问题现严重退化而导致问题无法顺利求解无法顺利求解无法顺利求解无法顺利求解。如：运输问题、指派问题等。如：运输问题、指派问题等。如：运输问题、指派问题等。如：运输问题、指派问题等。从约束条件入手OROR课件课件运 筹 帷 幄 之 中决 胜 千 里 之 外运输问题与指派问题第五章第五章Transportation ProblemIP& Assignment ProblemAPOROR课件课件运输问题与指派问题 运输问题和指派问题是一种特殊特殊的LP问题，要求了解两问题的基本特征；掌握两问题的求解算法原理及计算过程；学会对它们的特殊形式的处理。本章的要求TP & APOROR课件课件运输问题与指派问题重点重点本章重点与难点难点难点TP & AP运输与指派问题模型及其特征算法原理特殊问题的处理两算法的思想及其实现OROR课件课件运输问题与指派问题运输问题运输问题主要内容指派问题指派问题TP & AP运输问题及其数学模型求解方法表上作业法特殊运输问题的求解指派问题及其数学模型求解方法匈牙利法特殊指派问题的求解OROR课件课件运输问题运输问题及其数学模型运输问题及其数学模型TP & AP 设某种物资有m个产地：A1,A2,Am；产量分别为：a1,a2,am个单位；n个销地：B1,B2,Bn；销量分别为：b1,b2,bn个单位；假设产销总量是平衡的，即单位运价：Ai Bj：cij问：如何调运这种物资才能使总的运费最小？OROR课件课件运输问题单位运价表与平衡表（合表）单位运价表与平衡表（合表）TP & AP单位运价产销量（平衡）OROR课件课件运输问题模型模型TP & AP设：xij为AiBj的运量OROR课件课件运输问题表上作业法表上作业法TP & AP【简例】已知有关资料如下表算法的提出：观测模型的特征要求建立总运费最小的模型。OROR课件课件运输问题模型模型TP & AP约束条件个数为 m+n，但只有m+n-1 个是线性无关元素只有0和1，每列只有两个1OROR课件课件表上作业法算法思想算法思想TP & AP 与单纯形法一样，最优解在基本可行解中产生。但基于模型的特征，初始基本可行解是通过分析单位运价表，首先满足局部最优，然后通过调整（迭代）使整体达到最优。平衡表OROR课件课件表上作业法 步骤算法步骤及要点算法步骤及要点TP & AP初始调运方案检验数ij0 ?Y最优解最优解最优解最优解N调整：找到新的调运方案特征特征：解变量（基变量）个数为 m+n-1；以解变量为顶点不构成折现闭回路。方法方法：最小元素法、差值法方法：闭回路法、位势法方法：闭回路法OROR课件课件表上作业法初始方案折现闭回路：折现闭回路：TP & AP顶点: x11,x12,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 基本原理基本原理：以任一非基变量为顶点，其它顶点为基变量，所构成的闭回路是唯一的。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 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件工作。要求一个人做一件事，一件事只要求一个人做一件事，一件事只要求一个人做一件事，一件事只要求一个人做一件事，一件事只能由一个人完成能由一个人完成能由一个人完成能由一个人完成；由于每人的专长不同，各人做任一种工作的效率可能不同，因而创造的价值也不同。问如何安排，才能使创造的总价值最大总价值最大总价值最大总价值最大？OROR课件课件指派问题TP & AP数学模型数学模型【例】现有4辆装载不同货物的待卸车，派班员要分派给4个装卸班组，每个班组卸一辆车。由于各个班组的技术专长不同，各个班组卸不同车辆所需时间（小时）如下表。问派班员应如何分配卸车任务，才能使卸车所花的总时间最少？待卸车装卸组cijOROR课件课件指派问题数学模型TP & AP解：引入解：引入解：引入解：引入0 01 1变量变量变量变量x xij ij，并令并令并令并令: :待卸车装卸组bjai11111111OROR课件课件指派问题TP & AP匈牙利算法匈牙利算法算法的提出：观测模型的特征特殊的运输问题OROR课件课件匈牙利算法TP & AP算法原理算法原理cijnn不同行（列）减去最小元素 bijnn有相同的最优指派有相同的最优指派有相同的最优指派有相同的最优指派？OROR课件课件匈牙利算法TP & AP设：i，j 分别是系数矩阵cij 行和列减去的最小元素。则 bij=cij- i - j 因为bij0，xij0 则上式为bij所对应的最优目标值0。cij所对应的最优目标值为行、列减去的最小元素之和。当不同行不同列的当不同行不同列的当不同行不同列的当不同行不同列的b bij ij=0=0时，时，时，时，x xij ij1 1；否则，否则，否则，否则，x xij ij0 0OROR课件课件匈牙利算法TP & AP算法步骤算法步骤使使使使 c cij ij 的行（列）出现的行（列）出现的行（列）出现的行（列）出现0 0元素元素元素元素 c cij ij b bij ij ？Y确定最优指派确定最优指派确定最优指派确定最优指派调整方案：调整方案：调整方案：调整方案：使使使使 c cij ij 出现更多的出现更多的出现更多的出现更多的0 0元素元素元素元素N行（列）减去该行（列）的最小元素【例1】bij中存在不同行、不同列的0元素bij= (0)时，xij=1; 否则，xij=0变换系数矩阵【例2】OROR课件课件匈牙利算法TP & AP-1-2-3-2-2(0)(0)(0)(0) Z=1+2+5+2=1+2+3+2+2=10【例1】OROR课件课件匈牙利算法TP & AP-7-5-4-2-1【例2】(0)(0)(0)-1-11(0)(0)(0)(0)(0)(0)(0)(0)或：关键关键：能覆盖所有0元素的最少直线数最少直线数？如何画如何画 ？OROR课件课件匈牙利算法TP & AP Z=20【例2】或：OROR课件课件匈牙利算法TP & AP【例2】定理定理定理定理：能覆盖所有：能覆盖所有：能覆盖所有：能覆盖所有0 0元素的元素的元素的元素的最少直线数最少直线数最少直线数最少直线数等于在等于在等于在等于在0 0元元元元素处作出标号素处作出标号素处作出标号素处作出标号（0 0）的最多个数）的最多个数）的最多个数）的最多个数。画法画法：在没有（0）的行行打号对打号的行上的所有有0元素的列列打号再对打号的列上有（0）的行行打号有新的打号的行列行列吗？YN对没有打号的行行画横线对所有打号的列画纵线OROR课件课件指派问题TP & AP特殊指派问题的求解特殊指派问题的求解目标为MaxZ：令：Cij =M- Cij ，转化为MinS.“人多于事”（mn）：处理处理：加（m-n）件虚事，Ci虚0“事多于人”（mn）：处理处理：加（n - m ）个虚人，C虚j0OROR课件课件本章小结TP & AP本章重点介绍了一类特殊线性规划问题（运输问题和指派问题）的模型与求解；应注意到：应注意到：两问题都有最优解；两问题都有最优解；两问题都有最优解；两问题都有最优解；两算法思想基本相同，均从目标函数系数两算法思想基本相同，均从目标函数系数两算法思想基本相同，均从目标函数系数两算法思想基本相同，均从目标函数系数入手，并且直接求得整数最优解；入手，并且直接求得整数最优解；入手，并且直接求得整数最优解；入手，并且直接求得整数最优解；思考：两算法的区别？思考：两算法的区别？思考：两算法的区别？思考：两算法的区别？