- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
x11
2 8 4
x12
2
x13
7
x14
27
x21
3 5 9
x22
10
x23
6
x24 x34
13 19
x31
22 13
x32
12
x33
第三章 运输问题
9
运输表中一个基必须具备特点
运输表中一个基必须具备的特点
1、一个基应占表中的m+n-1格;
2、构成基的同行同列格子不能构成闭回路;
3、一个基在表中所占的格子应包括表的每行 和每列。
xij ai
j 1
i 1,2,..., m
xij b j
i 1
m
j 1,2,..., n
Xij ≥0
第三章 运输问题
5
2、运输模型的特点
1)系数矩阵为稀疏矩阵 x11 ... x1n x21 ...x2 n ... xm1 ... xmn 1 1 ...1 1 1 ... 1 A 1 1 1 1 1 1 ( m n )列
minZ=9X11+18X12+X13+10X14+11X21+6X22+8X23+18X24+14X31+12X32+2X33+16X34 s.t X11+X12+X13+X14 X21+X22+X23+X24 = 9 供 应 地 约 束 需 求 地 约 束
=
X31+X +X31 32+X33+X34 ==46 +X32 = 9 +X33 = 7
27
2
19
13 0 12 0 13 0
19
0
18
最小元素法（5）
1 6 1 8 2 5 3 22 2
第三章 运输问题
2 7 5
3 3
4 14 0
1
4 2 7
13 13
9 10
12
6
27
2
19
13 0 12 0 13 0
19
0
19
最小元素法（6）
1 6 1 8 2 5 3 22 0
第三章 运输问题
ui , v j 无符号约束
第三章 运输问题
7
二、 运输表的表示
运价
收点 发点
运量
B2 B3 1 B4 10
检验数
发量
B1 9X
A1
σij
ij
18
9
A2
11
6
8
18
10
A3
收量
14 4
12 9
2 7
16 5
6
第三章 运输问题
8
运输问题的表格表示
运价
1 1 6
σij
运量
2 3 5 3 4
检验数
7
14
10
X11 X12 X13 X14 +X21 +X22 +X23 +X24
+X34 = 5
X11 X12 X13 X14 X21 X22 X23 X24 X31 X32 X33 X34 ≥0
第三章 运输问题
4
运输问题线性规划模型
min z cij xij
i 1 j 1
n
m
n
s.t
4
-5
2
-5
7
-7
8
9
13
10
6
6
-9
27
6
13 12 13
13
19
z24-c24=(c23-c33+ c34)-c24=(2-10+6)-7=-9
第三章 运输问题
闭回路法(5)
1 6 1 8 2 5 3 7
2 5
3 3
4 14
14
4
-5
2
-5
7
-7
8
9
13
10
6
6
-9
27
+11
22 13 12
6
2) 对运输问题任一基B，其逆矩阵B 1必为一整数矩阵，若 ai , b j都为整数，则任一基可行解必为整数。X B B 1b) (
3) 对偶问题
max w ai ui b j v j
i 1 j 1 m n
s.t
ui v j cij i 1,2,..., m j 1,2,..., n
第三章 运输问题
例题，入基变量与进基变量的选择
1 6 1 8 2 5 3 7 2 5 3 3 4 u1=-4
14
4
-5
2
-5
7
-7
8
9
13
10
6
6
-9
u2=-2
+11
v1=10
+3
v2=6
6
v3=4
13
v4=0
u3=6
x31进基, min{x21,x33}=min{8,6}=6, x33离基
第三章 运输问题
调整运量,重新计算检验数,确定进基、离基变量
1 6 1 8 2 5 3 22 7
2 5
3 3
4 14
14
4
-5
2
-5
7
+4
2
9
13
10
12
6
+2
27
6
13
-8
12
-11
13
13
19
x14进基, min{x11,x34}=min{14,13}=13, x34离基
第三章 运输问题
调整运量, 重新计算检验数
0 3
12
第三章 运输问题
0
0
10
17
11
39
（二）无运输通路
如：Ａ２至Ｂ３无运输通路
在最优运输方案中, x23 0
可令c23 M (目标函数 min)
第三章 运输问题
40
无运输通路，则运价为M
1 1 2 3 4 12 5 2 10 2 6 7 M 11 3 22 18
第三章 运输问题
第三章 运输问题
1 1 ... 1 ( m n )行 1 由于前m个供应地约束和后n个需求 1 地约束是线性相关的，因此运输问题 1 系数矩阵的秩<m+n。可以证明，运
输问题系数矩阵的秩为m+n-1,即基可 行解只有m+n-1个变量
6
2、运输模型的特点
2 5
3 3
4 14
14
4
-5
2
-5
7
-7
8
9
13
10
6
6
27
6
13 12 13
13
19
z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7
第三章 运输问题
闭回路法(4)
1 6 1 8 2 5 3 22 7
2 5
3 3
4 14
14
第三章 运输问题
闭回路法(2)
1 6 1 8 2 5 3 22 7
2 5
3 3
4 14 7
14
4
-5
2
-5
8
9
13
10
6
6
27
6
13 12 13
13
19
σ13=z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5
第三章 运输问题
闭回路法(3)
1 6 1 8 2 5 3 22 7
第三章 运输问题
d4=13 总需求量60吨
2
供求平衡的运输问题
一、运输问题线性规划模型
1、运输问题的一般提法
收点
发点
B1 9 11
B2 18 6
B3 1 8
B4 10 18
发量
A1 A2
9 10
A3
收量
14
4
12
9
2
7
16
5
6
（供需平衡） 问：如何合理调运，才能使总运费最少？
第三章 运输问题
3
设Xij 为发点运往收点的运输量.i=1,2,3 j=1,2,3,4
第三章 运输问题
21
非基变量xij的检验数zij-cij—闭回路法(1)
1 6 1 8 2 5 3 22 7
2 5
3 3
4 14
14
4
-5
2 7
8
9
13
10
6
6
27
6
13 12 13
13
19
算法：空格（i,j)的检验系数σij可表示为：由空格所作出的闭回路中所有偶数 格对应的单位运价之和减去所有 奇数格对应的单位运价之和的差。 σ12=z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5
• 15
1
1
10
1 1 2
0 2 10
• 25
3 2 3 10 2 0 4
第三章 运输问题
34
利用西北角法给出初始解
1 8 1 7 2 10
+6
2 5 10 10 5 10 5 9 6
3
4
0 -2 -5 0
15
25 10
