19
销地 产地
B1
B2
B3 4+1
B4 3-1 +1 3
产量 7 4 9
A1 A2 A3 3 6
1-1
销量
销地 产地
3
B1 3
6
B2
5
B3
6
B4 产量
调整后的新调运方案如下表：
A1
A2 A3 销量 3 6 6
5
2
1 3
7
4 9
20
5
6
对调整后的调运方案再进行最优性检验
销地 产地
B1
3 (0) 1 (0) 7
的对偶变量为u1，u2，…， um;v1，v2，…，vn
ui v j cij s.t . ui , v j 无 约 束 决策变量 xij 的检验数
ij cij C B B 1 Pij
cij YPij cij ( u1 , , um , v1 , , v n ) Pij cij ( ui v j )
§2 表上作业法
• 表上作业法实质是单纯形法。可归纳为： • (1) 找出初始基可行解。即在(m×n)产销平衡表 上用西北角法或最小元素法或Vogel法给出 m+n-1 个数字，称为数字格。它们就是初始基变量的 取值。 • (2) 求各非基变量的检验数，即在表上计算空格 的检验数，判别是否达到最优解。如已是最优 解，则停止计算，否则转到下一步。 • (3) 确定换入变量和换出变量，找出新的基可行 解。在表上用闭回路法调整。 • (4) 重复(2)，(3)直到得到最优解为止。 1
例3-1 某公司经销甲产品。它下设三个加工
厂。每日的产量分别是：A1为7吨，A2为4吨， A3为9吨。该公司把这些产品分别运往四个销 售点。各销售点每日销量为：B1为3吨，B2为6 吨，B3为5吨，B4为6吨。已知从各工厂到各销 售点的单位产品的运价为表3-3所示。问该公 司应如何调运产品，在满足各销点的需要量的
x23 c23-(u2+v3)=0 即2-(u2+v3)=0 x34 c34-(u3+v4)=0 5-(u3+v4)=0 x21 c21-(u2+v1)=0 1-(u2+v1)=0 x32 c32-(u3+v2)=0 4-(u3+v2)=0 x13 c13-(u1+v3)=0 3-(u1+v3)=0 x14 c14-(u1+v4)=0 10-(u1+v4)=0 由u1=0可求得 u2=-1,u3=-5,v1=2,v2=9,v3=3,v4=10
8


B2
④
B3
⑤
B4
销地 B1 产地 3 A1
A2
11 9 4
3 2 10
10 8 5 [3],2
0,0,7 1,1,6 1,2
1 7 2,2
A3
[5] 1,1
初始调运方案 销地 B 1 产地 A1
A2
B2
B3
B4
产量 7 4 9
9
5
2 1
3 6
A3
3
销量
3
6
5
6
2-2 最优解的判别 判别的方法是计算空格(非基变量)的检验数 cij-CBB-1Pij，i, j∈N。因运输问题的目标函数是 要求实现最小化，故当所有的cij-CBB-1Pij ≥0 时，为最优解。 1.闭回路法 在给出调运方案的计算表上，从每一空格(非基 格)出发，用水平或垂直线向前划，当碰到一 数字格(基格)时转90°后，继续前进，直到回 到起始空格为止。闭回路如图所示。 从每一空格出发一定存在且可以找到唯一的闭 回路。注意：对于每个闭回路，除该空格外，其 余顶点都在有数字格（基格）。 10
。
18
2.3 改进的方法——闭回路调整法 选择负检验数中最小的检验数，以其对应的空 格(非基格)为调入格，具体步骤如下： 第一步，以 xij 为换入变量，找到运输表中的闭 回路； 第二步，以非基格 (Ai , Bj) 为第一个奇数顶点， 沿闭回路对其顶点依次编号； 第三步，闭回路所有偶数顶点中，找出运输量 最小的顶点，该最小运输量为调整量θ，该顶 点对应的变量为换出变量； 第四步，闭回路所有奇数顶点都加上调整量θ， 所有偶数顶 点都减去调整量θ，得出新的运 输方案。
9
5
销量
3
6
5
6
附加说明：
• 每次安排调运量时，总有某一产地的产量已被 全部调出或某一销地的销量已被全部调入，此 时要将该产地所在行或该销地所在的列在从单 位运价表中划去，如果在某次安排调运量时， 同时有一个产地的产量和一个销地的销量被全 部调出（入），此时，既要划去该产地所在的 行，又要划去该销地所在的列，为了保证有数 字格（基格）为m+n-1个，必须在所划去的行 与列的其它格上填写一个0，并将其视为基格。
15
基变量 xij 的检验数σij=cij-(ui+vj)=0， 共计m+n-1个方程， m+n个未知数 令u1 = 0 ( ui , vj中的任一个取任意数均可)，可以决定所有ui , vj
例1的由最小元素法得到的初始解中 x23，x34，x21，x32，x13，x14是基变量，对应的检验数：
基变量 检验数
以下是例3-1利用最小元素法得到的初始调运方 案，具体过程如图表所示。
4

销地 B1 产地 3 A1
A2
④ B2 11 9 4 6

B3
B4
产量
7 4 9 ⑤
3 2 10 5
10 8 5 6
1 7 3
A3
销量
初始调运方案 销地 B 1 产地 A1
A2
B2
B3
B4
产量 7 4
4 1 6
3
3
A3
3
成了以(A1，B1)空格为起点，其他为数字格的闭
回路。
12
经过这样的调整总运价改变的数值为： σ11=3-3+2-1= 1 销地 产地
B1
(+1) (-1) 3
B2
3 1 7 11 9
B3
(-1)
B4
3 10 3 8
产量
7 4
A1
A2
4
2 1 (+1)
10 5
A3
销量 3
6
6
4
3
6
5
9
13
2. 位势法
B2
11 (2) 9 (2) 4
B3
3 (0) 2 (1) 10
B4
10 (0) 8 (0) 5
ui
0 -2
A1 A2
A3
(9)
(0)
(12)
(0)
-5
vj
3
9
3
10
由于所有检验数均非负，现行方案已是最优方案。
21
2.4 表上作业法计算中可能出现如下情况 1. 无穷多最优解 所有变量检验数≥0，某个非基变量(非基格) 检验数=0 。 比如，例1最优解，x11检验数为0，经闭回路 调整后得到的新解仍是最优解。 2. 退化解 最优解中存在某些基变量的值为零。
22
6
2. Vogel法
最小元素法的缺点是：为了节省一处的费用，
有时造成在其他处要多花几倍的运费。伏
格尔法也考虑次小运费，如不能按最小运
费就近供应，就考虑次小运费，最小运费
与次小运费差额越大，说明不能按最小运 费调运时，运费增加越多。因而对差额最 大处，优先采用最小运费调运。
7
• 伏格尔法的步骤是： 第一步：分别计算出各行和各列的最小运费和次最小 运费的差额，并填入该表的最右列和最下行。 第二步：从行或列差额中选出最大者，选择它所在行或 列中的最小元素，确定调运关系，划去单位运价表中 相关的行或列。 第三步：对未划去的元素再分别计算出各行、各列的最 小运费和次最小运费的差额，并填入该表的最右列和 最下行。重复第一、二步。直到给出初始解为止。
3 (0) 2 (0) 10 (12) (-1) (0)
10
0 -1 -5
8
5 （0）
2
9
3
10
17
关于位势法的补充说明 • 利用位势法计算的各空格的检验数与利用闭回 路法计算的检验数是一致的。例如，计算空格 • (A1,B1)的检验数时，空格(A1,B1)所对应的闭回 路的四个顶点依次为(A1,B1)，(A1,B3)，(A2,B3) • (A2,B1)，因此： • 按闭回路计算为σ11=c11-c13+c23-c21; • 按位势法计算为σ11=c11-(u1+v1)=c11-[(u1+v3) • -(u2+v3)+(u2+v1)]=c11-c13+c23-c21
14
位势法的步骤： • 1.将调运方案中的调运量改为相应的单位运价； • 2.确定各行(列)的行(列)势，使得基格的单位运 价cij恰好等于其所在行的行势(ui)与所在列的列 势(vj)之和； • 3.计算各空格的行势(ui)与势(vj)之和ui+vj ； • 4.计算各空格的检验数λij=cij-(ui+vj) 。
调运方案中空格所对应的闭回路
销地 产地
B1
B2
B3
4
B4
3
产量
7 4
A1
A2
3
1
A3
销量 3
6
6 5
3
6
9
11
闭回路法计算检验数的经济解释为：在已给 出初始解的表中，可从任一给B1。为了保持产销
平衡，就要依次作调整：在(A1，B3)处减少1吨，
(A2，B3)处增加1吨，(A2，B1)处减少1吨，即构