运筹学OR-4-运输问题课件.ppt

《运筹学OR-4-运输问题课件.ppt》由会员分享，可在线阅读，更多相关《运筹学OR-4-运输问题课件.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Ningbo University运输问题Operations Research,Spring 2016,C.-J.ChangNingbo University运输问题的介绍n运输问题主要是求从许多起点(产地)到不同终点(销地)的最低总成本之调运方案。一般运输问题假设总产量等于总销量，此类问题称为产销平衡的运输问题，即ai=bj。2Ningbo University运输问题的线性规划模式3这个运输问题包含了12个(34)变量，7个(3+4)约束条件，其系数矩阵相当特殊；运输问题虽然可以用单纯形法求解，但解题效率不高，一般会改用表上作业法求解。Ningbo University运输问题的数学模型

2、n已知有m个生产地点Ai，i=1,2,m。可供应某种物资，其供应量(产量)分别为ai,i=1,2,m，有n个销地Bj，j=1,2,n，其需要量分别为bj，j=1,2,n，从Ai到Bj运输单位物资的运价(单价)为cij，这些数据可汇总于产销平衡表和单位运价表中，见下表。有时可把这两表合二为一。4产地销地B1B2BnA1c11c12c1nA2c21c22c2nAmcm1cm2cmn产地销地产量B1B2B3B4A1a1A2a2A3am销量b1b2bnNingbo UniversityNingbo University运输问题的数学模型n这就是运输问题的数学模型。它包含mn个变量，(m+n)个约束方程

3、，其系数矩阵的结构比较松散，且特殊。6Ningbo University运输问题的数学模型n该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1以外，其余的都为零。即 Pij=(0,1,0,0,1,0,0)T=ei+em+jn对产销平衡的运输问题，由于有以下关系式存在：所以模型最多只有m+n1个独立约束方程。即系数矩阵的秩m+n1。由于有以上特征，所以求解运输问题时，可用比较简便的计算方法，称为表上作业法。产销平衡的运输问题，一定存在可行解。又因为所有变量有界，因而存在最优解。7Ningbo University表上作业法n表上作业法是单纯形法在求解运输问题时的一种简

4、化方法，其实质是单纯形法，故也称运输问题单纯形法。但具体计算和术语有所不同。可归纳为：1.找出初始基可行解。即在mn格的产销平衡表上按一定的规则(最小元素法、Vogel法)给出m+n1个数字，称为数字格。它们就是初始基变量的取值。2.求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。3.确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。4.重复2与3直到得到最优解为止。8Ningbo UniversityNingbo University运输问题的表格形式n某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨

5、，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价为下表。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。10产地销地B1B2B3B4A1311310A21928A374105产地销地产量B1B2B3B4A17A24A39销量3656单位运价表产销平衡表Ningbo University运输问题的表格形式11销地B1B2B3B4产量产地A13113107A219284A3741059销量3656产地销地B1B2B3B4A1311310A21928A3741

6、05产地销地产量B1B2B3B4A17A24A39销量3656Ningbo UniversityNingbo UniversityEx.最小元素法13销地B1B2B3B4产量产地A13113107A219284A3741059销量3656301140403603330300过程中若遇到较小成本有两格相同时，可以任意选择。现在产销平衡表上已得到一个调运方案，此时的总运费成本为13+46+34+21+103+53=86Ningbo UniversityNingbo UniversityEx.伏格尔(Vogel)法15销地B1B2B3B4产量产地A13113107A219284A3741059销量3

7、6563011005260330220过程中若遇到差额或较小成本有相同时，可以任意选择。现在产销平衡表上已得到一个调运方案，此时的总运费成本为13+46+35+102+81+53=850112513276320000Ningbo University闭回路(踏石)法n闭回路法用来检查现有解是否最佳解，如果不是，则找一个更好的解；现有解中已有n+m1个不为0的格子称为数字(基)格，其它为0的格子称为空格闭回路法的观念是检查所有的空格，如果变成数字格的话，会不会使成本降低；也就是计算非基变量的检验数。要使一个空格变成基格，其必定会有运输量，那么它的同一行或同一列其它的基格就必须有一个减掉该运输量，

8、依照这样的连锁反应(每次到数字格就要转90后，再继续前进)，就会得到一条正负相间的封闭路线。运输单纯形表如果有n+m1个数字格，闭回路会是唯一的。每条闭回路可以根据正负号计算其单位成本。n若单位成本是负数，则该空格变成数字格，会降低成本。n若单位成本是正数，则该空格变成数字格，会增加成本。16Ningbo UniversityNingbo University销地B1B2B3B4产量产地A13113107 43A2192843 1 A37410596 3销量3656Ex.闭回路法18+11空格闭回路检验数111222243133+1181销地B1B2B3B4产量产地A13113107 52A2

9、192843 1A37410596 3销量3656(11)(13)(23)(21)(11)(12)(14)(34)(32)(12)(22)(23)(13)(14)(34)(32)(22)(31)(34)(14)(13)(23)(21)(31)(33)(34)(14)(13)(33)(24)(23)(13)(14)(24)+33+21=+5+1110+54=+2+92+310+54=+1+75+103+21=+10+105+103=+12+82+310=1Ningbo University销地B1B2B3B4产量产地A13113107 52A2192843 1A37410596 3销量3656E

10、x.闭回路法19空格閉回路檢驗數11(11)(14)(24)(21)(11)+310+81=+012(12)(14)(34)(32)(12)+1110+54=+222(22)(24)(34)(32)(22)+98+54=+223(23)(13)(14)(24)(23)+23+108=+131(31)(21)(24)(34)(31)+71+85=+933(33)(13)(14)(34)(33)+103+105=+1219因为检验数皆为非负，此调运方案已是最优解，此时的总运费成本为35+102+13+81+46+53=85Ningbo University表上作业法计算中的问题n无穷多最优解某非基

11、变量(空格)的检验数为0时，该问题有无穷多最优解。nEx.20销地B1B2B3B4产量产地A13113107 52A2192843 1A37410596 3销量3656空格(11)的检验数为0，此时有无穷多最优解，若我们依其闭回路调整，可得到另一组最优解，其总运费成本皆为85。销地B1B2B3B4产量产地A131131072 5A2192841 3A37410596 3销量3656Ningbo University表上作业法计算中的问题n退化当运输问题现有解的基格数目小于m+n1时，则发生退化解；此时执行闭回路法时，会有空格找不到封闭路线，而使我们无法继续求解。1.在给定初始解时，若在某交叉格

12、填入运输量后，会同时划去该行与该列，则会出现退化解。2.在用闭回路法调整时，在闭回路上出现两个或两个以上的具有(1)标记的相等最小值，这时经过调整后，会得到退化解。当发生退化解时，我们要在运输表上某些空格加上一个0的运输量，使其成为数字格，而使数字格数量等于m+n1；当一个空格上填入运输量0，它就要当作数字格来处理(一般运输量为0时，我们会空着不写，使其成为空格；为了区别，人工所填加0的运输量就不省略)。21Ningbo University位势法1.令运输单纯形表中，行对应的对偶变量为ui，列对应的对偶变量为vj。(为区别销量与产量的限制故用不同的符号)2.因为数字格的检验数应为0，由数字格

13、可得到其对应的cij(ui+vj)=0。3.令某一ui或vj的值为0，以求得其它ui与vj的值。4.依所找到的ui与vj计算空格的检验数。若所有检验数皆0，则已得到最优解。若存在检验数0，则尚未得到最优解，应继续运算。22Ningbo UniversityNingbo UniversityEx.位势法24销地B1B2B3B4产量产地A13113107 52A2192843 1A37410596 3销量3656u1u2u3v1v2v3v4令u1=00-2-539310(12)(0)(2)(2)(1)(9)检验数不存在负数，所以目前方案已是最优解，此时的总运费成本为35+102+13+81+46+

14、53=85(有检验数为0，此題有无穷多最优解。)Ningbo University位勢法的原理25cjCBCN0CBXBbXBXNXSCBXBB1bIB1NB1cj-zj0CNCBB1NCBB1Y=CBB1x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34Ningbo University产销不平衡的调整n在运输模式是以产销平衡为前提，但是实际问题中产销往往是不平衡的，这就需要把产销不平衡的问题化成产销平衡的问题。当产大于销，只要增加一个假想的销地，该销地的销量等于差额部份，而各产地到假想销地的单位运价为0当销大于产，只要增加一个假想的产地，该产地的

15、产量等于差额部份，而假想销地到各产地的单位运价为026销地B1B2B3虚拟产量产地A13750100 A2486090 A35670110 销量908010030300300销地B1B2B3产量产地A1375100 A248690 A3567110 销量9080100300270Ningbo UniversityNingbo University高低销量的应对n销量分两种情况的地区，可按照两个地区看待。低销量是第一个地区；虚产地是不可供给这个销地的，运输成本设为M。高低销量间的差额是第二地区；其运输成本除虚产地外，皆与第一个产地相同，而虚产地的运输成本设为0。28销地B1B1B2B3B3产量产

16、地A133755100 A24486690 A355677110 虚拟M0MM020 销量90208010030320320销地B1B2B3产量产地A1375100 A248690 A3567110 低销量高销量901108080100130270 300320Ningbo UniversityEx.产销不平衡的运输问题n设有三个化肥厂(A,B,C)供应四个地区(,)的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如下表所示。试求出总的运费最节省的化肥调拨方案。29需求地区产量化肥厂A1613221750B14 131915

17、60C19202350最低需求最高需求3050707003010不限销地产量产地A1616 13 22171750 B14 14 13 1915 1560 C1919 20 23MM50 虚拟M0M0M050 销量302070301050210210Ningbo UniversityNingbo University随堂练习n已知某运输问题的成本、产量和销量如下表。a.请以最小元素法找出一个起始解。b.请以伏格尔(Vogel)法找出一个起始解。c.请找出下列空格的闭回路径及其检验数值。d.请用闭回路修正法找出最佳调运方案及最小运输成本。销地B1B2B3产量A1674100A2536180A38

18、57200销量135175170480产地31销地B1B2B3产量产地A1674100 100A25361805 175A385720013070销量135175170480480Ningbo University随堂练习n已知某运输问题的成本、产量和销量如下表。請找出最佳的調運方案及最小運輸成本。32销地B1B2B3产量A1201624300A211108500A3121810100销量200400300900产地Ningbo University随堂练习n已知某运输问题的成本、产量和销量如下表。請找出最佳的調運方案及最小運輸成本。33销地B1B2B3产量A169100130A2123570A34811100销量8011060产地Ningbo UniversityThe end of this chapter.Thank You！