3
A
3
3 11 4 2 12
销量
6 2 7 7
【解答】
:显然该问题是一个供需平衡问题,利用伏格法求出初始方案,如下表所示。
B1 B2 B3 B4
产量
A1 6 4 8 8 4 6
A2 9 2 5 6 2 3 4
A3 0 3 11 7 4 5 2 12
销量
6 2 7 7
用位势法求出各非基变量(即空格)的检验数,如下表所示。
B1 B2 B3
B4
i
u
A1 6 4 (3)
8
(3) 8 (1) 4
1
u =0
A2 (5) 9 2
5
(1) 6 2 3
2
u =0
A3 0 3 (7)
11
7 4 5 2
3
u =-1
j
v
1
v =4
2
v =5
3
v =5
4
v
3
因为所有非基变量的检验数均为非负的,故表中的解为最优解。按照此种方案调运,最小费用为:
6× 4+2×5+2×3+0×3+7×4+5×2= 78
三、 用标号算法求解下图中从 V
1
到各点的最短路