运输问题的特殊解法.ppt

表上作业法图上作业法 第三章运输问题的特殊解法 TransportationProblem 第一节运输问题的表上作业法 一 运输问题的数学模型及其特点 设某种物品有m个产地A1 A2 Am 各产地的产量分别是a1 a2 am 有n个销地Bl B2 Bn 各销地的销量分别为bl b2 bn 假定从产地Ai i 1 2 m 向销地Bj j 1 2 n 运输单位物品的运价是cij 问怎样调运这些物品能使总运费最小 这是由多个产地供应多个销地的单品种物资运输问题 为直观清楚起见 可将数据汇总于产销平衡表和单位运价表中 1 产销平衡时 矩阵形式 2 产大于销时 3 产小于销时 特征运输问题的基本可行解中应包括m n 1个基变量平衡运输问题必有可行解 也必有最优解 二 表上作业法的思路和步骤 步骤 1 确定初始调运方案2 解的最优性判断3 调整方案4 重复2 3 步 直到找到最优方案 找到初始基可行解 最优性判断 调整找到新的基可行解 重复2 3步直到找到最优解 例1某部门有3个生产同类产品的工厂 产地 生产的产品由4个销售点出售 各工厂的有关资料如下表 问应怎样调运才使总运费最少 一 确定初始调运方案 解题步骤 1 在运价表中找到最小运价c1k 2 将的Al产品给Bk 若al bk 则将al改写为al bk 划掉bk 同时将运价表中k列的运价划掉 若al bk 则将bk改写为bk al 划掉al 同时将运价表中l行的运价划掉 3 如此重复 1 2 直到分配完毕 对应的目标函数值为 z 3 4 12 3十1 3十2 1 4 6十5 3 92 元 3 1 4 6 3 3 3 1 3 4 3 2 西北角法思路 该法优先满足运输表中西北角上空格的供销需求 3 4 2 2 3 6 对应的目标函数值为 z 3 3 11 4十9 2十2 2 10 3十5 6 135 元 解题步骤 1 计算运输表中每一行和每一列的次小单位运价和最小运价之间的差值 2 从行或列差中选择最大者 选择它所在行或列中的最小元素clk 将Al的产品优先供应Bk 同时将运价表中已满足的行或列划掉 3 如此重复 1 2 直到分配完毕 5 1 3 0 1 1 6 1 2 5 2 4 3 3 3 3 1 2 5 对应的目标函数值为 z 3 2 3 5十1 1十8 3 4 6十5 3 85 元 注 伏格尔法除确定供求关系的原则与最小元素法不同外 其余步骤与最小元素法相同 与最优解的接近程度 伏格尔法 最小元素法 西北角法 2 二 解的最优性检验 求出各非基变量的检验数 判别是否均不小于0 如果是 则得到最优解 停止计算 否则转入下一步 注 因为目标函数要求最小化 所以 ij0表示运费增加 表格中有调运量的地方为基变量 空格处为非基变量 基变量的检验数 ij 0 需计算非基变量的检验数是否不小于0 利用最小元素法形成的初始调运方案进行说明 解题步骤 1 编制位势表在运输问题的单价表中的基变量处画圈 同时在表中增加一行 列位势 和一列 行位势 2 填写位势数任选第一个位势数填入表中 其余按ul vk clk填写 基变量的 ij 0 3 计算检验数对运价表没画圈的cij按 ij cij ui vj 计算检验数 运价表 位势表 2 1 3 0 12 7 11 三 调整方案 闭回路法 实质 单纯形法的换基迭代 调整步骤 1 作第一个出现负检验数 ij的闭回路 2 求调整量 奇拐角点处的最小运量 3 调整 奇拐角点处的各运量均减去 偶奇拐角点处的各运量均加上 不在闭回路上的格子运量不变 1 1 1 1 1 1 检验数 1 1 1 1 12 3 11 3 7 2 0 12 3 11 5 7 4 0 检验数 2 2 2 2 所有 ij 0 得到最优解z 3 2 3 5十1 1十8 3 4 6十5 3 85 元 10 3 9 3 5 2 0 练习 某部门有3个生产同类产品的工厂 产地 生产的产品由4个销售点出售 各工厂的有关资料如下表 问应怎样调运才使总运费最少 8 2 10 2 10 6 6 6 14 8 8 利用位势法对上述方案进行检验 2 1 0 3 10 5 10 2 2 2 2 2 利用位势法对上述方案进行检验 2 2 0 2 9 3 8 所有 ij 0 得到最优解 最小运费为244元 三 关于表上作业法的几点说明 1 关于初始方案中运量填为 0 的规定 在编制初始调运方案时 如果当填上运量xij后 第i行的发量已发完 同时第j列的收量已收足 此时不能把运价表中的第i行和第j列都划去 而只能划去第i行 或第j列 此后再出现最小运价为 ckj 或 cit 时 尽管Bj已收足 或Ai已发完 但仍要在格子xkj 或xit 上填上 0 并把这个填 0 的格子与其他有运量的格子一样看待当收点个数为n 发点个数为m时 在方案表中 填有运量的格子数必须是m n 1个 例如 假设一个物资调运问题的平衡表和运价表如下 试用最小元素法确定初始调运方案 3 0 2 2 4 3 0 2 2 4 2 4 2 4 2 关于调整方案中运量填为 0 的规定 当奇拐角点中有多个运量都是 时 那么调整以后就会有多个奇拐点处的运量同时变为零 这时我们规定 把最上一行 最左边那个运量变为零的奇拐角点当作空格 而把其他几个拐角点处的运量填作 0 并把它们当作有运量的格子一样看待 若一个运输问题的最优调运方案表中 某个空格 非基变量 xkt对应的检验数 kt 0 那么该运输问题必有另一个最优调运方案 这个新的最优调运方案可以通过在原最优调运方案表上 沿 kt对应的空格作闭回路调整而得到 事实上 调整后总运费的减少数 kt 0 因 kt 0 可见新旧方案对应的总运费不变 因此调整后的调运方案必然仍为最优方案 3 最优方案不唯一的情况 单纯形法中 如果一个线性规划问题的最优基对应的单纯形表中某个非基变量对应的检验数等于零 那么该线性规划问题的最优解可能不唯一 例如 一个物资调运问题的平衡表及运价表如下 计算表中检验数发现 11 0 35 0 过相应的空格对上表中的最优调运方案作调整 可得下面两个表 4 产销不平衡情况的处理方法 思路 先将原问题变为平衡问题 再用前面的方法确定调运方案产大于销 增加假想销地 设定销量 运价为0 销大于产 增加虚拟产地 设定假想产量 运价为0 2 1 4 2 5 1 2 3 10 21 21 14 90 7 0 15 2 3 12 18 3 0 0 4 4 2 2 7 9 1 10 10 采用伏格尔法得初始调运方案 先将运价表中的0列划去 采用位势法进行最优性检验 0 0 3 7 3 8 1 3 6 计算检验数 练习水泥调运的产销不平衡情况及运价表 如下表所示 试求最优调运方案 在平衡表中增加库存一列 同时在运价表也相应地增加一列 该列的运价都是零 于是就得到一个新的平衡表和运价表 四 作物布局问题的表上作业法 例3某农场有土地9公顷 这些土地因土壤的肥沃程度和水源条件不同 可以分成三类 现在农场要在这三类土地上计划种植三种作物 各类土地面积 计划种植面积 以及各种作物在各类土地上的亩产量如下表所示 问应如何因地制宜安排作物布局 才能使作物总产量最多 目标函数求极大 解 1 确定初始种植方案 用最大元素法编制初始方案 1 3 1 4 1 1 0 2 最优方案的判别 用闭回路法计算检验数 如果所有检验数 0 就可判定这个方案是最优方案 否则 就要对方案进行调整 对于这个例子的初始方案 因为 11 50 所以需要调整 ij 偶拐角点亩产总和 奇拐点亩产总和 3 方案调整 用闭回路法调整种植方案 过第一个出现的正检验数对应的空格 作一闭回路 在闭回路奇拐角点的数字中找一个最小的数作为调整量 然后 在这条闭回路上 凡奇拐角点的数减去调整数 凡偶拐角点的数加上调整数 便得新的种植方案 初始方案经过调整后 得新方案如下表所示 注 也可用伏格尔法或西北角法确定初始种植方案用位势法计算检验数 第二节运输问题的图上作业法 一 物资调运流向图 适用范围 单位运价与运输距离成正比 总运费最小等价于周转量最小 交通图 收发点的大致相对位置流向图 在交通图上 发点用圈 表示 发货量记在圈 内 收点用方框 表示 收货量记在方框 内 相邻两收发点间的交通线称为一条 边 交通线的长度称为该两点的间距或边长 其数值记在交通线的旁边物资调运的方向称为流向 用 表示 并把 画在交通线前进方向的右侧 把通过的物资数量 称为流量 记 的右侧 并加上括号 二 最优调运方案的判定标准 如果一个物资调运流向图中 既没有对流运输 又没有迂回运输 那么该流向图就是最优流向图 对应的调运方案就是最优方案 1 对流运输 在物资调运流向图中 如果在一条边上同时标有两个相反的流向 就称在这条边上存在对流运输 如果一个物资调运流向图中的任何一条边上都没有对流 就称该流向图无对流 5 5 10 10 5 10 5 2 迂回运输 在交通图成圈的情况下 物资调运流向图中 有些流向画在圈内 称为内圈流向 有些流向画在圈外 称为外圈流向 内圈流向对应的各边边长之和称为内圈长 记为L内 外圈流向对应的各边边长之和称为外圈长 记为L外 该圈全部边长之和称为全圈长或总圈长 记为L总 20 10 30 30 20 10 三 图上作业法的一般步骤与方法 借助交通示意图编制既无对流又无迂回的物资调运流向图 求得最优物资调运方案的一种方法 步骤 1 编制无对流流向图 2 检查有无迂回 若无迂回 已得到最优流向图 若有迂回 转为下一步 3 利用交通图进行调整 重复第 2 步 直至没有迂回为止 4 根据最优流向图制定最优调运方案 1 交通图不成圈的情况 例1有某种物资17万吨 由Al A2 A3 A4出发 发量分别为5万吨 2万吨 3万吨 7万吨 收点是Bl B2 B3 B4 收量分别为8万吨 1万吨 3万吨 5万吨 收发平衡 交通图如下图所示 问应如何调运 可使周转量最小 7 5 1 2 1 2 5 1 作无对流流向图方法 由各端点开始 由外向里 逐步进行各收发点之间的供求平衡 标明物资的流向和流量 2 依最优流向图编制最优调运方案 2 交通图中有圈的情况 例2有某种物资21万吨 由发点A1 A2 A3 A4发出 发量分别为5万吨 8万吨 2万吨 6万吨 收点为B1 B2 B3收量分别为8万吨 7万吨 6万吨 收发量平衡 交通图如下图所示 问应如何调运 可使吨公里最小 1 作无对流的流向图 具体作法是 用丢边破圈 的方法 丢一条边 破一个圈 直至把有圈的交通图变成不成圈的交通图 然后在不成圈的新交通图上作无对流的流向图 选择最长的边丢掉 4 3 5 1 7 6 2 8 在作完无对流流向图之后 再把丢掉的边补回去 使交通图恢复原样 本例中 补回丢掉的边A3B1 和B2B3 就得到有圈的流向图 2 检查有无迂回 具体作法是 对流向图中只有一边没有流向的各圈进行检查 3 调整 对有迂回的圈进行调整 再检查有无迂回 注 1 调整后需重新检查每个只有一条边无流量的圈 2 若同时有几条边流量变为0 只能将其中一条边为无流向的边 一般取边长最大者 其余边看作流量为0 4 编制调运方案