【数学与应用数学专业】【毕业论文】单纯形法的综述及其应用

《【数学与应用数学专业】【毕业论文】单纯形法的综述及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、（　20　届）本科毕业论文单纯形法的综述及其应用30摘要：单纯形法是解线性规划问题的一种重要方法，也是最主要的算法，本文首先介绍单纯形法的历史背景，然后主要阐述了单纯形法的一些基本计算步骤，指出单纯形法在解决线性规划问题时一般形式、最简单单纯形表的结构，并通过一些具体的题目说明单纯形法的基本要点．另外，介绍了解一般线性规划问题中引入人工变量的方法，即大M法和两阶段法．以及一些改进的计算方法和计算机算法．最后，介绍了单纯形法在一些实际的线性规划问题中的应用．关键词：线性规划；最优解；单纯形法；人工变量30ReviewoftheSimplexMethodandItsAp

2、plicationAbstract：Thesimplexmethodisanimportantmethodandalsoistheprimaryalgorithmsinsolvingthelinearprogramproblem.Thistextintroducedthehistoricalbackgroundofsimplexmethodandmainlydiscussedsomebasiccalculationstepsofthesimplexmethod,pointedoutthecommonformandthesimpleststructureofsimpl

3、extableauaboutthesimplexmethodinsolvinglinearprogramproblem,andintroducedthebasicpointsofthesimplexmethodbysomeidiographictopics.Thenthetextintroducedthemethodofintroducingartificialvariablesingenerallinearprogrammingproblem,namely,BigMMethodandtwo-phasemethod,andintroducedsomeimproved

4、calculationmethodandcomputeralgorithms.Finally,thesimplexmethodisintroducedinsomepracticalapplicationoflinearprogramproblem.Keywords:LinearProgramming;OptimumSolution;SimplexMethod;ArtificialVariables3030目录1前言12单纯形法的原理12.1线性规划问题解的概念22.2单纯形法的计算步骤32.3初始基可行解的确定42.4最优性检验与解的判别53单纯形法的计算73.1单

5、纯形表的计算步骤73.1.1单纯形表73.1.2计算步骤83.2人工变量113.2.1大M法113.2.2两阶段法133.3单纯形法的改进的计算方法173.3.1基于矩阵初等变换初始可行解得算法173.3.2对偶单纯形法194单纯形法的计算机算法225单纯形法的应用235.1单纯形法在企业资源配置中的应用245.2单纯形法在城市轨道列车惰行点搜索中的应用256总结26致谢27参考文献2830301前言线性规划(LinearProgramming,简写LP)是运筹学的一个重要分支，早在20世纪30年代末，前苏联著名的数学家康托洛维奇就提出了线性规划的数学模型．它是研究

6、较早、理论较完善、应用最广泛的一个科学．它所研究的问题主要包括两个方面：一是在一项任务确定后，如何以最低成本（如人力、物力、资源和时间等）去完成这一任务；二是如何在现有资源条件下进行组织和安排，以产生最大收益．因此，线性规划是一组变量的值，使它满足一组线性式子，并且是一个线性函数的最大值（最小值）的数学方法．线性规划不仅仅是一种数学理论和方法，而且已成为现代管理工作中帮助管理者作出科学决策的重要手段[1]．线性规划也是运筹学的一个基本分支，越来越来受到人们的重视．特别是计算机的发展和普及，线性规划如虎添翼，计算能力得到飞速提高，使得它的应用领域更加广泛[2]．而后于

7、1947年由美国数学家G.B.Duntzg提出一般线性规划问题的求解方法——单纯形法，它是线性规划(LinearProgramming,简写LP)问题的通用解法．为线性规划的理论与计算奠定了基础．更使线性规划得以迅速的发展，可用计算机来处理成千上万个约束条件和变量的大规模线性规划问题，在工业、农业、商业、运输业以及决策分析部门都可以发挥作用．从范围来看，小到一个班级的计划安排，大到整个部门，以至国民经济计划的最优化方案分析，它都有用武之地．线性规划具有适应性强、应用面广、计算技术比较简单的特点[1]．从而使得线性规划的应用领域更加的广泛．线性规划这一学科也因此开