运输问题及解法

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

1.产销平衡问题

2.产销不平衡问题此时分为两种情形来考虑：供不应求：即产量小于销量时有

供过于求：即产量大于销量时有二.运输问题的模型产销平衡问题模型将约束方程式展开可得约束方程式中共mn个变量，m+n个约束。2.m+n个约束中有一个是多余的（因为其间含有一个平衡关系式）所以R(A)=m+n-1，即解的mn个变量中基变量为m+n-1个。三.运输问题的解法

运输问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是：

1.运输问题所涉及的变量多，造成单纯形表太大；

2.若把技术系数矩阵A中的0迭代成非0，会使问题更加复杂。以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法——表上作业法。表上作业法，实质上还是单纯形法。其步骤如下：1.确定一个初始可行调运方案。可以通过最小元素法、Vogel法来完成；2.检验当前可行方案是否最优，常用的方法有闭回路法和位势法，用这两种方法计算出检验数，从而判别方案是否最优；3.方案调整，从当前方案出发寻找更好方案，常采用闭回路法。（Ⅰ）运输问题的常用解法：最小元素法（确定初始方案）→闭回路法（检验当前方案）→闭回路法（方案调整）以下面例题说明这种方法的具体步骤：例12：某食品公司下设3个加工厂A1，

A2，A3，和4个门市部B1，

B2，B3，B4。各加工厂每天的产量、各门市部每天的销售量以及从各加工厂到各门市部的运价如下表所示。问：该公司应如何调运，在满足各门市部销售需要的情况下，使得运费支出为最少？

运输问题一般用表上作业法求解，需建立表格模型：单位运价表产销平衡表

用线性规划法处理此问题。设由产地i到销地j的运量为xij，模型为：minz=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij≥0(i=1,2,3;j=1,2,3,4)给出初始调运方案最常用的方法——最小元素法314633初始方案运费Z0=3×1+6×4+4×3+1×2+3×10+3×5=86(元)

表上作业法要求，调运方案的数字格必须为m+n-1个，且所有数字格不构成闭回路。一般，用最小元素法给出的方案符合这一要求。闭回路:从方案中某一始格出发，沿同行或同列前进，当遇到一个数字格时可以可转90度或继续前进，按此方法进行，直到回到始点的一个封闭曲线。同行或同列最多有两个点。最小元素法中的退化情况360542

出现退化时，要在同时被划去的行列中任选一个空格填0，此格作为有数字格。

①找出任意空格的闭回路—除此空格外，其余顶点均为有数格。如可找（A1

B1

）→（A1

B3

）→（A2

B3）→（A2

B1

）；

2.检验（闭回路法:计算空格的检验数）②计算出空格的检验数—等于闭回路上由此空格起奇数顶点运价与偶数顶点运价的代数和。如σ11＝c11

-c13+c23-c21=1

314633③计算出此空格的检验数σij,若σij≥０，则该方案为最优方案，否则转３；

注：检验数的经济意义，以σ11为例，空格表示原方案中X11=0,即A1→B1

的运输量为0。若试着运1单位，则这样所引起的总费用的变化恰是σ11，可见检验数σij的意义是：

Ai

→

Bj增运１单位所引起的总费用的增量。

σij>０，说明若增运一单位则在总运输量不变情况下，总运费会增加。此时不应在

Ai

→

Bj上增运。3.调整:从σij

为最大正值的空格出发.对其闭回路上的奇数顶点运量增加θ,偶数顶点的运量减少θ(这才能保证新的平衡)，其中θ为该空格闭回路中偶数顶点的最小值。∵σ24=-1<0，∴从（A2

B4）出发其闭回路上θ=1，调整后得到一个新方案（如下表），运量为θ=1的（A2

B3）变空格，得到新方案后再转

2。σ11=1，σ12=2σ22=1，σ24=-1σ31=10，σ33=12314633经再计算新方案的检验数全部大于0。所以，该新方案为最优方案，可计算得总运费为85元。注：若闭回路的偶数顶点中同时有两个格以上运量为θ，则调整后其中一个变空格，其余填0。（保证基变量个数不变）3613252.确定初始方案的方法之二—伏格尔法（Vogel法）⑴求各行各列运价最小与次小之差额，选其中最大的行或列中最小运价进行供应；

⑵如果某一行或某一列按照这种方法已被供应满，则划去该行或该列，在剩下的行列中重复这种方法，即得最优方案。36351227623.求空格检验数的方法之二—位势法原理：设有运输问题的对偶问题为

3146333101245仍以例一为例：对偶变量表面上是7个，实际上只有6个。∴有一个是自由变量。当找出σij<0的格后，调整方法仍用闭回路法。位势法步骤：

①由有数格cij=ui+vj求得ui和vj

（先令u1=0），原有数格（基变量）的检验数σij=0；

②空格σij=cij—

(ui+vj)；

③由此可得检验数表。（Ⅲ）产销不平衡的运输问题1.产大于销的情况：添加松弛变量xi,n+1xin+1的定义：由Ai向Bn+1的运量，而Bn+1并不存在，相当于增加了一个虚设的销地—Ai自己的仓库里，自己往自己的地方运，运费cin+1显然为0。实际上xin+1即Ai的剩余量。A1AmB1……BnBn+1C1100C1nCm1Cmn产大于销的单位运价表产大于销的产销量表A1Ama1amB1……BnBn+1b1……bn2.销大于产的情况：添加松弛变量xm+1j同理，此时xm+1j的意义为销售短缺的量，同样，Am+1不存在，cm+1j为0。销大于产的产销量表A1Ama1amB1……Bnb1……bnAm+1A1AmB1……BnC1100C1nCm1Cmn销大于产的单位运价表Am+1……四应用举例由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多。所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。下面介绍几个典型的例子。例3某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表3-29所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，作出使该厂全年生产(包括储存、维护)费用最小的决策。解由于每个季度生产出来的柴油机不一定当季交货，所以设xij为第i季度生产的用于第j季度交货的柴油机数。根据合同要求，必须满足又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有：第i季度生产的用于j季度交货的每台柴油机的实际成本cij应该是该季度单位成本加上储存、维护等费用。cij的具体数值见表3-30。设用ai表示该厂第i季度的生产能力，bj表示第i季度的合同供应量，则问题可写成：

显然，这是一个产大于销的运输问题模型。注意到这个问题中当i＞j时，xij=0，所以应令对应的cij=M，再加上一个假想的需求D，就可以把这个问题变成产销平衡的运输模型，并写出产销平衡表和单位运价表(合在一起，见表3-31)。

经用表上作业法求解，可得多个最优方案，表3-32中列出最优方案之一。即第Ⅰ季度生产25台，10台当季交货，15台Ⅱ季度交货；Ⅱ季度生产5台，用于Ⅲ季度交货；Ⅲ季度生产30台，其中20台于当季交货，10台于Ⅳ季度交货。Ⅳ季度生产10台，于当季交货。按此方案生产，该厂总的生产(包括储存、维护)的费用为773万元。例4某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数

见表3-33。假定各条航线使用相同型号的船只，又各城市间的航程天数见表3-34。又知每条船只每次装卸货的时间各需1天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求?解该公司所需配备船只分两部分。(1)载货航程需要的周转船只数。例如航线1，在港口E装货1天，E→D航程17天，在D卸货1天，总计19天。每天3航班，故该航线周转船只需57条。各条航线周转所需船只数见表3-35。以上累计共需周转船只数91条

.第4节应用举例(2)各港口间调度所需船只数。有些港口每天到达船数多于需要船数，例如港口D，每天到达3条，需求1条；而有些港口到达数少于需求数，例如港口B