极大极小对偶理论分析

《极大极小对偶理论分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编号:_《最优化方法》课程设计题目：极大极小对偶理论分析院系：专业：姓名学号：指导教师：日期：2014年01月02日摘要在极大极小对偶理论中，我们寻求原问题和对偶问题之间的求解，对偶单纯形法是非常重要的一种解法。本文主要介绍的对偶单纯形法，对偶单纯形法算法结构简单,容易使用matlab编程实现。在本次实验中,我首先分析对偶单纯形法，了解对偶单纯形法解对偶问题的步骤，进行实例求解，再运用对偶单纯形法的思路编写代码，进行matlab实例求解，加以分析，总结。进行算法比较。我把对偶单纯形法与单纯形法进行比较，先了解单纯形法解决问题的步骤，和实例求解过程，再编写代码，进行实例分

2、析，最后和对偶单纯形法进行比较。通过比较，我发现单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。关键词：极大极小；对偶单纯形法；单纯形法；AbstractInMinimaxdualitytheory,weseekbetweentheoriginalproblemandthedualproblemofsolvingthedualsimplexmethodisaveryimportantonesolut

3、ion.Thispaperdescribesthedualsimplexmethod,dualsimplexmethodalgorithmstructureissimple,easytousematlabprogramming.Inthisexperiment,Ifirstanalysisofthedualsimplexmethod,understandingofthedualsimplexmethodforsolvingthedualprobleminstepsandexamplestosolve,andthenapplytotheideaofdualsimplexm

4、ethodofwritingcode,conductmatlabexamplessolvedanalyze,summarize.Foralgorithmcomparison.Iputthedualsimplexmethodarecomparedwiththesimplexmethod,thefirststeptounderstandthesimplexmethodtosolvetheproblemsolvingprocessandexamples,andthenwritecodetoanalyzeanexample,lastanddualsimplexmethodfor

5、comparison.Bycomparison,Ifoundthesimplexmethodisfeasibletotheoriginalproblemfromoneiterationtoanotherfeasiblesolutionbysolution,untilthenumberoftestoptimalityconditionissatisfied.Dualsimplexruleofthumbistosatisfythedualfeasibilityconditionsfromthegradualdepartureoftheoriginalproblemthrou

6、ghaniterativesearchfortheoptimalsolution.Remaininaniterativeprocessbasedsolutionsfordualfeasibility,leavingtheinfeasibilitygraduallydisappear.Keywords:minimax；Dualsimplexmethod；simplexmethod；目录1、引言12、极大极小对偶理论的描述12.1对偶问题的描述12.2对偶问题的性质22.3对偶单纯形法33、数值实验43.1代码实现43.2算法测试53.3结果分析74、算法比较74.1单纯形

7、法74.2算法实现74.3算法测试94.4算法比较105、总结105.1总结概括105.2个人感言116、参考文献111、引言在计算对偶问题的各种算法中，对偶单纯形法（DualSimplexMethod）和单纯形法（SimplexMethod）是非常重要的两种。1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为