运输问题及解法

销地 产地 A1 B1 0 .3 B2 1 .1 B3 0 .3 B4 1 .0 产量
(+1)
0 .1 0 .9
400(-1)
0 .2
300
0 .8
700 400
A2
300(-1)
0 .7 0 .4
100(+ 1)
1 .0 0 .5
A3 销量
600 300 600 500
300 600
900
11= c11- c21+ c23- c13 = 0.3 - 0.3 + 0.2 - 0. 1 = 0.1 31= c31-c21+c23-c13 +c14-c34 = 0.7-0.1+0.2-0.3+1.0-0.5 = 1.0
已知从每个生产基地到各销售部门每箱药品的运价
如表所示，问该制药公司应如何调运，使在满足各 销售部门需要的情况下，总的运输费用最少？
表4-1
各生产基地到各销售部门每箱药品的运费
（金额单位：元） 销售部门
生产基地 B1 A1 0.3 B2 1.1 B3 0.3 B4 1.0
A2
A3
0.1
0.7
0.9
0.4
最小元素 0.1
销地 产地 A1 0 .1 A2 0 .9 0 .2 0 .8 B1 0 .3 B2 1 .1 B3 0 .3 B4 1 .0
一、初始基本可行解的求法
(一)最小费用法（p-140）
产量
700 300
0 .7 0 .4 1 .0 0 .5
400
A3 销量
900 300 ① 600 500 600 2000
运输问题
Transportation Problem

运输问题的解法运输问题是一类特殊的线性规划问题，最早是从物质调运工作中提出的，后来又有许多其它问题也归结到这一类问题中。

正是由于它的特殊结构，我们不是采用线性规划的单纯方法求解，而是根据单纯形方法的基本原理结合运输问题的具体特性须用表上作业的方法求解。

§1 运输问题的数学模型及其特性1.1 运输问题的数学模型设有 个地点（称为产地或发地） 的某种物资调至 个地点（称为销地或收地），各个发点需要调出的物资量分别为个单位，各个收点需要调进的物资量分别为 个单位。

已知每个发点到每个收点的物资每单位运价为 ，现问如何调运，才能使总的运费最小。

我们把它列在一张表上（称为运价表）。

设表示从产地运往销地的运价（ =1，2，…， ； =1，2，…，）。

表3-1如果（总发量）（总收量），我们有如下线性规划问题：m mA A A ,,,21 n nB B B ,,,21 ma a a ,,,21 nb b b ,,,21 iA jB ijc ijx iA jB i m jn（3.1）（3.1）式称为产销平衡运输问题的数学模型。

当（总发量）（总收量）时。

即当产大于销（）时，其数学模型为（3.2）当销大于产（）时，其数学模型为（3.3）因为产销不平衡的运输问题可以转化为产销平衡的运输问题。

所以我们先讨论产销平衡的运输问题的求解。

运输问题有个未知量,个约束方程。

例如当≈40,=70时（3.1）式就有2800个未知量，110个方程,若用前面的单纯形法求解，计算工作量是相当大的。

我们必须寻找特殊解法。

∑∑===m i nj ijij x c z 11min ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≥====∑∑==),,2,1;,2,1(0),,2,1(),,2,1(11n j m i x n j b x m I a x ij j mi ij i nj ij ∑∑==≠nj jm i i ba 11∑∑==>nj jm i i ba 11∑∑===m i nj ijij x c z 11min ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≥===≤∑∑==),,2,1;,2,1(0),,2,1(),,2,1(11n j m i x n j b x m I a x ij j mi ij i nj ij ∑∑==<nj jm i i ba 11∑∑===m i nj ijij x c z 11min ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≥=≤==∑∑==),,2,1;,2,1(0),,2,1(),,2,1(11n j m i x n j b x m I a x ij j mi ij i nj ij mn n m +m n1.2 运输问题的特性由于运输问题也是线性规划问题，根据线性规划的一般原理，如果它的最优解存在，一定可以在基可行解中找到。

当出现检验数<0，证明原初始方案或改 进方案还不是最优→如何进行基变量的 调入调出？
给检验数<0的非基变量赋值，越大 越好。但要考虑产销平衡问题。
11
8、运输问题的校验方法2 —位势法
利用行位势和列位势两类数据，将检验数与 单位运价联系起来
12
检 验 数 方 程
13
λ
= c – u – v ij ij i j
A、位势法求检验数的步骤

第一步：根据最小元素法或Vogel法确定的初始运量表做 一表格，将基变量（或运量）数据替换成与之对应的单位 运价；（或对单位运价表进行修改，只保留与基变量对应的运价信
息）
第二步：在右侧增加一列，下侧增加一行，用于填写位势 数据。右侧表示行位势ui（i=1，2...m），下侧表示列位 势vj（j=1，2...n）； 第三步：对于基变量对应的单位运价处，ui+vj=cij。随便 确定任一个位势，即可求解全部行和列位势； 第四步：在非基变量对应的空格处，计算检验数λij=cij（ui+vj）。并将检验数填入检验数表中； 第五步：判断检验数λij是否大于0，如是，则表示较优。 如不是，则需要调整基变量。 第六步：基变量的调整采用闭回路法进行。
收点 发点 9
B1
4
B2
1
B3
11
B4 -1
10 5
发量
偶 点 0 减 ， 2 奇 点 加 5
A1
14 ③奇点 9 18 1 A2 x x 1 9 11 6 8 0 A3 1 3 x 14 ②偶点 12 2
11 21 22 31
x 3 2
x 6 7
5
13
偶点④
9

i =1 j =1 n i =1
m
n
m
（3.1－4）
将后 n 个约束相加，得
∑∑ xij = ∑ b j ,
j =1 i =1 j =1 m n
m
n
（3.1－5）
因为，
（3.1-4）式与（3.1-5）式是相同的．由此可见，这 m + n 个约束 ∑ ai = ∑ b j ,所以，
i =1 j =1
不是独立的．我们可以证明：当所有的 ai , b j 都大于零时，任何 m + n − 1 个约束都是相互独立 的．即，系数矩阵 A 的秩 r ( A) = m + n − 1 ，事实上，
位(称为需求量)， 设 cij (i = 1, 2,L , m, j = 1, 2,L , n) 为由产地 Ai 运往销地 B j 的单位运费， xij 为从 Ai 调往 B j 的物资数量，试问如何调运，求能使总运费最小． 为了清楚起见，通常将上述数据列在一张表上，该表称为运输表(见表3.1-1)．
初看起来，最小元素法十分合理，但是，有时按某一最小单位运价优先安排物品调运时， 却可能导致不得不采用运费很高的其他供销点对，从而使整个运输费用增加．对每一个供应地 或销售地， 均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价， 并称这两个单位运价之差为该供应地或销售地的罚数．若罚数的值不大，当不能按最小单位运 价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造 成很大损失，故应尽量按最小单位运价安排运输，元素差额法就是基于这种考虑提出来的． 现结合上例说明这种方法： 首先计算运输表中每一行和每一列的次小单位运价和最小单位运价之间的差值，并分别称 之为行罚数和列罚数；将算出的行罚数填入位于运输表右侧行罚数栏的左边第一列的相应格子 中，列罚数填人位于运输表下边列罚数栏的第一行的相应格子中． A1 行中的次小和最小单位运 价分别为8和6，故其行罚数为2， B1 列中次小单位运价和最小单位运价分别为9和8，故其列罚 数为1，如此进行，可计算出 A1 , A2 , A3 的行罚数分别为2，2和4， B1 , B2 , B3 , B4 列的列罚数分别 为1，3，3，2．在这些罚数中最大者为4(在表4.2 - 6中用小圆圈标出)，它位于 A3 行，由于在