主讲人,卫 斌制 作,魏永牛天水师范学院 数理与信息科学学院 数学系
２００４年５月在处理产、供、销的经济活动中，
会经常遇到物资调拨的运输问题。如粮棉油、煤炭、钢铁、水泥、化肥、木材等物资要由若干个产地调运到若干个销售地。问题是，怎样制定合理的调用方案才能使总运输费用最少？本章将专门讨论这类特殊形式的线性规划问题。
导言第五章 运输问题例 某食品公司经销的主要商品之一是糖果，它下面设有三个加工厂。某个的产量分别为 A1— 7t,A2— 4t,A3— 9t该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为：
B1— 3t,B2— 6t,B3— 5t,B4— 6t 。已知从各个加工厂到各销售部门每吨的运价见下表：
5.1
运输问题的数学模型 31047A3
8291A2
103113A1
B4B3B2B1门市部加工厂单位：元 /t
问：该食品公司应如何调运，在满足各部门销售的情况下，
使总的运费支出为最少？
产销平衡的运输问题无论全国或一个地区，在各种生产或生活物资调运中都可以提出入上述问题类似的例子。
现在把问题概括一下，在线性规划中我们研究这样一类运输问题：
5.1
运输问题的数学模型产销平衡的运输问题设有某种物资要从 m个产地（或称发点）
Ai(i=1,2,…,m)运往 n个销地（或称收点） Bj(j=1，
2,…n),Ai的产量为 ai,Bj的销量为 bj，把 Ai运到 Bj的单位运价设为 cij，问怎样编制调运方案才能使总运费最少？
假设从 Ai运到 Bj的物资数量为 xij，总运费为 S，总产量 =总销量。那么这个运输问题的数学模型是：
5.1
运输问题的数学模型产销平衡的运输问题产销平衡的运输问题
5.1
运输问题的数学模型运输问题的数学模型是,
产销平衡表产量 ai产地 销地销量 bi
1 ２ … n
１
２
m
b1 b2 … bn
a1
a2
am
x11 x12 … x1n
x21 x22 … x 2n
xm1 xm2 … x mn
产地 销地 1 ２ … n
１
２
m
c11 c12 … c1n
c21 c22 … c 2n
cm1 cm2 … c mn
单位运价表
n
j
m
i
ijij xcS
1 1
m in
),,2,1,,,2,1(0,0,0
.
1 1
1
1
njmixba
ba
bx
ax
ts
ijji
m
i
n
j
ji
m
i
jij
n
j
iij
产销平衡的运输问题
5.1
运输问题的数学模型运输问题的数学模型是,
0,0
..
min
bX
bAXts
CXS
C=(c11,c12,…,c1n,c21,c22,c2n,…,cm1,cm2,…c mn)
B=（ a1,a2,…,am,b1,b2,…b n)T
X =(x11,x12,…,x1n,x21,x22,x2n,…,xm1,xm2,…x mn)T
5.1
运输问题的数学模型其矩阵形式为产销平衡的运输问题
100100100
010010010
001001001
111000000
000111000
000000111
A
行n
行m
（ 1）产量大于销量的情形
m
i
n
j
ji ba
1 1
m
i
n
j
ijij xcS
1 1
m in
),,2,1,,,2,1(0,0,0
..
1
1
njmixba
bx
ax
ts
ijji
m
i
jij
n
j
iij
5.1
运输问题的数学模型产销不平衡运输问题的转化其运输问题的数学模型是由于总量大于总销量，所以多余物资应储存在产地。
社某产地 Ai的多余存储量为 xi,n+1，于是运输问题的约束条件方程组为：
ini
n
j
n
j
ijij axxx
1,1
1 1
),,2,1( mi
m
i
jij bx
1
),,2,1( nj
1
11 1
1,?
n
n
j
i
m
i
m
i
ini bbax
则
5.1
运输问题的数学模型产销不平衡运输问题的转化
m
i
n
j
ijij xcS
1
1
1
m in
)1,,2,1,,,2,1(0,0,0
.
1
1
1
1
1
1
njmixba
ba
bx
ax
ts
ijji
m
i
n
j
ji
m
i
jij
n
j
iij
5.1
运输问题的数学模型可将不平衡的运输问题（ 5.3）化为如下的平衡运输问题
),,2,1(01,mic ni
产销不平衡运输问题的转化令
（ 2）产量大于销量的运输问题这时可增加一个设想的发点 Am+1，发出量为并令该发点到收点 Bｊ 的运价 Cｍ＋１,ｊ＝０ （ｊ＝１，２,…,ｎ），
同样可将不平衡的运输问题转化为平衡的运输问题。
如无特别说明，本章仅限于对平衡问题的运输问题求解的讨论。
同一般的线性规划问题一样，运输问题的最优解也一定能在它的基本可行解中找到。由于运输问题（５,２）的约束系数矩阵
Ａ的前ｍ行之和恰好等于后ｎ行之和，即矩阵Ａ的行向量组线性相关，因此Ａ的秩必小于ｍ +ｎ．
5.1
运输问题的数学模型产销不平衡运输问题的转化
n
j
m
i
ijm aba
1 1
1
100000
010000
001000
111100
000010
000001
01
5.1
运输问题的数学模型产销不平衡运输问题的转化根据以上讨论可知，运输问题（ 5.2）的基矩阵应由 m+n-1个线性无关的列向量组成，这些列向量是约束方程 Ax=b中去掉多余方程后剩下的 m+n-1个方程的系数列向量，因此在研究运输问题的基时只要在 A中找到 m+n-1个线性无关的系数列向量就可以了。
运输问题中的约束方程和变量个数一般比较多。例如 m=25,n=500
时，就有 525个约束方程和 12500个变量，这样的问题即使使用电子计算机求解也很困难。但根据运输问题具有的特殊结构，有专门为其设计的求解方法，这里不作介绍。对小规模的运输问题的求解，
可通过表上作业法和图上作业法去完成。
5.1
运输问题的数学模型因此秩（ A） =m+n-1。同样可得 A的增广矩阵 =（ a,b）的秩也等于 m+n-1。所以（ 5.2）式的 m+n个等式约束中有一个是多余的，
于是增广矩阵 的任意一行都可用其余 m+n-1行线性表出。这样，运输问题（ 5.2）中去掉任一个等式约束后就成为标准形式的线性规划问题，便可用单纯形或对偶单纯形方法求解。
A
A
产销不平衡运输问题的转化
B1 … Bj … Bn 发量
A1 x11C
11
… xijC
ij
… x1nC
1n
a1
… … … … … … …
Aj xi1
Ci1
… xijC
ij
… xin
Cin
ai
… … … … … … …
Am xm1C
m1
… xmjC
mj
… xmnC
mn
am
收量 b1 … bj … bn
5.2
运输问题的表上作业法对于小规模的运输问题其求解过程可以在表上进行。
5.2
运输问题的表上作业法表中共有 mn个格子，每个格子对应一个变量求解运输问题的首要任务是，在表上找到
m+n-1个格子对应的一组变量，
11211,,,2 nmnm jijiji xxx?
是一组变量。
为此，先引入以下概念和结论。
定义 5.1
5.2
运输问题的表上作业法称变量组的集合
},,,,,{ 132222111 jijijijijiji sss xxxxxx?
},,,,,{ 151333314145 xxxxxx
是一个闭回路。其中 i1,i2,…,i s互不相同,j1,j2,…,j s互不相同,称其中每个变量为闭回路的顶点。
例如，变量组中的 i1=4,i2=3,i3=1,j1=5,j2=1,j3=3 各互不相同，若在表格中把相邻两个顶点，第一个顶点与最后一个顶点用直线段连接起来，就可在下表 5.2中画出这个闭回路。
B1 B2 B3 B4 B5
A1
A2
A3
A4 X45X41
X31 X33
X13 X15
定义 5.1
5.2
运输问题的表上作业法
B1 B2 B3 B4 B5
A1
A2
A3
A4
X11
但变量组 {x11,x12,x22,x24,x44,x42,x21}不能构成一条闭回路，因为 x42不是拐角点。
X12
X22 X24
X44X42
X42
132222111,,,,,,jijijijijiji sss xxxxxx?若变量组是一个闭回路，则这个变量组对应矩阵 A中的列向量组线性相关。
证明 矩阵 A中的每列只有两个元素为１，其余都是０。变量
xij对应Ａ中的列向量是
5.2
运输问题的表上作业法定理 5.1
0
1
0
1
0
ij
p
第 i个分量第 m+j个分量
5.2
运输问题的表上作业法定理 5.1
通过计算闭回路中变量对应Ａ中的列向量，得
0132222111 jijijijijiji SSS PPPPPP?
这表明变量组对应矩阵Ａ中列向量组线性相关。
ss jijiji xxx,,,2211?变量组 对应矩阵Ａ中列向量组根据以上结论，给出了从表格上判断运输问题的方法。 m+n-1个变量是否为一组基变量就看表中
m+n-1个变量是否含有闭回路。于是可从表格上方便的求出运输问题的初始基本可行解来,
5.2
运输问题的表上作业法定理 5.2
ss jijiji ppp?,,2211
线性无关的充要条件是该变量组不含有闭回路。
求解运输问题的表上作业法可按以下步骤进行。
一,编制初始调运方案方法一 最小元素法令
jiij bax,min?
（ 1）若 ai<bj，则取 xij=ai,而 xik=0(k=1,2,…,j -
1,j+1,…,n),将 ai填入 (i,j)格内。这时
xi1+xi2+…+x i,j-1+xij+xi,j+1+…+x in=xij=ai
5.2
运输问题的表上作业法求解运输问题的表上作业法的步骤：
编制初始调运方案就是求运输问题的初始基本可行解，方法有两种
（ 2）若 ai>bj，则取 xij=bj,而 xsj=0(s=1,2,…,i -
1,i+1,…,m),将 bj填入 (i,j)格内。这时
x1j+x2j+…+x ij+…+x mj=xij=bj
例 5.1用最小元素法求下列运输问题的初始调运方案销地产地
B1 B2 B3 B4 B5
Ａ １
Ａ ２
Ａ ３
产量
ai
９
４
８
３ ５ ５ ３ ５销量 bj ２１
B1 B2 B3 B4 B5
10 20 5 9 10
2 10 8 25 6
1 15 7 10 4
平衡表 运价表
5.2
运输问题的表上作业法一,编制初始调运方案求解运输问题的表上作业法的步骤：
销地产地 B1 B2 B3 B4 B5
Ａ １
Ａ ２
Ａ ３
产量
ai
９
４
８
３ ５ ５ ３ ５销量 bj ２１
B1 B2 B3 B4 B5
10 20 5 9 10
2 10 8 25 6
1 15 7 10 4
平衡表 运价表初始基本可行解为
{x12,x13,x14,x22,x31,x32,x35}={1,5,3,4,3,0,5},
相应运价为：
{c12,c13,c14,c22,c31,c32,c35}={20,5,9,10,1,15,4},
由此表上作业得初始调运方案的总运费为
S=1x20+5x5+3x9+4x10+3x1+0x15+5x4=135（元）
5.2
运输问题的表上作业法一,编制初始调运方案求解运输问题的表上作业法的步骤：
1 5 3
4
3 0 5
解
1
5
23
4
4
1
5
1
6
7
方法二 左上角法 (也称西北角法）
令
1111,m in bax?
（ 1）若 a1<b1，则取 x11=a1,而 x1k=0(k=2,3,…,n),将 a1填入
(1,1)格内。这时
x11+x12+…+x 1n=x11=a1
（ 2）若 a1>b1，则取 x11=b1,则取 x11=b1,而 xs1=0(s=2,3,…,m),将 b1填入
(1,1)格内。这时
x11+x21+…+x m1=b1
5.2
运输问题的表上作业法一,编制初始调运方案求解运输问题的表上作业法的步骤：
例 5.2用左上角法求下列运输问题的初始调运方案销地产地 B1 B2 B3 B4 B5
Ａ １
Ａ ２
Ａ ３
产量
ai
9
４
８
３ ５ ５ ３ ５销量 bj ２１
B1 B2 B3 B4 B5
10 20 5 9 10
2 10 8 25 6
1 15 7 10 4
平衡表 运价表
5.2
运输问题的表上作业法一,编制初始调运方案求解运输问题的表上作业法的步骤：
5.2
运输问题的表上作业法一,编制初始调运方案求解运输问题的表上作业法的步骤：
解销地产地 B1 B2 B3 B4 B5
Ａ １
Ａ ２
Ａ ３
产量
ai
9
４
８
３ ５ ５ ３ ５销量 bj ２１
B1 B2 B3 B4 B5
10 20 5 9 10
2 10 8 25 6
1 15 7 10 4
平衡表 运价表
1
3 6
2
5
1 3
1
4
44
5
0
6
3 5 75
初始基本可行解为
{x11,x12,x13,x23,x33,x34,x35}={3,5,1,4,0,3,5},
相应运价为：
{c11,c12,c13,c23,c33,c34,c35}={10,20,5,8,7,10,4},
由此表上作业得初始调运方案的总运费为 S=
S=3x10+5x20+1x5+4x8+0x7+3x10+5x4=217 （元）
２００４年５月在处理产、供、销的经济活动中，
会经常遇到物资调拨的运输问题。如粮棉油、煤炭、钢铁、水泥、化肥、木材等物资要由若干个产地调运到若干个销售地。问题是，怎样制定合理的调用方案才能使总运输费用最少？本章将专门讨论这类特殊形式的线性规划问题。
导言第五章 运输问题例 某食品公司经销的主要商品之一是糖果，它下面设有三个加工厂。某个的产量分别为 A1— 7t,A2— 4t,A3— 9t该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为：
B1— 3t,B2— 6t,B3— 5t,B4— 6t 。已知从各个加工厂到各销售部门每吨的运价见下表：
5.1
运输问题的数学模型 31047A3
8291A2
103113A1
B4B3B2B1门市部加工厂单位：元 /t
问：该食品公司应如何调运，在满足各部门销售的情况下，
使总的运费支出为最少？
产销平衡的运输问题无论全国或一个地区，在各种生产或生活物资调运中都可以提出入上述问题类似的例子。
现在把问题概括一下，在线性规划中我们研究这样一类运输问题：
5.1
运输问题的数学模型产销平衡的运输问题设有某种物资要从 m个产地（或称发点）
Ai(i=1,2,…,m)运往 n个销地（或称收点） Bj(j=1，
2,…n),Ai的产量为 ai,Bj的销量为 bj，把 Ai运到 Bj的单位运价设为 cij，问怎样编制调运方案才能使总运费最少？
假设从 Ai运到 Bj的物资数量为 xij，总运费为 S，总产量 =总销量。那么这个运输问题的数学模型是：
5.1
运输问题的数学模型产销平衡的运输问题产销平衡的运输问题
5.1
运输问题的数学模型运输问题的数学模型是,
产销平衡表产量 ai产地 销地销量 bi
1 ２ … n
１
２
m
b1 b2 … bn
a1
a2
am
x11 x12 … x1n
x21 x22 … x 2n
xm1 xm2 … x mn
产地 销地 1 ２ … n
１
２
m
c11 c12 … c1n
c21 c22 … c 2n
cm1 cm2 … c mn
单位运价表
n
j
m
i
ijij xcS
1 1
m in
),,2,1,,,2,1(0,0,0
.
1 1
1
1
njmixba
ba
bx
ax
ts
ijji
m
i
n
j
ji
m
i
jij
n
j
iij
产销平衡的运输问题
5.1
运输问题的数学模型运输问题的数学模型是,
0,0
..
min
bX
bAXts
CXS
C=(c11,c12,…,c1n,c21,c22,c2n,…,cm1,cm2,…c mn)
B=（ a1,a2,…,am,b1,b2,…b n)T
X =(x11,x12,…,x1n,x21,x22,x2n,…,xm1,xm2,…x mn)T
5.1
运输问题的数学模型其矩阵形式为产销平衡的运输问题
100100100
010010010
001001001
111000000
000111000
000000111
A
行n
行m
（ 1）产量大于销量的情形
m
i
n
j
ji ba
1 1
m
i
n
j
ijij xcS
1 1
m in
),,2,1,,,2,1(0,0,0
..
1
1
njmixba
bx
ax
ts
ijji
m
i
jij
n
j
iij
5.1
运输问题的数学模型产销不平衡运输问题的转化其运输问题的数学模型是由于总量大于总销量，所以多余物资应储存在产地。
社某产地 Ai的多余存储量为 xi,n+1，于是运输问题的约束条件方程组为：
ini
n
j
n
j
ijij axxx
1,1
1 1
),,2,1( mi
m
i
jij bx
1
),,2,1( nj
1
11 1
1,?
n
n
j
i
m
i
m
i
ini bbax
则
5.1
运输问题的数学模型产销不平衡运输问题的转化
m
i
n
j
ijij xcS
1
1
1
m in
)1,,2,1,,,2,1(0,0,0
.
1
1
1
1
1
1
njmixba
ba
bx
ax
ts
ijji
m
i
n
j
ji
m
i
jij
n
j
iij
5.1
运输问题的数学模型可将不平衡的运输问题（ 5.3）化为如下的平衡运输问题
),,2,1(01,mic ni
产销不平衡运输问题的转化令
（ 2）产量大于销量的运输问题这时可增加一个设想的发点 Am+1，发出量为并令该发点到收点 Bｊ 的运价 Cｍ＋１,ｊ＝０ （ｊ＝１，２,…,ｎ），
同样可将不平衡的运输问题转化为平衡的运输问题。
如无特别说明，本章仅限于对平衡问题的运输问题求解的讨论。
同一般的线性规划问题一样，运输问题的最优解也一定能在它的基本可行解中找到。由于运输问题（５,２）的约束系数矩阵
Ａ的前ｍ行之和恰好等于后ｎ行之和，即矩阵Ａ的行向量组线性相关，因此Ａ的秩必小于ｍ +ｎ．
5.1
运输问题的数学模型产销不平衡运输问题的转化
n
j
m
i
ijm aba
1 1
1
100000
010000
001000
111100
000010
000001
01
5.1
运输问题的数学模型产销不平衡运输问题的转化根据以上讨论可知，运输问题（ 5.2）的基矩阵应由 m+n-1个线性无关的列向量组成，这些列向量是约束方程 Ax=b中去掉多余方程后剩下的 m+n-1个方程的系数列向量，因此在研究运输问题的基时只要在 A中找到 m+n-1个线性无关的系数列向量就可以了。
运输问题中的约束方程和变量个数一般比较多。例如 m=25,n=500
时，就有 525个约束方程和 12500个变量，这样的问题即使使用电子计算机求解也很困难。但根据运输问题具有的特殊结构，有专门为其设计的求解方法，这里不作介绍。对小规模的运输问题的求解，
可通过表上作业法和图上作业法去完成。
5.1
运输问题的数学模型因此秩（ A） =m+n-1。同样可得 A的增广矩阵 =（ a,b）的秩也等于 m+n-1。所以（ 5.2）式的 m+n个等式约束中有一个是多余的，
于是增广矩阵 的任意一行都可用其余 m+n-1行线性表出。这样，运输问题（ 5.2）中去掉任一个等式约束后就成为标准形式的线性规划问题，便可用单纯形或对偶单纯形方法求解。
A
A
产销不平衡运输问题的转化
B1 … Bj … Bn 发量
A1 x11C
11
… xijC
ij
… x1nC
1n
a1
… … … … … … …
Aj xi1
Ci1
… xijC
ij
… xin
Cin
ai
… … … … … … …
Am xm1C
m1
… xmjC
mj
… xmnC
mn
am
收量 b1 … bj … bn
5.2
运输问题的表上作业法对于小规模的运输问题其求解过程可以在表上进行。
5.2
运输问题的表上作业法表中共有 mn个格子，每个格子对应一个变量求解运输问题的首要任务是，在表上找到
m+n-1个格子对应的一组变量，
11211,,,2 nmnm jijiji xxx?
是一组变量。
为此，先引入以下概念和结论。
定义 5.1
5.2
运输问题的表上作业法称变量组的集合
},,,,,{ 132222111 jijijijijiji sss xxxxxx?
},,,,,{ 151333314145 xxxxxx
是一个闭回路。其中 i1,i2,…,i s互不相同,j1,j2,…,j s互不相同,称其中每个变量为闭回路的顶点。
例如，变量组中的 i1=4,i2=3,i3=1,j1=5,j2=1,j3=3 各互不相同，若在表格中把相邻两个顶点，第一个顶点与最后一个顶点用直线段连接起来，就可在下表 5.2中画出这个闭回路。
B1 B2 B3 B4 B5
A1
A2
A3
A4 X45X41
X31 X33
X13 X15
定义 5.1
5.2
运输问题的表上作业法
B1 B2 B3 B4 B5
A1
A2
A3
A4
X11
但变量组 {x11,x12,x22,x24,x44,x42,x21}不能构成一条闭回路，因为 x42不是拐角点。
X12
X22 X24
X44X42
X42
132222111,,,,,,jijijijijiji sss xxxxxx?若变量组是一个闭回路，则这个变量组对应矩阵 A中的列向量组线性相关。
证明 矩阵 A中的每列只有两个元素为１，其余都是０。变量
xij对应Ａ中的列向量是
5.2
运输问题的表上作业法定理 5.1
0
1
0
1
0
ij
p
第 i个分量第 m+j个分量
5.2
运输问题的表上作业法定理 5.1
通过计算闭回路中变量对应Ａ中的列向量，得
0132222111 jijijijijiji SSS PPPPPP?
这表明变量组对应矩阵Ａ中列向量组线性相关。
ss jijiji xxx,,,2211?变量组 对应矩阵Ａ中列向量组根据以上结论，给出了从表格上判断运输问题的方法。 m+n-1个变量是否为一组基变量就看表中
m+n-1个变量是否含有闭回路。于是可从表格上方便的求出运输问题的初始基本可行解来,
5.2
运输问题的表上作业法定理 5.2
ss jijiji ppp?,,2211
线性无关的充要条件是该变量组不含有闭回路。
求解运输问题的表上作业法可按以下步骤进行。
一,编制初始调运方案方法一 最小元素法令
jiij bax,min?
（ 1）若 ai<bj，则取 xij=ai,而 xik=0(k=1,2,…,j -
1,j+1,…,n),将 ai填入 (i,j)格内。这时
xi1+xi2+…+x i,j-1+xij+xi,j+1+…+x in=xij=ai
5.2
运输问题的表上作业法求解运输问题的表上作业法的步骤：
编制初始调运方案就是求运输问题的初始基本可行解，方法有两种
（ 2）若 ai>bj，则取 xij=bj,而 xsj=0(s=1,2,…,i -
1,i+1,…,m),将 bj填入 (i,j)格内。这时
x1j+x2j+…+x ij+…+x mj=xij=bj
例 5.1用最小元素法求下列运输问题的初始调运方案销地产地
B1 B2 B3 B4 B5
Ａ １
Ａ ２
Ａ ３
产量
ai
９
４
８
３ ５ ５ ３ ５销量 bj ２１
B1 B2 B3 B4 B5
10 20 5 9 10
2 10 8 25 6
1 15 7 10 4
平衡表 运价表
5.2
运输问题的表上作业法一,编制初始调运方案求解运输问题的表上作业法的步骤：
销地产地 B1 B2 B3 B4 B5
Ａ １
Ａ ２
Ａ ３
产量
ai
９
４
８
３ ５ ５ ３ ５销量 bj ２１
B1 B2 B3 B4 B5
10 20 5 9 10
2 10 8 25 6
1 15 7 10 4
平衡表 运价表初始基本可行解为
{x12,x13,x14,x22,x31,x32,x35}={1,5,3,4,3,0,5},
相应运价为：
{c12,c13,c14,c22,c31,c32,c35}={20,5,9,10,1,15,4},
由此表上作业得初始调运方案的总运费为
S=1x20+5x5+3x9+4x10+3x1+0x15+5x4=135（元）
5.2
运输问题的表上作业法一,编制初始调运方案求解运输问题的表上作业法的步骤：
1 5 3
4
3 0 5
解
1
5
23
4
4
1
5
1
6
7
方法二 左上角法 (也称西北角法）
令
1111,m in bax?
（ 1）若 a1<b1，则取 x11=a1,而 x1k=0(k=2,3,…,n),将 a1填入
(1,1)格内。这时
x11+x12+…+x 1n=x11=a1
（ 2）若 a1>b1，则取 x11=b1,则取 x11=b1,而 xs1=0(s=2,3,…,m),将 b1填入
(1,1)格内。这时
x11+x21+…+x m1=b1
5.2
运输问题的表上作业法一,编制初始调运方案求解运输问题的表上作业法的步骤：
例 5.2用左上角法求下列运输问题的初始调运方案销地产地 B1 B2 B3 B4 B5
Ａ １
Ａ ２
Ａ ３
产量
ai
9
４
８
３ ５ ５ ３ ５销量 bj ２１
B1 B2 B3 B4 B5
10 20 5 9 10
2 10 8 25 6
1 15 7 10 4
平衡表 运价表
5.2
运输问题的表上作业法一,编制初始调运方案求解运输问题的表上作业法的步骤：
5.2
运输问题的表上作业法一,编制初始调运方案求解运输问题的表上作业法的步骤：
解销地产地 B1 B2 B3 B4 B5
Ａ １
Ａ ２
Ａ ３
产量
ai
9
４
８
３ ５ ５ ３ ５销量 bj ２１
B1 B2 B3 B4 B5
10 20 5 9 10
2 10 8 25 6
1 15 7 10 4
平衡表 运价表
1
3 6
2
5
1 3
1
4
44
5
0
6
3 5 75
初始基本可行解为
{x11,x12,x13,x23,x33,x34,x35}={3,5,1,4,0,3,5},
相应运价为：
{c11,c12,c13,c23,c33,c34,c35}={10,20,5,8,7,10,4},
由此表上作业得初始调运方案的总运费为 S=
S=3x10+5x20+1x5+4x8+0x7+3x10+5x4=217 （元）
