天津大学管理学院：《管理科学基础》课程PPT教学课件（运筹学）第二章 线性规划（2.4）运输问题

第四节运输问题 运输问题的一般提法 在经济建设中,经常碰到物资调拨中 的运输问题。 例如煤、钢材、粮食、木材等物资,在全 国都有若干生产基地,分别将这些物资调 到各消费基地去,应如何制定调运方案, 使总的运输费用最少?

第四节 运输问题 一.运输问题的一般提法 在经济建设中，经常碰到物资调拨中 的运输问题。 例如 煤、钢材、粮食、木材等物资，在全 国都有若干生产基地，分别将这些物资调 到各消费基地去，应如何制定调运方案， 使总的运输费用最少？ 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。各加工厂每天的 产量、各门市部每天的销售量以及从各加工厂 到各门市部的运价如下表所示。 问：该公司应如何调运，在满足各门市部销 售需要的情况下，使得运费支出为最少？