运筹学ch3运输问题ppt课件

1、人们在从事生产活动中，不可避免地要进行物资调运工作。如人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。这样的问题称为运输问题。n供给及需求单位：供给及需求单位：1卡车的量卡车的量n单位运输成本：千元单位运输成本：千元运价表运价表2321341s2

2、=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地67538427591060 xxxxxxxxxxxx13xxx12xxx13xxx22xxx19xxxx27xxxx14xxxxs.t.x6x10 x9x5x7x2x4x8x3x5x7x6zmin343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211供应地约束需求地约束设设xij(i=1,2,3；j=1,2,3,4)为为i个工厂运往第个工厂运往第j个配送中心的运量

3、，个配送中心的运量，这样得到下列运输问题的数学模型：这样得到下列运输问题的数学模型：123467531x11x12x13x141484272x21x22x23x2427591063x31x32x33x341922131213知：知：m个产地记作个产地记作A1，A2，A3,Am），其产量分别为），其产量分别为a1,a2，am；n个销地记作个销地记作B1，B2，Bn），其需要量分别为），其需要量分别为b1,b2，bn；且产销平衡，即；且产销平衡，即 。从第从第i个产地到个产地到j 个销地的单位运价为个销地的单位运价为cij ，问：在满足各地需要的前提下，求总运输费用最小的调运方问：在满足各地需要的

4、前提下，求总运输费用最小的调运方案。案。 即即AiBj 的运量的运量xij 使使njjmiiba11njijijmixcz11minnjmiba11njmiba11求解的形式来这两种情形都可以化为jiba产销平衡问题模型1111 1,.1,.0 mnijijnijijmijjiijMin zaxxaimxbjnx 11112122111211112222 nnmmnmmmxxaxxaxxaxxxbxxx212 nnmnnbxxxb约束方程式中共mn个变量，m+n个约束。11 11 A= 111 1 1 1 1 1系数矩阵的特点:(1)约束条件的系数矩阵的元素只有两个:0,1.(2)元素 xij

5、 对应于每一个变量在前m个约束方程中(第i个方程中)出现一次,在后n个约束方程中(第m+j 个方程中)也出现一次.(3)产销平衡问题为等式约束.(4)产销平衡问题中各产地产量之和与各销售地点的销量之和相等.ijab3.m+n1个变量组构成基变量的充要条件是它不个变量组构成基变量的充要条件是它不包含任何闭回路。一条回路中的顶点数一定是偶数。包含任何闭回路。一条回路中的顶点数一定是偶数。【证】因为产销平衡，即【证】因为产销平衡，即 ，将前，将前m个约束方程两边相个约束方程两边相加得加得minjiiba11minjmiiijax111再将后再将后n个约束相加得个约束相加得njminjjijbx111

6、显然前显然前m个约束方程之和等于后个约束方程之和等于后n个约束方程之和，个约束方程之和，m+n个约束个约束方程是相关的，系数矩阵方程是相关的，系数矩阵【定理【定理1】设有】设有m个产地个产地n个销地且产销平衡的运输问题，则基变个销地且产销平衡的运输问题，则基变量数为量数为m+n-1。中任意中任意m+n阶子式等于零，取第一行到阶子式等于零，取第一行到m+n1行与行与对应的列共对应的列共m+n-1列组成的列组成的m+n1阶子式阶子式1, 1121121,nmnnnxxxxxx，m 行行n 行行111212122212111111111111111111nnmmmnxxxxxxxxxA0111111

7、111故故r(A)=m+n1所以运输问题有所以运输问题有m+n1个基变量。个基变量。为了在为了在mn个变量中找出个变量中找出m+n1个变量作为一组基变量，就是个变量作为一组基变量，就是要在要在A中找出中找出m+n-1个线性无关的列向量，通常引用闭回路的概个线性无关的列向量，通常引用闭回路的概念寻找这些基变量。念寻找这些基变量。运输单纯形法也称为表上作业法，是直接在运价表上求最优解运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤是：的一种方法，它的步骤是： 第一步：求初始基行可行解初始调运方案）。第一步：求初始基行可行解初始调运方案）。 常用的方法有常用的方法有最小元素

8、法、元素差额法最小元素法、元素差额法Vogel近似法）、左上角法。近似法）、左上角法。 第二步：求检验数并判断是否得到最优解。常用求检验的方法第二步：求检验数并判断是否得到最优解。常用求检验的方法有闭回路法和位势法，当非基变量的检验数有闭回路法和位势法，当非基变量的检验数ij全都非负时得到最全都非负时得到最优解，若存在检验数优解，若存在检验数lk0，说明还没有达到最优，转第三步。，说明还没有达到最优，转第三步。 第三步：调整运量，即换基。选一个变量出基，对原运量进行第三步：调整运量，即换基。选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。调整得到新的基可行解，转入第二步。表表 上

9、上 作作 业业 法法左上角法左上角法(亦称西北角法亦称西北角法)是优先从运价表的左上角的变量赋值，当行或列分是优先从运价表的左上角的变量赋值，当行或列分配完毕后，再在表中余下部分的左上角赋值，依次类推，直到右下角元素分配完毕后，再在表中余下部分的左上角赋值，依次类推，直到右下角元素分配完毕当出现同时分配完一行和一列时，仍然应在打配完毕当出现同时分配完一行和一列时，仍然应在打“”的位置上选一的位置上选一个变量作基变量，以保证最后的基变量数等于个变量作基变量，以保证最后的基变量数等于m+n1 1 2 3 4 6 7 5 3 1 14 8 4 2 7 2 27 5 9 10 6 3 19 22 13

10、 12 13 813131466最小元素法的思想是优先满足单位运价最小的业务，即最最小元素法的思想是优先满足单位运价最小的业务，即最小运价小运价Cij 对应的变量对应的变量xij优先赋值，优先赋值，然后再在剩下的运价中取最小运价对应的变量赋值并满足然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基可行解。约束，依次下去，直到最后得到一个初始基可行解。初始基础可行解最小元素法jiijbax,min123467531148427212271559106319221312130初始基础可行解最小元素法1）最小元素法2）1234675311314184272122

11、715591063192213121300最小元素法3）123467531131418427213122725910631922131213000最小元素法4）1234675311314184272131227259106319190221312133000最小元素法5）12346753111314084272131227259106319190221312132000最小元素法6）123467531113140842722131227059106319190221312130000初始基础可行解元素差额法（Vogel近似法）求初始基本可行解的步骤是：求初始基本可行解的步骤是： 第一步：求出每

12、行次小运价与最小运价之差，记为第一步：求出每行次小运价与最小运价之差，记为ui，i=1,2,m ；同时求出每列次小运价与最小运价之差，记为；同时求出每列次小运价与最小运价之差，记为vj，j=1，2，n ； 第二步：找出所有行、列差额的最大值，即第二步：找出所有行、列差额的最大值，即L=maxui，vi，差，差额额L对应行或列的最小运价处优先调运；对应行或列的最小运价处优先调运； 第三步：这时必有一列或一行调运完毕，在剩下的运价中再求第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运最大差额，进行第二次调运，依次进行下去，直到最后全部调

13、运完毕，就得到一个初始调运方案。完毕，就得到一个初始调运方案。 用元素差额法求得的基本可行解更接近最优解，所以也称为近用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。似方案。【例】用元素差额法求下表运输问题的初始基本可行解。【例】用元素差额法求下表运输问题的初始基本可行解。【解】【解】 求行差额求行差额 ui, i=1,2,3及列差额及列差额vj,j=1,2,3,4.计算公式为计算公式为 ui= i行次小运价行次小运价i行最小运价行最小运价 vj= j列次小运价列次小运价j例最小运价例最小运价【 】520【 】0除去除去B3列，重新计算差额列，重新计算差额200【 】10205求

14、出一组基可行解后，判断是否为最优解，仍然是用检验数来判求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记断，记xij的检验数为的检验数为ij由第一章知，求最小值的运输问题的最优由第一章知，求最小值的运输问题的最优判别准则是：判别准则是：所有非基变量的检验数都非负，则运输方案最优即为最优解）。所有非基变量的检验数都非负，则运输方案最优即为最优解）。求检验数的方法有两种，闭回路法和位势法。求检验数的方法有两种，闭回路法和位势法。1闭回路法求检验数闭回路法求检验数 求某一非基变量的检验数的方法是：在基求某一非基变量的检验数的方法是：在基本可行解矩阵中，以该非基变量为起点，以基变量为其它顶

15、点，本可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号找一条闭回路，由起点开始，分别在顶点上交替标上代数符号+、-、+、-、，以这些符号分别乘以相应的运价，其代数和就是，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。这个非基变量的检验数。第二步，求检验数，判优第二步，求检验数，判优12346753114148427281362759106361319221312135非基变量xij的检验数cij-zij闭回路法(1)12=c12-z12=c12- (c11-c21+c22) =7-6+8-4=512346753114

16、148427281362759106361319221312135闭回路法(2)13=c13-z13=c13- c11+c21-c23) =5-6+8-2=5512346753114148427281362759106361319221312135闭回路法(3)14=c14-z14=c14-(c11-c21+ c21 - c23 + c33 -c34)-=3- (6-8+2-10+6)=77512346753114148427281362759106361319221312135闭回路法(4)c24-z24=c24 -(c23-c33+ c34)=7 -(2-10+6)=99571234675

17、3114148427281362759106361319221312135闭回路法(5)c31-z31=c31- (c21-c23+ c33) =5 -(8-2+10)=-11-1157912346753114148427281362759106361319221312135闭回路法(6)c32-z32=c32-( c22-c23+ c33) =9 -(4-2+10)=-3-3579-11这里31和 320,得到最优解。Min z=61+3 13+8 2+4 13+2 12+5 19=1421155482 产销平衡表 单位：吨 单位运价表 单位：元/吨以此类推，得到一初始方案如下图）：X21=

18、3，X32=6，X13=4，X23=1，X14=3，X34=3有数格）X11=X31=X12=X22=X33=X24=0空格）注：（）有数格是基变量，共m+n-1=3+4-1=6个。空格是非基变量，共划去m+n=7条线；（）如果填上一个运量之后能同时划去两条线一行与一列），就须在所划去的该行或该列填一个0，此0格当有数个对待。初始方案运费Z0=31+64+43+12+310+35=86(元)每一个空格的检验数每一个空格的检验数=奇顶点运费之和奇顶点运费之和 偶顶点运费之和。偶顶点运费之和。(+1)*3+ (-1)*3+(+1)*2+(-1)*1=1空格检验数空格检验数24=(+1)*8+(-1

19、)*2+(+1)*3+(-1)*10=-1+-从ij 为最小负值的空格出发.对其闭回路上的奇数顶点运量增加,偶数顶点的运量减少(这才能保证新的平衡)，其中为该空格闭回路中偶数顶点的最小值。 240，从A2 B4） 出发其闭回路上=1，调整后得到一个新方案如下表），运量为=1的A2 B3变空格，得到新方案后再转 2。经再计算新方案的检验数全部大于0。所以，该新方案为最优方案，可计算得总运费为85元。注：若闭回路的偶数顶点中同时有两个格以上运量为，则调整后其中一个变空格，其余填0。（保证基变量个数不变）3B1B3A2A1A4B2B3.调整调整:12921124表上作业法须注意的问题：表上作业法须注

20、意的问题： i) 在最终调运表中，若有某个空格非基变量的检验在最终调运表中，若有某个空格非基变量的检验数为数为0时，则表明该运输问题有多重调运方案；时，则表明该运输问题有多重调运方案； ii) 在确定初始方案时，若某一行的产量与某一列的需求在确定初始方案时，若某一行的产量与某一列的需求量同时满足，这时也只能划去一行或一列绝对不能同时量同时满足，这时也只能划去一行或一列绝对不能同时把行、列划去，否则就不满足圈格把行、列划去，否则就不满足圈格=m+n1个的要求，即个的要求，即基变量的个数永远要保持为基变量的个数永远要保持为m+n1个）；个）； iii) 在用闭回路法调整时，当闭回路上奇顶点有几个相

21、同在用闭回路法调整时，当闭回路上奇顶点有几个相同的最小值时，调整后只能有一个空格，其余均要保留数的最小值时，调整后只能有一个空格，其余均要保留数“0”，以保证圈格，以保证圈格=m+n1个的需要。个的需要。 iv) 用最小元素法所得到的初始方案可以不唯一。用最小元素法所得到的初始方案可以不唯一。1 0nijijijjiijMin ZCXxaxbx添加松弛变量xin+111 0nijijijjiijMin ZCXxaxbxxin+1的定义：由Ai向Bn+1的运量，而Bn+1并不存在，相当于增加了一个虚设的销地Ai自己的仓库里，自己往自己的地方运，运费cin+1显然为0。实际上xin+1即剩余量就地

22、库存产大于销的产销量表A1Ama1amB1Bnb1bnBn+1A1AmB1BnC1100C1nCm1Cmn产大于销的单位运价表Bn+1jinbab11 0mijjiijiijMin ZCXxbxax添加松弛变量xm+1j11 0mijjiijiijMin ZCXxbxax同理，此时xm+1j的意义为销售短缺的量，同样，Am+1不存在， cm+1j为0。销大于产的产销量表A1Ama1amB1Bnb1bnAm+11jiabamA1AmB1BnC1100C1nCm1Cmn销大于产的单位运价表Amjjiba因为有：因为有：【例】求下列表中极小化运输问题的最优解。【例】求下列表

23、中极小化运输问题的最优解。 所以是一个产大于销的运输问题。所以是一个产大于销的运输问题。表中表中A2不可达不可达B1，用一个很大的正数，用一个很大的正数M表示运价表示运价C21。虚设。虚设一个销量为一个销量为b5=180160=20的销地的销地B5，Ci5=0，i=1，2，3，4。表的右边增添一列表的右边增添一列 这样可得新的运价表：这样可得新的运价表：下表为计算结果。可看出：产地下表为计算结果。可看出：产地A4还有还有20个单位没个单位没有运出。有运出。上例中，假定上例中，假定B1的需要量是的需要量是20到到60之间，之间，B2的需要量是的需要量是50到到70，试求极小化问题的最优解。试求极

24、小化问题的最优解。需求量不确定的运输问题需求量不确定的运输问题（1总产量为总产量为180，B1，B4的最低需求量的最低需求量 20+50+35+45=150，这时属产大于销；，这时属产大于销；（2B1，B4的最高需求是的最高需求是60+70+35+45=210，这时属销大于产，这时属销大于产（3虚设一个产地虚设一个产地A5，产量是，产量是210180=30，A5的产量只能供的产量只能供应应B1或或B2。（4将将B1与与B2各分成两部分各分成两部分 的需求量是的需求量是20， 的需求量是的需求量是40， 的需求量分别是的需求量分别是50与与20，因此，因此 必须由必须由A1，A4供应，供应， 可

25、由可由 A1、A5供应。供应。1122122111BBBBB，、及、21B2212BB 与1211BB 、2221BB 、（5上述上述A5不能供应某需求地的运价用大不能供应某需求地的运价用大M表示，表示，A5到到 、 的运价为零。得到下表的产销平衡表。的运价为零。得到下表的产销平衡表。先作如下分析：先作如下分析：11B21B12B22B得到这样的平衡表后，计算得到最优方案表得到这样的平衡表后，计算得到最优方案表5-29。产销平衡表产销平衡表 B3B4aiA1 352560A2 40 40A30 10 2030A42030 50A5 10 20 30bj204050203545210 11B21B12B22B表中：表中：x131=0