《二章四节运输问题》由会员分享，可在线阅读，更多相关《二章四节运输问题（23页珍藏版）》请在金锄头文库上搜索。
1、第四节 运输问题一.运输问题的一般提法在经济建设中，经常碰到物资调拨中 的运输问题。 例如 煤、钢材、粮食、木材等物资，在全 国都有若干生产基地，分别将这些物资调 到各消费基地去，应如何制定调运方案， 使总的运输费用最少？运输问题的一般提法是：1.产销平衡问题2.产销不平衡问题此时分为两种情形来考虑： 供不应求：即产量小于销量时有供过于求：即产量大于销量时有 二.运输问题的模型产销平衡问题模型将约束方程式展开可得约束方程式中共mn个变量，m+n个约束。上述模型是一个线性规划问题。但是 其结构很特殊，特点如下：1.变量多（mn个），但结构简单。技术系数矩阵2.m+n2.m+n个约束中有一个是多余
2、的（因为其间含个约束中有一个是多余的（因为其间含有一个平衡关系式有一个平衡关系式 ）所以所以R(A)=m+n-1R(A)=m+n-1，即解的即解的mnmn个变量中基变量个变量中基变量为为m+n-1m+n-1个。个。三.运输问题的解法运输问题仍然是线性规划问题，可以用 线性规划法中的单纯形法来解决。但是 ：1.运输问题所涉及的变量多，造成单纯 形表太大；2.若把技术系数矩阵A中的0迭代成非0 ，会使问题更加复杂。以上两个原因使得我们不得不利用运输 问题的特点设计出它的特殊解法表 上作业法。表上作业法，实质上还是单纯形法。其步 骤如下：1.确定一个初始可行调运方案。可以通过 最小元素法、西北角法、
3、Vogel 法来完 成； 2.检验当前可行方案是否最优，常用的方 法有闭回路法和位势法，用这两种方法 计算出检验数，从而判别方案是否最优 ； 3.方案调整，从当前方案出发寻找更好方 案，常采用闭回路法。（）运输问题的常用解法： 最小元素法（确定初始方案）闭回路法（检 验当前方案）闭回路法（方案调整） 以下面例题说明这种方法的具体步骤： 例12：某食品公司下设3个加工厂A1， A2，A3， 和4个门市部B1， B2，B3，B4。各加工厂每天的 产量、各门市部每天的销售量以及从各加工厂 到各门市部的运价如下表所示。问：该公司应如何调运，在满足各门市部销 售需要的情况下，使得运费支出为最少？门市部
4、加工厂B1 B2 B3 B4产 量A1 A2 A37 4 9销 量3 6 5 620门市部 加工厂B1 B2 B3 B4A1 A2 A33 11 3 101 9 2 87 4 10 5产销平衡表 单位：吨单位运价表 单位：元/吨解：1.确定初始方案:(最小元素法基本思想：就近供应，即从单位运 价表上最小的运价开始确定产销关系，以此类推， 直到给出初始方案为止) 从运价表上找出最小运价C21=1， A2 先保证供应 B1 ，X21=3，划去运价表上B1 列； 再从运价表上其余元素中找到最小的运价C23=2 ，加工厂A2 应供给B3， X23=1，划去A2行； 再从运价表上其余元素中找到最小的运价
5、C13=3 ，所以A1先保证供应B3 ， B3 尚缺4单位，因此 X13=4，划去B3 列。以此类推，得到一初始方案（如下图）：X21=3，X32=6，X13=4，X23=1，X14=3，X34=3（有数格）X11=X31=X12=X22=X33=X24=0（空格）B1B2B3B4 A 143A 231A 363注：（）有数格是基变量，共m+n- 1=3+4-1=6个。空格是非基变量， 共划去m+n=7条线；（）如果填上一个运量之后能同 时划去两条线（一行与一列），就 须在所划去的该行或该列填一个0， 此0格当有数个对待。 初始方案运费 Z0=31+64+43+12+310+35=86(元)2
6、.检验（闭回路法:计算空格的检验数） 找出任意空格的闭回路除此空格外，其余顶点均 为有数格。如可找（ A1 B1 ） （ A1 B3 ） （ A2 B3 ） （ A2 B1 ）； 计算出空格的检验数等于闭回路上由此空格起奇 数顶点运价与偶数顶点运价的代数和。如11c11- c13+c13-c21=3-3+2-1 计算出此空格的检验数ij,若ij ，则该方案为最 优方案，否则转；注：检验数的经济意义，以11为例，空格表示原方案中X11=0,即A1 B1 的运输量为0。若试着运1单位，则这样所引起的总费用的变化恰是11，可见检验 数ij的意义是： Ai Bj增运 单位所引起的总费用的增量。 ij，
7、说明若增运一单位则在总运输量不变情况下，总运费会增加。此时不应在 Ai Bj 上增运。3.调整:从 ij ij为最小负值的空格出发.对其闭回路上的 奇数顶点运量增加,偶数顶点的运量减少(这才能保 证新的平衡)，其中为该空格闭回路中偶数顶点的最 小值。 2424865=13586显然显然, ,由于它仅考由于它仅考 虑地理位置而不考虑地理位置而不考 虑运价虑运价, ,其效果不其效果不 如用最小元素法好如用最小元素法好. .2.确定初始方案的方法之三伏格尔法（Vogel法 ）求各行各列运价最求各行各列运价最 小与次小之差额，选小与次小之差额，选 其中最大的行或列中其中最大的行或列中 最小运价进行供应
8、；最小运价进行供应； 如果某一行或某一如果某一行或某一 列按照这种方法已被列按照这种方法已被 供应满，则划去该行供应满，则划去该行 或该列，在剩下的行或该列，在剩下的行 列中重复这种方法，列中重复这种方法， 即得最优方案。即得最优方案。如上图，一步即可得最优解。3.3.求空格检验数的方法之二求空格检验数的方法之二位势法位势法原理：设有运输问题的对偶问题为问题： ij ij与原问题有什么关系？ 由对偶性质， ij ij是原问题结构变量是原问题结构变量x xij ij 的检验数的检验数 当当x xij ij是基时，是基时， ij ij= =0 0，此时有，此时有 由此求由此求u ui i和和v v
9、j j，再代回（，再代回（* *）式求非基变量的）式求非基变量的 ij ij（空格检验数（空格检验数 ）当找出ij0的格后，调整方法仍用闭回路法。仍以例一为例：对偶变量 表面上是7个，实际上只 有6个。有一个是自由 变量。作法如右表，结果与闭回 路法一样，但比闭回路法 简单，尤其当变量多的时 候，用位势法比较好。位势法步骤： 由有数格ui+vj求得ui和vj （先令u1=0），原有数格（基原有数格（基 变量）的检验数变量）的检验数 ij ij= =0 0； 空格 ij ij= =c cij ij-(u-(ui i+v+vj j) )； 由此可得检验数表。由此可得检验数表。（）产销不平衡的运输问
10、题1.产大于销的情况：添加松弛变量xin+1xin+1的定义：由Ai向Bn+1的运量，而Bn+1并不存在 ，相当于增加了一个虚设的销地Ai自己的仓 库里，自己往自己的地方运，运费cin+1显然为0 。实际上xin+1即的剩余量。A1AmB1Bn Bn+1C1100C1nCm1Cmn产大于销的单位运价表产大于销的产销量表A1Ama1amB1Bn Bn+1b1bn2.销大于产的情况：添加松弛变量xm+1j同理，此时xm+1j的意义为销售短缺的量，同样，Am+1 不存在， cm+1j为0。销大于产的产销量表A1Ama1amB1Bnb1bnAm+1A1AmB1BnC1100C1nCm1Cmn销大于产的单位运价表Am+1
