1、毕业论文 开题报告 数学与应用数学 运输问题的求解及其应 用 一、 选题的背景、意义 （所选课题的历史背景、国内外研究现状和发展趋势） 作为一个发展中国家，交通运输对我国经济、社会发展起着显著的前导性作用。工农业生产、人民生活以及国防建设的诸多方面都和交通运输业的发展有着紧密的关系。尤其在中国加入 WTO 以后，迅猛的经济发展让交通运输的压力日益加大，交通运输问题也越来越多的出现，对于运输问题的研究也越来越被重视。 由于经济的发展等原因，国外对于运输问题的研究已经非常的深入，详见文献 2-4。 1995 年 Saad N Aljarad 和 William R Black 用非集计模型分析沙特
2、拉伯一巴林运输通道内城间非工作出行的 (non-business travel)运输方式选择。提出了两个独立的模型，即二项 Logit 模型和多项 Logit 模型。前者用于利雅得一巴林通道内的运输方式选择，后者用于沙特拉伯东部省份 (达兰、达曼、胡富夫等省 )一巴林通道内的运输方式选择。同年， Chandra R. Bhat3对加拿大 (Canada)的多伦多一蒙特利尔运输通道内工作日的工作出行 (weekday, business travel)进行了研 究，并且将用于计算出行者对运输方式 (train, car, plan)选择的式 Logit 模型 (NL)进行了改进，提出协方差巢式
3、Logit 模型 (COVNL). 1996 年 Hensher DAE4I 提出采用异方差极值 Logit 模型 (HEVL)对澳大利亚 (Australia)的悉尼一堪培拉(Sydney-Canberra) 通 道 内 的 四 种 运 输 方 式 (car, plane, scheduled coach, nonscheduledcoach)所占的市场份额进行了预测。但是 MNL, COVNL 和 HEVL 模型都是建立在效用 的随机项相互独立且服从 Gumbel 分布的假设基础之上。这种假设体现不出实际运输系统中各种运输方式的运行状况和营运效用相互作用、密切相关的特性。 1997 年 H
4、su C-I 和 Chung W-M 提出在铁路运输通道内乘客如何选择 High speed rail(HSR), Conventional rail(CR)的分析模型。按照可达性 (accessibility)将乘客分类，分别给出每种类型的乘客对运输方式选择的计算模型。根据乘客的出行时间、时间价值、出行距离、票价以及 HSR 和 CR 的服务特点建立运输方式选择模型。该 模型的合理性在于将费用转化成时间，并给出了时间价值的计算公式。这样做要比只以车内时间和车外时间为基础利用多项 Logit 模型 (MNL)或巢式 Logit 模型 (NL)计算市场份额要合理，但是该方法在费用和时间换算的过程
5、中误差很大。 2001 年 11， joon Chang 博士在其博士论文中将 Wardrop 原理应用到预测区域运输通道内各运输方式所占的市场份额中，并针对韩国 (Korea)京釜 (Seoul-Busan)通道内的四种运输方式 (Air, High-speed rail , Conventional rail ,Highway)分别从用户最优和系统最优的角度对其所占市场份额做了预测。并对传统广义出行费用的求解做了改进，这一点主要体现在对时间价值的确定问题上，对时间价值的求解摒弃了传统方法，采用 Wardrop 原理并结合 Dail 的几准则来求解时间价值，得出了各种运输方式旅客时间价值的概
6、率密度函数，使时间价值不再是常量，然后再利用 Wardrop 原理预测通道内各运输方式的客运量分担率，但是在应用该模型进行远期预测时，体现不出经济的发展和人们对价值观念认识的改变对时间价值函数的影响，进而就影响了应用该模型的可靠性。此外，在论 文中采用的是理想交通条件下的 Wardrop 原理，体现不出不确定因素对客运量分配的影响。 国外主要以运输问题求解算法为研究主体，以表上作业法、最短路法、最小费用最大流以及智能算法等为代表； 而 国内从算法、目标函数、约束函数这三个角度进行分类综述。 但是都存在由各种因素而导致的误差。 随着经济的发展需求，相信各国对运输问题的研究会更加深入，会有更加有效
7、可行的方法被发现。 二、 相关研究的最新成果及动态 运输问题是 一类具有特殊结构的 线性规划 问题。 通过文献 5我们知道 由于运输问题约束方程组的系数矩阵是完全么模的，即所有的子 行列式 为 0 或 1 ，存在着比 单纯形 法 更简单的特殊解法。对于规模不太大的运输问题可用图上作业法或表上作业法求解。这类问题的典型提法是，为了把某种产品从若干个产地调运到若干个销地，已知每个产地的供应量和每个销地的需求量，如何在许多可行的调运方案中，确定一个总运输费或总 运输量 最少的方案。 文献 6-7告诉我们 运输问题可用表上作业法求解。初始基本可行解的求法有三种： 左上角法。它的基本思想是给运输表中左上
8、角的变量 分配运输量以确定产销关系。 小元素法，或最小成本法。它的基本思想是就近供应，即从运输表中运价最小的格子开始分配运输量以确定产销关系。 元素差额法 ,又称沃格尔近似法，简称 VAM 法。它是从运输表中各行和各列的最小元素和次小元素的差额来确定产销关系。改进初始基本可行解的方法有两种： 闭回路法。这种方法需要对每一个空格寻找一条闭回路，并根据闭回路求出每个空格的检验数。当运输问题中 m 和 n 较大时，计算检验数的工作量很大。 位势法，或 乘数 法。先对初始调运方案求出位势，然后求各空格的检验数。当所有的检验数均为非负时，就得到最优方案。如果出现负的检验数，则从检验数为负的空格出发，作闭
9、回路，重新计算检验数，作进一步调整。用位势法求检验数就是对偶问题的表上作业法。 对于实际的运输问题，上述优化方法很难将运输过程中所发生的费用都考虑进去，因此，如果教条地采用上述优化方法直接进行优化，则很难保证此方案是真正的最佳方案。 要根据具体情况，综合应用各种优化技术求其最优的调运方案。 三、 课题的研究内容及拟采取 的研究方法（技术路线）、难点及预期达到的目标 （ 1）研究内容及研究方法 本课题主要探讨了如何判别一个运输问题的调运方案是最优，对通常采用的两种闭回路法或位势法做综述整理详见文献 8-9，同时探讨更好的一次性算法详见文献 10， 既避免了闭回路法中对所有非基变量检验数的一一计算
10、 ,又回避了位势法中需要多次求解线性方程组以计算位势的过程。本课题的目标就是利用已有或已得到的算法对实际问题进行分析研究。 （ 2）研究难点 闭回路法、位势法等方法计算量大，有缺陷，主要在于为了判别调整后的方案是否达到最优 ,需要对原始运价 矩阵重新进行计算 ,导致计算量偏大。 （ 3）预期达到的目标 通过对本课题的研究 ,预期达到的目的如下：第一， 熟悉高等代数及运筹学的知识及其相关概念、性质； 第二， 具有分析问题，解决问题的基本能力； 第三， 会用相关的数学知识解决实际问题并对问题进行求解； 四、 论文详细工作进度和安排 第七学期第 9 周至第 10 周：确定论文题目；开始查阅文献资料，
11、收集各种纸质、电子文件信息、材料并对其进行加工整理，形成系统材料；确定外文翻译资料； 第七学期第 11 周至第 12 周：收集资料，阅读相关文献，分析资料，完成外文翻译；对运输问题的背景和 意义形成系统材料，并对运输问题的算法作系统整理完成外文翻译； 第七学期第 13 周至第 17 周：认真阅读文献资料，加以归纳总结，完成文献综述，深入分析运输问题的算法及其缺陷，建立研究和解决问题的基本方案和技术路线，撰写开题报告； 第七学期第 18 周：完成网上确认；上传外文翻译，文献综述、开题报告 . 第八学期第 1 周至第 3 周：全面开展课题研究，按照研究方案和路线撰写论文，对运输问题的算法加以改进并
12、具体分析，并完成论文初稿； 第八学期第 4 周至第 10 周：进入实习单位进行毕业实习，对论文进行修改。继续完善论文初稿，把运输 问题的算法及其改进的算法作详细整理，此阶段任务着重对实际问题加以具体应用，完成研究任务； 第八学期第 11 周至第 12 周 : 对论文进行修改完善，定稿；对运输问题及其算法问题作研究总结； 第八学期第 13 周至第 14 周 : 做好毕业论文答辩准备事项，进行答辩 . 五、 主要参考文献 1 胡运权 . 运筹学 (第三版 )M.北京 :清华大学出版社， 2007.4. 2 李敏 . 运 输 问 题 中 最 优 调 运 方 案 的 新 检 验 法 J. 荆 楚 理
13、工 学 院 学报 ,2009,24(9):71-73. 2李德刚， 罗霞 . 基于用户的综合运输通 道结构配置 J. 西南交通大学学报 , 2005.4:249-253 3李友好 刘晓佳 施其洲 基于网络的运输通道客运流量分配模型 J 交通运输工程与信学报 2005.6： 57-62 4朱健梅 竞争性运输通道选择的博弈模型研究 J 西南交通大学学报 2003.6： 336-340 5 Hamdy A.Taha. Operations Research An Introduction( 运 筹 学 导论 )M. 北京：人民邮电出版社， 2007,01. 6 林同曾 .运筹学 M.北京 :机械工业出版 社 ,1986,6. 7郭强 .一般网络上的运输问题及其算法 M. 西北工业大学 ,2005,4. 8卢厚清，张永良求解运输问题的一种算法 J运筹与管理， 1999(1)： 27 33 9 王建平，李玉萍运输问题中最优调运方案的检验 J河南科学， 2007(3)： 367 371 10 李敏 . 运 输 问 题 中 最 优 调 运 方 案 的 新 检 验 法 J. 荆 楚 理 工 学 院 学报 ,2009,24(9):71-73.
