M1-4运输问题.ppt

*,/,57,*,第1章 线性规划模型及应用,1-1,线性规划问题的数学模型,1-2,单纯形方法,1-3,对偶线性规划问题,1-4,运输问题,1-5,整数规划,Linear programming model and application,一、运输问题的,数学模型,二、求解运输问题的,表上作业法,三、,表上作业法的,特殊情况,2.1,用最小元素法制定,初始调运方案,2.2,求检验数、最优性,判别,习题,作业,四、,运输问题的,应用,1-4 运输问题,2.3,求出调整量、在闭,回路上进行调整,案例,光明市的菜篮子工程,一、运输问题的数学模型,某种物资有,m,个产地,A,1,A,2,A,m,，联合供应,n,个销地,B,1,B,2,B,n,，各产地产量、各销地销量（单位：吨）、各产地到各销地的单位运价（单位：元,/,吨）如表,1-71,，应如何组织调运，才能使得总运费最省？,表,1-71,一般运输问题的平衡表与运价表,平衡表,运价表,销地,产地,B,1,B,2,B,n,产量（吨）,B,1,B,2,B,n,A,1,a,1,c,11,c,12,c,1,n,A,2,a,2,c,21,c,22,c,2,n,A,m,a,m,c,m,1,c,m,2,c,mn,销量,(,吨,),b,1,b,2,b,n,用矩阵形式表示为：,一、运输问题的数学模型,设,x,ij,表示产地,A,i,供应销地,B,j,的数量,(,i,=1,2,m,;,j,=1,2,n,),。,当产销平衡,(,),时，数学模型为,(,标准形,),：,其中：,一、运输问题的数学模型,在产销平衡的条件下，即 ，这里系数矩阵的秩 。可以证明：。因此，运输问题的任何一个基含有 个线性无关的列向量，即任何一个基可行解含有 个基变量，这时对应的基可行解就是一个可行的调运方案。关于运输问题的求解，当然可以用单纯形方法，但由于它结构的特殊性，用特殊的方法求解比较方便。下面介绍求解运输问题的表上作业法。,一、运输问题的数学模型,最小元素法,就是按运价最小的优先供应的原则,(,除了最小元素法以外,还有西北角法、沃格尔法,(Vogel),等,),。按照最小元素法先给定一个初始调运方案。,例,1,某种物资有,3,个产地、,4,个销地，各产地的产量、销地的销量以及各产销地之间的运价如表,1-72,，求最优的调运方案。,二、求解运输问题的表上作业法,2.1,用最小元素法制定初始调运方案,表,1-72,运输问题的平衡表与运价表,平衡表,(,单位：,t),运价表,B,1,B,2,B,3,B,4,发量,B,1,B,2,B,3,B,4,A,1,4,6,5,3,4,A,2,6,4,4,7,5,A,3,3,7,6,5,8,收量,2,4,3,4,13,二、求解运输问题的表上作业法,解,从运价表中观察出最小运价,c,13,=3,，就让,A,1,优先满足,B,3,的需要；从平衡表中看到,A,1,有,4,吨，而,B,3,需要,3,吨，从,A,1,的,4,吨中供应给,B,3,3,吨。即在平衡表上与,c,13,对应的格子里填上,3,，同时把,B,3,的收量,3,划去，表示,B,3,已经满足了需要，把,A,1,的发量,4,减去,3,改为,1,，表示,A,1,还剩,1,吨，并把,B,3,运价表中的那一列划去，因为,B,3,已经满足需求，这一列运价以后不要再考虑了,。,具体作法如下：,在运价未被划去的表中找出最小运价,此时有三个最小的,一般应取最上边一行最左边的,选,c,14,=4,就让,A,1,供应,B,4,；从平衡表中看到,A,1,有,1,吨，而,B,4,需要,4,吨，将,A,1,剩下的全部供应,B,4,，就在平衡表上与,c,14,对应的格子里填上,1,，同时把,B,4,的收量改为,3,，把,A,1,的发量,1,划掉，并把运价表中,A,1,的那一行划去。,二、求解运输问题的表上作业法,继续这种作法,直到,A,1,A,2,A,3,全部发完,B,1,B,2,B,3,B,4,完全满足为止。,在表上作业过程中,平衡表每填上一个数字,运价表就划去一行或一列。发量大于收量时，运价表划去列；收量大于发量时,运价表划去行,但由于最后一个数字要求平衡,即收量与发量相等,所以在运价表上填完最后一个数字时,在运价表任意划去一行或一列,这时运价表上的运价已全部划完。因而在运价表上应填上数字,m,+,n,-1,即,m,+,n,-1,个基变量。,二、求解运输问题的表上作业法,值得注意的是：,有时在作业的中间过程中发量与收量相等，这时只能划去一行或一列的运价，不能同时划去，另一行或另一列待以后在调运表中填写数字时再划去，且在调运表上填上数字“,0”,，这个,0,是基变量取,0,值，这个格子是有数字的格子,不是空格，它与非基变量的空格不同,否则就会造成调运表中数字,(,基变量,),的个数少于,m,+,n,-1,个。,如在运价表中，未被划去的最小元素,c,21,=4,，从,A,2,运往,B,1,A,2,有,6,吨，,B,1,需要,2,吨，从,A,2,供应,2,吨到,B,1,，在平衡表中,c,21,对应的格子填上,2,，把,B,1,的收量,2,划去，,A,2,的发量,6,改为,4,，并把运价表,B,1,对应的列划去。,二、求解运输问题的表上作业法,如上处理后，未被划去的最小元素,c,22,=4,，从,A,2,运往,B,2,A,2,有,4,吨，,B,2,需要,4,吨，从,A,2,供应,4,吨到,B,2,，在平衡表中,c,22,对应的格子填上,4,，这时收量与发量相等，因而只能划去,B,2,列或,A,2,行，,不能同时划去,!,如保留,A,2,行,划去,B,2,列,平衡表,A,2,行的发量改为,0,，,B,2,列的收量划去同时划去运价表,B,2,对应的列。,接下来，运价表中最小元素,c,24,=5,，从,A,2,运往,B,4,A,2,有,0,吨，,B,4,需要,3,吨，在平衡表中相应的格子填上“,0”,。这时再将,A,2,行划去，,B,2,列保持不变，这样做是为了保证基变量的个数为,m,+,n,-1,个。继续下去，最后可得初始调运方案，见表,1-73,。,二、求解运输问题的表上作业法,表,1-73,运输问题的初始调运方案,平衡表,运价表,B,1,B,2,B,3,B,4,发量,B,1,B,2,B,3,B,4,A,1,3,1,4,6,5,3,4,A,2,2,4,6,4,4,7,5,A,3,0,3,3,7,6,5,8,收量,2,4,3,4,13,表,1-73,中,有数字的格子,(,包括,0),对应的是基变量,空格所对应的变量是非基变量。,二、求解运输问题的表上作业法,显然，任何一个产销平衡的运输问题都可以用最小元,素法求出一个初始调运方案，又因为运输问题目标函,数必然有下界（且非负），所以平衡运输问题一定有,最优解。人们可能认为用最小元素法得到的初始方案,一定是最优的，其实不然。该方案对应的运费等于,Z=33+14+24+44+06+38=61,但该运输问,题的最小费用为,55,。,对于每一个非基变量（空格）都对应一个检验数，,则有以下最优性准则：,定理,1.4.1,(,最优性判别准则,),在运输问题的某个可行方案中，如果对应于每一个非基变量,x,ij,(,即空格,),的检验数,l,ij,0,，则该基可行解为最优解，对应的调运方案为最优方案。,为了说明如何在表上作业法的过程中求出非基变量的检验数，下面介绍闭回路的概念。,二、求解运输问题的表上作业法,2.2,求检验数、最优性判别,检验数,闭回路：,在调运方案中，从一个空格出发，沿水平或垂直方向前进，遇到一个适当的有数字的格子，则转向,90,前进，这样必会又遇到一个适当的有数字的格子，同样再转向,90,前进；经若干次后，必然会回到出发的那个空格，这样就形成一条由水平与垂直线构成的封闭折线，我们称这样的封闭折线为该空格的闭回路。该空格（非基变量）对应的检验数就等于该闭回路上所有偶次拐点的运价之和减去所有奇次拐点的运价之和。,二、求解运输问题的表上作业法,在例,1,中：,闭回路,:,闭回路,:,检验数,二、求解运输问题的表上作业法,闭回路,:,检验数,闭回路,:,检验数,闭回路,:,检验数,闭回路,:,检验数,初学者可能感到这样求检验数比较麻烦,但它反映了检验数的本质。我们也可以用位势法来求检验数。,位势法：,将运价表中基变量所对应的运价打“*”号或者将数字画圈“”，然后对运价表每一行、每一列同时加上或减去同一个数，当基变量对应的检验数（打“*”号的或画圈“”的）等于零，其余各数就是各个非基变量所对应的检验数。,二、求解运输问题的表上作业法,对例,1,，采用位势法求检验数过程如下,最后的数阵中没有标记,*,的数字就是非基变量的检验数。,从一个可行方案调整到另一个可行方案,也就是从一个基可行解换基迭代到另一个基可行解,且使目标函数值不断下降。运输问题表上作业法的换基迭代实际上是在调运表上负检验数对应的空格所在的闭回路上进行的,.,第一个检验数小于零,l,24,=-1,0,的空格所对应的非基变量为进基变量，并使这个非基变量的值由零增加到调整量。,二、求解运输问题的表上作业法,2.3,求出调整量、在闭回路上进行调整,调整量,：该闭回路上所有奇次拐点调运量的最小值。,调整方法：,闭回路上每个奇次拐点的调运量都减去调整量,(,其中有一个且仅允许有一个调运量为,0,变为空格成为非基变量，其他变为,0,的仍然要填上,0),，各偶次拐点的调运量均加上调整量，其中有一个由非基变量,(,空格,),变为基变量。,二、求解运输问题的表上作业法,对例,1,，取,表,1-74,运输问题调运方案调整表,B,1,B,2,B,3,B,4,发量,B,1,B,2,B,3,B,4,A,1,3,1,4,3,1,A,2,2,4-3,+3,6,2,1,3,A,3,0+3,3-3,3,3,收量,2,4,3,4,13,二、求解运输问题的表上作业法,使用位势法求检验数，过程如下：,有检验数,l,33,=-1,0,继续调整量,取,表,1-75,运输问题调运方案调整表,B,1,B,2,B,3,B,4,发量,B,1,B,2,B,3,B,4,A,1,3-3,1+3,4,4,A,2,2,1+3,3-3,6,2,4,0,A,3,3-3,+3,3,0,3,收量,2,4,3,4,13,注意,：这里经调整以后，有,3,个基变量,x,13,x,24,x,31,同时变为零！但只能有一个,x,13,成为非基变量,(,空格,),，另外两个,x,24,x,31,仍为基变量，其对应的调运量等于,0,。,二、求解运输问题的表上作业法,继续求检验数：,此时所有检验数全部非负，因此对应的调运方案是最优的。,min Z,=44+24+44+35=55,。,二、求解运输问题的表上作业法,例,2,求表,1-76,对应的运输问题的最优解：,表,1-76,运输问题的平衡表与运价表,B,1,B,2,B,3,B,4,发量,B,1,B,2,B,3,B,4,A,1,7,3,11,3,10,A,2,4,1,9,2,8,A,3,9,7,4,10,5,收量,3,6,5,6,20,解：,首先用最小元素法求初始调运方案，见表,1-77,。,表,1-77,运输问题的初始调运方案,B,1,B,2,B,3,B,4,发量,B,1,B,2,B,3,B,4,A,1,4,3,7,3,11,3,10,A,2,3,1,4,1,9,2,8,A,3,6,3,9,7,4,10,5,收量,3,6,5,6,20,总费用,Z,=,43+310+31+12+64+35=86,二、求解运输问题的表上作业法,采用位势法求检验数：,有检验数为负,非最优方案,需要进行方案的调整,见表,1-78,。,表,1-78,运输问题的调运方案调整表,B,1,B,2,B,3,B,4,发量,B,1,B,2,B,3,B,4,A,1,4+1,3-1,7,5,2,A,2,3,1-1,+1,4,3,1,A,3,6,3,9,6,3,收量,3,6,5,6,20,总费用,Z,=53+210+31+18+64+35=85,二、求解运输问题的表上作业法,采用位势法求检验数：,所有检验数全部非负,此方案是最优的调运方案。,由于非基变量,x,11,的检验数,l,11,=,0,该运输问题可能有不止一个最优方案。进行调整见表,1-79,，该表对应另一个最优方案。,最小费用,Z=53+210+31+18+64+35=85,。,二、求解运输问题的表上作业法,表,1-79,运输问题的调运方案调整表,B,1,B,2,B,3,B,4,发量,B,1,B,2,B,3,B,4,A,1,+2,5,2-2,7,2,5,A,2,3-2,1+2,4,1,3,A,3,6,3,9,6,3,收量,3,6,5,6,20,最小费用Z=23+53+11+38+64+35=85,对例,2,用,LINDO,软件进行求解，程序如下：,min 3x11+11x12+3x13+10 x14+x21+9x22,+2x23+8x24+7x31+4x32+10 x33+5x34,st,x11+x12+x13+x14=7,x21+x22+x23+x24=4,x31+x32+x33+x34=9,x11+x21+x31=3,x12+x22+x32=6,x13+x23+x33=5,x14+x24+X34=6,end,二、求解运输问题的表上作业法,LP OPTIMUM FOUND AT STEP 6,OBJECTIVE FUNCTION VALUE,1)85.00000,VARIABLE VALUE REDUCED COST,xX11 2.000000 0.000000,x12 0.000000 2.000000,x13 5.000000 0.000000,x14 0.000000,0.000000,x21 1.000000 0.000000,x22 0.000000 2.000000,x23 0.000000 1.000000,x24 3.000000 0.000000,x31 0.000000 9.000000,x32 6.000000 0.000000,x33 0.000000 12.000000,x34 3.000000 0.000000,二、求解运输问题的表上作业法,结果如下：,ROW SLACK OR SURPLUS DUAL PRICES,2)0.000000 -9.000000,3)0.000000 -7.000000,4)0.000000 -4.000000,5)0.000000 6.000000,6)0.000000,0.000000,7)0.000000 6.000000,8)0.000000 -1.000000,NO.ITERATIONS=6,二、求解运输问题的表上作业法,model:,!3,发点,4,收点运输问题,;,sets:,warehouses/wh1.wh3/:capacity;,vendors/v1.v4/:demand;,links(warehouses,vendors,):cost,volume;,endsets,!,目标函数,;,min=,sum(links,:cost*volume);,!,需求约束,;,for(vendors(J,):,sum(warehouses(I,):,volume(I,J,)=,demand(J,);,!,产量约束,;,二、求解运输问题的表上作业法,用,LINGO,求解的基本程序如下,for(warehouses(I,):,sum(vendors(J,):,volume(I,J,)=,capacity(I,);,!,这里是数据,;,data:,capacity=7,4,9;,demand=3,6,5,6;,cost=3,11,3,10,1,9,2,8,7,4,10,5;,enddata,end,二、求解运输问题的表上作业法,Objective value:85.00000,Variable Value Reduced Cost,VOLUME(WH1,V1)2.000000 0.000000,VOLUME(WH1,V2)0.000000 2.000000,VOLUME(WH1,V3)5.000000 0.000000,VOLUME(WH1,V4)0.000000,0.000000,VOLUME(WH2,V1)1.000000 0.000000,VOLUME(WH2,V2)0.000000 2.000000,VOLUME(WH2,V3)0.000000 1.000000,VOLUME(WH2,V4)3.000000 0.000000,VOLUME(WH3,V1)0.000000 9.000000,VOLUME(WH3,V2)6.000000 0.000000,VOLUME(WH3,V3)0.000000 12.00000,VOLUME(WH3,V4)3.000000 0.000000,二、求解运输问题的表上作业法,运行结果,(,部分,),如下,使用表上作业法，有以下特殊情况需要注意,在用最小元素法作初始调运方案时，,当出现供需相等时，这时可以,(,也只能,),满足一家！另一家供,(,需,),量相应地改为,0,；在下一次供应时，,0,也要进行供应或需求,(,如例,1,用最小元素法作初始调运方案,),。,三、表上作业法的特殊情况,在方案的调整过程中，,若奇次拐点的调运量有不止一个等于调整量，调整以后，有几个同时变为,0,，这时只允许一个变为空格成为非基变量，其余的仍为基变量，对应的调运量等于,0,，不能是空格。,（如例,1,，方案的调整）,在方案的调整过程中,，如果调整量等于,0,，这时也要作形式上的调整，只是,0,与空格的位置互换罢了。,产销不平衡问题,例,3,某建材公司有,3,个分厂，均生产水泥预制板，其产销情况及运价如表,1-80,所示，求运费最省的调运方案。,三、表上作业法的特殊情况,若供大于求，即 ，则可以增加一个虚的销地,(,仓库,),其需要量为 并且各个产地到仓库的运价等于,0,。,表,1-80,产销不平衡时运输问题的平衡表与运价表,B,1,B,2,B,3,B,4,发量,B,1,B,2,B,3,B,4,A,1,220,3,11,3,10,A,2,300,1,9,2,8,A,3,400,7,4,10,5,收量,220,240,260,110,三、表上作业法的特殊情况,解,由于总发量,920,吨，收量为,830,吨，产销不平衡，发量比收量多,90,吨。如果把这,90,吨看成是库存的需求量，因此可在运价表中虚加一列，运价表也相应地增加一列，但各发点到库存的运价全为零，于是得到产销平衡的运输问题,(,表,1-81),。,表,1-81,化为产销平衡运输问题的平衡表与运价表,B,1,B,2,B,3,B,4,库存,发量,B,1,B,2,B,3,B,4,库存,A,1,220,3,11,3,10,0,A,2,300,1,9,2,8,0,A,3,400,7,4,10,5,0,收量,220,240,260,110,90,920,其最优解,(,最小运输费,),为：,若用,LINDO,或,LINGO,进行求解，就不必化成产销平衡的情况，可直接求解。,model:,sets:,warehouses/wh1.wh3/:capacity;,vendors/v1.v4/:demand;,links(warehouses,vendors,):cost,volume;,endsets,min=,sum(links,:cost*volume);,for(vendors(J,):,sum(warehouses(I,):,volume(I,J,)=,demand(J,);,for(warehouses(I,):,sum(vendors(J,):,volume(I,J,)=,capacity(I,);,data:,capacity=220,300,400;,demand=220,240,260,110;,cost=3,11,3,10,1,9,2,8,7,4,10,5;,enddata,end,三、表上作业法的特殊情况,Global optimal solution found at iteration:5,Objective value:2430.000,Variable Value Reduced Cost,VOLUME(WH1,V1)0.000000 1.000000,VOLUME(WH1,V2)0.000000 7.000000,VOLUME(WH1,V3)180.0000 0.000000,VOLUME(WH1,V4)0.000000 5.000000,VOLUME(WH2,V1)220.0000 0.000000,VOLUME(WH2,V2)0.000000 6.000000,VOLUME(WH2,V3)80.00000 0.000000,VOLUME(WH2,V4)0.000000 4.000000,VOLUME(WH3,V1)0.000000 5.000000,VOLUME(WH3,V2)240.0000 0.000000,VOLUME(WH3,V3)0.000000 7.000000,VOLUME(WH3,V4)110.0000 0.000000,三、表上作业法的特殊情况,部分输出结果如下,(,与输入信息重复的和无用信息不再列出,),：,若是求最大化运输问题时，只需要作相应地改动：,用最大元素法作初始调运方案；,在最优性判别时，当所有检验数均非正时为最优；,对检验数大于零的空格所对应的闭回路进行调整。其他与最小化运输问题一样。,三、表上作业法的特殊情况,若供不应求，即 ，则可以增加一个虚的产地,其产量为 并且该产地到各个销地的运价等于,0,。（略）,这样就可以把产销不平衡问题化为产销平衡问题进行处理,.,不过,在用计算机软件求解时,一般不需要化为产销平衡问题,因为在软件的设计时,都能够自动处理,.,例,4,农作物布局问题,(,表,1-82),，求产量最大的布局方案。,表,1-82,农作物布局问题的平衡表与产量表,三、表上作业法的特殊情况,土地,农作物,B,1,B,2,B,3,B,4,土地面积,B,1,B,2,B,3,B,4,A,1,1000,5,7,2,6,A,2,400,4,1,0,3,A,3,1800,1,3,4,4,播种面积,600,800,500,1300,3200,解,：用最大元素法作初始调运方案（表,1-83,）：,三、表上作业法的特殊情况,表,1-83,农作物布局问题的初始方案,土地,农作物,B,1,B,2,B,3,B,4,土地面积,B,1,B,2,B,3,B,4,A,1,800,200,1000,5,7,2,6,A,2,400,400,4,1,0,3,A,3,200,500,1100,1800,1,3,4,4,播种面积,600,800,500,1300,3200,有检验数,不是最优解,进行调整,(,表,1-84),。,三、表上作业法的特殊情况,表,1-84,农作物布局问题的方案调整,土地,农作物,B,1,B,2,B,3,B,4,土地面积,B,1,B,2,B,3,B,4,A,1,+200,800,200-200,1000,200,800,A,2,400,400,400,A,3,200,-200,500,1100+200,1800,0,500,1300,播种面积,600,800,500,1300,3200,所有检验数全部非正，最优。最大产量：,maxZ,=2005+8007+4004+5004+13004=15400,使用位势法求检验数,三、表上作业法的特殊情况,经典运输问题“悖论”,.,例,5,对于例,2,讨论的运输问题,最优调运方案如下表所示,表,1-85,运输问题的平衡表与运价表,B,1,B,2,B,3,B,4,发量,B,1,B,2,B,3,B,4,A,1,2,5,7,3,11,3,10,A,2,1,3,4,1,9,2,8,A,3,6,3,9,7,4,10,5,收量,3,6,5,6,20,表,1-85,是最优方案。,min Z=23+53+11+38+64+35=85,三、表上作业法的特殊情况,对应的运输问题的数学模型为：,若将模型改为：,三、表上作业法的特殊情况,表,1-86,增加收发量的平衡表与运价表,三、表上作业法的特殊情况,则可得到以下两种情况下，运输量多，而总运费反而少的运输方案。这就是经典运输问题“悖论”，或者说是“多反而少”现象（表,1-86,，表,1-87,）。,B,1,B,2,B,3,B,4,发量,B,1,B,2,B,3,B,4,A,1,2,5,7,3,11,3,10,A,2,4,0,4,1,9,2,8,A,3,6,6,12,7,4,10,5,收量,6,6,5,6,23,表,1-86,所示方案是最优方案。,MinZ,=23+53+41+08+64+65=79,表,1-87,增加收发量的平衡表与运价表,表,1-87,是最优方案。,MinZ,=73+41+64+65=79,三、表上作业法的特殊情况,B,1,B,2,B,3,B,4,发量,B,1,B,2,B,3,B,4,A,1,7,7,3,11,3,10,A,2,4,0,0,4,1,9,2,8,A,3,6,6,12,7,4,10,5,收量,4,6,7,6,23,例,6,某工厂专造飞机发动机，根据合同，,14,月份交货量以及工厂的最大生产能力如表,1-88,，由于技术上的原因，生产发动机的成本波动，其变化情况见表,1-88,。,表,1-88,飞机发动机交货量与生产能力,月份,1,月,2,月,3,月,4,月,交货台数,10,15,25,20,工厂的最大生产能力,25,35,30,10,每台发动机成本（万元）,1.08,1.11,1.10,1.13,四、运输问题的应用,由于生产成本的变化，可能在某个月成本低时多生产些留到以后用，但每台发动机存贮一个月要,0.015(,万元,)(,包括成本的利息等,),。现要制定一个进度表，每月安排生产多少台可使总成本最小？,但是,2,月生产的不能在,1,月份供应,3,月份生产的不能在,1,、,2,月份供应,4,月份生产的不能在,1,、,2,、,3,月份供应,四、运输问题的应用,解：,由于有存贮费,因此,1,月份生产每台的成本,1.08,万元,如果,2,月份才卖出,那么成本为,1.08+0.015=1.095,万元,;,若留到,3,、,4,月份才卖出，相应的成本分别为,1.11,万元和,1.125,万元。其余的成本计算与此类似。,为了阻止这种行为发生，我们将对应的成本定为一个充分大的正数,M,。,由于生产能力的产量大于需求量，构造一个虚的需要地，其需要量为,25+35+30+10-10-15-25-20=30,。则可列表如表,1-89.,表,1-89,飞机发动机交货量与生产能力的平衡表,1,月,2,月,3,月,4,月,未生产,产量,1,月,2,月,3,月,4,月,未生产,1,月,10,15,25,1.08,1.095,1.11,1.125,0,2,月,0,5,30,35,M,1.11,1.125,1.140,0,3,月,25,5,30,M,M,1.10,1.115,0,4,月,10,10,M,M,M,1.130,0,需要量,10,15,25,20,30,100,四、运输问题的应用,取,M=1000,用计算机软件可求得最优解如表,1-89,，,Z=77.3,万元。,min 1.08x11+1.095x12+1.11x13+1.125x14+1000 x21+1.11x22,+1.125x23+1.14x24+1000 x31+1000 x32+1.1x33+1.115x34,+1000 x41+1000 x42+1000 x43+1.13x44,st,x11+x12+x13+x1425,x21+x22+x23+x2435,x31+x32+x33+x3430,x41+x42+x43+x44=30,x11+x21+x31=50,x12+x22+x32=70,x13+x23+x33=10,end,四、运输问题的应用,LP OPTIMUM FOUND AT STEP 10,OBJECTIVE FUNCTION VALUE,1)2460.000,VARIABLE VALUE REDUCED COST,x11 0.000000 4.000000,x12 50.000000 0.000000,x13 0.000000 7.000000,x14 0.000000 2.000000,x21 0.000000 2.000000,x22 20.000000 0.000000,x23 0.000000 4.000000,x24 40.000000 0.000000,x31 50.000000 0.000000,x32 0.000000,0.000000,x33 0.000000 1.000000,x34 0.000000 978.000000,四、运输问题的应用,ROW SLACK OR SURPLUS DUAL PRICES,2)0.000000 -15.000000,3)0.000000 -15.000000,4)0.000000 -22.000000,5)20.000000 0.000000,6)0.000000 3.000000,7)0.000000 2.000000,8)30.000000 0.000000,9)30.000000 0.000000,NO.ITERATIONS=10,四、运输问题的应用,表,1-92,三个化肥厂供应四个地区的化肥的计划表,产量,A,50,50,16,13,22,17,B,20,40,60,14,13,19,15,C,50,50,19,20,23,最低需求,30,70,0,10,最高需求,50,70,30,不限,当然，如果用,LINGO,直接编程求解也是很方便的。,四、运输问题的应用,于是可得到总运费最省的化肥调拨方案如,1-92,所示,:,