运筹学课件第三章运输问题.

第三章运输问题一、运输问题及其数学模型二、表上作业法三、运输问题的进一步讨论四、应用举例第三章2312341一、运输问题及其数学模型s2=27s3=19s1=14供应量供应地运价d1=22d2=13d3=12d4=13需求量需求地6753842759106引例：运输问题网络图第三章0xxxxxxxxxxxx13xxx12xxx13xxx22xxx19xxxx27xxxx14xxxxs.t.x6x10x9x5x7x2x4x8x3x5x7x6zmin343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211供应地约束需求地约束一、运输问题及其数学模型第三章运输问题的描述：设某种物品有m个产地A1,A2,...,Am，各产地的产量分别是a1,a2,...,am；有n个销地B1,B2,...,Bn，各销地的销量分别为b1,b2,....bn。假定从产地Ai(i=1,2,…,m)向销地出Bj(j＝l,2,….n)运输单位物品的运价是cij，问怎样调运这些物品才能使总运费最小?一、运输问题及其数学模型第三章运价表销地产地B1B2…Bn产量A1C11C12…C1na1x11x12…x1nA2C12C22…C2na2x21x22…x2n……..…………………AmC1mC2m…Cmnamxm1xm2…xmn销量b1b2…bm一、运输问题及其数学模型第三章产销平衡运输问题的数学模型表示：（Ⅰ）一、运输问题及其数学模型第三章该模型是一个线性规划模型，可以用单纯形法求解。但是变量数目非常多。如3个产地，4个销地。变量数目会有19个之多。因此应该寻求更简便的解法。为了说明适于求解运输问题的更好的解法，先分析运输问题数学模型的特点。一、运输问题及其数学模型第三章运输问题数学模型的特点：1．运输问题有有限最优解是一个可行解。同时，目标函数有下界，且不会趋于负无穷。所以，必存在有限最优解。一、运输问题及其数学模型第三章2．运输问题约束条件的系数矩阵A=n行m行系数列向量：第i个第m+j个一、运输问题及其数学模型第三章由此可知，运输问题具有下述特点：(1)约束条件系数矩阵的元素等于0或1；(2)约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次；对产销平衡运输问题，除上述两个特点外，还有以下特点：(3)所有结构约束条件都是等式约束；(4)各产地产量之和等于各销地销量之和。秩(A)=m+n-1运输问题的基可行解中应包含m+n-1个基变量.一、运输问题及其数学模型第三章3.运输问题的解(1)解x必须满足模型中的所有约束条件；(2)基变量对应的约束方程组的系数列向量线性无关；(3)解中非零变量xij的个数不能大于(m+n-1)个，原因是运输问题中虽有(m+n)个结构约束条件，但由于总产量等于总销量，故只有(m+n-1)个结构约束条件是线性独立的；(4)为使迭代顺利进行，基变量的个数在迭代过程中保持为(m+n-1)个。运输问题解的每一个分量，都唯一对应其运输表中的一个格填有数字的格或空格一、运输问题及其数学模型第三章销地产地B1B2B3B4产量A141241116826A2210391010A38511622148销量814121448下表给出了例1的一个解。一、运输问题及其数学模型第三章二、表上作业法表上作业法是一种迭代法，迭代步骤为：1、先按某种规则找出一个初始解(初始调运方案)；2、再对现行解作最优性判别；3、若这个解不是最优解，就在运输表上对它进行调整改进，得出—个新解；4、再判别，再改进；5、直至得到运输问题的最优解为止。迭代过程中得出的所有解都要求是运输问题的基可行解。第三章例1：销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448二、表上作业法第三章销地产地B1B2B3B4产量A141241116A22103910A38511622销量81412144882101486所以，初始基可行解为：……目标函数值Z＝246二、表上作业法1、初始基可行解－－最小元素法第三章在满足约束条件下尽可能的给最左上角的变量最大值.销地产地B1B2B3B4产量A141241116A22103910A38511622销量8141214488864814所以，初始基可行解为：……目标函数值Z＝3721、初始基可行解－－西北角法二、表上作业法第三章沃格尔法计算步骤：1)分别算出各行、各列的罚数。2)从行、列中选出差额最大者，选择它所在行、列中的最小元素，进行运量调整。3)对剩余行、列再分别计算各行、列的差额。返回1)、2)。二、表上作业法1、初始基可行解－－沃格尔法第三章销地产地B1B2B3B4产量A141241116A22103910A38511622销量81412144814所以，初始基可行解为：……目标函数值Z＝244881224二、表上作业法4-4=03-2=16-5=14-2=210-5=54-3=19-6=3018-6=24-2=24-3=19-6=3第三章销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448821014861211012-1二、表上作业法2、解的最优性检验－－闭回路法某空格的检验数是以该空格为第一个顶点，某回路的奇数顶点运价和减去其偶数顶点运价和。第三章原问题设其对偶变量为：2、解的最优性检验－－对偶变量法二、表上作业法第三章对偶问题:考虑原问题变量xj的检验数为：二、表上作业法第三章假设已得到一个基可行解，其基变量为：则有：s=m+n-1则运输问题变量xij的检验数为：二、表上作业法第三章方程组有m+n-1个方程。因为运输表中每行和每列均有基变量，因此上面方程组含有全部m+n个对偶变量。故解不唯一，其解称为位势。若上述方程的某组解满足对偶问题的所有条件，即：此时，原问题与对偶问题均可行，故达到最优。其解分别为：二、表上作业法第三章例：销地产地B1B2B3B4产量UiA141241116A22103910A38511622销量814121448Vj82101486二、表上作业法10-429310121-11012第三章改进的方法是在运输表中找出这个空格对应的闭回路，在满足所有约束条件的前提下，使xij尽量增大并相应调整此闭回路上其它顶点的运输量，以得到另一个更好的基可行解。3、解的改进－闭回路调整法二、表上作业法第三章解改进的具体步骤(1)以xij为换入变量，找出它在运输表中的闭回路；(2)以空格(Ai,Bj)为第一个奇数顶点，沿闭回路的顺(或逆)时针方向前进，对闭回路上的顶点依次编号；(3)在闭回路上的所有偶数顶点中，找出运输量最小的顶点(格子)，以该格中的变量为换出变量；(4)以换出变量的运输量为调整量，将该闭回路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减去这一数值，从而得出一新的运输方案。该运输方案的总运费比原运输方案减少，改变量等于换出变量的检验数。然后，再对得到的新解进行最优性检验，加不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止。二、表上作业法第三章销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448例：821014861211012-1二、表上作业法min(6,2)=22-2=00+2=26-2=410+2=12第三章销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448例：821214840229121由于所有非基变量的检验数全非负，故这个解为最优解。又由于非基变量有零检验数，所以有无穷多最优解。二、表上作业法第三章练习题销地产地B1B2B3B4产量A167531414A28427278136A35910619613销量22131213二、表上作业法练习题第三章练习题销地产地B1B2B3B4产量A167531414557A284272781369A35910619-11-3613销量22131213二、表上作业法练习题第三章练习题销地产地B1B2B3B4产量A16753141455-4A284272721312-2A35910619681113销量22131213二、表上作业法第三章销地产地B1B2B3B4产量A167531415513A2842727213122A35910619198114销量22131213销地产地B1B2B3B4产量A1675314113A284272721312A3591061919销量22131213答案二、表上作业法第三章1）若运输问题的某一基可行解有几个非基变量的检验数均为负，在继续进行迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但通常取小于零的检验数中最小者对应的变量为换入变量。2）当迭代到运输问题的最优解时，如果有某非基变量的检验数等于零，则说明该运输问题有多重(无穷多)最优解。4、需要说明的几个问题二、表上作业法第三章3）（二）退化某一基变量的值为0初始解在确定初始解的供需关系时，若在确定（i,j）的数字时，要划去第i行,第j列。为使在产销平衡表上有m+n-1个数字格，须在第i行或j列中（非i,j)选一数字格为0。退化解闭回路中有（-）标记中有两个或以上相等的最小数。调整后出现退化解，必须在一数字格中填入0，以表明其为基变量。二、表上作业法第三章三、运输问题的进一步讨论上一节讲述的运输问题的算法，是以总产量等于总销量(产销平衡)为前提的。实际上，在很多运输问题中，总产量不等于总销量。第三章0,ijjiCba其中njmixnjbxmiaxxCzijmijijnjiijminjijij1,10,...2,1,...2,1min1111（Ⅰ）表上作业法——以产销平衡为前提。jiba1、产销不平衡的运输问题三、运输问题的进一步讨论第三章2321341s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地6753842759106例：假设供应量大于需求量+55d5=5假想销地000s3=24三、运输问题的进一步讨论第三章0,...2,1,...2,1min1111ijmijijnjiijminjijijxnjbxmiaxxCzjiba产大于销产销不平衡产销平衡模型：三、运输问题的进一步讨论第三章设为Ai的贮存量。1,nixmiaxxxinjijninjij,...,2,1111,1jininijmiijbaxnjbx11,1,...,2,1将多余物原地贮存。令：101'njnjCCijij三、运输问题的进一步讨论第三章111njjmiiba理解：产销假想有一销地j=n+1销量为运价njjmiiba110'1,niC01,...2,1,...2,1min111111'ijmijijnjiijminjijijxnjbxmiaxxCz模型：三、运输问题的进一步讨论第三章销地产地B1B2…BnBn+1（贮存）产量A1C11C12…C1n0a1x11x12…x1nx1,n+1A2C12C22…C2n0a2x21x22…x2nx2,n+1……..………………………AmC1mC2m…Cmn0amxm1xm2…xmnxm,n+1销量b1b2…bmΣa-Σb三、运输问题的进一步讨论第三章例：某市有三个造纸厂A1，A2，A3，其纸的产量分别为8，5和9个单位，有4个集中用户B1，B2，B3，B4，其需用量分别为4，3，5和6个单位。由各造纸