运筹学第三章31运输问题模型与性质.ppt

第三章 特殊的线性规划运输问题,&模型及其特点&求解思路及相关理论&求解方法表上作业法&运输问题的推广 产销不平衡的运输问题 转运问题,3.1 运输问题模型与性质一、运输问题的数学模型 1、运输问题的一般提法：某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？,单位根据具体问题选择确定。,表3-1 有关信息,2、运输问题的数学模型,设xij为从产地Ai运往销地Bj的物资数量（i=1，m；j=1，n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足：,同理，运到Bj的物资总量应该等于Bj的销量bj，所以xij还应满足：总运费为：,运输问题的数学模型,（3-1）,二、运输问题的特点与性质1约束方程组的系数矩阵具有特殊的结构写出式（3-1）的系数矩阵A，形式如下：,矩阵的元素均为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阶单位阵。,2.运输问题的基变量总数是m+n-1写出增广矩阵,证明系数矩阵A及其增广矩阵的秩都是m+n-1,前m行相加之和减去后n行相加之和结果是零向量，说明m+n个行向量线性相关，因此 的秩小于m+n；？,因此 的秩恰好等于m+n-1，又D本身就含于A中，故A的秩也等于m+n-1,由 的第二至m+n行和前n列及 对应的列交叉处元素构成m+n-1阶方阵D 非奇异；？,可以证明：m+n个约束方程中的任意m+n-1个都是线性无关的。,定义3.1 凡是能排成(3-4)或(3-5)形式的变量集合称为一个闭回路,并称式中变量为该闭回路的顶点；其中 互不相同,互不相同。,3.m+n-1个变量构成基变量的充要条件是它们不构成闭回路。,例3-1 设m=3，n=4，决策变量xij表示从产地Ai到销地Bj的调运量，列表如下，给出闭回路 在表中的表示法用折线连接起来的顶点变量。,三、运输问题的求解方法,1、单纯形法（为什么？）2、表上作业法 由于问题的特殊形式而采用的更简洁、更方便的方法,3.2 运输问题的表上作业法 一、表上作业法的基本思想是:先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如图3-1所示。表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。,图3-1 运输问题求解思路图,二、初始方案的确定 1、作业表（产销平衡表）初始方案就是初始基本可行解。将运输问题的有关信息表和决策变量调运量结合在一起构成“作业表”（产销平衡表）。表3-3是两个产地、三个销地的运输问题作业表。,表3-3 运输问题作业表（产销平衡表）,其中xij是决策变量，表示待确定的从第i个产地到第j个销地的调运量，cij为从第i个产地到第j个销地的单位运价或运距。2、确定初始方案的步骤：（1）选择一个xij，令xij=minai，bj=,将具体数值填入xij在表中的位置；,（2）调整产销剩余数量：从ai和bj中分别减去xij的值，若ai-xij=0，则划去产地Ai所在的行，即该产地产量已全部运出无剩余，而销地Bj尚有需求缺口bj-ai；若bj-xij=0，则划去销地Bj所在的列，说明该销地需求已得到满足，而产地Ai尚有存余量ai-bj；（3）当作业表中所有的行或列均被划去，说明所有的产量均已运到各个销地，需求全部满足，xij的取值构成初始方案。否则，在作业表剩余的格子中选择下一个决策变量，返回步骤（2）。,按照上述步骤产生的一组变量必定不构成闭回路，其取值非负，且总数是m+n-1个，因此构成运输问题的基本可行解。对xij的选择采用不同的规则就形成各种不同的方法，常用的方法有最小元素法和伏格尔法。下面通过具体实例分别介绍。,3、举例,例3-2 甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见表3-4，求使总运输量最少的调运方案。,表3-4 例3-2有关信息表,例3-2 的数学模型,使用最小元素法求出初始方案（1）最小元素法基本思想是“就近供应”：即从单位运价表或运距表中的最小元素开始确定供销关系，然后次小，一直到给出初始基可行解为止。,用最小元素法确定例3-2初始调运方案,150,100,100,100,100,100,100,得到初始调运方案为：x11=100，x13=100，x22=150，x23=100,最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费(运距)。,（2）伏格尔法,它的基本思想是：考虑次小运费(运距)，这就有一个差额。因而对差额最大处，就应当采用最小运费(运距)调运。,找最大差额的最小运费,用伏格尔法确定例3-2初始调运方案,200,50,15,150,50,50,50,50,最小,次小,差额,得到初始调运方案为：x11=50，x12=150，x21=50，x23=200,三、最优性检验,检查当前调运方案是不是最优方案的过程就是最优性检验。检查的方法：计算非基变量的检验数 未填上数值的格(空格)空格的检验数 若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。,1、闭回路法 以确定初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。闭回路的特点：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。,约定:起始顶点为非基变量，记为偶数次顶点，其它顶点从1开始顺次排列，那么，该非基变量xij的检验数：,现在，用最小元素法确定例3-2初始调运方案的基础上，计算非基变量X12的检验数：,=(闭回路上偶数次顶点运距或运价之和)(闭回路上奇数次顶点运距或运价之和),(3-6),例3-2初始调运方案中以X12(X21)为起点的闭回路,非基变量X12的检验数：,非基变量X21的检验数：,=（c12+c23）-（c13+c22）=70+75-(100+65)=-20，,=（c21+c13）-（c11+c23）=80+100-（90+75）=15。,经济含义 在保持产销平衡的条件下，该非基变量增加一个单位运量而成为基变量时目标函数值的变化量。,2、位势法,以例3-2初始调运方案为例，设置位势变量 和，在初始调运方案表的基础上增加一行和一列（见下页表格）。然后构造下面的方程组：,（3-7）,例3-2初始调运方案位势变量对应表,方程组的特点：方程个数是m+n-1=2+3-1=4个，位势变量共有m+n=2+3=5个，通常称ui为第i行的位势，称vj为第j列的位势；初始方案的每一个基变量xij对应一个方程-所在行和列对应的位势变量之和等于该基变量对应的运距（或运价）：ui+vj=cij；方程组恰有一个自由变量，可以证明方程组中任意一个变量均可取作自由变量。,给定自由变量一个值,解方程组式(3-7)，即可求得位势变量的一组值，根据式(3-6)结合方程组(3-7)，则计算非基变量xij检验数的公式 ij=cij-（ui+vj）（3-8）,在式(3-7)中,令u1=0,则可解得 v1=90,v3=100,u2=-25,v2=90，12=c12-（u1+v2）=70-（0+90）=-20 21=c21-（u2+v1）=80-（-25+90）=15与前面用闭回路法求得的结果相同。,四、方案调整 当至少有一个非基变量的检验数是负值时，说明作业表上当前的调运方案不是最优的，应进行调整。若检验数ij小于零，则首先在作业表上以xij为起始变量作出闭回路,并求出调整量:,上例中12=-20，画出以x12为起始变量的闭回路,计算调整量：=Min（100，150）=100。按照下面的方法调整调运量：闭回路上：闭回路之外的变量调运量不变。奇数次顶点的调运量减去，偶数次顶点的调运量加上；,得到新的调运方案：,重复上面的步骤，直至求出最优调运方案.,结 果 最优调运方案是：x11=50，x12=150，x21=50，x23=200 相应的最小总运输量为：Zmin=9050+70150+8050+75200=34000（吨公里）,3.3运输问题的推广,一、产销不平衡的运输问题,增加虚拟销地,增加虚拟产地,产销平衡的运输问题,对应的运距（或运价）？,二、转运问题特点:调运的物资不是由产地直接运送到销地，而是经过若干中转站送达。求解思路：转化成一个等价的产销平衡运输问题，再用表上作业法求出最优调运方案。,如何转化？,第一步，将产地、转运点、销地重新编排，转运点既作为产地又作为销地；第二步，各地之间的运距（或运价）在原问题运距（运价）表基础上进行扩展：从一地运往自身的单位运距（运价）记为零，不存在运输线路的则记为M（一个足够大的正数）；,第三步，由于经过转运点的物资量既是该点作为销地的需求量，又是该点作为产地时的供应量，但事先又无法获取该数量的确切值，因此通常将调运总量作为该数值的上界。对于产地和销地也作类似的处理。,