b1
c 12 … c 22 … .… .… .… c m2 … c m+1,2 …
b2 …
c 1n c 2n . . . c mn c m+1,n
bn
a1 a2 .
.
.
am am+1
作业 P103 3.7 3.8(a) 例2. 已知见表:试决定总运费最少的调运方案。
销地 产地
A1 A2 A3
销量
B1 B2 B3 B4
2. 进行最优性检验的位势法 运输问题的对偶问题数学模型为
m
n
maxw aiui bjvj
i1
j1
ui vj cij(i 1,2,...,m; j 1,2,...,n)
ui
,vj无约束 (i 1, 2, .., . m;j
1, 2, .., . n)
对约束条件加松弛变量,得
ui vj ysij cij 或写成
m)
j1
n
x ij x i,n 1 a i (i 1,2 ,..., m )
j1
m
x ij b j ( j 1,2 ,...,
n)
i1
m
x ij
i1
b j ( j 1,2 ,..., n 1)
x
ij
0(i
1,2 ,...,
m;
j
1,2 ,...,
n)
x
ij
0(i
1,2 ,...,
(0) 35 (0) 55 25
20
10 15 20 35 5
一次调整后方案
销地
B1
产地
A1
25
A2
A3
销量
25
B2 B3