1、1毕业论文开题报告数学与应用数学运输问题相关研究与应用一、选题的背景与意义在经济建设中，经常碰到大宗物资调运问题。如煤、钢铁、木材、粮食等物资，在全国有若干生产基地，根据已有的交通网，应如何制订调用方案，将这些物资运到各消费地点，而总运费要最小，这就是运输问题所要研究的。近两年，物流已成为当今中国经济最热门名词之一。运输是物流的一个核心流程，物流成本的降低关系到整个物流环节运营的优劣。运输活动不创造实物产品，而是提供运输劳务，使物资发生位移。在现代社会，随着制造业、服务业的发展和人的生活水平的提高，就有了资源、制造产地和市场这三者的区位关系，而且运输成本在经济发展中的作用日益突出。降低运输成本
2、，能对整个供应链产生较大的影响。现有的关于运输问题的研究主要是在探讨在某种条件限制下的运输问题模型及算法，或者是对其算法进行改进或完善。这些研究虽然分类明确，但是缺乏系统性。所以对各类运输问题及算法进行总结显得尤为必要，这样不仅可以使彼此间的关系更为密切，分类更为具体，而且对于运输问题的应用也会显得更为合理。在解决实际工作的具体问题时能更有效的建立较为合适的数序模型，选取最佳的求解方法。二、研究的基本内容与拟解决的主要问题运输问题在实际工作中的应用拟解决的主要问题1、归纳运输问题的相关算法2、利用运输问题的数学模型求解实际工作中的具体问题三、研究的方法与技术路线查阅相关资料，找出运输问题的相关
3、算法和运输问题在实际工作中运用的实例。在指导老师的指导下完成论文。四、研究的总体安排与进度2010112020101210查阅相关资料，并做些准备工作。201012112010121612月17日前完成文献综述、文献翻译和开题报告，并上传2至毕业论文系统中。201012172010122312月24日前完成开题论证。20101224201104034月4号前完成毕业设计（论文）初稿，交指导老师审批、修改。20110405201104284月29日前毕业论文定稿、修改、打印。2011042920110503完成答辩PPT。五、参考文献1臧运华运输问题的一种图上解法D运筹与管理,2002,42张家
4、善LINGO软件求解运输问题与表上作业法的比较J湛江师范学院学报,2010,6,33戴建平基于MATLAB的运输问题求解方法J宁波职业技术学院学报,2009,24张国玉,夏文汇运用MATLAB软件求解物流运输问题J物流技术,2010,4,2145谢凡荣求解运输问题的一个算法D运筹与管理,2002,11,36司南,任佳莉运输问题的一种计算机算法D计算机应用与软件,2004,77卢厚清,张永良,王宁生求解运输问题的一种算法D运筹与管理,1999,3,8,18蒋宏锋运输问题的逐块选优解法D科学技术与工程,2006,4,6,89刘徽,黄宽娜运输问题求解的一种内点算法J乐山师范学院学报,2009,510
5、袁勋,严从荃,刘徽运输问题求解的一种网络算法D运筹与管理,2005,2,14,111何莉敏,石琳,侯玉双,李德荣,田红晓,刘丽钢管定购与运输问题的数学模型与求解的新方法J,内蒙古大学学报,2010,212蒋翔,罗蔓,张丽君工商管理常见运输问题的运筹学解法D商场现代化,2007,10,51913云俊运输问题优化方法的综合应用J武汉理工大学学报,2001,9,25,314夏少刚,张建华求解运输问题的一种新算法D运筹与管理,2007,2,16,115苏若葵运输问题的简化解法D商场现代化,2009,1,56316单海英运输问题的推广及算法研究的重要意义D中国教育技术装备,2010,4,L2,19817
6、王有鸿,费威运输问题国内外研究评述J中文核心期刊要目总览,贸易经济类核心期刊商业时代（原名商业经济研究）,2010,2418教材编写组编著运筹学M北京清华大学出版社，2008319XINFENGYANG，YINZHENLI，RUICHUNHE，LINZHONGLIUMODELANDALGORITHMOFTRANSPORTATIONPROBLEMONNETWORKDJOURNALOFSYSTEMSSCIENCEANDINFORMATION,2008，VO16，NO4，PP32533220CHENHAIFENG，CHOJOONGRAE，LEEJEONGTAEJCHONGQINGUNIVENGEDS
7、OLVINGHITCHCOCKSTRANSPORTATIONPROBLEMBYAGENETICALGORITHMMDECEMBER2004VOL3NO24毕业论文文献综述数学与应用数学运输问题相关研究与应用运输问题是社会经济生活和军事活动中经常出现的优化问题。在经济建设和国防建设中，经常遇到煤、钢铁、木材、粮食、武器装备等物资的调运问题。如何制定调运方案，将物资运往指定地点，而且实现运输成本最小，即为运输问题。运输问题是特殊的线性规划问题，它是早期的线性网络最优化的一个例子。与一般线性规划问题不同，它的约束方程组的系数矩阵具有特殊的结构，这就需要采用不同的甚至更为简便的求解方法来解决这种在实际
8、工作中经常遇到的问题。运输问题不仅代表了物资合理调运、车辆合理调度等问题，有些其他类型的问题经过适当变换后也可以归结为运输问题。从算法角度考虑，目前对于运输问题的求解提出了很多可行的解法，如表上作业法、图上求解法以及应用计算机实现的启发式多种算法等。表上作业法是解决一般运输问题最常用的解法，因其求解工作均在运输表上进行而得名。它是一种迭代算法，迭代步骤为先按某种规则找出一个初始解；再对现行解作最优性判别；若该解不是最优解，就在运输表上对它进行调整改进，从而得出一个新解，再重复判别改进的过程，直至得到运输问题的最优解为止。表上作业法一方面是在求解过程中首先要找出初始基可行解，需要一定计算工作量，
9、即需要经过（MN1）次加减运算给出初始方案。另一方面是在初始基可行解基础上，还要用繁琐的闭回路法或位势法计算所有空格（非基变量）的检验数，再判别是否达到最优解。如果没有得出最优解，还需要在表上用闭回路法进行调整，确定换入变量和换出变量，找出新的基可行解，再进行检验等步骤，直到求出最优解为止。由于当产地M、销地N较大时表上作业法的操作显得尤为繁琐。文献1提出了运输问题的一种新解法，该方法通过构造赋权二部图，应用图论的相关理论，给出求解运输问题的另一种图上解法。其一般步骤为第一步把运输问题转化为赋权完全二部图G。第二步用最小权元素法，求初始基可行解，即求G的一个生成树TX。第三步取TX的权最大边E
10、，若两个以上取其中之一。第四步TXE为两棵树TL和T2，若TL的产地与T2的销地之间无权小于E的边可添加，转第六步。否则，添加权小于叫WE的边构成一个闭回路，验证总运费是否减少若总运费5不减少，转第六步，否则，用图上闭回路调节法，得到新的生成树TX1，且其总运费少于TX的总运费。第五步取TX1中的权最大边，仍记为E，转第四步。第六步除E外取TX中的权最大边，仍记为E，转第四步。一直到取遍TX中的每一边E，去掉E后的两棵树T1与T2的产地与销地之间无权小于E的边可添加，或者有权小于E的边可添加，添加后总运费不减少，则得到最优树。图上求解法与表上作业法相比，用图上求解法判别最优解时，需要验证（MN
11、1）基变量边是否可以用非基变量对应边代替（其中M、N分别是产地和销地的数量）。当M、N较大时，MN（MN1）远远大于（MN1），因此当M、N较大时，理论上用图上求解法较方便。但同时当M、N很大时，图上边、权及边线太多，易混淆，不利于实际操作。而文献21给出了求解运输问题的一种网络算法，运用网络图求解运输问题，可以更直观、快速、形象地得到初始解，并且该初始解更接近最优解或已经是最优解，可以大大减少计算工作量。但当产销地数量较多时，网络图绘制可能相对麻烦些。此外文献2、3、4、5、6等还提出利用某些数学软件编程求解运输问题的方法，比较表上作业法计算繁琐,方案调整的工作量大,容易出错的缺陷，文献2提
12、出的LINGO软件语法简洁,具有良好的可读性,准确性高，易于被用户掌握。而文献3提出用线性规划的方法来解决运输问题，但由于此类问题所涉及的条件变量较多，一般的数学方法运算难度较大，结果不容易求出，所以作者利用MATLAB软件构建函数用来解决线性规划问题。随后文献4直接用这种方法来解决实际中的物流运输问题。文献5对运输问题的一般提法和模型给出了数值算法，概念清楚，步骤明确，易于编程实现，且有很好地收敛性。而文献6对用最小元素法求初始基本可行解的过程进行编程调解，减少了工作量，具有较强的通用性。文献7提出了又提出了求解运输问题的一种新算法，以平衡运输问题为例，其求解的算法基本步骤为第一步对平衡运输
13、问题的运价矩阵进行变换，使得在各行各列中都出现0元素。1从运价矩阵的每行列元素减去该行列的最小元素；2再从所得运价矩阵的每列行减去该列行的最小元素。第二步计算各行产地和各列销地的分配数。行的分配数就是该行中为0的那些元素所对应的销量之和；列的分配数就是该列中为0的那个元素所对应的产量之和；第三步比较分配数与产量销量，对于分配数小于产量销量的行41减去该行列的最小正数。并消去由此而产生的列行中的负数，0元素，即在出现负数的列行加上对应的6正数。直至所有行列所得到的分配数大于或等于产量销量为止。第四步此时若0元素的个数大于或等于MN1，在0元素的位置上分配调运量使产销平衡得最优调运方案后停止。在具
14、体分配调运量时，可在只有一个零元素的列或行的零元素位置上先分配调运量，然后再分配余下零元素位置上的调动量，使产销平衡。零元素的个数等于MN1时问题有唯一解，当零元素的个数大于打MN1时，问题有多重最优解。当0元素的个数小于MN1时，有时也能在0元素的位置上分配调运量使产销平衡得运输问题的最优调运方案；当0元素的个数小于MN1且无法分配调运量使产销平衡时，转第五步。第五步在运价矩阵中非0最小元素所对应的行或列中减去该最小元素，并消去由此而产生的列或行中的负数。计算各行列的分配数，此时若出现分配数小于产量销量转第三步，否则转第四步。该方法将求运输问题的最小元素法的思想与求指派问题的匈牙利解法巧妙地
15、结合起来，设计了一种求解运输问题的解法，该解法避开了原先求运输问题先确定初始可行解，再求检验数并进行多次迭代的方法，求解具有一次终止性，计算过程容易掌握。文献8提出了运输问题的逐块选优解法，其步骤为1计算产地和销地的有效目标函数梯度得到各产地和各销地的判别数，分别按判别数排序；2计算各产地和各销地的判别向量；3产地和销地匹配选优；4按选优结果去掉一个产地或和一个销地修改产地和销地数据，得到下一轮逐块选优求解的降维运输问题。类似的，还有运输问题的内点算法（文献9）、网络算法（文献10）等，以及对类似算法的改进。而文献11、12、13等研究了实际工作中运输问题的应用。通过以上的文献，我认为可以对运
16、输问题的各种算法进行归纳，通过对其分析、比较，找出各种算法的适用范围。对于不同类型的运输问题就可以套用不同算法，从而建立一套完善的运输问题的解题模式。同时在现已有的结论的基础上推广运输问题在解决其它的优化问题中的应用，并使之应用到更广泛的实际工作中。参考文献1臧运华运输问题的一种图上解法D运筹与管理,2002,472张家善LINGO软件求解运输问题与表上作业法的比较J湛江师范学院学报,2010,6,33戴建平基于MATLAB的运输问题求解方法J宁波职业技术学院学报,2009,24张国玉,夏文汇运用MATLAB软件求解物流运输问题J物流技术,2010,4,2145谢凡荣求解运输问题的一个算法D运
17、筹与管理,2002,11,36司南,任佳莉运输问题的一种计算机算法D计算机应用与软件,2004,77卢厚清,张永良,王宁生求解运输问题的一种算法D运筹与管理,1999,3,8,18蒋宏锋运输问题的逐块选优解法D科学技术与工程,2006,4,6,89刘徽,黄宽娜运输问题求解的一种内点算法J乐山师范学院学报,2009,510袁勋,严从荃,刘徽运输问题求解的一种网络算法D运筹与管理,2005,2,14,111何莉敏,石琳,侯玉双,李德荣,田红晓,刘丽钢管定购与运输问题的数学模型与求解的新方法J,内蒙古大学学报,2010,212蒋翔,罗蔓,张丽君工商管理常见运输问题的运筹学解法D商场现代化,2007,
18、10,51913云俊运输问题优化方法的综合应用J武汉理工大学学报,2001,9,25,314夏少刚,张建华求解运输问题的一种新算法D运筹与管理,2007,2,16,115苏若葵运输问题的简化解法D商场现代化,2009,1,56316单海英运输问题的推广及算法研究的重要意义D中国教育技术装备,2010,4,L2,19817王有鸿,费威运输问题国内外研究评述J中文核心期刊要目总览,贸易经济类核心期刊商业时代（原名商业经济研究）,2010,2418教材编写组编著运筹学M北京清华大学出版社，200819XINFENGYANG，YINZHENLI，RUICHUNHE，LINZHONGLIUMODELAN
19、DALGORITHMOFTRANSPORTATIONPROBLEMONNETWORKDJOURNALOFSYSTEMSSCIENCEANDINFORMATION,2008，VO16，NO4，PP32533220CHENHAIFENG，CHOJOONGRAE，LEEJEONGTAEJCHONGQINGUNIVENGEDSOLVINGHITCHCOCKSTRANSPORTATIONPROBLEMBYAGENETICALGORITHMMDECEMBER2004VOL3NO289本科毕业设计（20届）运输问题相关研究与应用10摘要【摘要】随着物流领域的不断发展，运筹学尤其是运输问题在其中所发挥的作用也
20、越来越明显。就目前，对运输问题求解方法的研究结果也层出不穷，其中的解法思路、基本思想也开始涉及到很多其他的学科。虽然求解方法很多，但缺乏系统的归纳总结，在实际应用中如何选取最适当的方法，高速有效地解决运输问题才是理论应用于实际的最好体现。选择正确恰当的求解方法能将复杂繁琐的运输问题化难为易，极大程度的节省人力、物力资源。所以面对实际的物流运输问题，要抓住问题的根本性特征，从而选择最为合适的求解方法，实现方法选择上的最优化。本文列举六种典型的运输问题求解方法表上作业法、图上求解法、LINGO软件求解法、MATLAB求解法、一种基于“分配数”的算法、网络算法求解。先进行理论上的基本原理阐释，再针对
21、一个具体的运输问题，分别用这六种典型的求解方法进行求解，最后对求解过程及其结果进行横向比较分析，总结归纳面对实际运输问题时选取求解方法的一般原理。最后提出一种新的计算机软件求解方法MAPLE。【关键词】运筹学；运输问题；求解方法；数学软件11ABSTRACT【ABSTRACT】WITHTHECONSTANTLYDEVELOPMENTOFLOGISTICS,THEOPERATIONALRESEARCH,ESPECIALLYTRANSPORTATIONMATTERPLAYSAMOREANDMOREAPPARENTROLEINTHISFIELDATPRESENT,THERESEARCHRESULTS
22、TOSOLVETRANSPORTATIONMATTEREMERGEINENDLESSLYTHEINVOLVEDSOLUTIONANDBASICTHOUGHTSSTARTTOCOMEDOWNTOMANYOTHERSUBJECTSTHOUGHTHEREAREMANYMETHODSOFSOLVING,SYSTEMATICSUMMERYISINSHORTAGETHEBESTREFLECTIONOFAPPLYINGTHEORYTOREALITYISHOWWECHOOSETHEBESTWAYINPRACTICEANDSOLVETHETRANSPORTATIONMATTEREFFICIENTLYCHOOSI
23、NGRIGHTANDAPPROPRIATESOLUTIONHELPSTOMAKETHECOMPLEXTRANSPORTATIONMATTEREASIER,SAVEMANPOWERANDPHYSICALRESOURCESFORTHEMOSTPARTTHEREFORE,WHENFACINGTHELOGISTICTRANSPORTATIONINREALITY,WESHOULDGRASPTHEESSENTIALFEATURESOFTHISMATTERANDTHENCHOOSETHEMOSTAPPROPRIATESOLUTIONANDBRINGABOUTTHEBESTCHOOSINGMETHODTHIS
24、PAPERLISTSSIXTYPESOFTYPICALTRANSPORTATIONMATTERSOLUTIONTABLEDISPATCHINGMETHOD,CHARTMETHOD,LINGOSOFTWAREMETHOD,MATLABMETHOD,METHODBASEDONFENPEISHUALGORITHMANDNETWORKALGORITHMWECANFOLLOWTHESTEPSBELOWFIRST,EXPLAINTHEBASICPRINCIPLEINTHEORYANDTHENAPPLYTHESIXTYPICALMETHODSTOSOLVETHEPROBLEMACCORDINGTOTHESP
25、ECIFICTRANSPORTATIONMATTERWHATSMORE,ANALYSISTHESOLVINGPROCESSANDRESULTANDSUMMARIZETHEGENERALPRINCIPLEOFCHOOSINGTHESOLUTIONATLAST,COMEUPWITHAKINDOFNEWCOMPUTERSOFTWARESOLUTIONMAPLE【KEYWORDS】OPERATIONSRESEARCH；TRANSPORTATIONPROBLEM；SOLUTION；MATHEMATICALSOFTWARE12目录1运输问题相关简介1311运输问题的定义及基本数学模型13111运输问题的定
26、义13112运输问题的基本数学模型1312运输问题的研究现状及算法研究的重要意义142产销平衡运输问题的典型解法1521表上作业法【18】15211主要思想15212主要步骤1522运输问题的图上解法【1】15221主要思想15222理论依据16223一般步骤16224实际计算中存在的局限性1723LINGO软件求解法【2】17231程序代码及其具体含义17232主要优势1824MATLAB求解运输问题【3】【4】18241基本思路18242实际问题中的应用优势1925一种基于“分配数”的算法【7】19251基本步骤19252理论依据20253解法的创新之处2026网络算法求解运输问题【10】
27、21261基本步骤21262优势及其局限性213六种典型解法在具体运输问题中的应用及其横向比较2231一个实际运输问题及其数学模型【4】2232六种典型解法的求解过程及其结论2333横向分析及其适用性比较394对新算法的探索4241MAPLE软件求解运输问题425附注关于产销不平衡的运输问题45参考文献47致谢错误未定义书签。附录48131运输问题相关简介11运输问题的定义及基本数学模型111运输问题的定义运输问题是社会经济生活和军事活动中经常出现的优化问题。在经济建设和国防建设中，经常遇到煤、钢铁、木材、粮食、武器装备等物资的调运问题。如何制定调运方案，将物资运往指定地点，而且实现运输成本最
28、小，即为运输问题。112运输问题的基本数学模型运输问题的数学模型如下已知有M个生产地点,1,2,IAIM。可供应某种物资，其供应量（产量）分别为,1,2,IAIM，有N个销地,1,2,JBJN，其需要量分别为,1,2,JBJN，从IA到JB运输单位物资的运价（单价）为IJC。12N产量12M11C12C1CN21C22C2CN1CM2CMCMN1A2AMA销量1B2BBN若用IJX表示从IA到JB的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，可求解以下数学模型销地产地1411,1,1MIN1,2,1,2,0MNIJIJIJMIJJINIJIJIJZCXXBJNXAIMX这就是运输
29、问题的数学模型。12运输问题的研究现状及算法研究的重要意义目前，对于运输问题的求解存在很多方法，基本上有这么几类首先是表上作业法，其次是图上求解法、网络解法等，再者还有比较方便的计算机软件求解法，如、LINGO软件、MATLAB软件等。求解方法虽多，但都存在一定的局限性，在不同的实际条件下选择不同的求解方法可以给计算带来很大的便利。但现在对求解方法的探索还在继续，研究方法多种多样，但对已得出的一些求解思路与方法缺乏系统性的归纳和总结，以及面对实际问题如何进行求解方法的选择，以最优化的方法得到最优的解决方案。152产销平衡运输问题的典型解法21表上作业法【18】211主要思想表上作业法是单纯形法
30、在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。212主要步骤用表上作业法求解运输问题的主要步骤可以归纳为（1）找出初始基可行解。即在MN产销平衡表上给出1MN个数字格。最常用的方法有最小元素法和伏格尔法。（2）求各非基变量的检验数，即在表格计算空格的检验数，判别是否达到最优解。如果已是最优解，则停止计算，否则转到下一步。（3）确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。（4）重复（2）、（3）直到得到最优解为止。22运输问题的图上解法【1】221主要思想构造一个赋权完全二部图G（1V，2V），其中1/1,2,IVAIM，2/1,2,JVBJN，
31、IJE为IA到JB的边，边权IJIJEC，点IA有权IIAA表示IA的产量，点JB有权JJBB表示JB的销量，IA到JB之间的调运量IJX在图上用IJX表示，这样把运输问题转化成了赋权完全二部图。接着用图论中树的相关知识求解。利用最小权元素法求得一个生成树，再用图上闭回路调整法得到最优解。1A2AIAMA1A2AIAMA1B2B3BJBNB1B2B3BJBNB16222理论依据引理1运输问题的任一可行解与图的生成子图相对应。引理2运输问题的任一基可行解与图G的生成树相对应。引理3设T为一棵树，则去掉T中的任意一条边，T变为两棵树。定义1使总运费最小的基可行解X是运输问题的最优解，X对应的G的生
32、成树TX称为最优树。图上闭回路调节法设TX是运输问题的基可行解对应的生成树，IJE为TX的权最大边，由引理3可知，IJTXE变为两棵生成树1T与2T。在1T的产地与2T的销地之间添加一边，以新添加边为开始边构成一个闭回路C，验证添加边后，总运费是否减少若总运费减少，设为闭回路C上偶数边中运量最少的调运量，则奇数边运量加上，偶数边运量减去，去掉一个运量为0的边，新调整方案得到的基可行解为1X，其对应的生成树1TX总运费比TX的要少，这种方法称为图上闭回路调整法。定理1设IJE为G的生成树TX的一条边，IJE为下列情况之一。（1）设IJE为TX的权最大边，IJTXE变为二棵树1T和2T，1T的产地
33、与2T的销地之间可添加的边权均不小于IJE。（2）1T的产地与2T的销地之间有权小于IJE的边可添加，添加后，总运费没有减少，则除IJE外取TX中权最大的边，仍记为IJE，IJTXE变为1T与2T，的产地与的销地之间无权小于IJE的边可添加。则去掉IJE，调整后得到的新的生成树总运费不减少。223一般步骤使总运费最小的基可行解X是运输问题的最优解，X对应的G的生成树TX为最优树。下面给出求解最优生成树的一般步骤（1）把运输问题转化为赋权完全二部图G。（2）用最小权元素法，求初始基可行解，即求G的一个生成树TX。17（3）取TX的权最大边E，若两个以上取其中之一。（4）TXE为两棵树1T和2T，
34、若1T的产地与2T的销地之间无权小于E的边可添加，转（6）。否则，添加权小于E的边构成一个闭回路，验证总运费是否减少若总运费不减少，转（6），否则，用图上闭回路调节法，得到新的生成树1TX，且其总运费少于TX的总运费。（5）取1TX中权的最大边，仍记为E，转（4）。（6）除E外取TX中的权最大边，仍记为E，转（4）一直到取遍TX中的每一边E，去掉E后的两棵树1T和2T的产地和销地之间无权小于E的边可添加，或者有权小于E的边可添加，添加后总费用不减少，则得到最优树。224实际计算中存在的局限性由于图上求解法要将运输问题转化为赋权完全二部图来求解，所以当M、N很大时，图上边、权及连线太多，不利于实
35、际操作。23LINGO软件求解法【2】231程序代码及其具体含义MODELM个产地N个销地的运输问题SETSWAREHOUSES/WH1WHM/CAPACITYVENDORS/V1VN/DEMANDLINKSWAREHOUSES,VENDORSCOST,VOLUMEENDSETS目标函数；MINSUMLINKSCOSTVOLUME需求约束；FORVENDORSJSUMWAREHOUSESIVOLUMEI,JDEMANDJ产量约束18FORWAREHOUSESISUMVENDORSJVOLUMEI,J0表示优化过程中变量收敛于解X，ECLEARF314573862392Q111100000000
36、000011110000000000001111100010001000010001000100001000100010000100010001P50507540556020Q000000000000X,V,ELINPROGF,Q,P,QOPTIMIZATIONTERMINATEDX34000000000050000000000000004000001000000000040000015000000000200000V5650000E1分析由E10可知,优化过程中变量收敛于解X，即当123456789101112005000401004015020XXXXXXXXXXXX时，运输总费用最小，为
37、565元。5、基于“分配数”的算法35表1甲乙丙丁产量A314550B738650C239275销量40556020175第一步对运价矩阵进行变换，使得在各行各列中都出现0元素。并计算各行各列的分配数，结果见表2。表2甲乙丙丁产量分配数A2004505560115B40235055C014075402060销量40556020175分配数7550501005075第二步由于第三行的分配数小于产量，故对第一行减去该行的最小元素1，结果见表3。表3甲乙丙丁产量A200450B402350C103175销量40556020175第三步由于第一列和第四列出现负数，对第一列和第四列加1，并重新计算各行各
38、列的分配数。结果见表4。表4销地产地销地产地销地产地36甲乙丙丁产量分配数A3005505560115B50245055C003075405520115销量40556020175分配数755050751755075第四步由于第三列的分配数小于销量，故对第三列减去该列的最小元素2，结果见表5。表5甲乙丙丁产量A302550B500450C001075销量40556020175第五步由于第一行出现负数，对第一行加2，并计算各行各列的分配数，结果见表6。表6甲乙丙丁产量分配数A52075060B5004505560115C001075405520115销量40556020175分配数75507512
39、5505010075第六步由于各行（列）的分配数均已不小于产量销量，且0元素的个数不小于6（NM1），故可在0元素处分配调运量并使平衡得最优调运方案。销地产地销地产地销地产地37即解方程组367910129610371250507540556020XXXXXXXXXXXX，求解得到36791012504010401520XXXXXX。即当123456789101112005000401004015020XXXXXXXXXXXX时，运输总费用最小，为565元。（6）、网络算法求解甲乙丙丁产量A314550B738650C239275销量40556020175销地产地38首先绘制网络图50甲40A
40、50乙55SVBTV75丙60C丁20找出最大需求量丙，132333MIN,4CCC,所以首先由A的供应量50满足丙，还差10，2333MIN,8CC，即应由B流向丙，流量为10。此时丙已经得到满足。下一步应该满足乙，122232MIN,1CCC，而这是A已经流完，2232MIN,3CC，从B剩下的40全部流向乙，而乙还差15，只有从C流向乙，流量为15。此时乙得到满足。再下一步应该满足甲，由于A、B都已经流完，只能从C流向甲，流量为40。此时甲也得到满足。满足丁，而只有从C流向丁，丁满足。此时初始解已经获得50A丙，10B丙，40B乙，15C乙，40C甲，20C丁，即350X，710X，64
41、0X，1015X，940X，1220X用位势法检验此解就是最优解。此时504403108402153202565Z元39所以当123456789101112005000401004015020XXXXXXXXXXXX时，运输总费用最小，为565元。33横向分析及其适用性比较从上述六种典型算法对同一个运输问题的求解过程中可以看出，虽然都能求出结果，但求解过程的复杂性各不相同。横向比较这六种求解方法表上作业法相对于其他方法而言显得较为复杂，求解过程甚是繁琐，在对初始基可行解的求解过程中，首先要选择方法最小元素法或是伏格尔法，对于不同的运输问题，如果选对了方法就可以省去很多不必要的步骤，如本题中用伏
42、格尔法给出的初始基可行解比最小元素法给出的初始基可行解更接近最优解。随后对初始基可行解进行最优解的判定，可以选择闭回路法或者是位势法。用闭回路法求检验数时，需要每一个空格找一条闭回路，当产销点很多时，这种计算方法很烦琐；采用位势法求检验数虽然相对于闭回路法而言有所简单，但由于有多次的加加减减，容易出错。用图上解法求解运输问题，是图论知识在运筹学中的一种应用。这种方法相对于表上作业法而言显得较为简单。但是当N、M很大时，图上边、权及连线太多，不利于实际操作。而且在求解生成树，即初始基可行解的时候先要用最小权元素法，随后用图上闭回路调节法进行调节，最后得到最优树，即为最优解。所以对于一些不适合用最
43、小元素法求初始基可行解的运输问题而言，如若采用图上求解法会带来很多繁琐的步骤，走很多的弯路。就如上述例子中由于最小运费和次小运费之间相差很小，而且各产量和销量相对于运费而言较大，所以采用图上解法在求解过程中会产生较大的偏差，给求解带来很多麻烦。因此，本文在求解过程中采用相对最小权法求解基可行解，即在考虑运输量的基础上选择相对较小单位运价的运输路线。所以在求解类型的运输问题时，若要采用图上求解法，则应该避开最小元素法的局限，结合运输量一起考虑，这样会使计算方便很多。总的来说，图上求解法基本理念跟表40上作业法相似，它只是把表格转换成了图形，图论中称之为树，更加直观，也更加形象化。LINGO软件求
44、解法和MATLAB求解法是计算机在运筹学中的典型应用。显然，相对于其他求解方法而言，这两种计算机求解方法显得尤为简洁，只要简单编写程序就可以很快解决繁琐的计算量，无须进行任何调整，准确性较高，高效、便捷。而且利用MATLAB求解时，顺便可以求得该运输问题是否有最优解，即是否收敛于所求得的解。本题由于产地、销地较少，利用计算机软件求解的优势不能体现的很到位，如果N、M大到一定的程度，那么利用LINGO软件或是MATLAB求解运输问题的可行性、可操作性及其计算优势会表现得淋漓尽致。利用“分配数”求解运输问题不失为一种很不错的方法，它不同于常规的求解方法，因为它抛弃了一般的最小元素或是闭回路等一般的
45、求解思路，而是简单的对单位运价矩阵进行初等变换，最后只要保证各行（列）的分配数均不小于产量（销量），且满足0元素的个数不小于NM1，即可得到最优解。对本题而言采用“分配数”求解法也不失为一个不错的选择。网络求解法同图上求解法在表征上很相似，都是把抽象的运输问题转化为图形，直观、形象的表达出来。但是基本原理却是截然不同。网络求解法求解运输问题的基本思路是从各产地到各销地的运输量运入手，首先着眼于最大的销售量（即需求量），所以对本题所列举的例子而言，采用网络求解法是个明智的选择。因为影响最小总运费的因素主要是单位运价以及各个产地到各个销地的运输量，对于本题而言，影响最小总运费的主要因素是运输量，所
46、以采用网络求解法求得的初始基可行解最有可能接近最优解，但还是必须对其进行最优解检验。但若用网络求解法得到的初始基可行解不是最优解时，如何在网络图上予以调整和检验，这还是个尚在探讨研究中的问题。当然也可以用最基本的方法将其初始解还原到表中，用闭回路法或是位势法进行检验和调整。横向比较归纳表切入点求解初始解的形式初始解的优劣性最优解检验总计算量独特优势表上作业法单位运价（一般最小元素法或伏格尔法）表格（单位运价表）不能保证初始解接近最优解闭回路法或位势法检验计算量大，过程较为繁琐最基本的方法图上解法单位运价完全二部不能保证闭回路法计算量相利用图论比较方法41（最小元素法）图（形象、直观）初始解接近
47、最优解调整对较小，过程较为简易知识，在图上就可进行最优解检验LINGO软件程序编写一步到位相当便捷，可操作性强MATLA软件程序编写一步到位相当便捷，可操作性强“分配数”算法单位运价表（矩阵的初等变换，不涉及最小运价）表格（单位运价表）初始解即为最优解求解方程组，得到最优解计算简单，可操作性较强利用高等代数知识，无须最优解检验网络算法运输量（先满足最大销售量）网络图（形象、直观）较接近最优解还原成表格，用闭回路法或位势法检验计算量相对较大以运输量作为切入点综上所述，对于实际的运输问题，选择适当的求解方法很大程度上可以缩减工作量。所以面对各类运输问题，求解方法的选择显得尤为重要。下面对各类运输问
48、题及其较为适合的求解方法进行简单的总结归纳单位运价是主要影响因素以最小元素法为基本求解思想的求解方法，如表上作业法、图上求解法等。运输问题（N、M较小）运输量是主要影响因素以运输流量为首要考虑对象的求解方法，如网络求解法等。不易区分主要影响因素一般可以采用“分配数”求解法。运输问题（N、M较大）一般采用计算机软件求解法，如LINGO、MATLAB等。424对新算法的探索41MAPLE软件求解运输问题根据上述的阐述和具体应用，我们不难发现，使用数学软件求解运输问题，高效便捷，可操作性强，而且准确度高。以上已经有了LINGO、MATLAB软件在求解实际运输问题中的应用，不妨再来探索下MAPLE软件在求解该类运输问题时的具体操作（1）主要程序代码将优化程序包加载到MAPLE中WITHOPTIMIZATION定义目标函数OBJECTFUNCTIONMINZ11MINMNIJIJIJZCX定义约束方程CONSTRAINTEQUATIONSL1,1,2,MIJJIXBJN，1,1,2,NIJIJXAIM，0IJX利用MINIMIZE求最小解MINIMIZEOBJECTFUNCTIONMINZ,CONSTRAINTEQUATIONSL（2）用MAPLE求解实际运输问题以“三”中所列举的实际运输问题为例，进行MAPLE编程WITHOPTIM
