[理学]运筹第4章运输问题.ppt

1,第四章 特殊的线性规划 运输问题,模型及其特点 求解思路及相关理论 求解方法表上作业法 运输问题的推广 产销不平衡的运输问题 转运问题,2,4.1 运输问题模型与性质,一、运输问题的数学模型 1、 运输问题的一般提法： 某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？,3,单位根据具体问题选择确定。,表4-1 有关信息,4,2、运输问题的数学模型,设xij为从产地Ai运往销地Bj的物资数量（i=1，m；j=1，n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足：,5,同理，运到Bj的物资总量应该等于Bj的销量bj，所以xij还应满足： 总运费为：,6,运输问题的数学模型,7,二、运输问题的特点与性质,1约束方程组的系数矩阵具有特殊的结构,写出系数矩阵A，形式如下：,8,矩阵的元素均为1或0； 每一列只有两个元素为1，其余元素均为0； 列向量Pij =(0,，0，1，0,0,1,0,0)T，其中两个元素1分别处于第i行和第m+j行。 将该矩阵分块，特点是：前m行构成m个mn阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，m）；后n行构成m个n阶单位阵。,9,2.运输问题的基变量总数是m + n -1,写出增广矩阵,10,定义4.1 凡是能排成 或 形式的变量集合称为一个闭回路,并称式中变量为该闭回路的顶点；其中 互不相同, 互不相同。,3. m+n-1个变量构成基变量的充要条件 是它们不构成闭回路。,11,例4-1 设m=3，n=4，决策变量xij表示从产地Ai到销地Bj的调运量，列表如下，给出闭回路 在表中的表示法用折线连接起来的顶点变量。,12,练习4-1 请给出闭回路 和 在表中的表示法。,13,练习4-2 下面的折线构成的封闭曲线连接的顶点 变量哪些不可能是闭回路？为什麽？,表中的折线构成一条封闭曲线， 且所有的边都是水平或垂直的；为什麽？,表中的每一行和每一列由折线相连的闭回路 的顶点只有两个；为什麽？,14,三.运输问题求解 表上作业法,一、表上作业法的基本思想是:先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如图4-1所示。 表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。,15,图4-1 运输问题求解思路图,16,表4-2 运输问题作业表（产销平衡表）,17,1、初始基本可行解的确定 找到 m + n 1 个不构成闭回路的基变量。 较常用的方法有西北角法、最小元素法和伏格尔法。,二、产销平衡问题表上作业法步骤,18,西北角法,甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见表3-4，求使总运输量最少的调运方案。,19,用西北角法确定例4-2初始调运方案,100,100,100,50,50,200,200,20,得到初始调运方案为： x11=100，x12=100，x22=50，x23=200 运输费用为34250,21,用最小元素法确定例3-2初始调运方案,150,100,100,100,100,100,100,22,得到初始调运方案为：,x11=100，x13=100，x22=150，x23=100,运输费用为36250,23,用伏格尔法确定例3-2初始调运方案,50,50,200,150,50,50,50,24,得到初始调运方案为：,x11=50，x12=150，x21=50，x23=200,运输费用为34000,25,2、最优性检验,检查当前调运方案是不是最优方案的过程就是最优性检验。检查的方法：计算非基变量（未填上数值的格，即空格）的检验数（也称为空格的检验数），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。,26,闭回路法,以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。 该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。 可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。,27,约定作为起始顶点的非基变量为偶数次顶点， 其它顶点从1开始顺次排列， 那麽，该非基变量xij的检验数：,现在，在用最小元素法确定例4-2初始调运方案的基础上，计算非基变量X12的检验数 ：,28,例4-2初始调运方案中以X12(X21)为起点的闭回路,29,非基变量X12的检验数：,非基变量X21的检验数：,=（c12+c23）-（c13+c22） =70+75-（100+65）=-20，,=（c21+c13）-（c11+c23） =80+100-（90+75）=15。,经济含义：在保持产销平衡的条件下，该非基变量增加一个单位运量而成为基变量时目标函数值的变化量。,30,位势法,以例4-2初始调运方案为例，设置位势变量 和 ，在初始调运方案表的基础上增加一行和一列（见下页表格）。 然后构造下面的方程组：,（3-7）,31,例4-2初始调运方案位势变量对应表,32,方程组的特点：, 方程个数是m+n-1=2+3-1=4个，位势变量共有m+n=2+3=5个，通常称ui为第i行的位势，称vj为第j列的位势； 初始方案的每一个基变量xij对应一个方程-所在行和列对应的位势变量之和等于该基变量对应的运距（或运价）：ui+vj=cij； 方程组恰有一个自由变量，可以证明方程组中任意一个变量均可取作自由变量。,33,12=c12-（u1+v2）=70-（0+90）=-20 21=c21-（u2+v1）=80-（-25+90）=15 与前面用闭回路法求得的结果相同。,34,位势法计算非基变量xij检验数的公式 ij=cij-（ui+vj）,=（闭回路上偶数次顶点运距或运价之和）-（闭回路上奇数次顶点运距或运价之和）,闭回路法计算非基变量xij检验数的公式：,复习比较检验数计算的两种方法,35,3、方案调整,当至少有一个非基变量的检验数是负值时，说明作业表上当前的调运方案不是最优的，应进行调整。 若检验数ij小于零，则首先在作业表上以xij为起始变量作出闭回路，并求出调整量： =min该闭回路中奇数次顶点调运量xij ij,36,继续上例，因12=-20 ，画出以x12为起始变量的闭回路,37,计算调整量：=Min（100，150）=100。 按照下面的方法调整调运量： 闭回路上，奇数次顶点的调运量减去，偶数次顶点（包括起始顶点）的调运量加上；闭回路之外的变量调运量不变。 得到新的调运方案：,38,重复上面的步骤，直至求出最优调运方案：,39,40,结 果,最优调运方案是：,x11=50，x12=150，x21=50，x23=200,相应的最小总运输量为：,Zmin=9050+70150+8050+75200,=34000（吨公里）,41,三、产销不平衡的运输问题,增加虚拟销地,增加虚拟产地,产销平衡的运输问题,对应的运距（或运价） ？,42,1、产量大于销量,增加虚拟销地 虚拟销地的销量？运价？,43,运价见下表，产地产量分别为7、5、7t，销地销量分别为2、3、4、6t，试决定总运费最少的调运方案。,44,45,2、产量小于销量,增加虚拟产地 虚拟产地的产量？运价？,46,运价见下表，产地产量分别为7、5、2t，销地销量分别为2、3、4、6