第四节运输问题 运输问题的一般提法 在经济建设中,经常碰到物资调拨中 的运输问题。 例如煤、钢材、粮食、木材等物资,在全 国都有若干生产基地,分别将这些物资调 到各消费基地去,应如何制定调运方案, 使总的运输费用最少?
第四节 运输问题 一.运输问题的一般提法 在经济建设中，经常碰到物资调拨中 的运输问题。 例如 煤、钢材、粮食、木材等物资，在全 国都有若干生产基地，分别将这些物资调 到各消费基地去，应如何制定调运方案， 使总的运输费用最少？ A1，
运输问题的一般提法是: 1产销平衡问题 已知:m个产地A,,An,产量分别是:a, n个销售地B,……,Bn,销量分别是:b,……,b, 产销平衡即∑a=∑b,由A→>B的运价为cn 问:应如何调运使总费用最省? 即求A,→>B的运量x,使运费可达极小化
运输问题的一般提法是： 1.产销平衡问题 1 m 1 m 1 n 1 n 1 1 A A : B B : , , A B c ? A B m n i j i j ij i j i j ij m a a n b b a b x = = = → → 已知: 个产地 ， ， ， 产量分别是 ， ， ， 个销售地 ， ， ，销量分别是 ， ， ， 产销平衡 即 由 的运价为 。 问:应如何调运使总费用最省 即求 的运量 ，使运费可达极小化
2.产销不平衡问题 此时分为两种情形来考虑 供不应求:即产量小于销量时有∑a<∑b 供过于求:即产量大于销量时有∑a<∑b 这两种情形都可以化为∑a=∑b的形式来 求解
2.产销不平衡问题 此时分为两种情形来考虑： 供不应求：即产量小于销量时有 供过于求：即产量大于销量时有 求解 这两种情形都可以化为ai =bj 的形式来
二运输问题的模型 销平衡问题模型 Min b x≥0
二.运输问题的模型 产销平衡问题模型 1 1 1 1 1,...... 1,...... 0 m n ij ij n ij i j m ij j i ij Min z a x x a i m x b j n x = = = = = = =
将约束方程式展开可得 x1+… xn;+∴+x x,+∴+x X+ 12 约束方程式中共mn个变量,m+n个约束
将约束方程式展开可得 11 1 1 21 2 2 1 11 21 1 1 12 22 2 n n m mn m m m x x a x x a x x a x x x b x x x + + = + + = + + = + + = + + 2 1 2 n n mn n b x x x b = + + = 约束方程式中共mn个变量，m+n个约束
上述模型是一个线性规划问题。但是 其结构很特殊,特点如下: 1变量多(mn 结构 简单。 技术系数矩阵A
上述模型是一个线性规划问题。但是 其结构很特殊，特点如下： 1.变量多（mn 个），但结构 简单。 技术系数矩阵 1 1 1 1 A= 1 1 1 1 1 1 1 1
2m+n个约束中有一个是多余的(因为其间含 布个平衡关系式∑4=∑b 所以R(A=m+n-1,即解的mn个变量中基变量 为m+n-个
i j a b = 2.m+n个约束中有一个是多余的（因为其间含 有一个平衡关系式 ） 所以R(A)=m+n-1，即解的mn个变量中基变量 为m+n-1个
运输问题的解法 运输问题仍然是线性规划问题,可以用 线性规划法中的单纯形法来解决。但是: 1运输问题所涉及的变量多,造成单纯 形表太大; 2若把技术系数矩阵A中的0迭代成非0, 会使问题更加复杂。 以上两个原因使得我们不得不利用运输 问题的特点设计出它的特殊解法——一表 上作业法
三.运输问题的解法 运输问题仍然是线性规划问题，可以用 线性规划法中的单纯形法来解决。但是： 1.运输问题所涉及的变量多，造成单纯 形表太大； 2.若把技术系数矩阵A中的0迭代成非0， 会使问题更加复杂。 以上两个原因使得我们不得不利用运输 问题的特点设计出它的特殊解法——表 上作业法
表上作业法,实质上还是单纯形法。其步 骤如下: 1.确定一个初始可行调运方案。可以通过 最小元素法、西北角法、Voge法来完 成 2.检验当前可行方案是否最优,常用的方 法有闭回路法和位势法,用这两种方法 计算出检验数,从而判别方案是否最优; 3.方案调整,从当前方案出发寻找更好方 案,常采用闭回路法
表上作业法，实质上还是单纯形法。其步 骤如下： 1.确定一个初始可行调运方案。可以通过 最小元素法、西北角法、Vogel 法来完 成； 2.检验当前可行方案是否最优，常用的方 法有闭回路法和位势法，用这两种方法 计算出检验数，从而判别方案是否最优； 3.方案调整，从当前方案出发寻找更好方 案，常采用闭回路法
(工)运输问题的常用解法: 最小元素法(确定初始方案)→闭回路法(检 验当前方案)→闭回路法(方案调整) 以下面例题说明这种方法的具体步骤: 例12:某食品公司下设3个加工厂A,A2,A 和4个门市部B,B,B,B。各加工厂每天的 产量、各门市部每天的销售量以及从各加工厂 到各门市部的运价如下表所示 问:该公司应如何调运,在满足各门市部销 售需要的情况下,使得运费支出为最少?
（Ⅰ）运输问题的常用解法： 最小元素法（确定初始方案）→闭回路法（检 验当前方案）→闭回路法（方案调整） 以下面例题说明这种方法的具体步骤： 例12：某食品公司下设3个加工厂A1，A2，A3， 和4个门市部B1，B2，B3，B4。各加工厂每天的 产量、各门市部每天的销售量以及从各加工厂 到各门市部的运价如下表所示。 问：该公司应如何调运，在满足各门市部销 售需要的情况下，使得运费支出为最少？