第五章数学规划（整数规划）2011.ppt

运输问题
人们在从事生产活动中,不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资,分别运到需要这些物资的地区,根据各地的生产量和需要量及各地之间的运输费用,如何制定一个运输方案,使总的运输费用最小。这样的问题称为运输问题。
1
【例】求表3-6所示的运输问题
表3-6
销地
产地
B1
B2
B3
产量
A1
8
6
7
30
A2
4
3
5
45
A3
7
4
8
25
销量
60
30
10
100
2
m个产地n个销地且产销平衡的运输问题数学模型为:
3
【定理1】设有m个产地n个销地且产销平衡的运输问题,则基变量数为m+n-1。
【证】因为产销平衡,即,将前m个约束方程两边相加得
再将后n个约束相加得
显然前m个约束方程之和等于后n个约束方程之和,m+n个约束方程是相关的,系数矩阵中任意m+n阶子式等于零,
故r(A)=m+n-1所以运输问题有m+n-1个基变量。
4
表上作业法也称为运输单纯形法,是直接在运价表上求最优解的一种方法,它的步骤是:
第一步:求初始基行可行解(初始调运方案),常用的方法有最小元素法、元素差额法(Vogel近似法)、左上角法。
第二步:求检验数并判断是否得到最优解,常用求检验的方法有闭回路法和位势法,当非基变量的检验数λij全都非负时得到最优解,若存在检验数λlk<0,说明还没有达到最优,转第三步。
第三步:调整运量,即换基,选一个变量出基,对原运量进行调整得到新的基可行解,转入第二步。
5
初始基可行解
,即最小运价Cij对应的变量xij优先赋值
然后再在剩下的运价中取最小运价对应的变量赋值并满足约束,依次下去,直到最后一个初始基可行解。
6
【例】求表3-6所示的运输问题的初始基可行解。
表3-6
销地
产地
B1
B2
B3
产量
A1
8
6
7
30
A2
4
3
5
45
A3
7
4
8
25
销量
60
30
10
100
7
(Vogel近似法)运费差额法对最小元素法进行了改进,考虑到产地到销地的最小运价和次小运价之间的差额,如果差额很大,就选最小运价先调运,否则会增加总运费。例如下面两种运输方案,
15 15 15 15
前一种按最小元素法求得,总运费是Z1=10×8+5×2+15×1=105,后一种方案考虑到C11与C21之间的差额是8-2=6,如果不先调运x21,到后来就有可能x11≠0,这样会使总运费增加较大,从而先调运x21,再是x22,其次是x12这时总运费Z2=10×5+15×2+5×1=85<Z1。
8
运费差额法求初始基本可行解的步骤是:
第一步:求出每行次小运价与最小运价之差,记为ui,i=1,2,…,m;同时求出每列次小运价与最小运价之差,记为vj,j=1,2,…,n;
第二步:找出所有行、列差额的最大值,即L=max{ui,vi},差额L对应行或列的最小运价处优先调运;
第三步:这时必有一列或一行调运完毕,在剩下的运价中再求最大差额,进行第二次调运,依次进行下去,直到最后全部调运完毕,就得到一个初始调运方案。
用运费差额法求得的基本可行解更接近最优解,所以也称为近似方案。
9
求检验数
求出一组基可行解后,判断是否为最优解,仍然是用检验数来判断,记xij的检验数为λij由第一章知,求最小值的运输问题的最优判别准则是:
所有非基变量的检验数都非负,则运输方案最优(即为最优解)。
求检验数的方法有两种,闭回路法和位势法。
闭回路法求检验数求某一非基变量的检验数的方法是:在基本可行解矩阵中,以该非基变量为起点,以基变量为其它顶点,找一条闭回路,由起点开始,分别在顶点上交替标上代数符号+、-、+、-、…,以这些符号分别乘以相应的运价,其代数和就是这个非基变量的检验数。
10