第三章(运输问题).ppt

1、运 筹 学,运 输 问 题,物资运输问题,某种物资有m个产地Ai，i=1,2,.,m，产量分别为ai个单位；有n个销地Bj，销量分别为bj个单位，j=1,2,.n，Ai与Bj之间的单位运价为Cij，问应如何安排运输方案，才能使总运费最少？ 设从产地Ai，运往销地Bj的销量为Xij，则目标为总运费最小,物资运输问题,产地约束条件,销地约束条件,非负约束,物资运输问题,物资运输问题,产销平衡的运输问题,Proof :,则取,显然有 ，,又,所以 ，是问题的一个可行解。,又因为 ，对于任一可行 解有目标函数值 ，对于求极小化问题，目标函数 值有下界，则必有最优解。,物资运输问题,某地区有两个煤矿A1

2、 A2 ，所产的煤要运往三个城市B1 B2 B3，各产地的产量、销地的销量以及各产地到各销地的单位运费见下表，求使总运费最小的运输方案,物资运输问题,运输问题,总运费为Z=32500元,物资运输问题,求一个初始基本可行解 是 判断基本可行解是否最优 结 束 不是 求使目标得到改善的基本可行解,约束方程系数矩阵结构,约束方程系数矩阵结构,约束方程系数矩阵结构,基变量个数m+n-1,A 的增广矩阵的秩小于m+n,基变量个数m+n-1,A 的增广矩阵的秩等于m+n-1,基变量的构成,闭回路,其中，（i1i2,.,is互不相同，j1j2,.,js互不相同） 上述形式的变量的集合称为一个闭回路 其中的变

3、量称为闭回路的顶点,基变量的构成,闭回路,定义 1,凡是能排列成,（其中 互不相同， 互不相同）,形式的变量集合，称为一个闭回路，其中诸变量称为 这个闭回路的顶点.,如：,变量集合,变量集合,2、每一行（或列）若有闭回路的顶点，则有两个 顶点；,3、每两个顶点格子的连线都是水平的或垂直的；,4、闭回路中顶点的个数必为偶数.,闭回路的几何特征：,1、每一个顶点格子都是 90转角点；,基变量的构成,对于闭回路,线性相关,其对应的列向量,基变量的构成,若变量组中有一部分构成闭回路，则变量组线性相关。 不包含任何闭回路的变量组中必有孤立点。 孤立点 是其所在行或所在列中包含在该变量组中的唯一向量。 定

4、理：r个变量对应的系数列向量线性无关的充要条件是变量组不包含闭回路。 推论：m+n-1个变量构成基变量的充要条件是不含闭回路。,运输问题求解,初始基本可行解的确定 在供需表中任选一个单元xij，尽量匹配产销，使一个约束方程得以满足，填入相应位置； 调整Ai的拥有量及Bj的需求量，分别减去xij ，得到调整后的拥有量ai和需求量bj ； 若ai=0，则划去对应的行（拥有的量全部运走），若bj=0则划去对应的列（需求的量全部运来），且每次只划去一行或一列（每次只去掉一个约束）； 若平衡表中所有的行或列均被划去，则结束。 否则，在剩下的平衡表中选下一个变量，转,运输问题求解,b j= b j- x

5、ij a i= a i- x ij,x ij,ai,b j,基变量的构成,按照上述方法所产生的一组变量的取值将满足下面条件： a所得的变量均为非负，且变量总数恰好为m+n-1个； b所有的约束条件均得到满足； c所得的变量不构成闭回路。 因此所得的解一定是运输问题的基本可行解。 在上面的方法中， xij的选取方法并没有加以限定，如果采取一定的规则来选取，则会产生不同的方法，若每次在调整后的供需表中选取最左上角的元素，则称为左上角方法（或称西北角法），若每次在调整后的供需表中选取对应单位运费最小的元素，则称为最小费用法。,西北角法,运输问题 某地区有两个煤矿A1 A2 ，所产的煤要运往三个城市B

6、1 B2 B3，各产地的产量、销地的销量以及各产地到各销地的单位运费见下表，求使总运费最小的运输方案,西北角法,Note : 在填入一个数时，如果行和列同时饱和， 规定只划去一行或一列,最小费用法,关键,3,1,5,按最小元素法,3,4,2,3、Vogel 法 (元素差额法),规则：计算各行各列的最小元素与次小元素的差额，,优先安排差额最大的所 在行或列的单位运价最 小的产地与销地之间的 运输任务,最优性检验,21=C21- C11+ C12- C22=80-90+70-65=-5 13=C13- C23+ C22- C12=95-75+65-70=15,最优性检验：闭回路法,闭回路方法 原理

7、是通过寻找闭回路来找到非基变量的检验数。 可以证明，如果对闭回路的方向不加区别，那么以每一个非基变量为起始顶点，以基变量为其它顶点的闭回路就存在而且唯一。 如果规定作为起始顶点的非基变量为偶数次顶点，闭回路的其他顶点依次为第一个顶点、第二个顶点，那么就有：检验数=偶数点单位运费之和奇数点单位运费之和 若所有非基变量检验数0，则最优。,最优性检验：位势法,位势法 其原理是利用约束条件的特殊性来找到非基变量的检验数。 从约束条件中解出基变量（用非基变量表示基变量），代入目标后消去目标中的基变量，得到的非基变量的系数就是检验数。 这一过程若用消元的方法加以实现，则产生位势法。 若所有非基变量检验数0

8、，则最优。,最优性检验：位势法,位势法,最优性检验：位势法,位势法,最优性检验：位势法,最优性检验：位势法,最优性检验：位势法,最优性检验：位势法,最优性检验：位势法,最优性检验：位势法,最优性检验：位势法,位势法（对偶变量法）,约束方程的系数矩阵的秩为m+n -1,约束方程的系数矩阵的秩为m+n,对任意的 a0， 与原问题等价,x0必为基变量, x0= 0,xj 的检验数,由于,设： 为基变量，由于基变量 的检验数等于零,有解，不唯一,ui 称为行位势， vj 称为行位势,调整流量,X21进基， = minx 11, x22=min100,50=50 X22出基,调整流量,调运量的调整步骤：

9、 闭回路上的奇数次顶点的调运量减去； 闭回路上的偶数次顶点（包括起始变量）的调运量加上； 非闭回路顶点的其他变量调运量不变； 奇数点上被修改为0的变量为出基变量，在新的方案中不再标出其值。但若有两个为零的变量，则只取其一作为出基变量。,调整流量,22=C22- C21+ C11- C12=65-80+90-70=5 13=C13- C23+ C21- C11=95-75+80-90=10,最优性检验：位势法,最优性检验：位势法,最优性检验：位势法,一、初始方案的确定,1、西北角法,Ex. 1,50,已知某商品有三个产地A1、A2、A3和四个销地 B1、B2、B3、B4 ，产量、销量及单位运价如

10、表.问应 如何调运，在满足各销地需要的情况下，使总的运费 支出为最少？,解：,5,10,10,20,5,规则:从运输表的西 北角开始,优先安排 编号小的产地和销地 的运输任务.,50,0,2、最小元素法,40,10,25,5,10,10,0,0,10,10,20,50,二、最优性检验,40,10,25,5,10,10,1、闭回路法,+1,-1,+1,-1,检验数表,-5,-1,0,6,6,6,检验数表,-5,-1,0,6,6,6,-2,-1,2,0,2,7,3,见 Ex. 1 最小元素法得到的初始基可行解,10,0,5,3,-1,2,-5,三、基可行解的改进,40,10,25,5,10,10,检验数表,-5,-1,0,6,6,6,选择进基变量,则取非基变量 xst 为进基变量,确定出基变量,调整量,则基变量 xkl 出基（运量擦去）,调整方法：在该闭回路上，奇点运量