运输问题的求解方法探讨开题报告

1. 研究目的与意义

运输问题是运筹学的一个分支，是线性规划的特殊形式.它研究的是如何在一个大物资调运中，制定出一个由若干个产地将物资根据已知的运输交通网运到各个销售地的方案，使得总运费最小. 运输问题是现实生活中很重要的一类问题.本课题主要研究两类运输问题，即产销平衡运输问题和产销不平衡的运输问题，并分别介绍其求解方法.同时结合金融中的实际问题，对运输问题的应用进行分析.在物流运输中运用Matlab软件，借助遗传算法的思想，解决运输线路的优化问题，简化了复杂的运输过程,提高了运输规划的效果.且能寻找出物流运输方案的最优解，从而降低物流成本，使得一些公司在物流上的投资可以进行优化，赢得更多的效益.

2. 研究内容和预期目标

一、研究内容：1.表上作业法和单纯形法2.产销平衡运输问题3.产销不平衡运输问题二、拟解决的关键问题： 建立两类运输问题的数学模型，寻找不同问题的求解方法.同时，结合金融实例，验证模型和求解方法的有效性.三、写作提纲：1.题目2.中文摘要3.英文摘要 4.引言5.表上作业法和单纯形法6.产销平衡运输问题7.产销不平衡运输问题8.参考文献

3. 国内外研究现状

国内外研究现状：[1]提出了单纯形法作为求解运输问题的最初单纯形方法，随后发展了逐级算法，该算法提供了决定单纯形方法信息的可选择途径.给出了求解经典运输问题的一种搜索算法，该算法思想以Balas 过滤算法为基础，最后给出了该运输问题在实际中的应用.[2]利用增加原有线路指标数据结构，对算法进行了改进.提出原问题的拉格郎日松弛问题，由此可获得条件惩罚函数，但由于缺少有效运输节点，使算法的计算结果并不理想.[3]给出求解运输问题的拍卖算法.拍卖算法是一种求解经典指派问题的平行松弛算法.他们将拍卖算法应用于线性运输问题的求解，该算法的思想是将运输问题转化为指派问题，然后修改拍卖算法，使其适用于运输问题的特殊结构.[4]给出了求解线性运输问题的遗传算法(遗传算法是仿照自然选择的进化过程寻找问题的解)，并举例说明了具有代表性的结构之间的关系，研究了遗传算法实现的程序，给出了多种不同结构的运输问题.在改进网络流算法的基础上，给出了一般运输问题的网络流算法，算法使用了大量的检测迭代，是一种求解运输问题的强多项式算法.[5]将运输问题转化为图问题，通过构造赋权二分图G,应用图论理论，给出运输问题一种图上解法.[6]从基变量判断和寻找闭回路思想出发，提出不同于位势法和闭回路调整的运输问题迭代算法，但算法仍具有传统表上作业法的缺点，先求初始可行解再构造上述三个矩阵进行检测调整.[7]讨论了两类运输问题的算法，传统运输问题的算法和受时间约束运输问题的方案及算法.该算法从运输问题可行域的内部出发，沿着中心路径的方向，通过反复迭代寻找运输问题的近似最优解.[8]针对实数线性运输问题，提出了一种新型进化算法，在遗传算法的基础上引进了差异进化的思想，设计出具有全局搜索能力的重组算子，重组算子能够从理论上保证约束条件的满足，仿真实例显示了该算法的可行性和有效性.[9]设计了基于遗传算法和粒子群优化算法的求解运输问题的GAPSO算法，为避开对非可行解的处理，该算法对迭代过程也进行了特殊设计，从而简化了运用随机搜索算法解决运输问题的过程.[10]给出了求解经典运输问题的一种搜索算法，该算法思想以Balas过滤算法为基础，最后给出了该运输问题在实际中的应用.

4. 计划与进度安排

1．2022年11月9日：完成选题工作；2．2022年11月29日：完成开题工作；3．2022年3月15日：完成初稿和中期检查工作；4．2022年4月30日：完成论文修改、定稿、外文文献翻译工作；5．2022年5月25日：完成答辩环节工作，成绩发布；6．2022年6月20日：完成校级优秀毕业论文评选工作；7．2022年6月10日至6月30日：院系完成论文工作总结、遴选参评省优论文、督导组毕业论文校内抽检工作。

5. 参考文献

[1]段连伟，牛凤秋，刘芬.基于运输问题的求解方法探讨[J].中国市场,2015(33):73-74.[2]崔春生.运筹学中几种运输问题的求解方法探讨[J].数学的实践与认识,2014(44):295-300.[3]王有鸿，费威.运输问题国内外研究评述[A].运城学院经济管理系，东北财经大学数学与数量经济学院,山西运城，辽宁大连，2010.[4]毕笑天.运筹学的发展以及运输问题的求解方法探讨[J].SILICON VALLEY,2014(21):143.[5]戴建平.基于MATLAB的运输问题求解办法[J].宁波职业技术学院学报,2009(13):93-95.[6]李小林.运筹学产销不等运输问题新解[J].学术探讨,2011(12):358.[7]管强，邓敬源，袁明明.利用Excel Vba求解运输问题的计算机辅助算法[J].计算机应用与软件,2017(07).[8]Hitchcock FL. .The distribution of a product from several sources to numerous localities[J]. Journal of Mathematics Physics, 1941, 20(4).[9]G.B. dantizig. Application of the simplex method to a transportation problem in activity analysis of production and allocation. Chap. XXIII.Wiley,New York( 1951).[10]Adriano de maio,Claudio roveda politecnicodi. An all zero-one algorithm for a certain class of transportation problems. Operations Research, 1974(6).