最优化结课论文

《最优化结课论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

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

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

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

6、的解。换句话说，扰动就相当于增加松弛变量。R.G.Bland于1976年提出一个避免循环的方法。此方法的思想是：利用单纯形法求解线性规划问题中查看检验数时，如果几个检验数是正的，则选择下标最小的非基变量作进基变量。同时基变量中选择卜•标最小的作离基变量。Bland的理论价值很高，但计算效率低。•改进的单纯形法改进的单纯形法是Dantzig于1954年提出的，利用单纯形法求解线性规划问题时，经过每次换基，整个单纯形表都要重新制作，导致计算效率低。故为了提高效率，只关注检验数、进基向量和离基向量。这样，虽然关注的数据少了，但关注的内容不变

7、，因此大大捉高了计算的冇效性而确保找到最优解。到现在为止,有很多改进的单纯形法出现，其主要思想就是采取更简捷方法来观察检验数、进基向量和离基向量，从而提高计算效率。一.单纯形法的应用单纯形法的应用十分广泛，下而我们举一个在决策方而的用用问题。决策是为实现某一目标，运用科学的理论与方法，系统的分析主观条件，提出各种方案，从屮选择出一个能最佳实现口标的最优方案，以达到最佳的经济效果和社会效果的过程。因此一个决策问题的成立，必须具备下列的条件：•有明确的目标(包括总目标和分目标)。•存在两个以上为实现同一目标可相互替代的策略或方案。•在不同

8、的自然情况下，各策略的实施结果可依据一定的理论与方法估计出来。•在各种策略中只能确定一个行动方案。所谓确定型决策指的是决策者对决策目标的未來发展有十分清楚的了解，其有关条件都能准确的实例，每种决策只可能冇一种后果。确定型