简单三-运输问题.ppt

1 第三章运输问题 运输问题约束条件的系数矩阵具有特殊的结构 有更为简单的求解方法 从而节约大量的计算时间和费用 2 产地 m个 Ai表示 i 1 2 m 产量ai i 1 2 m 表3 1 要求使总运费最小的调运方案 Cij 从Ai到Bj运输单位物资的运价 销售地 n个 Bj表示 j 1 2 n 销售量bj j 1 2 n 3 1 运输问题的数学模型 3 产销平衡运输问题 数学模型解 假设xij表示从Ai到Bj的运量 则所求的数学模型为 总产量等于其总销量 即 4 LP问题 m n个变量 m n个约束条件 单纯形法求解 在每个约束上加入一个人工变量若m 4 n 5 变量个数就有29个之多 非常复杂 5 1 基本概念与重要结论系数矩阵特点 1 元素等于0或1 2 每列只有两个元素为1 其余都是0 3 每一个变量 在前m个约束方程中只出现一次 在后n个约束方程中也只出现一次 3 2表上作业法 6 运输问题的解 代表着一个运输方案变量xij的值 由Ai调运数量为xij的物品给Bj 基变量 m n 1个 只有m n 1个约束条件是线性独立的 进一步我们想知道 怎样的m n 1个变量会构成一组基变量 7 8 基本概念闭回路 顶点 出现在闭回路中的变量闭回路的边 相邻两个变量用一条直线相连 x11 x12 x32 x34 x24 x21构成一个闭回路 9 10 定理3 1 m n 1个变量构成基变量的充分必要条件是它不包含有任何闭回路 11 求解运输问题的一种简化方法 实质是单纯形法 1 找初始基可行解 即在 m n 产销平衡表上给出m n 1个数字格 不能构成闭回路 且行和等于产量 列和等于销售量 2 求非基变量检验数 在表上求出空格的检验数 判别是否达到最优解 如果达到最优解 则停止计算 否则转入下一步 3 确定换入变量和换出变量 找出新的基可行解 在表上用闭回路法进行调整 4 重复 2 3 步 直到求得最优解为止 2 表上作业法 12 基本思想 就近供应 即从单位运价表中最小的运价开始确定产销关系 依次类推 直到给出初始方案为止 1 确定初始基可行解 方法一 最小元素法 例3 2某公司有3个生产同类产品的工厂 生产的产品由4个销售点销售 各工厂的生产量 各销售点的销售量以及各工厂到各销售点的单位产品运价如表3 5所示 问该公司应如何调运产品 在满足各销售点的需要量的前提下 使总的运费为最小 13 表3 5 3 1 14 方案的总运费为86元 15 两种特殊情况 多个元素同时最小 任选一个作基变量 对于最小元素 发现该元素所在行的剩余产量等于该元素所在列的剩余销售量 这时在产销平衡表相应的位置填上一个数 而在单位运价表中就要同时划去一行和一列 为了使调运方案中有数字的格仍为 m n 1 个 需要在同时划去的行或列的任一空格位置添上一个 0 这个 0 表示该变量是基变量 只不过它取值为0 即此时的调运方案是一个退化的基可行解 16 单位产品运价如表3 8所示 利用最小元素法 求初始调运方案 例3 3 初始调运方案 如表3 9 17 伏格尔法一产地的产品 假如不能按最小运费就近供应 就考虑次小运费 这就有一个差额 差额越大 说明不能按最小运费调运时 运费增加就越多 因此 对于差额最大处 就优先采用最小运费调运 方法二伏格尔法 最小元素法缺点为节省一处的费用 有时造成在其它地方要花多几倍的运费 18 表3 10 19 6 3 3 1 5 2 2 2 20 目标函数是要求最小化 所以当所有的非基变量检验数全都大于等于0时为最优解 求空格检验数 方法一 闭回路法 方法二 位势法 2 最优解的判别 21 方法一 闭回路法 例 检验数的经济解释 保持产销平衡 检验数 调整方案使运费的改变量 1 3 1 3 1 2 1 1 1 元 22 所有空格检验数 表3 13 表3 7不是最优解 还需要进一步改进 1 23 m n个未知量u1 um v1 vn 由上述基本可行解可构造如下一个方程组 是一组基可行解 现在引进 方法二 位势法 其中cij为单位运价 方程组 3 2 共有m n个未知数和m n 1个方程 3 2 的解存在且恰有一个自由变量 称u1 um为行位势 v1 vn为列位势 24 定理3 2设已给了一组基本可行解 则对每一个非基变量xij来说 它所对应的检验数为 ij cij ui vj 25 仍以例3 2所给出的初始基可行解表3 7为例 先令u1 0 然后按ui vj cij i j 基变量指标集 相继确定ui vj 0 10 5 9 3 1 2 26 计算所有的空格检验数 ij cij ui vj i j 还有负检验数 未得到最优解 进一步进行改进 1 2 1 1 10 12 11 c11 u1 v1 3 0 2 1 27 若有两个或两个以上的检验数为负时 一般选择其中最小的负检验数 以它对应的空格为调入格 即以它对应的非基变量为换入变量 由表3 16可知 A2 B4 为调入格 即以它对应的变量x24为换入变量 以此格为出发点 作一闭回路 如表3 17所示 基可行解改进的方法 闭回路调整法 28 闭回路上 1 数字格中的最小者 即 min 1 3 1然后按闭回路上的正 负号 加入和减去此值 得到调整方案 A2 B4 格的调入量 29 再用闭回路法或位势法求表3 18各空格的检验数 检验数都大于等于0 表3 18为最优解 总运费最小值是85元 30 产销平衡的运输问题必定存在最优解 那么有唯一最优解还是无穷多个最优解 依据仍然是看非基变量 即空格处 的检验数是否有为0的 若有 则存在无穷多个最优解 否则 只有唯一最优解 表3 19 例3 2有无穷多个最优解 31 最优表3 18中以 A1 B1 为调入格 作闭回路 q min 2 3 2 经调整后得到另一个最优解 32 调入量0 2中的任一实数 这时的解仍为最优解 表3 21不是基可行解线性规划问题可以在顶点取到最优解 也可在非顶点即是边界点上取到最优解 33 转化为产销平衡 3 3 产销不平衡的运输问题及其求解方法 当产大于销时 34 多余的物资在那一个产地贮存的问题 设xin 1是产地Ai的贮存量 故有 产量大于销量 35 将其分别代入 得到 这是一个产销平衡的运输问题 36 销大于产 37 设有三个化肥厂供应四个地区的农用化肥 假定等量的化肥在这些地区使用的效果相同 各化肥厂年产量 各地区年需要量及从各化肥厂到各地区运送单位化肥的运价表如表3 22所示 试求出总的运费最省的化肥调拨方案 例3 4 38 表3 22单位运价 万元 万吨 39 表3 24最优调运方案 由于在变量个数相等的情况下 表上作业法的计算远比单纯形法的计算简单得多 所以在解决实际问题时 人们常常尽可能把某些线性规划问题化为运输问题的数学模型 40 某厂按合同规定须于当年每个季度末分别提供10 15 25 20台同一规格的柴油机 已知该厂各季度的生产能力及生产每台柴油机的成本如表3 25所示 又如果生产出来的柴油机当季不交货 每台每季度需存储费 维护费等共0 15万元 要求在完成合同的情况下 做出使该厂全年生产 包括储存 维护等 费用最小的决策 表3 25 例3 5 41 解 设xij表示为第i季度生产的用于第j季度交货的柴油机数 生产能力限制x11 x12 x13 x14 25x22 x23 x24 35x33 x34 30 x44 10 合同要求x11 10 x12 x22 15x13 x23 x33 25x14 x24 x34 x44 20 42 ai 第i季度生产能力bj 第j季度的合同供应量则问题可写成 xij的单台实际成本cij 该季度单位成本 储存 维护等费用 cij的具体数值见表3 26 43 产大于销注意 当i j时 xij 0 应令对应的cij M 加一个假想的需求季度V 变成产销平衡 表3 27产销平衡表与单位运价表 44 表上作业法求解 可得多个最优方案表3 28中列出最优方案之一该厂总生产 储存 维护 费用 773万元 表3 28最优调运方案 45 3 4转运问题 转运问题 运输问题的一个扩充 产销地之间再增加中转点 在转运问题中我们还允许把物品一个产地运往另一个产地或中转点或销地 也允许把物品从一个中转点运往另一个中转点或产地或销地 也允许把物品从一个销地运往另一个中转点或产地 在每一个产地的供应量都有一个限量 而每一个销地的需求量也都有一个限制 任意两点间的单位物品的运价已知 如何使总的运输费最小 46 例3 5 某公司有三个分厂生产某种物资 分别运往四个地区的销售公司去销售 有关分厂的产量 各销售公司的销量及运价如表3 29所示 求总的运费最小的调运方案 这是一个普通的产销平衡运输问题 但是如果假定 47 1 每个分厂的物资不一定直接发送到销地 可以从其中几个产地集中一起运 2 运往各销地的物资可以先运给其中几个销地 再转运给其它销地 3 除产地 销地外 还有几个中转站 在产地之间 销地之间或产地与销地之间转运 各产地 销地 中转站及相互之间每吨物资的运价如表3 30所示 问在考虑产销之间直接运输和非直接运输的各种可能方案的情况下 如何将三个分厂的物资运往销售公司 使总的运费最少 48 表3 30 1 由于问题中的所有产地 销地 中转站都可以看成产地 也可以看成销地 因此整个问题可以看成是一个由11个产地和11个销地组成的运输问题 2 对于扩大的运输问题建立运价表 表中的不可能运输方案的运价用M代替 3 所有中转站的产量等于销量 也即流入量等于流出量 由于运费最少时不可能出现物资的来回倒运现象 因此每个中转站的运量不会超过20吨 所以可以规定中转站的产量和销量均为20吨 这样就可以得到扩大的产销平衡运输问题及其运价表 如表3 31 50 表3 31 51 利用表上作业法求得最优解如表3 32 52 3 5案例分析3 5 1报刊征订 推广费用的节省问题 1 问题的提出中华图书进出口总公司的主营业务之一就是中文书刊对国外出口业务 由中文书刊出口部及深圳分公司和上海分公司负责 就中文报刊而言 每年10 12月为下一年度报刊订阅的征订期 在此期间 为巩固老订户 发展新订户 要向国外个人 大学图书馆 科研机构等无偿寄发小礼品和征订宣传推广材料 2 有关数据由于中文书刊的出口的订户大部分集中在日本 韩国以及香港地区 因此公司要根据订户的分布数量的不同 寄发征订材料的数量也就不同 由于三个部门都同属于中华图书进出口总公司 为了避免内部恶性竞争 三个部门所寄宣传材料的数量由总公司统一安排 一般情况下 这些材料无论由三家中那一家寄出 征收用户的效果大致相同 同时无论读者向那个部门订阅 为总公司创造的利润大致相同 但由于各部门与三个用户的距离不同 邮寄方式及人工费用不同 导致从各部门寄往各地的费用也不同 53 表3 33三个部门寄出的征订材料数量 表3 34寄往三个地区的征订材料数量 表3 35各部门寄往各地的费用 54 要求作出一个公司整体的中文书刊材料的邮递方案 使得公司总的邮运费最小 解 记A1 A2和A3分别表示 中文书刊出口部 深圳分公司 和 上海分公司 B1 B2和B3分别表示 日本 香港 和 韩国 转化为一个产销平衡运输问题 表3 36 55 表3 37 表中数字表示Ai邮寄到Bi的邮件数量 56 3 5 2宏达电子的货物转运问题 宏达电子仪器公司 其生产线分别在大连 广州 大连分厂每月生产400台某种仪器 广州分厂每月生产600台某种仪器 在任意分厂的生产线生产的产品可能被运往公司设在长沙或天津的地区仓库中的任意一个 从这些仓库 公司向南京 西安 济南和上海的零售商发货 这些城市间的每台仪器的运费我们标在两个城市间上的弧上 单位为万元 工厂和零售商的供给与需求在图的左侧和右侧标明如图3 1所示 问应该如何调运仪器 使总的运费最低 57 图3 1宏达电子仪器公司转运网络图 58 解 该转运问题可以转化为一个运输问题 1 由于问题中的所有产地 中转站都可以看成产地 而中转站与