运输问题和指派问题.ppt

第五章运输问题和指派问题 第一节运输问题的数学模型 运输问题的一般描述 某种物质 粮食 棉花 煤等 有若干个产地和销地 现在需要把物质从各个产地运往各个销地 产量总数等于销量总数 调运方案很多 若已知各产地的产量 各销地的销量以及各产地到销地的单位运价 或运输距离 又假定运费和运输量成正比 问如何调运 才能使总运费最省 第一节运输问题的数学模型 设Xij为第i个产地运往第j个销地的数量这是m n个变量 约束条件为m n个的线性规划问题 MinZ CijXij xij ai i 1 2 m xij bj j 1 2 n xij 0 i 1 2 m j 1 2 n 第一节运输问题的数学模型 一 运输问题约束条件系数矩阵 A 11 1111 1 11 111 1111 111 m n mn 第一节运输问题的数学模型 二 运输问题的基变量共有m n 1个三 m n 1个变量构成基变量的充要条件是它们不构成闭合回路 第二节表上作业法 表上作业法求解运输问题的思路和单纯形法完全类似 建立作业表 确定初始调运方案 现行方案的最优性检验 现行方案的调整 第二节表上作业法 一 初始方案的确定 1 西北角法 左上角法 从表的左上角开始 保证产销平衡 每填上一个数划去一行或一列 直到有m n 1行或列划去即可 填上数字为基变量 从而保证其个数为m n 1个又不构成闭合回路 第二节表上作业法 一 初始方案的确定 2 最小元素法采用 就近供应 的思想 从运输表的运费最小的元素开始 保证产销平衡 每填上一个数划去一行或一列 直到有m n 1行或列划去即可 填上数字为基变量 从而保证其个数为m n 1个又不构成闭合回路 第二节表上作业法 一 初始方案的确定 3 元素差额法 Vogel近似法 是在最小元素法基础上的改进 求每行和每列的行罚数和列罚数从行罚数和列罚数最大的行或列的运费最小的元素开始 保证产销平衡 每填上一个数划去一行或一列 重复 和 直到有m n 1行或列划去即可 填上数字为基变量 从而保证其个数为m n 1个又不构成闭合回路 第二节表上作业法 二 最优性检验1 闭合回路法 2 位势法 三 调整 表上作业法的几点说明 1 若运输问题的某一基可行解有多个非基变量的检验数为负时 在迭代时可取它们中任一非基变量进基均可使目标函数值得到改善 但通常取最小者对应的非基变量进基 2 当迭代到最优解时 有某非基变量的检验数为0时 则问题有无穷多最优解 3 当在表上作业时 同时划去了一行和一列运输价格时 就出现了退化 此时必须在当前划去的运价中某一空格填入一个0 表示该格中的变量是取值为0的基变量 第三节产销不平衡的运输问题 一 产大于销的运输问题虚设销地 其需要量为 ai bj 相应的运费为0 化成产销平衡的运输问题 MinZ CijXij xij ai i 1 2 m xij bj j 1 2 n xij 0 i 1 2 m j 1 2 n 第三节产销不平衡的运输问题 一 销大于产的运输问题虚设产地 其产量为 bj ai 相应的运费为0 化成产销平衡的运输问题 MinZ CijXij xij ai i 1 2 m xij bj j 1 2 n xij 0 i 1 2 m j 1 2 n 14 第四节指派问题 指派问题的标准形式 以人和事为例 是 有n个人和n件事 已知第i人做第j事的费用为Cij i j 1 2 n 要求确定人和事之间的一一对应的指派方案 使完成这件事的总费用最少 如 15 第四节指派问题 一 指派问题的标准形式及其数学模型令 1当指派第i人完成第j项任务0当不指派第i人完成第j项任务 xij minz cijxij xij 1 j 1 2 n xij 1 i 1 2 nxij 1或0 16 第四节指派问题 二 指派问题的匈牙利解法标准的指派问题是一类特殊的0 1整数规划问题 可以用多种相应的解法来求解 但是 这些方法都没有充分利用指派问题的特殊性质来有效减少计算量 1955年 库恩 W W Kuhn 利用匈牙利数学家康尼格 D K nig 的关于矩阵中独立零元素的定理 提出了指派问题的一种解法 由此 习惯上称之为匈牙利解法 17 第四节指派问题 二 指派问题的匈牙利解法匈牙利解法的关键是利用了指派问题最优解的如下性质 若从指派问题的系数矩阵C cij n n的某行 或某列 各元素分别减去一个常数k 得到一个新的系数矩阵C c ij 则以C和C 为系数矩阵的两个指派问题有相同的最优解 匈牙利解法的一般步骤步骤一 变换系数矩阵 使其每行及每列至少有一个零元素 同时不出现负元素 步骤二 进行试指派 即确定独立零元素 步骤三 继续变换系数矩阵 然后返回步骤二 19 第四节指派问题 指派问题 assignmentproblem 匈牙利解法的一般步骤 对没有加圈零元素的行打 号 对所有打 号行的所有含零元素的列打 号 再对已打 号的列中含零元素的行打 号 重复2 和3 直到再也不能找到可以打 号行或列为止 对没有打 号的行画一横线 对打 号的列画一竖线 这样就得到能覆盖所有零元素的最少直线数目的直线集合 20 指派问题 assignmentproblem 匈牙利解法的一般步骤以上例说明步骤 2151341041415914161378119 01311260101105740142 2497 min cij 21 指派问题 assignmentproblem 匈牙利解法的一般步骤以上例说明步骤 01311260101104740142 0042 min 01370606905320100 c ij 22 指派问题 assignmentproblem 匈牙利解法的一般步骤以上例说明步骤 01370606905320100 此时加圈0元素的个数m n 4 所以得到最优解 23 指派问题 assignmentproblem 匈牙利解法的一般步骤以上例说明步骤 0001010010000010 xij 24 指派问题 assignmentproblem 匈牙利解法的一般步骤例 25 指派问题 assignmentproblem 匈牙利解法的一般步骤 1279798966671712149151466104107109 76764 50202230000105729800406365 26 指派问题 assignmentproblem 匈牙利解法的一般步骤 50202230000105729800406365 此时加圈0元素的个数m