【数学与应用数学专业】【毕业论文】运输问题的求解及其应用

《【数学与应用数学专业】【毕业论文】运输问题的求解及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、（20__届）本科毕业论文运输问题的求解及其应用摘要：本课题主要探讨了如何判别一个运输问题的调运方案是最优，对通常采用的两种闭回路法或位势法做综述整理，同时探讨更好的一次性算法，既避免了闭回路法中对所有非基变量检验数的一一计算,又回避了位势法中需要多次求解线性方程组以计算位势的过程。本课题主要利用了已有或已得到的算法对实际问题进行分析研究。关键词：运输问题；最优方案；一次性算法；闭回路法；位势法TransportationproblemsolvinganditsapplicationAbstract:Mys

2、ubjectmainlydiscusseshowtodistinguishthetransportationproblemwithoptimalsolutionscheme,thensyntheticallyinducesaboutclosedloopmethodorpotentialsmethodwhichwealwaysuse.Atthesametime,weexploreabettermethodtoone-timelygettheresult.Itnotonlyavoidscalculatingon

3、ebyoneallthebasicvariableinspectionnumberwithclosedloopmethod,butalsoavoidstheprocessofsolvingthelinearequationsmanytimestocalculatpotentialswithpotentialsmethod.Inshort,thegoalofmytopicisanalyzingandstudyingpracticalproblemswithexsitedorachievedmethods.Ke

4、ywords:Transportationproblem;Theoptimalsolution;One-timealgorithm;Closedloopmethod;Potentialsmethod目录1运输问题简介12运输问题模型23几种常用检验法的缺陷33.1闭回路法的缺陷43.2位势法的缺陷83.3改进的闭回路法的缺陷113.4动态规划法的缺陷124一种新的检验方法125应用举例136运输问题在消防中的应用157结束语17致谢18参考文献191运输问题简介运输问题是一类具有特殊结构的线性规划问题。由于

5、运输问题约束方程组的系数矩阵是完全么模的，即所有的子行列式为0或±1，存在着比单纯形法更简单的特殊解法。对于规模不太大的运输问题可用图上作业法或表上作业法求解。这类问题的典型提法是，为了把某种产品从若干个产地调运到若干个销地，已知每个产地的供应量和每个销地的需求量，如何在许多可行的调运方案中，确定一个总运输费或总运输量最少的方案。具有上述特点的线性规划问题通常被称为运输型问题。现已发现的运输型问题有以下6类:①一般运输问题,又称希契科克运输问题，简称H问题。②网络运输问题，又称图上运输问题,简称T问题。③最

6、大流量问题,简称F问题。④最短路径问题,简称S问题。⑤任务分配问题，又称指派问题,简称A问题。⑥生产计划问题，又称日程计划问题,简称CPS问题。其中一般运输问题、任务分配问题和生产计划问题通常都可以用表上作业法求解，而网络运输问题、最大流量问题和最短路径问题一般可用图上作业法或网络技术求解（参见文献[1]）。当使用表上作业法求解运输问题时。初始基本可行解的求法有三种：①左上角法。它的基本思想是给运输表中左上角的变量分配运输量以确定产销关系。②最小元素法，或最小成本法。它的基本思想是就近供应，即从运输表中运价

7、最小的格子开始分配运输量以确定产销关系。③元素差额法,又称沃格尔近似法，简称VAM法。它是从运输表中各行和各列的最小元素和次小元素的差额来确定产销关系。改进初始基本可行解的方法有两种：①闭回路法。这种方法需要对每一个空格寻找一条闭回路，并根据闭回路求出每个空格的检验数。当运输问题中m和n较大时，计算检验数的工作量很大。②位势法，或乘数法。先对初始调运方案求出位势，然后求各空格的检验数。当所有的检验数均为非负时，就得到最优方案。如果出现负的检验数，则从检验数为负的空格出发，作闭回路，重新计算检验数，作进一步调

8、整。用位势法求检验数就是对偶问题的表上作业法（参见文献[2]）。但是我们发现对于实际的运输问题，上述优化方法很难将运输过程中所发生的费用都考虑进去，因此，如果教条地采用上述优化方法直接进行优化，则很难保证此方案是真正的最佳方案。实际的运输问题中上述方法没考虑到的因素有：（1）对运输问题中的中转再分拨，其中转的装卸搬运费用，无论是求最小费用最大流的优化方法还是表上作业法求具有中转站的运输问题最佳方案时，都没有考虑此