最优化结课论文

最优化方法课程论文引言在我们以前学习的《运筹学》中不难发现，线性规划是其的一个重要分支，它是研究在满足一组线性约束条件下，使某一线性目标函数达到最优的问题。1947年G.B.Dantzig（丹齐克）提出了求解一般线性规划的方法——单纯形法以后，线性规划的理论趋向成熟，实际应用领域日益广泛和深入。随着计算机能够初级成千上万个约束条件和决策变量的线性规划之后，线性规划的应用领域更加广泛了，目前线性规划已成为现代科学管理的重要手段之一，并在国防、科技、农业、工业、商业、交通运输、换将工程、经济计划、管理决策和教育等领域得到了广泛应用。本文将会介绍单纯形法和对偶单纯形法的理论知识及其发展，并列举单纯形法和对偶单纯形法在我们日常生活中的应用实例，谈论这一理论的重要性。一．单纯形法的产生和发展求线性规划问题最优解的单纯形法是由G.B.Dantzig（丹齐克）在1947年提出的，这是20世纪数学界最重大的成果之一，由于这一方法的有效性，几十年来一直在几乎所有的领域得到广泛的应用。近年来，对于大规模的线性规划问题，尽管它受到了内点算法的挑战，但单纯形法还是收到广大用户的青睐。当最优化问题中的目标函数与约束函数都是变量nxR的线性函数时称为线性规划。工程与管理科学中大量的问题都是变量数目成百上千，乃至上万或数十万的线性规划问题。学习和研究线性规划的求解方法，不仅可以用于求解大量的实际线性规划问题，而且可以用于非线性最优化问题的求解，这是因为当用迭代法求一个非线性最优化问题时，如果我们在迭代点对问题中的有关函数取局部线性近似，所的问题就是一个线性规划问题。单纯形法同其他的数值求解方法一样是一种迭代法，它根据线性规划问题的特点在问题可行域的顶点中逐步确定问题的最优解。在每一个是基本可行解的迭代点（即顶点），如果它不是最优的，单纯形法从与该顶点相连接的边中确定一个使目标函数值下降的边，沿该边移动可以确定一个与该顶点相邻且目标函数又优于该顶点的新顶点（新的基本可行解）。由于可行域的顶点数是有限的，如果每一次的移动都能使目标函数值下降，则经过有限次的移动方法必须终止于问题的一个最优顶点。考察标准形线性规划问题min()..,0TfxcxstAxbx设()kxF作为一个基本可行解，单纯形法首先检验它的最优性。如果它不是最优的，确定与该顶点相连的一条使目标函数下降的边；接下来确定沿这条边移动可以到达另一个更优的相邻顶点，也就是得出一个新的基本可行解。为了更进一步的理解单纯形法，我们在《运筹学》中学习了单纯形表，在下面的例子中将会提到。虽然单纯形法是求解线性规划问题的最有效的方法，但是在很多情况下不能直接用或效率不高，因此人们就开始寻找更有效解决问题的方法。从而对单纯形法进行了改进的发展。二阶段法对于如下形式的线性规划问题，不能直接应用单纯形法来求解。min()..,0TfxcxstAxbx为此，Dantzig引进松弛变量来把线性规划问题进行转化，即大M法。然后，利用单纯形法求出原问题的一个基本可行解，再利用单纯形法求出原问题的最优解。这样两次应用单纯形法求解线性规划问题叫做二阶段法。扰动法和Bland法前面讨论的利用单纯形法求解线性规划问题是约束线性函数非退化的情况下得到。约束线性函数退化的情况下，可能出现循环现象，如果出现循环现象，可以用扰动法。扰动法的主要思想是如果对常数项b做一个扰动，使b变动以后得到的线性规划问题是非退化的，则可以单纯形法求解。经过有限次的迭代可得到新问题的解。再把b重新变回来，从而得到原问题的解。换句话说，扰动就相当于增加松弛变量。R.G.Bland于1976年提出一个避免循环的方法。此方法的思想是:利用单纯形法求解线性规划问题中查看检验数时，如果几个检验数是正的，则选择下标最小的非基变量作进基变量。同时基变量中选择下标最小的作离基变量。Bland的理论价值很高，但计算效率低。改进的单纯形法改进的单纯形法是Dantzig于1954年提出的，利用单纯形法求解线性规划问题时，经过每次换基，整个单纯形表都要重新制作，导致计算效率低。故为了提高效率，只关注检验数、进基向量和离基向量。这样，虽然关注的数据少了，但关注的内容不变，因此大大提高了计算的有效性而确保找到最优解。到现在为止，有很多改进的单纯形法出现，其主要思想就是采取更简捷方法来观察检验数、进基向量和离基向量，从而提高计算效率。二．单纯形法的应用单纯形法的应用十分广泛，下面我们举一个在决策方面的用用问题。决策是为实现某一目标,运用科学的理论与方法,系统的分析主观条件,提出各种方案,从中选择出一个能最佳实现目标的最优方案,以达到最佳的经济效果和社会效果的过程。因此一个决策问题的成立,必须具备下列的条件:有明确的目标(包括总目标和分目标)。存在两个以上为实现同一目标可相互替代的策略或方案。在不同的自然情况下,各策略的实施结果可依据一定的理论与方法估计出来。在各种策略中只能确定一个行动方案。所谓确定型决策指的是决策者对决策目标的未来发展有十分清楚的了解,其有关条件都能准确的实例,每种决策只可能有一种后果。确定型决策除必须具备决策问题的4个必备条件外,它还应该有一个特定的条件,即决策对象所处的自然状态是确定的。确定型决策的关键在于人们如何正确估计自然状态,在实践中人们往往由于无法了解唯一存在着的自然状态而使决策失误。因此从某种意义上说,确定型决策的成败很大程度上依赖于预测的准确性。本文介绍一种线性规划决策方法来定量评价投标备选项目,为承包商做出正确投标决策提供理论依据。下面以某承包商要在同一时间内对两个不同的项目进行投资决策的例子来说明如何求解此类问题。某建设工程承包公司准备同时承包两个项目A和B,但是现在要求其每年消耗的总人工费、机械费和材料费不超过150万元,总耗项目措施费及其他建设费不超过100万元,两个项目每年分别的消耗费用见表2。如若项目A每年能获得利润200万元,项目B每年能获得利润100万元。请问两个项目的工期各自控制在多久,可以使该承包商在充分利用有限资金的条件下获利最多?表：费用定额（万元/年）确定决策变量,建立线性规划的数学模型先设变量:1x为项目A的工期;2x为项目B的工期;3x4x为对两个不等式约束引入的非负松弛变量。再写出其约束条件:123124123430501505020100,,,0xxxxxxxxxx最后写出目标函数:max123420010000Zxxxx用单纯形解法寻求初始解表：初始单纯形表注:选择3x，4x作为基变量；选max(0)jjCZ对应的变量1x进基；选minB列元素主元列正元素对应的基变量4x出基；表中的“↑”表示该列为主元列,“←”表示该行为主元行,“（）”表示该括号中的数字为该表的主元素。用单纯形解法寻求最优解表：最终单纯形表注:所有的检验数jjCZ均为非正值,即说明该表已经成为最优表。通过找主元、做初等变换得0jjCZ时的最优为:*2090001938Tx,即是1x=20/19年=1.053年=385天,2x=90/38年=2.368年=865天,340xx,相对应的目标函数最大值为maxZ=447.37万元。即该承包商的最佳投标方案为:必须将A项目的工期控制在385天,B项目的工期控制在865天内,最后可以获利447.37万元。三．对偶单纯形法的产生与单纯形法相对应的还有对偶单纯形法，对偶理论是最优化中很重要的理论。对每一个线性规划问题，可以构造另一个与之相应且密切的线性规划问题，如果前者称为原是问题，后者就称为对偶问题。线性规划的原始问题和对偶问题无论从数学的角度还是从经济的角度都有十分密切的关系。四．单纯形法所面临的的问题单纯形法从其产生日起，因为其能有效的解决各类线性规划问题而得到越来越广泛的应用。随着线性规划问题规模的扩大，对单纯形法性能的了解也变得十分必要。大量的统计分析和理论研究表明单纯形法求解线性规划问题的平均迭代次数是问题约束个数m的一个不大的倍数。但是我们假设所需的运算工作量的阶数是以幂指数计算的，那么按照我们现在计算机的工作效率，得到结果将会是14410年后的事了。虽然这是人为设想的最坏情况，但这方面的研究工作者却提出了两个问题：对线性规划问题是否存在时间复杂性是多项式的算法；如果存在多项式时间算法，如何设计这样的算法。对于第一个问题，前苏联数学家Khachiyan在1979年作出了正面回答，提出了椭球算法求不等式问题的解，并证明了算法的时间复杂性是多项式的。利用对偶理论，线性规划问题可以转化成不等式问题，这就明确回答了对线性规划存在多项式算法，但是计算的实际表明，椭球算法的效果要比单纯形法差得多，不是一个又实用价值的算法。对于第二个问题的回答始于在美国贝尔工作室工作的印度数学家Karmarkar在1984年的杰出工作。他对线性规划的求解提出了一个具有多项式时间复杂度的内点算法。现如今，内点算法已经成为求解大规模线性规划问题的有效算法之一。我们已经知道，求线性规划问题解的单纯形法在问题的基本可行解中确定最优解，在几何上，每次迭代都是沿着可行域的边界从一个顶点到另一个更好的顶点移动来实现。而内点算法却完全不同，他是从可行域中的一个严格内点开始，产生一个使目标函数值逐步改善的严格内点序列，并最终收敛于问题的最优解。五．单纯形法的引申提起单纯形法，就不能不说灵敏度分析。所谓灵敏度分析是指在一个线性规划问题的有关数据，如果价值系数向量c，或约束的右端向量b，或约束系数矩阵A的某些元素发生变化或存在某种程度的误差时，分析最优解*x所受的影响，并如何从原有的最优解确定变化后的最优解。而在实际问题提炼而成的线性规划问题，由于环境、条件、时间以及具体要求等各种可能因素的变化，导致相关数据的变化；其次这些实际数据大部分是通过观测，测量和统计出来的，出现误差是常有的、难免的。因此利用灵敏度分析确定数据有误差或数据发生变化后线性规划问题的最优解是十分必要的。以工厂生产3种产品A,B,C，有5种生产方案为例简单的介绍一下灵敏度分析，下面给出两个表：表：每组方案生产产品的数量及单位售价品种组别单位售价/元12345产量A3244010B612145C265184表：每组方案耗费的资源及生产费用资源组别资源限制12345耗时人工工时/h0461280h/天机器工时/h1121150h/天每组生产费用481930447其中，该工厂与某单位签订合同，规定每天供应A产品至少一个，求收益最大的组合方案。首先设jx为各种方案的组数（1,...,5j），6x为A产品的剩余变量，78,xx分别为工人工时和机器工时的松弛变量，工厂收益为()fx。经过整理，我们可以得到如下线性规划：12345max()203040545fxxxxxx1234623457123458324411046280..2500,1,...,8jxxxxxxxxxxstxxxxxxxj利用单纯形法解上述模型，下面给出最后结果：表1：最优单纯形表影子价格在线性规划中，某一种资源的影子价格是指在当前最优解的基础上，该资源减少一个（很小）单位时目标函数的变化率。而松弛变量的机会成本就是这个资源的影子价格。分析：从表一可以看出，6x的机会成本为8。由于6x是产品A的剩余变量，所以产品A的影子价格为168qz，它的经济意义是：如果多生产A产品1个单位，则将使目标函数减少8元。反之，如果少生产A产品1个单位，则将使目标函数数值增加8元，因此，A产品的订购合同不合理。我们通过单纯形表可以看出8x是机器的松弛变量，它的影子价格为44，所以机器的租费上限应为44元。基变量价值系数的灵敏度分析BCBXb1x2x3x4x5x6x7x8x203040545000201x26100.410-0.2-0.20.4302x16011.40.50-0.20.3-0.6455x8000.2-0.510.4-0.11.