1、1毕业论文文献综述数学与应用数学运输问题相关研究与应用运输问题是社会经济生活和军事活动中经常出现的优化问题。在经济建设和国防建设中，经常遇到煤、钢铁、木材、粮食、武器装备等物资的调运问题。如何制定调运方案，将物资运往指定地点，而且实现运输成本最小，即为运输问题。运输问题是特殊的线性规划问题，它是早期的线性网络最优化的一个例子。与一般线性规划问题不同，它的约束方程组的系数矩阵具有特殊的结构，这就需要采用不同的甚至更为简便的求解方法来解决这种在实际工作中经常遇到的问题。运输问题不仅代表了物资合理调运、车辆合理调度等问题，有些其他类型的问题经过适当变换后也可以归结为运输问题。从算法角度考虑，目前对于
2、运输问题的求解提出了很多可行的解法，如表上作业法、图上求解法以及应用计算机实现的启发式多种算法等。表上作业法是解决一般运输问题最常用的解法，因其求解工作均在运输表上进行而得名。它是一种迭代算法，迭代步骤为先按某种规则找出一个初始解；再对现行解作最优性判别；若该解不是最优解，就在运输表上对它进行调整改进，从而得出一个新解，再重复判别改进的过程，直至得到运输问题的最优解为止。表上作业法一方面是在求解过程中首先要找出初始基可行解，需要一定计算工作量，即需要经过（MN1）次加减运算给出初始方案。另一方面是在初始基可行解基础上，还要用繁琐的闭回路法或位势法计算所有空格（非基变量）的检验数，再判别是否达到
3、最优解。如果没有得出最优解，还需要在表上用闭回路法进行调整，确定换入变量和换出变量，找出新的基可行解，再进行检验等步骤，直到求出最优解为止。由于当产地M、销地N较大时表上作业法的操作显得尤为繁琐。文献1提出了运输问题的一种新解法，该方法通过构造赋权二部图，应用图论的相关理论，给出求解运输问题的另一种图上解法。其一般步骤为第一步把运输问题转化为赋权完全二部图G。第二步用最小权元素法，求初始基可行解，即求G的一个生成树TX。第三步取TX的权最大边E，若两个以上取其中之一。第四步TXE为两棵树TL和T2，若TL的产地与T2的销地之间无权小于E的边可添加，转第六步。否则，添加权小于叫WE的边构成一个闭
4、回路，验证总运费是否减少若总运费不减少，转第六步，否则，用图上闭回路调节法，得到新的生成树TX1，且其总运费少于TX的总运费。第五步取TX1中的权最大边，仍记为E，转第四步。运输问题相关研究与应用2第六步除E外取TX中的权最大边，仍记为E，转第四步。一直到取遍TX中的每一边E，去掉E后的两棵树T1与T2的产地与销地之间无权小于E的边可添加，或者有权小于E的边可添加，添加后总运费不减少，则得到最优树。图上求解法与表上作业法相比，用图上求解法判别最优解时，需要验证（MN1）基变量边是否可以用非基变量对应边代替（其中M、N分别是产地和销地的数量）。当M、N较大时，MN（MN1）远远大于（MN1），因
5、此当M、N较大时，理论上用图上求解法较方便。但同时当M、N很大时，图上边、权及边线太多，易混淆，不利于实际操作。而文献21给出了求解运输问题的一种网络算法，运用网络图求解运输问题，可以更直观、快速、形象地得到初始解，并且该初始解更接近最优解或已经是最优解，可以大大减少计算工作量。但当产销地数量较多时，网络图绘制可能相对麻烦些。此外文献2、3、4、5、6等还提出利用某些数学软件编程求解运输问题的方法，比较表上作业法计算繁琐,方案调整的工作量大,容易出错的缺陷，文献2提出的LINGO软件语法简洁,具有良好的可读性,准确性高，易于被用户掌握。而文献3提出用线性规划的方法来解决运输问题，但由于此类问题
6、所涉及的条件变量较多，一般的数学方法运算难度较大，结果不容易求出，所以作者利用MATLAB软件构建函数用来解决线性规划问题。随后文献4直接用这种方法来解决实际中的物流运输问题。文献5对运输问题的一般提法和模型给出了数值算法，概念清楚，步骤明确，易于编程实现，且有很好地收敛性。而文献6对用最小元素法求初始基本可行解的过程进行编程调解，减少了工作量，具有较强的通用性。文献7提出了又提出了求解运输问题的一种新算法，以平衡运输问题为例，其求解的算法基本步骤为第一步对平衡运输问题的运价矩阵进行变换，使得在各行各列中都出现0元素。1从运价矩阵的每行列元素减去该行列的最小元素；2再从所得运价矩阵的每列行减去
7、该列行的最小元素。第二步计算各行产地和各列销地的分配数。行的分配数就是该行中为0的那些元素所对应的销量之和；列的分配数就是该列中为0的那个元素所对应的产量之和；第三步比较分配数与产量销量，对于分配数小于产量销量的行41减去该行列的最小正数。并消去由此而产生的列行中的负数，0元素，即在出现负数的列行加上对应的正数。直至所有行列所得到的分配数大于或等于产量销量为止。第四步此时若0元素的个数大于或等于MN1，在0元素的位置上分配调运量使产销平衡得最优调运方案后停止。在具体分配调运量时，可在只有一个零元素的列或行的零元素位置上先分配调运量，然后再分配余下零元素位置上的调动量，使产销平衡。零元素的个数等
8、于MN1时问题有唯一解，当零元素的个数大于打MN1时，问题有多重最优解。当0元素的个数小于MN13时，有时也能在0元素的位置上分配调运量使产销平衡得运输问题的最优调运方案；当0元素的个数小于MN1且无法分配调运量使产销平衡时，转第五步。第五步在运价矩阵中非0最小元素所对应的行或列中减去该最小元素，并消去由此而产生的列或行中的负数。计算各行列的分配数，此时若出现分配数小于产量销量转第三步，否则转第四步。该方法将求运输问题的最小元素法的思想与求指派问题的匈牙利解法巧妙地结合起来，设计了一种求解运输问题的解法，该解法避开了原先求运输问题先确定初始可行解，再求检验数并进行多次迭代的方法，求解具有一次终
9、止性，计算过程容易掌握。文献8提出了运输问题的逐块选优解法，其步骤为1计算产地和销地的有效目标函数梯度得到各产地和各销地的判别数，分别按判别数排序；2计算各产地和各销地的判别向量；3产地和销地匹配选优；4按选优结果去掉一个产地或和一个销地修改产地和销地数据，得到下一轮逐块选优求解的降维运输问题。类似的，还有运输问题的内点算法（文献9）、网络算法（文献10）等，以及对类似算法的改进。而文献11、12、13等研究了实际工作中运输问题的应用。通过以上的文献，我认为可以对运输问题的各种算法进行归纳，通过对其分析、比较，找出各种算法的适用范围。对于不同类型的运输问题就可以套用不同算法，从而建立一套完善的
10、运输问题的解题模式。同时在现已有的结论的基础上推广运输问题在解决其它的优化问题中的应用，并使之应用到更广泛的实际工作中。参考文献1臧运华运输问题的一种图上解法D运筹与管理,2002,42张家善LINGO软件求解运输问题与表上作业法的比较J湛江师范学院学报,2010,6,33戴建平基于MATLAB的运输问题求解方法J宁波职业技术学院学报,2009,24张国玉,夏文汇运用MATLAB软件求解物流运输问题J物流技术,2010,4,2145谢凡荣求解运输问题的一个算法D运筹与管理,2002,11,36司南,任佳莉运输问题的一种计算机算法D计算机应用与软件,2004,77卢厚清,张永良,王宁生求解运输问
11、题的一种算法D运筹与管理,1999,3,8,18蒋宏锋运输问题的逐块选优解法D科学技术与工程,2006,4,6,89刘徽,黄宽娜运输问题求解的一种内点算法J乐山师范学院学报,2009,510袁勋,严从荃,刘徽运输问题求解的一种网络算法D运筹与管理,2005,2,14,1运输问题相关研究与应用411何莉敏,石琳,侯玉双,李德荣,田红晓,刘丽钢管定购与运输问题的数学模型与求解的新方法J,内蒙古大学学报,2010,212蒋翔,罗蔓,张丽君工商管理常见运输问题的运筹学解法D商场现代化,2007,10,51913云俊运输问题优化方法的综合应用J武汉理工大学学报,2001,9,25,314夏少刚,张建华求
12、解运输问题的一种新算法D运筹与管理,2007,2,16,115苏若葵运输问题的简化解法D商场现代化,2009,1,56316单海英运输问题的推广及算法研究的重要意义D中国教育技术装备,2010,4,L2,19817王有鸿,费威运输问题国内外研究评述J中文核心期刊要目总览,贸易经济类核心期刊商业时代（原名商业经济研究）,2010,2418教材编写组编著运筹学M北京清华大学出版社，200819XINFENGYANG，YINZHENLI，RUICHUNHE，LINZHONGLIUMODELANDALGORITHMOFTRANSPORTATIONPROBLEMONNETWORKDJOURNALOFSYSTEMSSCIENCEANDINFORMATION,2008，VO16，NO4，PP32533220CHENHAIFENG，CHOJOONGRAE，LEEJEONGTAEJCHONGQINGUNIVENGEDSOLVINGHITCHCOCKSTRANSPORTATIONPROBLEMBYAGENETICALGORITHMMDECEMBER2004VOL3NO2
