运筹学运输问题.ppt

第五章运输与指派问题 运输问题的表示运输问题模型 运价表运输问题的求解表上作业法指派问题 运输 指派和转运问题 实际上都可以用L P 模型加以描述 所以可以认为它们是L P 的特例单列一章的原因在于 应用面极广 实践性很强 而特有的数学结构使得人们设计出了特别有效的方法对此类模型进行求解本章的重点在 掌握表格化方法求解运输 简述 提出问题 有A1 A2 A3三个砖瓦厂月产量分别为14 27 19万块 供应B1 B2 B3 B4四个工地 月需要量分别为22 13 12 13万块 每万块运费如下表 求总运费最少的方案 运输问题 运输问题线性规划模型 供应地约束 需求地约束 3 1运输问题模型与性质一 运输问题的数学模型1 运输问题的一般提法 某种物资有若干产地和销地 现在需要把这种物资从各个产地运到各个销地 产量总数等于销量总数 已知各产地的产量和各销地的销量以及各产地到各销地的单位运价 或运距 问应如何组织调运 才能使总运费 或总运输量 最省 运输问题的一般数学模型 有m个产地生产某种物资 有n个地区需要该类物资令a1 a2 am表示各产地产量 b1 b2 bn表示各销地的销量 ai bj称为产销平衡设xij表示产地i运往销地j的物资量 cij表示对应的单位运费 则我们有运输问题的数学模型如下 运输问题 二 运输问题的特点与性质1 约束方程组的系数矩阵具有特殊的结构写出式 3 1 的系数矩阵A 形式如下 矩阵的元素均为1或0 每一列只有两个元素为1 其余元素均为0 列向量Pij 0 0 1 0 0 1 0 0 T 其中两个元素1分别处于第i行和第m j行 三 运输问题的求解方法 1 单纯形法 为什麽 2 表上作业法由于问题的特殊形式而采用的更简洁 更方便的方法 3 2运输问题的表上作业法一 表上作业法的基本思想是 先设法给出一个初始方案 然后根据确定的判别准则对初始方案进行检查 调整 改进 直至求出最优方案 如图3 1所示 表上作业法和单纯形法的求解思想完全一致 但是具体作法更加简捷 图3 1运输问题求解思路图 二 初始方案的确定1 作业表 产销平衡表 初始方案就是初始基本可行解 将运输问题的有关信息表和决策变量 调运量结合在一起构成 作业表 产销平衡表 表3 3是两个产地 三个销地的运输问题作业表 表3 3运输问题作业表 运价表 3 举例 例3 2甲 乙两个煤矿供应A B C三个城市用煤 各煤矿产量及各城市需煤量 各煤矿到各城市的运输距离见表3 4 求使总运输量最少的调运方案 表3 4例3 2有关信息表 例3 2的数学模型 初始解的确定 一 最小元素法 最小元素法的基本思想是 就近供应 二 西北角法 西北角法则不考虑运距 或运价 每次都选剩余表格的左上角 即西北角 元素作为基变量 其它过程与最小元素法相同 三 沃格尔法 VOGLE 用最小元素法确定例3 2初始调运方案 150 100 100 100 100 100 100 用西北角法确定例3 2初始调运方案 100 100 100 50 50 200 200 得到初始调运方案为 x11 100 x12 100 x22 50 x23 200 元素差额法 Vogel近似法 最小元素法只考虑了局部运输费用最小 有时为了节省某一处的运费 而在其它处可能运费很大 元素差额法对最小元素法进行了改进 考虑到产地到销地的最小运价和次小运价之间的差额 如果差额很大 就选最小运价先调运 否则会增加总运费 例如下面两种运输方案 前一种按最小元素法求得 总运费是Z1 10 8 5 2 15 1 105后一种方案考虑到C11与C21之间的差额是8 2 6 先调运x21 再是x22 其次是x12这时总运费Z2 10 5 15 2 5 1 85 Z1 基于以上思路 元素差额法求初始基本可行解的步骤是 第一步 求出每行次小运价与最小运价之差 记为ui i 1 2 m 同时求出每列次小运价与最小运价之差 记为vj j 1 2 n 第二步 找出所有行 列差额的最大值 即L max ui vi 差额L对应行或列的最小运价处优先调运 第三步 这时必有一列或一行调运完毕 在剩下的运价中再求最大差额 进行第二次调运 依次进行下去 直到最后全部调运完毕 就得到一个初始调运方案 用元素差额法求得的基本可行解更接近最优解 所以也称为近似方案 表5 13 例5 5 用元素差额法求表5 13运输问题的初始基本可行解 解 求行差额ui i 1 2 3及列差额vj j 1 2 3 4 计算公式为ui i行次小运价 i行最小运价vj j列次小运价 j例最小运价 表5 14 5 表5 15 20 0 表5 16 20 0 10 20 5 基本可行解为 总运费Z 10 8 20 1 5 2 20 8 270 检查当前调运方案是不是最优方案的过程就是最优性检验 检查的方法 计算非基变量 未填上数值的格 即空格 的检验数 也称为空格的检验数 若全部大于等于零 则该方案就是最优调运方案 否则就应进行调整 一 闭回路法二 对偶变量法 三 最优性检验 1 闭回路法什么是闭回路 表中的折线构成一条封闭曲线 且所有的边都是水平或垂直的 以确定了初始调运方案的作业表为基础 以一个非基变量作为起始顶点 寻求闭回路 该闭回路的特点是 除了起始顶点是非基变量外 其他顶点均为基变量 对应着填上数值的格 可以证明 如果对闭回路的方向不加区别 对于每一个非基变量而言 以其为起点的闭回路存在且唯一 1 闭回路法 约定作为起始顶点的非基变量为奇数点1其它顶点顺次排列 那麽 该非基变量xij的检验数 现在 在用最小元素法确定例3 2初始调运方案的基础上 计算非基变量X12的检验数 例3 2初始调运方案中以X12 X21 为起点的闭回路 非基变量X12的检验数 非基变量X21的检验数 c12 c23 c13 c22 70 75 100 65 20 c21 c13 c11 c23 80 100 90 75 15 经济含义 在保持产销平衡的条件下 该非基变量增加一个单位运量而成为基变量时目标函数值的变化量 以例3 2初始调运方案为例 设置位势变量和 在初始调运方案表的基础上增加一行和一列 见下页表格 2 位势法 例3 2初始调运方案位势变量对应表 100 100 100 150 2 位势法 然后构造下面的方程组 3 7 方程组的特点 方程个数是m n 1 2 3 1 4个 位势变量共有m n 2 3 5个 通常称ui为第i行的位势 称vj为第j列的位势 初始方案的每一个基变量xij对应一个方程 所在行和列对应的位势变量之和等于该基变量对应的运距 或运价 ui vj cij 方程组恰有一个自由变量 可以证明方程组中任意一个变量均可取作自由变量 给定自由变量一个值 解方程组式 3 7 即可求得位势变量的一组值 根据式 3 6 结合方程组 3 7 推出计算非基变量xij检验数的公式 ij cij ui vj 3 8 在式 3 7 中 令u1 0 则可解得v1 90 v3 100 u2 25 v2 90 于是 12 c12 u1 v2 70 0 90 20 21 c21 u2 v1 80 25 90 15与前面用闭回路法求得的结果相同 位势法计算非基变量xij检验数的公式 ij cij ui vj 3 7 复习比较检验数计算的两种方法 四 方案调整当至少有一个非基变量的检验数是负值时 说明作业表上当前的调运方案不是最优的 应进行调整 若检验数 ij小于零 则首先在作业表上以xij为起始变量作出闭回路 并求出调整量 继续上例 因 12 20 画出以x12为起始变量的闭回路 计算调整量 Min 100 150 100 按照下面的方法调整调运量 闭回路上 偶数顶点的调运量减去 奇数顶点 包括起始顶点 的调运量加上 闭回路之外的变量调运量不变 得到新的调运方案 重复上面的步骤 直至求出最优调运方案 结果最优调运方案是 x11 50 x12 150 x21 50 x23 200相应的最小总运输量为 Zmin 90 50 70 150 80 50 75 200 34000 吨公里 退化问题 1 初始解退化 即初始基变量的个数少于m n 1 必须补足基变量的个数 否则不能正常解出m n个ci和vj2 迭代过程中出现退化闭合回路中标有 的基变量同时有多个达到最小变换后 有多个原基变量变为0 选运费最大者为出变量 其余保留在新的基础解中退化较严重时 可能会出现多次迭代只有值为0的基变量在转移 此时 一要耐心 二要正确选择出变量 运输问题 3 3运输问题的推广 一 产销不平衡的运输问题 增加虚拟销地 增加虚拟产地 产销平衡的运输问题 对应的运距 或运价 运输问题进一步讨论 产销不平衡产销平衡供过于求 即 ai bj 增加一个虚收点Dn 1 bn 1 ai bj 令wi n 1 0 i 1 2 m供小于求 即 ai bj 增加一个虚发点Wm 1 am 1 bj ai 令wm 1 j 0 j 1 2 n 运输问题应用举例 如产地3的产量变为130 又B地区需的115单位必须满足 试重新确定最优调拨方案 得到这样的平衡表后 应用举例1 杭州某电视机厂在三个经济区建立分厂 生产产品销往上海 北京 广州 运价表如下 假定产地2的物资至少运出38个单位 产地3的物资至少运出27个电位 试列出新的运价表 得到这样的平衡表后 应用举例2 已知某运输问题一个最优调运方案如下表 求K值范围 指派问题 例 有一份中文产品说明书需译成英 日 德 俄四种语言 现有甲 乙 丙 丁四人都可以胜任 他们译成不同语言所需时间不同 如下表 求如何分配使所需总时间最少 每人只译一种 整数规划 55 指派问题的标准形式及其数学模型指派问题的标准形式 以人和事为例 是 有n个人和n件事 已知第i人做第j事的费用为Cij i j 1 2 n 要求确定人和事之间的一一对应的指派方案 使完成这件事的总费用最少 如 指派问题 assignmentproblem 例 有一份中文产品说明书需译成英 日 德 俄四种语言 现有甲 乙 丙 丁四人都可以胜任 他们译成不同语言所需时间不同 如下表 求如何分配使所需总时间最少 每人只译一种 建立模型 设xij 1 0 译英文 x11 x12 x13 x14 1 译日文 x21 x22 x23 x24 1 译德文 x31 x32 x33 x34 1 译俄文 x41 x42 x43 x44 1 甲 x11 x21 x31 x41 1 乙 x12 x22 x32 x42 1 丙 x13 x23 x33 x43 1 丁 x14 x24 x34 x44 1 xij 0或1 i 1 2 3 4 j 1 2 3 4 Minz aijxij aij 效率 i 1j 1 44 若第i项工作交与第j个人完成 若第i项工作不交与第j个人完成 57 一般模型 指派问题的标准形式 令 1当指派第i人完成第j项任务0当不指派第i人完成第j项任务 xij minz cijxij xij 1 j 1 2 n xij 1 i 1 2 nxij 1或0 58 匈牙利解法 标准的指派问题是一类特殊的0 1整数规划问题 可以用多种相应的解法来求解 但是 这些方法都没有充分利用指派问题的特殊性质来有效减少计算量 1955年 库恩 W W Kuhn 利用匈牙利数学家康尼格 D K nig 的关于矩阵中独立零元素的定理 提出了指派问题的一种解法 由此 习惯上称之为匈牙利解法 59 匈牙利解法的关键是利用了指派问题最优解的如下性质 若从指派问题的系数矩阵C cij n n的某行 或某列 各元素分别减去一个常数k 得到一个新的系数矩阵C c ij 则以C和C 为系数矩阵的两个指派问题有相同的最优解 匈牙利解法 60 步骤一 变换系数矩阵 使其每行及每列至少有一个零元素 同时不出现负元素 步骤二 进行试指派 即确定独立零元素 步骤三 继续变换系数矩阵 然后返回步骤二 匈牙利解法的一般步骤 61 以上例说明步骤 2151341041415914161378119 01311260101105740142 2497 min cij 匈牙利解法的一般步骤 62 指派问题 assignmentproblem 匈牙利解法的一般步骤以上例说明步骤 01311260101104740142 0042 min 01370606905320100 c ij 指派问题 assignmentproblem 63 以上例说明步骤 01370606905320100 此时加圈0元素的个数m n 4 所以得到最优解 指派问题 assignmentproblem 64 匈牙利解法的一般步骤以上例说明步骤 0001010010000010 xij 指派问题 assignmentproblem 65 匈牙利解法的一般步骤例 指派问题 assignmentproblem 66 匈牙利解法的一般步骤 1279798966671712149151466104107109 76764 50202230000105729800406365 指派问题 assignmentproblem 67 匈牙利解法的一般步骤 50202230000105729800406365 此时加圈0元素的个数m 4 而n 5 所以解题没有完成 独立零元素 加圈零元素 少于n个 表示还不能确定最优指派方案 此时需确定能覆盖所有零元素的最少直线数目的直线集合 方法如下 指派问题 assignmentproblem 68 匈牙利解法的一般步骤 对没有加圈零元素的行打 号 对所有打 号行的所有含零元素的列打 号 再对已打 号的列中含零元素的行打 号 重复2 和3 直到再也不能找到可以打 号行或列为止 对没有打 号的行画一横线 对打 号的列画一竖线 这样就得到能覆盖所有零元素的最少直线数目的直线集合 指派问题 assignmentproblem 69 匈牙利解法的一般步骤 50202230000105729800406365 指派问题 assignmentproblem 70 匈牙利解法的一般步骤继续变换系数矩阵 其方法是在未被直线覆盖的元素中找出一个最小元素 然后在打 号行各元素都减去这一最小元素 而在打 号列的各元素都加上这一最小元素 以保证原来的0元素不变 这样得到新系数矩阵 其最优解和原问题相同 若得到n个独立的0元素 则已得最优解 否则重复该步骤继续变换系数矩阵 指派问题 assignmentproblem 71 匈牙利解法的一般步骤 50202230000105729800406365 最小元素 2 70202430000835011800404143 指派问题 assignmentproblem 72 匈牙利解法的一般步骤 70202430000835011800404143 此时加圈0元素的个数m 5 而n 5 独立零元素 加圈零元素 等于n个 此时已得到最优解 其解矩阵为 指派问题 assignmentproblem 73 匈牙利解法的一般步骤 xij 0100000100000010001010000 最优指派 甲 B乙 C丙 E丁 D戊 A 指派问题 assignmentproblem 74 在实际应用中 常会遇到各种非标准形式的制派问题 一般的处理方法是先将其转化为标准形式 然后再用匈牙利法求解 最大化指派问题 设最大化指派问题系数矩阵C cij 其中最大元素为m 令矩阵B bij m cij 则以B为系数矩阵的最小化指派问题和以C为系数矩阵的最大化指派问题有相同最优解 人数和事数不等的指派问题 若人少事多 则添加一些虚拟的 人 其费用系数取0 若人多事少 则添加一些虚拟的 事 其费用系数取0 非标准形式的指派问题 75 非标准形式的指派问题一个人可做几件事的指派问题 若某个人可以做几件事 则将该人化作几个 人 来接受指派 这几个 人 做同一件事的费用系数当然都一样 某事一定不能由某人做的指派问题 若某事一定不能由某人做 则可将相应的费用系数取为足够大的数M 非标准形式的指