线性双层规划性质和算法的研究

《线性双层规划性质和算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、论文题目：线性双层规划的性质和算法研究作者姓名：张志江入学时间：2005年9月专业名称：应用数学研究方向：数学模型与计算机算法研究指导教师：赵茂先职称：教授论文提交日期：2008年5月论文答辩日期：2008年6月授予学位日期：STUDYONTHEPROPERTIESANDALGORITHMSOFTHELINEARBILEVELPROGRAMMINGADissertationsubmittedinfulfillmentoftherequirementsofthedegreeofMASTEROFS

2、CIENCEfromShandongUniversityofScienceandTechnologybyZhangZhijiangSupervisor:ProfessorZhaoMaoxianCollegeofInfoScienceandEngineeringMay2008声明本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于其它任何学术机关作鉴定。硕士生签名：日期：AFFIRMATIONIdeclarethatthis

3、dissertation,submittedinfulfillmentoftherequirementsfortheawardofMasterofScienceinShandongUniversityofScienceandTechnology,iswhollymyownworkunlessreferencedofacknowledge.Thedocumenthasnotbeensubmittedforqualificationatanyotheracademicinstitute.Signature:Da

4、te:山东科技大学硕士学位论文摘要摘要许多实际问题，如生产计划、资源分配和工程设计问题等，需要考虑系统的层次性，即在整个系统中不只一个决策者，并且它们控制不同的决策变量和目标函数。用传统的数学规划技术已不能较好地解决这类问题，因此多层规划已逐步引起人们的重视。双层规划是多层规划的基本形式，任何多层规划可以看作是双层规划的复合。因而双层规划具有重要的研究价值。论文分六章进行讨论：第1章绪论部分着重介绍了双层规划的主要特点及其数学模型，对双层规划在主要领域的应用和求解算法的研究现状进行了综述。第2章讨论了

5、线性双层规划问题，介绍了线性双层规划数学模型、概念和一些性质，并总结了目前求解线性双层规划的主要思想和方法。论文第3、4、5章是本文研究的主要内容。第3章通过分析线性双层规划转化形式，引入平衡点概念，利用平衡点分析线性双层规划的有关性质和最优性条件。在平衡点基础上，对线性双层规划上层目标函数值进行定界，利用二分法原理，构造一个双线性规划来修正当前的界，直到求得线性双层规划的全局最优解。提出了求解线性双层规划问题的å−全局最优解算法，并验证了算法的有限终止性和可行性。第4章由于线性双层规划的约束条件全部是线性

6、函数，而单纯形方法是目前解决线性规划最有力的工具，如何将线性双层规划进行变形，进而利用单纯形方法去求解问题是本章考虑的对象。基于这种思路，对可行极点对应的检验数进行讨论，提出两种求解线性双层规划局部最优解的单纯形方法，第一种是先对可行极点进行单纯形迭代，然后判断新得到极点的可行性；第二种是先选取合理的进基变量，然后进行迭代，确保得到新的可行极点。第5章在局部最优解的基础上，利用割平面的思想，提出两个求解线性双层规划的全局最优解算法。最后，总结论文所做的工作，并展望了以后研究的工作方向。关键词：双层规划；线性

7、双层规划；平衡点；双线性规划；å−全局最优解；单纯形方法；局部最优解山东科技大学硕士学位论文摘要AbstractManyproblems,suchasproductiveplan,resourcedistribution,engineeringdesignproblemsneedconsideringthehierarchycharacterofsystem,thatisahierarchicaldecisionproblemmayhasmorethanonedecisionmakers,whichhav

8、etheirowndecisionvariablesandobjectives.Thetraditionalmathematicaloptimizationmethodscouldn'tsolvetheseproblemssuccessfully.Forthissake,multilevelprogramminghascaughtpeople'sattentions.Bilevelprogrammingisthe