B1 c11 c21 ┇ cm1 b1
B2 … Bn c12 … c1n c22 … c2n ┇ ┇ ┇
产量 a1 a2 ┇ am
cm2 … cmn b2 … bn
分两种情况来讨论：
（1）
a b
i 1 i j 1
m
n
j
。即运输问题的总产量等于其总
销量，这样的运输问题称为产销平衡的运输问题。 （2）
（2）位势法（对偶变量法）
对于一个调运方案的每列赋予一个值，称为列位 势，记 v1 , v 2 , , v n ，对于每行赋予一个值，称为行位 势，记为 u1 , u2 ,, um 它们的值由下列方程组决定：
ui v j cij
其中， cij 是所有基变量（数字格）xij 的运价系数 。
（1）闭回路法
在单纯形法中，为了检验一个基本可行解是 不是最优解，需要求出所有非基变量的检验数。 在运输问题中，每个空格对应一个非基变量。因 此，我们需要求出每个空格的检验数。 由于目标要求极小，因此，当所有的检验数 都大于或等于零时该调运方案就是最优方案。
①对方案表中每一空格，确定一条由空格出发的闭回路。
u1 + v4 = c14 = 10 u2 + v3 = c23 = 2 u3 + v4 = c34 = 5
令u1 = 5 则有 v4 = 5 v3 = -2 u2 = 4 u3=0 v2=4 v1= -3 再求非基变量（空格）检验数： 11 = c11 – u1 - v1 = 3 – 5 – (-3) = 1 12 = c12 – u1 – v2 = 11 – 5 – 4 = 2 22 = c22 – u2 – v2 = 9 – 4 – 4 = 1 24 = c24 – u2 – v4 = 8 – 4 – 5 = -1 31 = c31 – u3 - v1 = 7 – 0 – (-3) = 10
A2
A3
3 6
1 3
（有数格）
X11=X31=X12=X22=X33=X24=0 （空格）
初始方案运费
Z0=3×1+6×4+4×3+1×2+3×10+3×5=86(元)
注： （ⅰ）有数格是基变量，共m+n-1=3+4-1=6个。空格是非基 变量，共划去m+n=7条线； （ⅱ）如果填上一个变量之后能同时划去两条线（一行与 一列），就须在所划去的该行或该列填一个0，此0格当有 数格对待。
m ( 3 1) x ij b j j 1,2, , n i 1 n s .t . x ij a i i 1,2, , m j 1 x 0 ij m n 其中，ai和bj满足： ai b j 称为产销平衡条件。
i 1 j 1
B2 11 9 4 5
B3 3 2 10 1 1
B4 10 8 5 3 2
5 3 6
3 6 5
2 1 3
6
0 07
1 16
1 2
2、判断当前方案是否为最优
用单纯形法解线性规划问题时，在迭代过程中 每次求得一个基本可行解以后，都要检验它是不是 最优解，如果不是最优解，就要继续进行迭代，直 到求得最优解或者判定无最优解。 表上作业法是用以下两种方法来处理这个问题 的：闭回路法和位势法。
例3.1
某公司从三个产地A1、A2、A3 将物品运往四个
销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产 地运往各销地每件物品的运费如下表3-4所示
销地 产地 A1 A2 A3 销量 B1 3 1 7 3 B2 11 9 4 6 B3 3 2 10 5 B4 10 8 5 6 产量 7 4 9 20（产销平 衡）
销地。产地Ai的产量为 ai ( i 1,2,, m ) ；销地Bj的销 量 b j ( j 1,2,, n)。从第i个产地向第j个销地运输每单位物资 的运价为Cij。 这就是由多个产地供应多个销地的单品种物资运输问
题。问如何调运这些物资才能使总运费达到最小。
单位运价表
销地 产地 A1 A2 ┇ Am 销量
4
1
3
A1
A2 3 6 B1 B2
4
1
3
3
A3
3 B3 B4
B1
A1 A2 A3
B2
B3
4
B4
3
A1
A2 3 6
4
1
3
3
6
1
3
A3
3
②计算出空格的检验数—等于闭回路上由此空格起奇数顶点 运价与偶数顶点运价负值的代数和。 B1 B2 B3 B4 销地
产地 A1 A2 A3 B1 3 1 7 B2 B3 B4
则检验数为： ij = cij - ui - vj i = 1, … , m ; j = 1, … , n
方案表
销 产 A1 A2 A3 B1 B2 B3 4 B4 3 产量 7 4 3 9 B1 3 B2 11 9
运价表
B3 3 3 2 2 10 B4 10 10 8 5 5 u1 u2 u3
B1
B2
B3
B4
产量
75
B1
3 2 6
B2
8 9 3
B3
5 4 7
B4
9 8 5
35
40 0 40 15
40
65
65
80 195
35
40
55
(3)伏格尔法（次小运价与最小运价之差大者先安排）
方案表 运价表
销
产
A1 A2 A3 需求
B1
B2 B3 B4
产 量 7 4 9 20
B1 3 1 7 2 2
问应如何调运，可使得总运输费最小?
1、确定初始方案
即初始基本可行解的确定，与一般线性规划 问题不同，产销平衡运输问题总是存在可行解。 确定初始基本可行解的方法很多，一般希望方 法是既简便，又尽可能接近最优解。下面介绍两种 方法：最小元素法，西北角法、 Vogel 法
（1）最小元素法
最小元素法的基本思想是优先满足单位运价最小的 供销业务。 首先找出运价最小的，并以最大限度满足其供销量 为原则确定供销业务。同样的方法反复进行直到确定了所 有的供销业务，得到一个完整的调运方案即初始基本可行
解为止。
方案表 销
运价表
产
A1 A2 A3
B1
B2
B3
B4
产量
7 4
B1
3 1 7
B2
11 9
B3 3
2 2 10
B4
10 8 5
4 3 6
3 6 5
3
1 3
6
9
4
需求
20
B1 A1
B2
B3 4
B4 3
以此，得到一初始方案：
X13=4 , X14=3， X21=3，X23=1， X32=6， X34=3
该系数矩阵中每列只有两个元素为1，其余的都为零。
2.m+n个约束中有一个是多余的（因为其间含有一个平衡关系 式 ） ai b j 所以R(A)=m+n-1，即解的mn个变量中基变量为m+n-1个。
二、 表上作业法
运输问题仍然是线性规划问题，可以用线性规划 法中的单纯形法来解决。但是：
3
4 2 2 3
5
4
6
6
9 20
注：应用西北角法和最小元素法，每次填完数，都只划去一 行或一列。 当填上一个数后行、列同时饱和时，也应任意划去一行 (列)。在饱和的列（行）没被划去的格内标一个 0 , 然后划去 该列（行）。
例3.2 某公司下属有生产一种化工产品的三个产地A1、A2、
A3 ，有四个销售点B1、B2、B3、B4 销售这种化工产品。各
1.运输问题所涉及的变量多，造成单纯形表太大；
2.若把技术系数矩阵A中的0迭代成非0，会使问题 更加复杂。
以上两个原因使得我们不得不利用运输问题的 特点设计出它的特殊解法——表上作业法。
二、表上作业法（续）
表上作业法，实质上还是单纯形法。其步骤如下： 1.确定一个初始可行调运方案。可以通过最小元素法、 西北角法、Vogel 法来完成； 2.检验当前可行方案是否最优，常用的方法有闭回路法 和位势法，用这两种方法计算出检验数，从而判别方 案是否最优； 3.方案调整，从当前方案出发寻找更好方案，常采用闭 回路法。
闭回路是由水平或垂直线组成的闭合图形。闭回路上的 顶点除了这个空格外，其余均为有数格。
B1 A1 A2 A3 3
B2
B3 4 1
B4 3
B1
B2
B3
B4
A1
A2 3 6
4
1
3
Байду номын сангаас
6
3
A3
3
可以证明，对每一个空格都存在而且惟一存在 这样一条封闭回路。
B1
B2
B3
B4
B1
B2
B3
B4
A1
A2 A3 3 6
A1 A2 3
4 1
3
11 9 4
3 2 10
10 8 5
A3
11=3 - 3+2 - 1=1 22= 9-2+3–0+5–4 =1 31= 7-5+10–3+2–1=10
6
3
12=11 - 10+5 - 4=2 24= 8–10 +3 – 2 =-1 33=10 - 5+10 -3=12
将约束方程式展开可得
a1 x11 x1n x21 x2 n a2 xm1 xmn am x21 xm1 b1 x11 x12 x22 xm 2 b2 x1n x2 n xmn bn