运输问题与指派问题第.ppt

OR课件从约束条件入手在决策的实践中，有些问题约束条件存在一定的特殊性，按常规办法有可能出现严重退化而导致问题无法顺利求解。如：运输问题、指派问题等。但是：1回顾到目前为止，针对规划问题所建立的算法有一个共同的特征：2OR课件运筹帷幄之中决胜千里之外运输问题与指派问题第五章TransportationProblem—IPAssignmentProblem—AP01OR课件02运输问题与指派问题03运输问题和指派问题是一种特殊的LP问题，要求了解两问题的基本特征；掌握两问题的求解算法原理及计算过程；学会对它们的特殊形式的处理。04本章的要求05TPAP运输问题与指派问题本章重点与难点TPAPOR课件运输与指派问题模型及其特征算法原理特殊问题的处理重点1难点两算法的思想及其实现2运输问题与指派问题主要内容TPAP运输问题OR课件运输问题及其数学模型求解方法－－表上作业法特殊运输问题的求解指派问题指派问题及其数学模型求解方法－－匈牙利法特殊指派问题的求解OR课件运输问题运输问题及其数学模型TPAP设某种物资有m个产地：A1,A2,…,Am；产量分别为：a1,a2,…,am个单位；n个销地：B1,B2,…,Bn；销量分别为：b1,b2,…,bn个单位；假设产销总量是平衡的，即单位运价：Ai?Bj：cij问：如何调运这种物资才能使总的运费最小？OR课件TPAP单位运价产销量（平衡）运输问题单位运价表与平衡表（合表）5%55%30%10%OR课件TPAP模型设：xij为Ai?Bj的运量运输问题OR课件01TPAP02【简例】已知有关资料如下表03表上作业法算法的提出：观测模型的特征要求建立总运费最小的模型。04运输问题OR课件TPAP元素只有0和1，每列只有两个1模型约束条件个数为m+n，但只有m+n-1个是线性无关0103020405运输问题表上作业法OR课件算法思想TPAP与单纯形法一样，最优解在基本可行解中产生。但基于模型的特征，初始基本可行解是通过分析单位运价表，首先满足局部最优，然后通过调整（迭代）使整体达到最优。平衡表表上作业法步骤OR课件算法步骤及要点TPAP初始调运方案检验数?ij?0?Y最优解N调整：找到新的调运方案特征：解变量（基变量）个数为m+n-1；以解变量为顶点不构成折现闭回路。方法：最小元素法、差值法方法：闭回路法、位势法方法：闭回路法1OR课件2折现闭回路：3TPAP6定理：以m+n-1个变量构成的基本可行解的充要条件是它不含折现闭回路。5顶点：x12,x13,x33,x34,x24,x224顶点:x11,x12,x32,x31表上作业法?初始方案OR课件表上作业法?初始方案最小元素法TPAP基本思想：“就近供应”或称“就廉供应”3?????42?345Z=1×3＋9×5＋4×3＋2×4＋7×4＋2×2＝100OR课件表上作业法?初始方案差值法[伏格尔（Vogel)法]TPAP基本思想：在考虑最大差值的基础上，就近供应差值（行、列）＝次小元素－最小元素Z=2×3＋9×5＋4×3＋2×4＋7×1＋2×5＝883??25??2854?13?15闭回路法OR课件表上作业法?最优性检验TPAP基本原理：以任一非基变量为顶点，其它顶点为基变量，所构成的闭回路是唯一的。3?????42?345－47－1323OR课件表上作业法?最优性检验TPAP基本原理：由于找闭回路带来的麻烦，根据对偶理论，设两组变量（对偶变量）ui和vj，及基变量的检验数等于0，建立一组参数方程：基变量所对应的价格系数非基变量所对应的价格系数行位势列位势OR课件表上作业法?最优性检验TPAP3?????42?345vjui令u1=00-5-56977-47-1323OR课件表上作业法?方案调整TPAP3?????42?345-47-1313基本思想：确定换入、换出变量。在闭回路上采用“奇加偶减”调整运量xij，闭回路以外xij不变。