资源描述：
《运输问题与指派问题第ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、OR课件回顾到目前为止，针对规划问题所建立的算法有一个共同的特征：但是：在决策的实践中，有些问题约束条件存在一定的特殊性，按常规办法有可能出现严重退化而导致问题无法顺利求解。如：运输问题、指派问题等。从约束条件入手OR课件运筹帷幄之中决胜千里之外运输问题与指派问题第五章TransportationProblem—IP&AssignmentProblem—APOR课件运输问题与指派问题运输问题和指派问题是一种特殊的LP问题，要求了解两问题的基本特征；掌握两问题的求解算法原理及计算过程；学会对它们的特殊形式的处理。本章的要求TP&APOR课件运输问题与指派问题重点本
2、章重点与难点难点TP&AP运输与指派问题模型及其特征算法原理特殊问题的处理两算法的思想及其实现OR课件运输问题与指派问题运输问题主要内容指派问题TP&AP运输问题及其数学模型求解方法－－表上作业法特殊运输问题的求解指派问题及其数学模型求解方法－－匈牙利法特殊指派问题的求解OR课件运输问题运输问题及其数学模型TP&AP设某种物资有m个产地：A1,A2,…,Am；产量分别为：a1,a2,…,am个单位；n个销地：B1,B2,…,Bn；销量分别为：b1,b2,…,bn个单位；假设产销总量是平衡的，即单位运价：AiBj：cij问：如何调运这种物资才能使总的运费最小？O
3、R课件运输问题单位运价表与平衡表（合表）TP&AP单位运价产销量（平衡）OR课件运输问题模型TP&AP设：xij为AiBj的运量OR课件运输问题表上作业法TP&AP【简例】已知有关资料如下表算法的提出：观测模型的特征要求建立总运费最小的模型。OR课件运输问题模型TP&AP约束条件个数为m+n，但只有m+n-1个是线性无关元素只有0和1，每列只有两个1OR课件表上作业法算法思想TP&AP与单纯形法一样，最优解在基本可行解中产生。但基于模型的特征，初始基本可行解是通过分析单位运价表，首先满足局部最优，然后通过调整（迭代）使整体达到最优。平衡表OR课件表上作业法步骤
4、算法步骤及要点TP&AP初始调运方案检验数ij0?Y最优解N调整：找到新的调运方案特征：解变量（基变量）个数为m+n-1；以解变量为顶点不构成折现闭回路。方法：最小元素法、差值法方法：闭回路法、位势法方法：闭回路法OR课件表上作业法•初始方案折现闭回路：TP&AP顶点:x11,x12,x32,x31顶点：x12,x13,x33,x34,x24,x22定理：以m+n-1个变量构成的基本可行解的充要条件是它不含折现闭回路。OR课件表上作业法•初始方案最小元素法TP&AP基本思想：“就近供应”或称“就廉供应”342345Z=1×3＋9×5＋4×3＋2×
5、4＋7×4＋2×2＝100OR课件表上作业法•初始方案差值法[伏格尔（Vogel)法]TP&AP基本思想：在考虑最大差值的基础上，就近供应差值（行、列）＝次小元素－最小元素Z=2×3＋9×5＋4×3＋2×4＋7×1＋2×5＝8832528541315OR课件表上作业法•最优性检验闭回路法TP&AP基本原理：以任一非基变量为顶点，其它顶点为基变量，所构成的闭回路是唯一的。342345－47－1323OR课件表上作业法•最优性检验TP&AP位势法基本原理：由于找闭回路带来的麻烦，根据对偶理论，设两组变量（对偶变量）ui和vj，及基变量的检验数
6、等于0，建立一组参数方程：基变量所对应的价格系数非基变量所对应的价格系数行位势列位势OR课件表上作业法•最优性检验TP&AP342345vjui令u1=00-5-56977-47-1323OR课件表上作业法•方案调整TP&AP342345-47-1313闭回路法基本思想：确定换入、换出变量。在闭回路上采用“奇加偶减”调整运量xij，闭回路以外xij不变。315???OR课件表上作业法•方案调整TP&AP453153vjui0297-5-57411-1323560403635vjui027-58-464101432S
7、=83OR课件运输问题TP&AP特殊运输问题及其求解目标取极大（MaxZ）：用ij0进行最优性检验。供过于求（产>销）：加虚销点，且Ci虚＝0，销量为产销之差【例】供不应求（销>产）：加虚产点，且C虚j=0，产量为销产之差【例】OR课件特殊运输问题及求解TP&AP2115OR课件特殊运输问题及求解TP&AP2125OR课件指派问题TP&AP问题的提出设有n个人，需要分派他们去做n件工作。要求一个人做一件事，一件事只能由一个人完成；由于每人的专长不同，各人做任一种工作的效率可能不同，因而创造的价值也不同。问如何安排，才能使创造的总价值最大？OR课件指派问题TP
8、&AP数学模型【例】现有
