运筹学-第四章-运输问题

运输问题运输问题及其数学模型运输问题的表上作业法运输问题的进一步讨论例1：某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的生产量、各销售点的销售量（假定单位均为t）以及各工厂到各销售点的单位运价（元/t）示于下表中要求研究产品如何调运才能使总运费最小4.1运输问题及其数学模型单位销地运价产地产量2910291342584257销量38464321BBBB321AAAA2A3B2A1B3B4B1s2=5s3=7d1=3d2=8d3=4d4=6s1=9供应量供应地运价需求量需求地2910213428425运输问题网络图)4.3.2.1,3.2.1(06483759524824371092min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij约束条件：目标函数：为运量设产量约束销量约束运输问题的一般提法是：设某种物资有个产地m,1A,2A,,mA各产地的产量是;,,,21maaa有个销地,1B,2B,,nBn各销地的销量是.,,,21nbbb假定从产地),,2,1(miAi到销地),,2,1(njBj运输单位物品的运价是，问ijc怎样调运这些物品才能使总运费最小？销地产地产量销量1A2AmA1B2BnB11c12cnc111x12xnx121c22cnc221x22xnx21mc2mcmnc1mx2mxmnx1b2bnb1a2ama运价表)(0min11ijjijijiijminjijijxbabxaxxcZ当产销平衡时，其模型如下：0,0,0ijijabc假设：当产大于销时，其模型是：)(0min11ijjijijiijminjijijxbabxaxxcZ当产小于销时，其模型是：min()0ijijijiijjijijZcxxaxbabx1、平衡运输问题必有可行解，也必有最优解；运输问题数学模型的特点证明记.11dbaminjji则令dbaxjiij),,2,1;,,2,1(njmi则为运输问题的一个可行解。事实上：ijxnjijinjnjjiijabdadbax111),,2,1(mimijijmimijiijbadbdbax111),,2,1(nj又因.0,0jiba所以.0ijx故是一组可行解。[]ijx又因为总费用不会为负值（存在下界）。这说明，运输问题既有可行解，又必然有下界存在，因此一定有最优解存在。2、运输问题约束条件的系数矩阵运输问题数学模型的特点对运输问题数学模型的结构约束加以整理，可知其系数矩阵具有下述形式：111111111111111111m行n行1．运输问题是一个具有m×n个变量和n+m个等型约束的线性规划问题。（4－1）mnmmnnxxxxxxxxx,,,,,,,,,;,,,212222111211jmiijeep),,2,1;,,2,1(njmi()1()1()1000110000101000ijimjmnmnmnpee2．运输问题约束方程组的系数矩阵是一个只有0和1两个数值的稀疏矩阵,其中1的总数为2×m×n个。3、约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次4、约束条件系数矩阵的秩是m+n-1。即运输问题的基变量总数是m+n-1证明：因A的前m行对应元素的和与后n行对应元素的和相等，恰好都是：nmE)1,,1,1(1所以A的行向量是线性相关的。从而r(A)≤m+n.去掉A的第一行，并取如下m+n-1列，得到m+n-1阶子式1112121311||00010000001000000110100111010000001000nmDpppppp所以r(A)=m+n-1.对于产销平衡运输问题，除了上述特点外，还有以下特点：1所有结构约束条件都是等式约束2各产地产量之和等于各销地销量之和3、运输问题的解运输问题数学模型的特点运输问题是一种线性规划问题。前面讲述的单纯形法是求解线性规划问题十分有效的一般方法，因而可用单纯形法求解运输问题。但是当用单纯形法求解运输问题时，先得在每个约束条件中引入一个人工变量，这样一来，即使对于m=3、n=4这样简单的运输问题，变量数目也会达到19个之多。因此，我们利用运输问题数学模型的特点，引入了表上作业法来求解运输问题4.2用表上作业法求解运输问题表上作业法的基本思想：先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如下图所示。初始化最优性检验迭代（Iteration）最优？yesSTOPno这和单纯形法的求解思想完全一致，但是具体的作法则更加简捷。例1某部门有3个同类型的工厂（产地），生产的产品由4个销售点出售，各工厂的生产量、各销售点的销售量（假定单位为t）以及各工厂到销售点的单位运价（元/t）示于表4-2中，问如何调运才能使总运费最小？销地产地产量4124111621039108511622销量8141214481A2A1B2B3B4B3A表4-211x12x13x14x21x22x23x24x31x32x33x34x34333231242322213141141312116115893102114124minxxxxxxxxxxxxxczijijij4,3,2,1;3,2,1,01412148221016342414332313322212312111343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxij该运输问题的数学模型为：可以证明：约束矩阵的秩r(A)=m+n-1.基变量的个数为m+n-1.表上作业法计算步骤：1、给出初始方案2、检验是否最优3、调整调运方案,Goto2表上作业法计算步骤：1、给出初始方案2、检验是否最优3、调整调运方案,Goto2下面介绍三种常用的方法。一、给出运输问题的初始可行解（初始调运方案）最小元素法西北角法沃格尔(Vogel)法1。最小元素法思想：优先满足运价（或运距）最小的供销业务。销地产地产量4124111610398511622销量141214481A2A1B2B3B4B3A表3-2①228810销地产地产量412411162109108511622销量81414481A2A1B2B3B4B3A表3-2①3②210128销地产地产量412112109108511622销量8141214481A2A1B2B3B4B3A表3-2①3②210416106③8销地产地产量4121182109108116销量81214481A2A1B2B3B4B3A表3-2①3②210416106③5142214④8销地产地产量412118210910811销量812481A2A1B2B3B4B3A表3-2①3210416106③5142214④86146⑤②销地产地产量4128210910811销量812481A2A1B2B3B4B3A表3-2①3210416106③5142214④86146⑤11⑥⑥②此时得到一个初始调运方案（初始可行解）：,1013x,614x,821x,223x,1432x,834x其余变量全等于零。总运费为（目标函数值）3141ijijijxcz246685143228116410此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6).⒉西北角法西北角法是优先满足运输表中西北角（左上角）上空格的供销需求。销地产地产量41241121039108511622销量141214481A2A1B2B3B4B3A表3-281611x销地产地产量41241121039108511622销量141214481A2A1B2B3B4B3A表3-2816①88销地产地产量41241121039108511622销量1214481A2A1B2B3B4B3A表3-2816①8812x14销地产地产量41241121039108511622销量141214481A2A1B2B3B4B3A表3-2816①88②6销地产地产量412411210398511622销量141214481A2A1B2B3B4B3A表3-2816①88②622x10销地产地产量412411210398511622销量141214481A2A1B2B3B4B3A表3-2816①88②6106③4销地产地产量412411210398511622销量1414481A2A1B2B3B4B3A表3-2816①88②6106③423x12销地产地产量412411210398511622销量141214481A2A1B2B3B4B3A表3-2816①88②6106③4④8销地产地产量4124112103985116销量141214481A2A1B2B3B4B3A表3-2816①886106③4②④32x822销地产地产量4124112103985116销量141214481A2A1B2B3B4B3A表3-2816①886106③4②④8228⑤14销地产地产量4124112103985116销量1412481A2A1B2B3B4B3A表3-2816①886106③4②④8228⑤1434x14销地产地产量4124112103985116销量141214481A2A1B2B3B4B3A表3-2816①886106③4②④8228⑤14⑥⑥此时得到一个初始调运方案（初始可行解）：,811x,812x,622x,423x,833x,1434x其余变量全等于零。总运费为（目标函数值）3141ijijijxcz3726141183410612848此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6).⒊沃格尔（Vogel)法初看起来，最小元素法十分合理。但是，有时按某一最小单位运价安排物品调运时，却可能导致不得不采用运费很高的其他供销点，从而使整个运输费用增加。沃格尔法的思想：对每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地或销售地的罚数。若罚数的值不大，当不能按最小运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大的损失，故应尽量按最大罚数安排运输。销地产地产量行罚数1234124111602103910181161销量8121448列罚数12513231A2A1B2B3B4B3A51422148销地产地产量行罚数123412411160021039101185112212销量8141248列罚数12513221331A2A1B2B3B4B3A8146146销地产地产量行罚数12341241116000103911185112212销量141248列罚数12513221