第四章--运输问题(Transportation--Problem)

2020/5/181运输问题(TransportationProblem)运输规划的数学模型表上作业法产销不平衡的运输问题有转运的运输问题2020/5/182一、运输问题的数学模型例：某运输问题的资料如下：单位销地运价产地B1B2B3B4产量A1291029A213425A384257销量38462020/5/183)4.3.2.1,3.2.1(06483759524824371092min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij约束条件：目标函数：为运量设2020/5/184运输问题数学模型的一般形式已知某产品有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-1，表4-2。有时可把这两表合二为一。2020/5/185表4-1产销平衡表销地产地B1B2┉Bn产量A1A2┆Ama1a2┆am销量b1b2┈bn2020/5/186表4-2单位运价表销地产地B1B2┉BnA1A2┆Amc11c12┈c1nc21c22┈c2n┇cm1cm2┈cmn2020/5/187运输问题数学模型的一般形式若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，其数学模型为)(0min11ijjijijiijminjijijxbabxaxxcZ2020/5/188运输问题数学模型的特点1.运输问题有有限个最优解2.运输问题约束条件的特点：运输问题的数学模型包含m×n个变量，(m+n)个约束方程，其系数矩阵的结构比较松散且特殊。行行nmvvvuuuxxxxxxxxxnmmnmmnn11111111111111111121212122221112112020/5/189运输问题数学模型的特点该系数矩阵中对应于某一变量的系数向量，其分量中除第i个和第m+j个为1以外，其余的都为零，在约束条件中，前m个约束条件的含义是：由某一产地运往各销地的产品数量之和等于该产地的产量；后n个约束条件的含义是：由各产地运往某一销地的产品数量之和等于该销地的销量。2020/5/1810运输问题的对偶问题运输问题的对偶问题可按照前面写线性规划问题的对偶问题的方法给出（略）2020/5/1811运输问题的解运输问题也是一个线性规划问题，其求解时仍然可以先找一个基可行解，进行解的最优性检验，若不是最优，就进行迭代，继续检验和调整直到最优，因此要求每步得到的解都是基可行解，需满足(1)满足所有约束条件；(2)基变量对应的系数列向量线性无关；(3)解中非零变量的个数不能大于m+n-1个，原因是运输问题中虽有m+n个约束条件，但由于总产量等于总销量，故只有m+n-1个约束条件是线性独立的；(4)保持基变量的个数在迭代过程中为m+n-1个。2020/5/1812第2节表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法,但具体计算和术语有所不同，其步骤可归纳为：(1)找出初始基可行解：即在(m×n)产销平衡表上用西北角法或最小元素法、Vogel法给出m+n-1个数字，称为数字格，它们就是初始基变量的取值。(2)求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。(3)确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。(4)重复(2)，(3)直到得到最优解为止。2020/5/1813例题单位销地运价产地产量311310719284741059销量3656产销平衡321AAA例：某食品公司下属的A1、A2、A3，3个厂生产方便食品，要运输到B1、B2、B3、B4，4个销售点，数据如下：求最优运输方案。4321BBBB2020/5/1814一初始基可行解的确定确定初始基可行解的方法很多，有西北角法，最小元素法和沃格尔(Vogel)法等，一般希望的方法是既简便，又尽可能接近最优解。下面分别予以介绍：1.最小元素法此方法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，…，一直到给出初始基可行解为止。以上例进行讨论得下表：2020/5/1815B1B2B3B4产量A17A24A39销量3656311310192741058341633总的运输费用＝（3×1）＋（6×4）＋（4×3）＋（1×2）＋（3×10）＋（3×5）＝86元2020/5/18162.西北角法（或左上角法）：此法是纯粹的人为规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因而受欢迎。方法如下：365674934490656404902562029005620090036360000000340002200036总的运费＝(3×3)＋(4×11)＋(2×9)＋(2×2)＋(3×10)＋(6×5)＝135元2020/5/18173.沃格尔法最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费。沃格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。沃格尔法的步骤是：第一步：在原表中分别计算出各行和各列的最小运费和次小运费的差额，并填入该表的最右列和最下行，见表4-12020/5/1818表4-1销地产地B1B2B3B4行差额A1A2A3317119432101085011列差额2513第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表4-1中B2列是最大差额所在列。B2列中最小元素为4，可确定A3的产品先供应B2的需要。得表4-2：2020/5/1819销地产地B1B2B3B4产量A1A2A36749销量3656同时将运价表中的B2列数字划去。如表4-3所示（表4-3）：表4-2销地加工厂B1B2B3B4行差额A1A2A3317119432101085012列差额2132020/5/1820销地加工厂B1B2B3B4产量A1A2A3365213749销量3656第三步：对表4-3中未划去的元素再分别计算出各行、各列的最小运费和次小运费的差额，并填入该表的最右列和最下行，重复第一、二步，直到给出初始解为止。用此法给出上例的初始解列于表4-4（下表）。2020/5/1821说明由以上可见：沃格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。沃格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。本例用沃格尔法给出的初始解就是最优解。2020/5/1822二最优解的判别最优性检验就是检查所得到的方案是不是最优方案。检查的方法与单纯形方法中的原理相同，即计算检验数。由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。下面介绍两种求检验数的方法：1.闭回路法；2.位势法2020/5/18231闭回路法在给出调运方案的计算表上，如上例表，从每一空格出发找一条闭回路。它是以某空格为起点，用水平或垂直线向前划，当碰到一数字格时可以转90°后，继续前进，直到回到起始空格为止。闭回路如图(a),(b),(c)等所示。销地加工厂B1B2B3B4产量A1A2A3365213749销量36562020/5/1824闭回路法计算检验数的经济解释为：在已给出初始解的表中，可从任一空格出发，如(A1，B1)，若让A1的产品调运1吨给B1。为了保持产销平衡，就要依次作调整：在(A1，B3)处减少1吨，(A2，B3)处增加1吨，(A2，B1)处减少1吨，即构成了以(A1，B1)空格为起点，其他为数字格的闭回路，如下表虚线所示。在这表中闭回路各顶点所在格的右上角数字是单位运价销地加工厂B1B2B3B4产量A13(+1)1134(-1)1037A213(-1)921(+1)84A374610539销量36562020/5/1825可见这调整的方案使运费增加(+1)×3+(-1)×3+(+1)×2+(-1)×１=1(元)将“1”这个数填入(A1，B1)格，这就是检验数。按以上所述，可找出所有空格的检验数，见下表。空格闭回路检验数(11)(12)(22)(24)(31)(33)(11)-(13)-(23)-(21)-(11)(12)-(14)-(34)-(32)-(12)(22)-(23)-(13)-(14)-(34)-(32)-(22)(24)-(23)-(13)-(14)-(24)(31)-(34)-(14)-(13)-(23)-(21)-(31)(33)-(34)-(14)-(13)-(33)121-110122020/5/1826B1B2B3B4产量A17A24A39销量365600000121-112100当检验数还存在负数时，说明原方案不是最优解，要继续改进。闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。运输问题的约束条件共有m+n个，其中：m是产地产量的限制；n是销地销量的限制。其对偶问题也应有m+n个变量，据此：σij=cij－(ui+vj),其中前m个计为ui（i=1.2…m）,前n个计为vj（j=1.2…n）由单纯形法可知，基变量的σij＝0∴cij－(ui+vj)＝0因此ui,vj可以求出。⑵.位势法2020/5/1828仍以上面的例子说明。第一步：按最小元素法给出表的初始解，然后做下表：即在对应表的数字格处填入单位运价：销地加工厂B1B2B3B4A1A2A314321052020/5/1829第二步：在上表中增加一行一列，在列中填入ui，在行中填入vj，得下表：销地加工厂B1B2B3B4uiA1A2A314321050-1-5vj29310先令u1=0，然后按ui+vj=cij，i，j∈B相继地确定ui，vj。由上表可见，当u1=0时，由u1+v3=3可得v3=3，由u1+v4=10可得v4=10；在v4=10时，由u3+v4=5可得u3=-5，以此类推可确定所有的ui，vj的数值。2020/5/1830第三步：按σij=cij-(ui+vj),i,j∈N计算所有空格的检验数。如σ11=c11-(u1+v1)=3-(0+2)=1，σ12=c12-(u1+v2)=11-(0+9)=2这些计算可直接在上表中进行。为了方便，特设计计算表，如下表所示销地加工厂B1B2B3B4uiA131=3-(0+2)112=11-(0+9)30=3-(0+3)100=10-(0+10)0A210=1-(-1+2)91=9-(-1+9)20=2-(-1+3)8-1=8-(-1+10)-1A3710=7-(-5+2)40=4-(-5+9)1012=10-(-5+3)50=5-(-5+10)-5vj29310在此表中还有负检验数，说明未得最优解，还可以改进。2020/5/1831亦即：B1B2B3B4A1310u1A212u2A345u3v1v2v3v4成本表B1B2B3B4A1293100A21829－1A3－34－25－529310u2+v1=1u2+v3=2u3+v2=4u1+v4=10u1+v3=3u3+v4=5令：u1＝0u1＝0v1＝2u2＝－1v2＝9u3＝－5v3＝3v4＝10(ui+vj)2020/5/1832按σij=ci