第四章运输问题

运输问题 4 1运输问题及其数学模型 典型背景 单一物资运输调度问题设某种物品有 m个产地 产量 n个销地 销量 从产地到销地的单位运价是 求总运费最小的调度方案 决策变量表示由到的物品数量 产销平衡问题 总产量 总销量即产销不平衡问题 总产量 总销量 总产量 总销量总产量 总销量 产销平衡问题的数学模型 运输问题数学模型的特点 运输问题有有限最优解运输问题约束条件的系数矩阵约束条件系数矩阵每一列只有两个1 其余为0 对产销平衡问题约束条件均为等式 且产量之和 销量之和 约束条件的独立方程最多有m n 1个 即 i j 其中 4 2运输问题的解法 表上作业法 表上作业法是单纯形法在求解运输问题的一种简便方法 单纯形法与表上作业法的关系 1 找出初始基可行解 2 求各非基变量的检验数 3 判断是否最优解 换基 4 确定换入变量和换出变量找出新的基可行解 5 重复 2 3 直至求出最优解 停止 例1 举例说明表上作业法 某部门三个工厂生产同一产品的产量 四个销售点的销量及单位运价如下表 第一步 确定初始基可行解 最小元素法 伏格尔法 最小元素法思路 就近供应 即优先供应单位运价小的收点与发点之间的业务 最小元素法缺点 会出现顾此失彼 运费差额问题 8 2 2 0 10 10 0 6 14 8 6 8 0 0 0 0 6 0 最小元素法举例 最小元素法举例 伏格尔法 Vogel 最小元素法的缺点是 为了节省一处的费用 有时会造成在其他处要多花几倍的运费 伏格尔法考虑到 一产地的产品假如不能按最小运费就近供应 就应考虑次小运费 这就有一个差额 差额越大 说明不能按最小运费调运时 运费增加越多 因而对差额最大处 就应当采用最小运费调运 伏格尔法基本步骤 在运价表中分别计算出各行和各列的最小运费和次小运费的差额 并填入该表的最右列和最下行 从行或列差额中选出最大者 选择它所在行或列中的最小元素 按类似于最小元素法优先供应 划去相应的行或列 对表中未划去的元素重复1 2步 直至所有的行和列划掉为止 3 1 5 6 3 2 二 解的最优性检验 思路 计算空格 非基变量 的检验数 求空格检验数的两种方法 1 闭回路法 2 位势法 闭回路法 闭回路 闭回路是以某空格为起点 用水平或垂直线向前划 每碰到一数字格转90度后继续前进 直至回到起始空格为止 所形成的回路 注 1 每一空格有且仅有一条闭回路 2 如果某数字格有闭回路 则此解不是可行解 若令则 运费的增量 分析 从初始表分析 要保证产销平衡 则 称为闭回路 2 1 检验数表 2 1 1 1 10 12 表中的解不是最优解 位势法 设是对应运输问题的m n个约束条件的对偶变量 因基变量的检验数等于0 即cij ui vj 0 可以求出ui vj的值 又利用 cij ui vj 即可求出各非基变量的检验数 方法 1 在给定初始解的表上增加一行和一列 在列中填入ui 在行中填入vj 2 令u1 0 再按cij ui vj 0 基变量的cij求出其余的ui与vj 3 再运用 cij ui vj 求出非基变量的检验数 位势表 1 0 2 1 9 4 8 检验数表 若所有检验数非负则是最优解 三 解的 改进 调整 闭回路法 当在表中空格处出现负检验数时 表明未得最优解 若有两个或两个以上的负检验数时 一般选用其中最小的负检验数 以它对应的空格为调入格 即以它对应的非基变量为换入变量 做一闭回路 闭回路法进行解的调整的步骤 1 取一个检验数最小的非基变量作进基变量 其对应的格为进基格 以进基格为起始点作其闭回路 在该闭回路上 从所有偶数号格点的调运量中选出最小值作为调整量 该格即为离基格 对应的变量即为离基变量 2 对闭回路上的运输量作出调整 所有奇数号格的调运量加上调整量 所有偶数号格的调运量减去 其余的不变 这样就得到一个新的调运方案 即一个新的基可行解 三 解的 改进 调整 闭回路法 调整位置 1 1 非空 回路角上的格至少为空 且保证数字的非负性 2 2 2 2 调整后的解为 此时的解为最优解 有无穷多最优解 表上作业法计算中的问题 1 无穷多最优解空格的检验数为零2 退化确定初始方案时候闭合回路调整时 最小元素法中的退化情况 3 6 0 5 4 2 出现退化时 要在同时被划去的行列中任选一个空格填0 此格作为有数字格 作业 1 用表上作业法求出最优解 2 用伏格尔法直接给出近似最优解 1 这是一个产销平衡的问题 1 初始调运方案 最小元素法 40 15 20 25 10 25 初始调运方案的总运费为420元 2 最优解的判别 闭环回路法 3 调整调运方案 得新的方案 以 22 格为调入格 以此格为出发点 作一闭环回路 经检验 所有检验数都大于0 该调运方案是最优的方案 总运费为395元 2 用伏格尔法直接给出近似最优解 5 20 20 25 20 10 0 0 用伏格尔法直接找到了近似最优方案 总运价为305元 第二种算法 用伏格尔法直接找到了近似最优方案 总运价为345元 四 产销不平衡运输问题 解决原则 将产销不平衡运输问题转变为产销平衡运输问题 方法 当产 销 即 只要增加一个假想的销地j n 1 实际上是贮存 该销地总需要量为 而在单位运价表中从各产地到假想销地的单位运价为0 就转化为一个产销平衡运输问题 产销不平衡运输问题 当销大于产时 可以在产销平衡表中增加一个假想的产地i m 1 该地产量为 在单位运价表上令从该假想产地到各销地的运价为0 同样可以转化为一个产销平衡的运输问题 例设有三个化肥厂供应四个地区的农用化肥 假定等量的化肥在这些地区使用效果相同 各化肥厂年产量 各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如下表所示 试求出总的运费最节省的化肥调运方案 三个化肥厂共可供应化肥160吨 问 根据现有三个化肥厂的产量 地区IV最高需求是否可以不限 最高需求是多少 160 30 70 0 60吨四个地区对化肥的最高需求为50 70 30 60 210吨 练习求下列运输问题 五 运输问题的应用 一 生产与储存的问题例某厂按合同规定须于当年每个季度末分别提供10 15 25 20台同一规格的柴油机 已知该厂各季度的生产能力及市场每台柴油机的成本如下表所示 又如果生产出来的柴油机当季不交货的 每台每积压一个季度需储存 维护费用0 15万元 要求在完成合同的情况下 做出使该厂全年生产 包括储存 维护 费用最小的决策 设Xij为第i季度生产的用于第j季度交货的柴油机数实际的成本为该季度生产成本加上储存和维护费用 四个季度的生产能力为100台 而四个季度末共须提供柴油机70台 二 调度问题 例某航运公司承担六个港口初始A B C D E F的四条固定航线的物资运输任务 已知各条航线的起点 终点城市及每天航班数见下表1 假定各条航线使用相同型号的船只 又各城市间的航程天数见表2 又知每条船只每次装卸货的时间各需1天 则该航运公司至少应配备多少条船 才能满足所有航线的运货需求 表1 表2 1 载货航程需要的周转船只数 例如 航线1 在港口E装货1天 E D航程17天 在D卸货1天 总计19天 每天3航班 故该航线需周转船57条以上共需周转船只数91条 2 各港口间调度所需船只数 有些港口每天到达船数多于需要船数 例如 港口D 每天到达3条 需求1条 为使各港口间调度周转所需的空船数最少 其产销平衡表如下 单位运价应为相应各港口之间的船只航程天数 可求出空船的最优调度方案如下 由上表可计算得知最少周转的空船数为40条 所以 在不考虑维修 储备等情况下 该公司至少应配备131条船 三 转运问题例 某电子仪器公司在大连和广州有两个分厂 大连分厂每月生产400台某种仪器 广州分厂每月生产600台某种仪器 该公司在上海与天津有两个销售公司负责对南京 济南 南昌与青岛四个城市的仪器供应 又因为大连与青岛相距较近 公司同意大连分厂也可以向青岛直接供货 这些城市间的每台仪器的运输费用我们标在两个城市间的弧上 单位为百元 问应该如何调运仪器 使得总的运输费最低 思路 将转运问题化为无转运问题 中转地3 4既可作为产地 也可作为销地 例 某公司经销甲产品 它下设三个加工厂 每日的产量分别为A1 7吨 A2 4吨 A3 9吨 该公司把这些产品分别运往四个销售点 各销售点每日销量为B1 3吨 B2 6吨 B3 5吨 B4 6吨 已知从各工厂到各销售点的单位产品的运价如下表所示 如果假定1 每个工厂生产的产品不一定直接发运到销售点 可以