最优化结课论文

《最优化结课论文》由会员分享，可在线阅读，更多相关《最优化结课论文（6页珍藏版）》请在金锄头文库上搜索。

1、最优化方法课程论文最优化方法课程论文姓名：李涛姓名：李涛专业：检测专业：检测 s131s131学号：学号：201371236201371236学院：电信学院学院：电信学院求解一般线性规划的方法求解一般线性规划的方法单纯形法单纯形法【摘要摘要】 在最优化方法课程的学习过程中，我发现线性规划是其的一个重要分 支，它是研究在满足一组线性约束条件下，使某一线性目标函数达到最优的问 题。单纯形法是被 G.B.Dantzig（丹齐克）提出来以后，线性规划的理论趋向 成熟，实际应用领域日益广泛和深入。随着计算机能够初级成千上万个约束条 件和决策变量的线性规划之后，线性规划的应用领域更加广泛了。【关键字关键字

2、】 单纯形法 迭代法 对偶单纯形法一单纯形法的产生和发展一单纯形法的产生和发展求线性规划问题最优解的单纯形法是由 G.B.Dantzig（丹齐克）在 1947 年 提出的，这是 20 世纪数学界最重大的成果之一，由于这一方法的有效性，几十 年来一直在几乎所有的领域得到广泛的应用。近年来，对于大规模的线性规划 问题，尽管它受到了内点算法的挑战，但单纯形法还是收到广大用户的青睐。当最优化问题中的目标函数与约束函数都是变量的线性函数时称为nxR线性规划。工程与管理科学中大量的问题都是变量数目成百上千，乃至上万或 数十万的线性规划问题。学习和研究线性规划的求解方法，不仅可以用于求解 大量的实际线性规划

3、问题，而且可以用于非线性最优化问题的求解，这是因为 当用迭代法求一个非线性最优化问题时，如果我们在迭代点对问题中的有关函 数取局部线性近似，所的问题就是一个线性规划问题。 单纯形法同其他的数值求解方法一样是一种迭代法，它根据线性规划问题 的特点在问题可行域的顶点中逐步确定问题的最优解。在每一个是基本可行解 的迭代点（即顶点），如果它不是最优的，单纯形法从与该顶点相连接的边中 确定一个使目标函数值下降的边，沿该边移动可以确定一个与该顶点相邻且目 标函数又优于该顶点的新顶点（新的基本可行解）。由于可行域的顶点数是有 限的，如果每一次的移动都能使目标函数值下降，则经过有限次的移动方法必 须终止于问题

4、的一个最优顶点。 考察标准形线性规划问题min( ) . .,0Tf xc x st Axb x设作为一个基本可行解，单纯形法首先检验它的最优性。如果它不是最( )kxF优的，确定与该顶点相连的一条使目标函数下降的边；接下来确定沿这条边移 动可以到达另一个更优的相邻顶点，也就是得出一个新的基本可行解。 虽然单纯形法是求解线性规划问题的最有效的方法，但是在很多情况下不 能直接用或效率不高，因此人们就开始寻找更有效解决问题的方法。从而对单 纯形法进行了改进的发展。 二阶段法 对于如下形式的线性规划问题，不能直接应用单纯形法来求解。min( ) . .,0Tf xc x st Axb x为此，Dan

5、tzig 引进松弛变量来把线性规划问题进行转化，即大M法。然后，利 用单纯形法求出原问题的一个基本可行解，再利用单纯形法求出原问题的最优 解。这样两次应用单纯形法求解线性规划问题叫做二阶段法。 扰动法和Bland 法 前面讨论的利用单纯形法求解线性规划问题是约束线性函数非退化的情况 下得到。约束线性函数退化的情况下，可能出现循环现象，如果出现循环现象， 可以用扰动法。扰动法的 主要思想是如果对常数项 做一个扰动，使变动以后得到的线性规划问题是bb 非退化的，则可以单纯形法求解。经过有限次的迭代可得到新问题的解。再把b 重新变回来，从而得到原问题的解。换句话说，扰动就相当于增加松弛变量。 R.G

6、. Bland 于1976 年提出一个避免循环的方法。此方法的思想是: 利用 单纯形法求解线性规划问题中查看检验数时，如果几个检验数是正的，则选择 下标最小的非基变量作进基变量。同时基变量中选择下标最小的作离基变量。 Bland 的理论价值很高，但计算效率低。 改进的单纯形法 改进的单纯形法是Dantzig 于1954 年提出的，利用单纯形法求解线性规划 问题时，经过每次换基，整个单纯形表都要重新制作，导致计算效率低。故为 了提高效率，只关注检验数、进基向量和离基向量。这样，虽然关注的数据少 了，但关注的内容不变，因此大大提高了计算的有效性而确保找到最优解。到 现在为止，有很多改进的单纯形法出

7、现，其主要思想就是采取更简捷方法来观 察检验数、进基向量和离基向量，从而提高计算效率。二单纯形法的应用二单纯形法的应用单纯形法的应用十分广泛，下面我们举一个在决策方面的用用问题。决策 是为实现某一目标, 运用科学的理论与方法, 系统的分析主观条件, 提出各种 方案, 从中选择出一个能最佳实现目标的最优方案, 以达到最佳的经济效果和 社会效果的过程。因此一个决策问题的成立, 必须具备下列的条件: 有明确的目标(包括总目标和分目标)。 存在两个以上为实现同一目标可相互替代的策略或方案。 在不同的自然情况下, 各策略的实施结果可依据一定的理论与方法估计出 来。 在各种策略中只能确定一个行动方案。 所

8、谓确定型决策指的是决策者对决策目标的未来发展有十分清楚的了解, 其有 关条件都能准确的实例, 每种决策只可能有一种后果。确定型决策除必须具备 决策问题的4个必备条件外, 它还应该有一个特定的条件, 即决策对象所处的自 然状态是确定的。确定型决策的关键在于人们如何正确估计自然状态, 在实践 中人们往往由于无法了解唯一存在着的自然状态而使决策失误。因此从某种意 义上说, 确定 型决策的成败很大程度上依赖于预测的准确性。本文介绍一种线性规划决策方 法来定量评价投标备选项目, 为承包商做出正确投标决策提供理论依据。 下面以某承包商要在同一时间内对两个不同的项目进行投资决策的例子来说明如何求解此类问题。

9、某建设工程承包公司准备同时承包两个项目A和B, 但是现 在要求其每年消耗的总人工费、机械费和材料费不超过150万元, 总耗项目措施 费及其他建设费不超过100万元, 两个项目每年分别的消耗费用见表2。如若项 目A 每年能获得利润200万元, 项目B 每年能获得利润100万元。请问两个项目 的工期各自控制在多久, 可以使该承包商在充分利用有限资金的条件下获利最 多? 表：费用定额（万元/年）确定决策变量, 建立线性规划的数学模型先设变量:为项目A的工期;为项目B的工期;为对两个不等式约束引入1x2x3x4x的非负松弛变量。再写出其约束条件:123124123430501505020100,0xx

10、xxxxx x x x最后写出目标函数: max123420010000Zxxxx用单纯形解法寻求初始解 表：初始单纯形表注: 选择，作为基变量；选对应的变量进基；选3x4xmax(0)jjCZ1x对应的基变量出基；表中的“”表示该列为主元列,minB 列元素 主元列正元素4x“”表示该行为主元行,“（）”表示该括号中的数字为该表的主元素。 用单纯形解法寻求最优解 表：最终单纯形表注: 所有的检验数 均为非正值, 即说明该表已经成为最优表。jjCZ通过找主元、做初等变换得时的最优为:0jjCZ*2090001938T x,即是=20/19年=1.053年=385天, = 90/38年= 2.3

11、68年= 865天, , 1x2x340xx相对应的目标函数最大值为= 447.37万元。即该承包商的最佳投标方案为:maxZ必须将A项目的工期控制在385天,B项目的工期控制在865天内, 最后可以获利 447.37万元。三对偶单纯形法的产生三对偶单纯形法的产生与单纯形法相对应的还有对偶单纯形法，对偶理论是最优化中很重要的理 论。对每一个线性规划问题，可以构造另一个与之相应且密切的线性规划问题， 如果前者称为原是问题，后者就称为对偶问题。线性规划的原始问题和对偶问 题无论从数学的角度还是从经济的角度都有十分密切的关系。四单纯形法所面临的的问题四单纯形法所面临的的问题单纯形法从其产生日起，因为

12、其能有效的解决各类线性规划问题而得到越 来越广泛的应用。随着线性规划问题规模的扩大，对单纯形法性能的了解也变 得十分必要。大量的统计分析和理论研究表明单纯形法求解线性规划问题的平 均迭代次数是问题约束个数的一个不大的倍数。但是我们假设所需的运算工m 作量的阶数是以幂指数计算的，那么按照我们现在计算机的工作效率，得到结果将会是年后的事了。虽然这是人为设想的最坏情况，但这方面的研究144 10工作者却提出了两个问题： 对线性规划问题是否存在时间复杂性是多项式的算法； 如果存在多项式时间算法，如何设计这样的算法。 对于第一个问题，前苏联数学家 Khachiyan 在 1979 年作出了正面回答，提

13、出了椭球算法求不等式问题的解，并证明了算法的时间复杂性是多项式的。利 用对偶理论，线性规划问题可以转化成不等式问题，这就明确回答了对线性规划存在多项式算法，但是计算的实际表明，椭球算法的效果要比单纯形法差得 多，不是一个又实用价值的算法。 对于第二个问题的回答始于在美国贝尔工作室工作的印度数学家 Karmarkar 在 1984 年的杰出工作。他对线性规划的求解提出了一个具有多项式 时间复杂度的内点算法。现如今，内点算法已经成为求解大规模线性规划问题 的有效算法之一。我们已经知道，求线性规划问题解的单纯形法在问题的基本 可行解中确定最优解，在几何上，每次迭代都是沿着可行域的边界从一个顶点 到另一个更好的顶点移动来实现。而内点算法却完全不同，他是从可行域中的 一个严格内点开始，产生一个使目标函数值逐步改善的严格内点序列，并最终 收敛于问题的最优解。五结束语五结束语线性规划加速了数学规划的普及。线性规划是有史以来传播速度最快的学 科之一。诞生后很快就普及五大洲，并几乎应用到所有的行业，故后兴起的整 数规划、二次规划和非线性规划等倍受关注、期待和欢迎。我对单纯形法只是 简单的了解了一下，以上有很多内容是通过查资料而得到的，有不足之处可以 指出。