销地
B3 3 x14 8 B4 10
供应
7 4
需求
3
6
5
6
20
元素差额法(VAM法) 例 设有A1, A2和A3的产品需要运到B1, B2, B3 . 元素差额法是在最小元素法的基础上改进的 和 B4四个销地，求如何调运使总运费最少？ 在确定产销关系时，不从最小元素开始，而 从运输表中各行各列的最小元素和次小元素 产地 销地 供应 B1 B2 B3. B4 之间的差额来确定产销关系
2
5
×
3 差 额
3
8
4
4
×
6
2 1
1
1 5
2 8
3 2
初始调运方案为
2 3 5 9 7 1 2 5 4 3 2 4 88
作业： 用元素差额法求解下列问题的调运方案
产地
B1 A1 x11 A2 x21 A3 x31 7 x32 1 x22 4 x33 3 x12 9 x23 10 x34 B2 11 x13 2 x24 5 9
初始总运费为
5 9 4 7 3 1 2 2 3 4 4 2 100
作业： 用最小元素法求解下列问题的调运方案
产地
B1 A1 x11 A2 x21 A3 x31 7 x32 1 x22 4 x33 3 x12 9 x23 10 x34 B2 11 x13 2 x24 5 9
供 应
9 9-3 9-3-6 5 5-2 5-2-3 7 7-1 21
3
A2 A3 需求
1
6-6 6
初始调运的运费为
3 2 6 9 2 3 3 4 1 2 6 5 110
作业： 用西北角法求解下列问题的调运方案
产地 销地 供应
B1
A1 x11 3 x12
产地 B1 A1 2 B2 9 销地 B3 10 B4 7 9 5 供应
x11
A2 x21 1
x12
3 x22
x13
4 x23
x14
2 x24
A3
x31 需求 3
8
x32 8
4
x33 4
2
x34 6
5
7
21
这是一个产销平衡问题，西北角法具体步骤 第一步，做产销空格表，将空格对应的产销 地运费填在空格的右上角.
第三步，在差额行和差额列中选取差额最大 的一行或一列进行分配，并对该行(列)的最 小元素填数，填数规则同最小元素法. 第四步，重新计算差额并进行分配，直到每 一个格上都被填上数字或画×为止.
B1
A1 A2 2
B2
9
B3
10
B4
差额
7 2 9 5 7 21
3
1
5
3
×
4
1 5
2 5 1
×
A3 8
×
4
×
第二步，在表中增加一行vj和一列ui , 使得表 中的基变量的单位运价cij刚好是ui和vj的和. 第三步，计算空格处的检验数: σij=cij-( A1 A2 3 A3 7 6 4 3 1 B2 11 4 9 1 10 3 5 9 2
销地
B3 3 3 8 B4 10
闭回路法 由一个空格开始，沿水平方向或垂直方向前 进. 遇到一个有数字的格子时，则可以按前 进方向的垂直方向转向前进，经过若干次后, 必然回到原出发点. 这样就形成了一条由水平线段和垂直线段组 成的封闭折线，称为闭回路法. 拐角：填有数字，并且前进方向改变的格子. 检验数求法：从空格开始沿闭回路前进，空 格的单位运费取正，第一个转角运费取负， 第二个取正, …, 然后将这些运费加起来，即 空格的检验数.
A1 x11 A2 x21 A3 8 1 x22 4 2 x12 3 x23 2 9 x13 4 x24 5 7 21 10 x14 2 5 7 9
x31
需求 3
x32
8
x33
4
x34
6
第一步，做产销空格表，并将空格对应的产 销地运费填在空格的右上角.
第二步，产销空格表上增加一行和一列作为 差额行和差额列，填上对应行和对应列的最 小元素和次小元素的差额.
例 求下表A2B2的一个闭回路和检验数
产地
B1 A1 A2 3 A3 7 6 4 3 1 B2 11 4 9 1 10 3 5 9 2
销地
B3 3 3 8 B4 10
供应
7 4
需求
3
6
5
6
20
检验数:
9 4 5 10 3 2 1
第三章
第二节 表上作业法
运输问题
2 最优调运方案的判断 位势法 如果产销地的个数很多，闭回路法应用起来 非常麻烦，对于这种情况，采用位势法: 第一步，做产销空格表，并作初始调运方案， 表中的数字是相应的单位运价和运量.
销地
B3 3 x14 8 B4 10
供应
7 4
需求
3
6
5
6
20
2 最优调运方案的判断 判断一个调运方案是否是最优方案，实质是 判别一个基本可行解是否为最优解. 单纯形法中，最优解是根据对应的非基变量的 检验数来判断的. 运输问题也采用类似的方法.
由单纯形法可知，最优解中非基变量一般取0 那么运输问题中，哪些是非基变量呢？ 调运量为零(即×位置)的对应于非基变量！ 所以只要判别出每个空格的检验数就可以了 检验数该如何求？ 闭回路法和位势法
供应
7 4
需求
3
6
5
6
20
解：
产地
B1 A1 A2 3 A3 B2 3 1
销地
B3 11 4 9 1 4 6 2 3 3 B4 10
位势
1
2
2 9 1
1 0 -4
-1 9
8 5
8
7
10
-3
12 -2
10 3
位势
1
8
2
9
此方法求出的检验数和闭回路法求的是一致的
求得检验数后，就可以判断这个运输方案是 否是最优的. 由于运输问题的目标函数是极小化问题 所以所有的检验数都是非负的时候，最优. 如果有检验数为负值，该如何处理？
第二步，在表中对左上角进行分配 (1) 如果产大于销，则在这个方格填上销量, 并在表中划去这一列 (2) 如果销大于产，则在这个方格填上产量, 并在表中划去这一行 第三步，在剩下的表中，反复进行第二步.
产地
B1 A1 2 B2
销地
B3 9 6 1 × 8 × 3-3 3 × 8-6-2 8-6 8 2 4 3 3 2 × 4 × 5 6 4 4-3 4-3-1 10 × 2 B4 7
第二节 表上作业法
表上作业法一般分为两个阶段 第一阶段，制定初始调运方案; 第二阶段，从初始调运方案出发，调整调运 方案，逐步获得最优解. 1 制定初始调运方案 下面通过例题来介绍几种常用的求运输问题 的初始基本可行解的方法
左上角法(西北角法) 例 设有A1, A2和A3的产品需要运到B1, B2, B3 和B4四个销地，求如何调运使总运费最少？
销地
位势
B3 B4 3 10 2 2 1 10 3 5 8
0 3
B1 3 1
2 9 2 7
6
B2 11 5 9 4
2
9 -2
7
1 1 12 -2
0
-3
1 7 1 8 所有的检验数均已大于等于零 所以此表为最优调运方案，总运费为
位势
s 1 3 6 4 5 3 2 10 1 8 3 5 85
3 调整已有的调运方案 就是从一个已知方案求出另一个较好的方案. 实质上就是从一个基本可行解找出另一个基 本可行解，使目标函数下降. 具体步骤如下:
第一步，选出一个检验数为负的空格(一般选 具有最负值的检验数的空格，如果两个空格 的检验数一样，则任选一个)，然后做选出空 格的闭回路. 第二步，从空格处出发，沿闭回路前进，在 各奇数次拐角点的调运量中选取一个最小的 调运量. 第三步，在空格中填上所选的最小调运量， 并使所有的奇数次拐角的调运量减去这个最 小调运量，偶数次拐角的调运量加上最小调 运量.
B2
11 x13
B3
3 x14
B4
10 7
A2
x21 A3 x31 需求 3
1
x22 7 x32 6
9
x23 4 x33 5
2
x24 10 x34 6
8
5
4
9 20
最小元素法 例 设有A1, A2和A3的产品需要运到B1, B2, B3 和B4四个销地，求如何调运使总运费最少？
产地
B1 A1 2 B2 9
产地
B1 A1 A2 A3 位势 3 10 -3 1 1 2 3 1 7 6 8 2 9 1 8 B2
销地
B3 11 3 B4 10
位势
1 0 -4
4+1 4
9 2
3-1 3
-1 19 3 8 5 9
1-1 1
4 12 -2 2 10
相当于单纯形法的转轴运算. 重新计算位势和检验数.
产地
A1 A2 3 A3
销地
B3 10 B4 7
供应
9 5 7 21
x11
A2 x21 A3 x31 需求 3 8 1
x12
3 x22 4 x32 8
x13
4 x23 2 x33 4
x14
2 x24 5 x34 6
第一步，做产销空格表，并将空格对应的产 销地运费填在空格的右上角; 第二步，在表中找出运价最小的一个，对比 产地和销地;
(1) 如果产大于销，则在该格中填上销量; (2) 如果销大于产，则在该格中填上产量;