1、1（20_届）本科毕业设计信息与计算科学运输问题及其解法2摘要本文从一般运输问题的最基本解法讲起，对于现在所遇到的运输问题给出相应的解法和他们之间的优越性比较。主要涉及到的解法有表上作业法，结合最短路径求解运输问题，以及LINGO软件的实现。另外,给出了几类特殊的运输问题,并举了例子进行了说明。关键字运输问题,表上作业法,最短路径法TRANSPORTATIONPROBLEMANDITSSOLUTIONABSTRACTTHISARTICLESTARTEDFROMTHEMOSTBASICMETHEDABOUTSOLUINGSOLUATINSOFTHEGENERALTRANSPORTATIONPRO
2、BLEM，PROVIDETHEBETWEENMETHEDOFTHETRANSPORTATIONPROBLEMENCOUNTEREDPRESENTANDCOMPAREDTHESUPERIORITYITMAINLYINVOLVESSOLUTIONSHAVETABULARMETHOD，THEMETHEDSOLVINGTRANSPORTATIONPROBLEMCOMBINEDWITHTHESHORTESTPATH，ANDTHEREALIZATIONOFTHELINGOSOFTWARE。BESIDES，WEARESEVERALSPECIALKINDSOFTRANSPORTATIONPROBLEM，AND
3、TOOKEXAMPLESILLUSTRATINGKEYTRANSPORTATIONPROBLEM，TABULARMETHOD,SHORTESTPATHMETHOD31引言从古至今运输问题一直都是人们急需解决的社会生活问题，随着我国国民经济的不断发展，企业之间的交易活动更加频繁、同地区、不同地区、甚至跨国的交易活动也不断发生，交通运输则成为交易的活动重点了。交通运输作为国民经济的一个重要部门，作为人类进步、社会发展的一个重要推动力，其发展模式正在对环境产生越来越重要的影响。传统的运输方式已经不能满足环境保护、经济发展以及交通运输本身发展的需求，探寻与环境、资源条件相适应的运输是非常重要的一个问题
4、。人们在交通运输方面趋利避害建立更好的运输方法，让交通运输的方法达到一个更高的水平。对于运输问题的研究也就有了更进一步的发展，下面就运输问题及其解法进行一些相关的讨论。2运输问题及几种常用解法21运输问题的形成1运输问题是特殊的线性规划问题,它是早期的线性网络最优化的一个例子。最早研究这类问题的是美国学者希奇柯克HITCHCOCK,1941年他在研究生产组织和铁路运输方面的线性规划问题时提出运输问题的基本模型后来柯普曼KOOPMANS在1947年独立地提出运输问题并详细地对此问题加以讨论从上世纪40年代早期开始,康脱洛维奇KANTOROVICH围绕着运输问题作了大量的研究,因此运输问题又称为希
5、奇柯克问题或康脱洛维奇问题。现在人们对于运输问题有了进一步的了解，也在现在大学的运筹学的课程中有一章专门涉及到运输问题的解法，在这当中是这样定义运输问题的，所谓的运输问题是指从若干个产地往若干个销地运输某种物资,根据各产地的产量、各销地的销量和现有的交通网络,如何安排运输使总运费最少的问题。现在社会的发展，特别是物流行业的发展使得人们对运输问题的研究就越来越在意了，研究的内容也就更加的丰富。22产销平衡运输问题的基本解法所谓的运输问题是指即已知有M个地点可以供应物资（即产地I1，2，,M）,以及N个地点需要这种物资（即销地J1,2,N）,M个产地可供应的物资量（即产量）分别为AII1,2,M,
6、N个销地的需要量（即销量）分别为BJJ1,2,N,用CIJ表示从第I个产地到第J个销地的单位物资运价，用XIJ表示第I个产地调运给第J个销地的物资的数量。则运输问题就是MINZIJNJIJMIXC11ST,2,1,1MIAXNJIIJ（1）,2,1,1NJBXMIJIJ4NJMIXIJ,2,1,2,10下面就一个例子对运输问题的解法做出相应的介绍和总结例某公司经销一种产品，他下设三个工厂和四个销售部门，三个工厂的日生产量为1A7吨，2A4吨，3A9吨，各部门的日销量为1B3吨，2B6吨，3B5吨，4B6吨，各厂到各个销售部门的单位运价表如下表，问该公司如何调运才能完成任务并使得运费最小表1产地
7、销地1B2B3B4B1A3113102A19283A74105第一种方法表上作业法2第一步给出初始调运方案（最小元素法）表2产地销地1B2B3B4B产量1A4372A3143A639销量3656注意如果出现退化时，要在同时被划去的行和列的任意空格的位置添上一个0；第二步检验初始方案（位势法）在表中的下面和右边添加一行和一列JV和IU，使得表中的每一个树都可以用这两个数的和来表示，假设用IJA来表示表中的数，则使得JIIJVUA。再求出空格处的检验数JIIJIJVUC，如下图所示表3产地销地1B2B3B4BUI1A2391143310152A3189129803A3764210354VJ1829
8、第三步调整闭回路法从检验数为负数且最小的检验数开始和其他没有括号括起来的数字组成闭回路，该闭回路一定唯一，沿着该闭回路进行调整，使得其中一个变成0，在进行检验如途中被选中的区域就够成了唯一的闭回路。调整从检验数为负数的位置开始以和错开的方式加或减其余三个数字中最小的一个，则变成下图的调运方案表4产地销地1B2B3B4B产量1A5272A3143A639销量3656再进行检验得表5产地销地1B2B3B4BUI1A339115321022A3179121803A2764210353VJ1718此时所有的检验数都大于0，则得到了最优运输方案，即1A3B5吨61A4B4吨，2A1B3吨，2A4B1吨，
9、3A2B6吨，3A4B3吨。最小运费为220元。小结表上作业法的实质就是单纯型法，只是将单纯型法的迭代方式进行了一定的简化，以表格的形式代替单纯型法中的高数迭代过程。第二种方法最短路径3对于传统的运输问题，只是考虑了运费上达到最低，但是在现在的运输问题中交通网络也是要考虑的问题之一，如果在上面的问题上加上一个交通网络问题，则此时的运输方案将需要考虑所走的路径问题。此时的运输问题需要结合最短路径来进行解决。例如在上面的例题的基础上，但是到达这三个城市的有许多种路径，单位运费调整（元/吨/公里），为如下图所示注上图中线段上的数字表示两地之间的路径长短可以根据DIJKSTRA算法求出最短路径从A1，
10、A2，A3分别到B1，B2，B3，B4的最短路径A1B1A1C1B1路径长为19；A1B2A1C1B2路径长为26；A1B3A1C1D2B3路径长为32；A1B4A1C1D2B4路径长为24；A2B1A2C1B1路径长为17；A2B2A2C1D2B2路径长为24；A2B3A2C1D1B3路径长为26；A2B4A2C1D2B4路径长为22；A3B1A3C2D1B1路径长为31；A3B2A3C2D2B2路径长为33；7A3B3A3C2D1B3路径长为27；A3B4A3C3B4路径长为21；当销地确定时,各产地到销地的最短路径为A2B1173吨,A2B2241吨,A1B2265吨,A3B3275吨,
11、A1B4242吨,A3B4214吨。此时的运费为Z3394721452410227105265112419171元。23运输问题的基本解法之间的优越性比较用表上作业法解决运输问题算法，是传统运输问题的解法，也是运输问题的最基本解法，这种方法是基于线性规划发展而来的，主要用来解决在运输路径一定的情况下确定如何调运，此时考虑的是如何使生产满足所需，只是考虑从产地A1，A2，A3这三个产地中以最佳的方式分配来满足销地的所需就可以了。这种算法的优点在于那些产地和销地确定了运输路线，只需要确定分配运输的数量问题。但是，随着现代物流业发展以及交通网络的发展，运输问题中要考虑的问题也越来越多，其中尤为突出的
12、就是运输线路的确定的问题，这种问题是现在运输问题中重点考虑的一类，而最短路径的解法比较适合这种运输问题的求解。3几种特殊的运输问题31多目标决策运输问题多目标决策运输问题的模型】【4,2,1,2,10,2,1,2,1,MIN1111121111NJMIXNJBXMIAXSTCCXCZIJMIJIJNJIIJTNJKIJMINJIJMIIJIJMJMI（2）0IA表示第I个产地的产量，0JB表示第J个销地的销量，0IJCK表示第K个目标函数的费用系数，XIJM1IN1JKIJC可以表示总运费、总能耗、总运输时间、运输对环境所造成的破坏等。下面介绍一下此类问题的算法1用最小元素法或伏格法等找出1X
13、F的一个初始基可行解或直接求出1XF的最优解,并把基变量的取值写在产销平衡表相应格点I,J中。82计算当前基可行解的位势向量,并分别附加在产销平衡表的右端和下端3用位势法求出每一个目标函数的非基变量的检验数IJK，写在产销平衡表相应格点非基变量所对应的格点中CKIJ（K1,2,NM）的右边，4令K1,检查所有检验数向量的第K个分量5如果存在某个CKJI0,1IM,1JN,且SIJS1,2,K1,则继续下一步否则,转76从格点I,J）（XJI对应的格点），开始找一条闭回路,进行优化调整,得到一个新的基可行解重新计算位势向量、检验数向量,转57如果KL,则已经得到有效解,停止计算否则令KK1,转5
14、。广义运输问题有着广泛的实用背景,因此很多学者在此领域进行研究，以期找到问题较好的解决方法，以上两种运输问题都是现实中经常遇到的运输问题，本文提供了这两种运输问题的一般解法，能很好的解决绝大部分问题。32松约束运输问题】【5松约束运输问题的定义如下假设某种材料有M个原材料产地AII1,2,3M可以提供，它们的生产能力分别为AI，I1，2，3，,M有N个目的地BJ，J1,2,N需要这种材料,每个目的地的需求量分别为BJ，CIJ是从AI到BJ的运输费用（参见表6）。该问题是要求出怎样的运输方案能使总运输费用最少表6运输问题销地1B2BNB产量1A11C12CNC11A产地2A21C22CNC22A
15、1MA1MC2MCMNCMA需求1B2BNB基本解题思路第一步给一组从小到大的初始的运输方案，表示为X0IJ，总费用为Z0。9第二步从X0IJ中从大到小依次减少运输成本，得到运输成本最小的解XIJ其运输费用为Z。第三步对XIJ进行测试和调整得到最优解。例（受时间约束的运输问题）有4个地区（1234BBBB，急需某种油料，现从油库1234,AAAA调运，各地区需要的油量，各油库所能提供的油量，以及从各油库到各地区所需的费用（运价单位千元吨）如表7所示，从各油库到各地区的时间如表8所示。表7单位运价表1B2B3B4B供应量T1A311310302A1928353A74105304A3271020需
16、求量T30402025表8运输时间表TH1B2B3B4B1A102832A103943A6151344A2013911问如何运输才能保证在40H以内将油量以尽可能小的费用送到各地区解首先算出其调运时间表，如表9所示，按照传统运输问题的表上作业法所得的最优解如表10所示（运量单位吨）。所算的最少费用为40万元。但此方案所需的时间为213245TTH，不满足时间约束条件，需用最小损失闭回路法进行调整。表9调运时间表TH1B2B3B4B1A403238332A45384439103A364543344A40432931表10运输问题的表上作业法的调运量1B2B3B4B供应量TTH1A10203040
17、2A201535453A201030454A202033需求量T30402025先按照下标的顺序选取第一个大于40H的21X项，对它进行调整。与其不在同一行，不在同一列的基变量有13323442,XXXX。对于基变量13X，由于234440T，因而不满足要求。对于基变量32,X算得22312132971412CCCC对于基变量34,X算得2431213487159XCCC对于基变量42,X算得2241214293129CCC古可选基变量42,X对基变量21X进行调整，此时4221MIN,20XX，调整的结果茹表11所示（运量单位吨）表11经一次调整后的调运量1B2B3B4B供应量TTH1A10
18、2030402A201535393A201030454A202040需求量T30402025运费增加18万元。此时的方案所需的时间仍为3245,TH不满足约束条件，继续进行调整。与其不在同一行，不在同一列的基变量有11132441,XXXX和。对于基变量，算得123111321173411CCCC11对于基变量13X，由于334340T，因而不满足要求。对于基变量24,X算得2234322495482CCCC对于基变量41,X算得3142324192432CCCC故可选基变量41,X对基变量32X进行调整，此时4132MIN,20XX，调整的结果如表12所示（运量单位吨）表12经二次调整后的调
19、运量1B2B3B4B供应量TTH1A102030402A201535393A201030364A202033需求量T30402025运费增加4万元。此时方案所需的时间是1140,TH满足时间约束。从而表12所示的方案可在40小时内将油量运到各地区，此时的费用最小为62万元。需要指出如果调整的顺序不同，所得的最优解不同，即最优解不唯一，但算得的最小费用一样。上例说明了（1）运输问题存在不能用线性问题解决是正常的。（2）宽松的约束性模型在解决此类问题上是最好的模型。（3）这种算法很容易计算，学习和更快的速度收敛。最后，对比其他的解法，宽松的约束性模型能更好的解决此类问题。33运输费用不确定的运输问
20、题在传统的运输问题中,总假设从产地到销地的单位物资运价是确定的,但是在特殊情况下,如在发生自然灾害的情况下运输救灾物资、在战时运输军需物资等,因现有的交通网络可能遭到破坏战争时期,即使交通网络没有遭到破坏,运输车辆通过各路段的费用所付出的代价还与各路段受敌人火力控制的程度以及遭敌袭击的可能性有关,所以单位物资运价不再是确定的,而只能根据实际情况12估计出一个大概的范围，即是一个理灰数】【6。这就是运费不确定运输问题产生的历史条件。他的数学模型】【97可表示为一般地,设在M个产地某物资的储备量分别A1,A2,AM,N个销地对该物资的需求量分别为B1,B2,BN,从第I个产地到第J个销地的单位物资
21、运价或里程等为有理灰数,则上述问题可归结为如下数学模型。MINFMI1NJ1IJXIJ。STNJ1XIJIAI1,2,M（3）MI1XIJJBJ1,2,NXIJ0I1,2,MJ1,2,N。这里IJJIBA,0,0表示理灰数，I1,2,MJ1,2,N。一般理灰数都是不确定的实数,所以有时不能追求达到数学上的最优,但我们可以给出几种决策准则,根据这些准则可以求出灰优值的白化值987和相应的拟优解（1）动态型准则若在灰色运输问题中,有理灰数IJ是按时间列给出的,比如,2,1NTTTIJIJIJIJ可用灰色预测的方法10求出预测值1NTIJ作为有理灰数IJ的白化值,也可以用平均值KTTNKIJNIJ1
22、作为有理灰数IJ的白化值,然后求出最优解作为灰色运输问题的运输方案,即拟优解。动态型准则的基本思想是遵循事物的发展变化规律，以科学预测为依据，尽量使运输方案优化。所以一般认为用动态型准则求出的拟优值是比较符合实际情况的，而相应的拟优解则是比较理想的近优运输方案。由此可见，灰色运输问题不仅适用于静态的，还适用于发展变化中的运输问题。如果在发生自然灾害以前便可根据有关预报资料及早规划救灾物资的筹集，调运等等，以把自然灾害的损失13减少到最低限度。战争时期，在部署作战方案的同时，便可安排军需物资的供应问题，这对于整个战阵的成败也是至关重要的。（2）乐观型准则用下限运输问题BGTP的最优解作为灰色运输
23、问题的运输方案，即拟优解。这种准则的基本思想是对客观事物总是持乐观的态度。其主要特点是充分挖掘现有的运力资源（运输吨公里数或运输能力），使其得到极大度的利用，不留余地，所以有一定的冒险性。在运输能力有限的前提下可以考虑使用，但用于战地运输时一定要慎重起见。此外，如果用乐观型准则求出的拟优值比现有的运输能力（吨公理数）还要大，则说明即使是竭尽全力，运输能力也不能满足需要。在这种情况下，应及时向有关部门反应情况，请求支援。3悲观型准则用上限运输问题BGTP的最优解作为灰色运输问题的运输方案，即拟优解。这种准则的基本思想是对客观情况总是持悲观的态度。其最大特点是稳妥行事，运输物资按计划到位率高。但对
24、资源（运输能力）的利用率不高。在运输能力充裕的条件下可以考虑使用。（4）乐观系数型准则在灰色运输问题中，用,10TABTATIJIJIJIJ作为有理灰数IJ的白化值，然后求出最优解作为灰色运输问题的运输方案，即拟优解。乐观系数型准则的主要特点是对客观情况的估计既不那么乐观也不那么悲观，而用一个系数T（称为乐观系数）来平衡一下。特别，当1,0,21TTT和时，分别称为折中型系数，冒险型系数和保守型系数。用这种方法确定有理灰数IJ的白化值，可信度可以定义为122TT005051TT如此定义可信度的理由见参考文献10。（5）加权型准则在灰色运输问题中，用IJIJIJIJIJABAT,10IJ作为有理
25、灰数IJ的白化值,然后求出最优解作为灰色运输问题的运输方案,即拟优解这里IJ称为加权系数,它根据各消费地区对物资需求的急缓程度或决策者对消费地区的重视程度而定加权系数型准则的要求特点是能突出主次,照顾重点用于战地运输时能根据首长的意图,保障重点供应（6）经验型准则14若在灰色运输问题中,自然灾害或战争对于交通网络的破坏程度一时还无法知道,则可用三值估计法或二值估计法确定IJ的白化值。三值估计法由决策者，专家及有关人员对IJ的白化值作为三种估计最可能的估计IJ，最乐观的估计IJ和最悲观的估计IJ，然后用三者的加权平均值6/4IJIJIJIJT作为有理灰数IJ的白化值。二值估计法如果一时还难以作出
26、最可能的估计，则可用最乐观的估计IJ和最悲观的估计IJ的加权平均值,5/23IJIJIJT作为有理灰数IJ的白化值。然后求出最优解作为灰色运输问题的运输方案，即拟优解10。中国的交通状况不容乐观,有些地区道路拥挤,运输能力有限。中国又是一个高速发展中的国家,“时间就是金钱”。所以在今天的中国,单位物资的运价不只与里程有关,有时还与时间有关,而因交通堵塞所耽误的时间是无法确知的。可见灰色运输问题（即运费不确定的运输问题）颇具普遍性。此种运输问题的算法有待统一。以上三种运输问题是现实中常见的运输问题，但是由于里面的可变因素太多，所以统一的算法还没有形成，在现实中人们只是用一般的算法和一些估算来解决
27、此类问题。4LINGO软件对运输问题的实现随着社会经济的发展,运输业在经济生活中的地位越来越重要,国内国际的物流、人流最终都离不开具体的运输环节。在社会产品的最终成本中,运输成本约占1030,所以,开展合理运输,节约运输成本,对于降低社会产品的总成本起着重要作用。因此,运输企业需要在众多运输方案中选择总运费最小的。这样的问题,在物流运筹学中称为运输问题。在求解运输问题方面,我们通常介绍的是表上作业法。这是一种手工做法。当输出地个数M,和输入地个数N比较大时,这种手工的表上作业法就显得很繁琐了,这时我们要处理的是至少M1行N1列的表格。因此,我们考虑用计算机来处理这个问题。可以用来求解运输问题的
28、软件常见的有,LINGO、MATLAB、OFFICE中的EXCEL等。他们各有特色,下面就通过一个实例来介绍LINGO软件在运输问题中的应用。为了说明如何使用LINGO软件来实现运输问题的求解，本文就以下面的例题的求解过程来加以说明15例某公司经销一种商品,它下设654321,AAAAAA六个工厂和87654321,BBBBBBBB八个销售部门,各厂的生产能力、各销售部门的需求量及各厂到各个销售部门的单位运价表如下表13，问公司该如何调运才能完成任务并使运费最小表13销地产地1B2B3B4B5B6B7B8B产量1A62674259602A49538582553A52197433514A7673
29、9271435A23957265416A5522814352销量3537223241324338模型的建立假设从产地IA到销地JB的运量为IJX，用Z表示运费,1,2,6IIA表示六个产地的产量，1,2,8JJB表示上表8个销地的销量，则有MINZ6811IJIJIJCXST8161,1,2,6,1,2,80,1,2,61,2,8IJIJIJJIIJIJIJXAXBX由LINGO软件求解可得最优调运方案具体见表14,相应的最小运费为66400016表141B2B3B4B5B6B7B8B1A19412A1323A11404A5385A3476A22273MODELSETSSUPPLY/16/PR
30、ODUCEDEMAND/18/SELLLINKSUPPLY,DEMANDCOST,XENDSETSDATAPRODUCE605551434152SELL3537223241324338COST626742594953858252197433767392712395726555228143ENDDATAMINSUMLINKXCOSTFORSUPPLYISUMDEMANDJXI,JPRODUCEIFORDEMANDJSUMSUPPLYIXI,JSELLJEND5结论17本文对运输问题进行了初步的分析和求解，在运输问题中，本文只考虑了供需平衡的情况，在供需不平衡或运输有优先级的情况下虽然比较复杂，但
31、其模型也可以以此供需平衡模型为基础，稍加改造即可实现。随着现在社会经济技术的不断发展，特别是处在加速发展状态下的中国，运输问题已经得到了人们的足够的重视，随着交通网的不断发展，运输问题以前的一些解法将会迎来新的挑战，本文只是对现阶段的运输问题及其解法做了一定的小结，现实中的运输问题要考虑的条件还很多，特别是现在物流的发展，运输问题的解法就会更加复杂。总之，对于运输问题，利用基本解法加上现实约束是最好的解决方法。参考文献1胡运权等运筹学基础及其应用（第五版）M北京高等教育出版社,20072刘晓岚表上作业法求解运输问题的思考N山东省农业管理干部学院学报,2009,2361551563田珏，桂岚，李
32、增光一种结合最短路径的运输问题求解方法J长沙理工大学,2008,125257584白国仲求解多目标运输问题的表上作业法N信阳师范学院学报,20071044035LUHOUQING,JIANGGUOLIANGWANGNINGSHENGANEWMODELANDSOLUTIONFORTRANSPOREATIONPROBLEMJNANJINGPUBLICSECURITYCOLLEGE,NANJING210005,PRCHINA,20006白国仲求解多目标运输问题的表上作业法N信阳师范学院学报,20071044057邓聚龙灰色系统社会经济M北京国防工业出版社,19858邓聚龙灰理论基础M武汉华中科技大学出版社,20029王清印灰色系统理论的数学方法及其应用M重庆西南交通大学出版业,199010华罗庚统筹方法平话及补充M北京中国工业出版社,196511徐国松LINGO软件在运输问题中的应用N江苏省连云港工贸高等职业技术学,2008,36172
