线性规划与非线性规划算法综述开题报告

 2021-08-08 02:24:32

全文总字数:1222字

1. 研究目的与意义

线性规划(LinearProgramming简称LP)是运筹学的一个重要分支,自1947年丹齐克(G.B.Dantzig)提出了一般线性规划问题求解法单纯形法之后,线性规划在理论上变得趋向成熟,在实际运用中也日益变得广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后,线性规划的适用领域更为广泛了,从解决技术问题的最优化设计,到工业、农业、商业、交通运输业、军事、经济计划和管理决策领域都可以发挥重大作用,它已是现代科学管理的重要手段之一。

一般来说,解非线性规划问题要比求解线性规划问题困难得多,而且也不像线性规划那样有统一的数学模型及如单纯形法这一通用解法。非线性规划的各种算法大都有自己特定的适用范围。都有一定的局限性,到目前为止还没有适合于各种非线性规划问题的一般算法。这正是需要人们进一步研究的课题。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用,为最优设计提供了有力的工具。例如:如何在现有人力、物力、财力条件下合理安排产品生产,以取得最高的利润;如何设计某种产品,在满足规格、性能要求的前提下,达到最低的成本;如何确定一个自动控制系统的某些参数,使系统的工作状态最佳;如何分配一个动力系统中各电站的负荷,在保证一定指标要求的前提下,使总耗费最小;如何安排库存储量,既能保证供应,又使储存费用最低;如何组织货源,既能满足顾客需要,又使资金周转最快等。对于静态的最优化问题,当目标函数或约束条件出现未知量的非线性函数,且不便于线性化,或勉强线性化后会招致较大误差时,就可应用非线性规划的方法去处理。

2. 国内外研究现状分析

一、线性规划

法国数学家J.-B.-J.傅里叶和C.瓦莱-普森分别于1832和1911年独立地提出线性规划的想法,但未引起注意。1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题,也未引起重视。1947年美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法,为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域,扩大了它的应用范围和解题能力。50年代后对线性规划进行大量的理论研究,并涌现出一大批新的算法。例如,1954年C.莱姆基提出对偶单纯形法,1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题,1956年A.塔克提出互补松弛定理,1960年G.B.丹齐克和P.沃尔夫提出分解算法等。1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法,并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大,建立线性规划模型的方法。

二、非线性规划

解决最优化问题的算法分为经典优化算法和启发式优化算法。经典算法的确立可以从丹齐克(G.B.Dantzig1947)提出解决线形规划的单纯形(Simplexmethod)开始,但单纯形不是多项式算法。随后,Kamaka提出了椭球算法(多项式算法),内点法。对于非线性问题,起初人们试图用线性优化理论去逼近求解非线性问题,但效果并不理想。后来的非线性理论大多都建立在二次(凸)函数的基础上,也就用二次函数去逼近其他非线性函数。在此基础上提出许多优化经典的优化算法。无约束的优化算法包括:最速下降法(steepest)、共轭梯度法、牛顿法(NewtonAlgorithm)、拟牛顿法(pseudoNewtonAlgorithms)、信赖域法。约束优化算法包括:拉格朗日乘子法(AugmentedLagrangianAlgorithms),序列二次规划(SQP)等。非线性规划的一个重要理论是1951年Kuhn-Tucker最优条件(简称KT条件)的建立.此后的50年代主要是对梯度法和牛顿法的研究.以Davidon(1959),Fletcher和Powell(1963)提出的DFP方法为起点,60年代是研究拟牛顿方法活跃时期,同时对共轭梯度法也有较好的研究.在1970年由Broyden,Fletcher,Goldfarb和Shanno从不同的角度共同提出的BFGS方法是目前为止最有效的拟牛顿方法.由于Broyden,Dennis和More的工作使得拟牛顿方法的理论变得很完善.70年代是非线性规划飞速发展时期,约束变尺度(SQP)方法(Han和Powell为代表)和Lagrange乘子法(代表人物是Powell和Hestenes)是这一时期主要研究成果.计算机的飞速发展使非线性规划的研究如虎添翼.80年代开始研究信赖域法、稀疏拟牛顿法、大规模问题的方法和并行计算,90年代研究解非线性规划问题的内点法和有限储存法.可以毫不夸张的说,这半个世纪是最优化发展的黄金时期.以后随着电子计算机的普遍使用,非线性规划的理论和方法有了很大的发展,其应用的领域也越来越广泛,特别是在军事,经济,管理,生产过程自动化,工程设计和产品优化设计等方面都有着重要的应用。

3. 研究的基本内容与计划

研究内容、方法:线性规划与无约束、约束非线性规划算法及其应用实例

1、阐述线性规划与无约束、约束非线性规划基本概念和应用范畴。

2、列出线性规划与无约束、约束非线性规划的理论知识和方法。

剩余内容已隐藏,您需要先支付后才能查看该篇文章全部内容!

4. 研究创新点

1、详细阐述线性规划与无约束、约束非线性规划的各种相关算法,比较各种算法的优缺点并加以总结。

2、原理、方法、算法和实例分析相结合。

剩余内容已隐藏,您需要先支付 10元 才能查看该篇文章全部内容!立即支付

课题毕业论文、开题报告、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。