2021年 运输问题.ppt

一、运输问题模型及其求解思路
1、问题的提出：
某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3。
各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示。
问：应如何调运可使总运输费用最小？
运输问题
2021/1/15
1
一、运输问题模型及其求解思路
B1
B2
B3
产量
A1
6
4
6
200
A2
6
5
5
300
销量
150
150
200
运价表
销量和＝产量和
产销平衡
运输问题
2021/1/15
2
一、运输问题模型及其求解思路
B1
B2
B3
产量
A1
x11
x12
x13
200
A2
x21
x22
x23
300
销量
150
150
200
为建立模型，设 xij 为从产地Ai运往销地Bj的运输量，得到下表：
运量表
运输问题
2021/1/15
3
一、运输问题模型及其求解思路
据题意，可建立线性规划模型：
Min f = 6x11+4x12+6x13+6x21+5x22+5x23
. x11+ x12 + x13 = 200
x21 + x22+ x23 = 300
x11 + x21 = 150
x12 + x22 = 150
x13 + x23 = 200
xij≥0(i=1,2；j=1,2,3）
运输问题
2021/1/15
4
一、运输问题模型及其求解思路
2、产销平衡运输问题模型的特点
从模型的建立可知：
列数为2（产地数）×3（销地数）＝6；
行数为2（产地数）+3（销地数）＝5；
再观察模型的系数矩阵：
运输问题
2021/1/15
5
一、运输问题模型及其求解思路
1 1 1 0 0 0 200
0 0 0 1 1 1 300
1 0 0 1 0 0 150
0 1 0 0 1 0 150
0 0 1 0 0 1 200
前2行之和＝后3行之和
运输问题
2021/1/15
6
一、运输问题模型及其求解思路
对于产销平衡的运输问题，若产地为m个，销地为n个，
则变量个数为m×n个，线性无关的约束条件个数为m+n-1，
故基本解中的基变量个数为m+n-1。
运输问题
2021/1/15
7
一、运输问题模型及其求解思路
3、运输问题求解思路——表上作业法
由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。
人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。
运输问题
2021/1/15
8
一、运输问题模型及其求解思路
B1
B2
B3
产量
A1
6
x11
4
x12
6
x13
200
A2
6
x21
5
x22
5
x23
300
销量
150
150
200
我们关心的量均在运价表和运量表中，故将两表和为作业表：
运输问题
2021/1/15
9
一、运输问题模型及其求解思路
表上作业法的总体思路和单纯形法类似：
基本可行解
是否最优解
结束
换基
是
否
每个步骤都充分利用运输表的特点
运输问题
2021/1/15
10