还剩7页未读,继续阅读
文本内容:
线性规划与非线性规划线性linear,指量与量之间按比例、成直线的关系,在数学上可以理解为一阶导数为常数的函数;非线性non-linear则指不按比例、不成直线的关系,一阶导数不为常数如问两个眼睛的视敏度是一个眼睛的几倍?很容易想到的是两倍,可实际是6-10倍!这就是非线性激光也是非线性的!天体运动存在混沌;电、光与声波的振荡,会突陷混沌;地磁场在400万年间,方向突变16次,也是由于混沌甚至人类自己,原来都是非线性的与传统的想法相反,健康人的脑电图和心脏跳动并不是规则的,而是混沌的,混沌正是生命力的表现,混沌系统对外界的刺激反应,比非混沌系统快非线性规划nonlinear programming具有非线性约束条件或目标函数的数学规划,是运筹堂的一个重要分支非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的极值问题,且目标函数和约束条件至少有一个是未知量的非线性函数目标函数和约束条件都是线性函数的情形则属于线性规划简史非线性规划是20世纪50年代才开始形成的一门新兴学科1951年H.W.库恩和A.W.塔克发表的关于最优性条件(后来称为库恩-塔克条件)的论文是非线性规划正式诞生的一个重要标志在50年代还得出了可分离规划和二次规划的n种解法,它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的50年代末到60年代末出现了许多解非线性规划问题的有效,的算法70年代又得到进一步的发展非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用,为最优设计提供了有力的工具实例例1(投资决策问题)某企业有n个项目可供选择投资,并且至少要对其中一个项目投资已知该企业拥有总资金A元,投资于第i个项目需花资金ai元,并预计可收益bi元试选择最佳投资方案解设投资决策变量为则投资总额为Eaixi,投资总收益为》bixi因为该公司至少要对一个项目投资,并且总的投资金额不能超过总资金,故有限制条件另外,由于xi只取值或1,所以还有最佳投资方案应是投资额最小而总收益最大的方案,所以这个最佳投资决策问题归结为总资金以及决策变量取或1的限制条件下,极大化总收益和总投资之比因此,其数学模型为上面例题是在一组等式或不等式的约束下,求一个函数的最大值或最小值问题,其中目标函数或约束条件中至少有一个非线性函数,这类问题称之为非线性规划问题,简记为NP1可概括为一般形式NP,,其中x=[xl...xn]称为模型NP的决策变量f称为目标函数gi和hj称为约束函数另外,gix=O称为等式约束,hjx=0称为不等式约束常见问题对于一个实际问题,在把它归结成非线性规划问题时,一般要注意如下几点i确定供选方案首先要收集同问题有关的资料和数据,在全面熟悉问题的基础上,确认什么是问题的可供选择的方案,并用一组变量来表示它们ii提出追求目标经过资料分析,根据实际需要和可能,提出要追求极小化或极大化的目标并且,运用各种科学和技术原理,把它表示成数学关系式iii给出价值标准在提出要追求的目标之后,要确立所考虑目标的好或坏的价值标准,并用某种数量形式来描述它iv寻求限制条件由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果,因此还需要寻找出问题的所有限制条件,这些条件通常用变量之间的一些不等式或等式来表示数学模型对实际规划问题作定量分析,必须建立数学模型建立数学模型首先要选定适当的目标变量和决策变量,并建立起目标变量与决策变量之间的函数关系,称之为目标函数然后将各种限制条件加以抽象彳导出决策变量应满足的一些等式或不等式,称之为约束条件非线性规划问题的一般数学模型可表述为求未知量xl,x2,…,xn,使满足约束条件gixl,...,xn0i=hjxl,...,xn=0j=L…,P,并使目标函数fxl…,xn达到最小值或最大值其中f,诸gi和诸hj都是定义在n维向量空间Rn的某子集D定义域上的实值函数,且至少有一个是非线性函数上述模型可简记为min fxs.t.gix0i=hjx=Oj=l,...,p其中x=xl,…,xn属于定义域D,符号min表示求最小值,符号st表示受约束于定义域D中满足约束条件的点称为问题的可行解全体可行解所成的集合称为问题的可行集对于一个可行解x*,如果存在x*的一个邻域,使目标函数在x*处的值fx*优于指不大于或不小于该邻域中任何其他可行解处的函数值,则称x*为问题的局部最优解简称局部解X如果fx*优于一切可行解处的目标函数值,则称x*为问题的整体最优解简称整体解X实用非线性规划问题要求整体解,而现有解法大多只是求出局部解一维最优化方法指寻求一元函数在某区间上的最优值点的方法这类方法不仅有实用价值,而且大量多维最优化方法都依赖于一系列的一维最优化常用的一维最优化方法有黄金分割法、切线法和插值法
①黄金分割法又称
0.618法它适用于单峰函数其基本思想是在初始寻查区间中设计一列点,通过逐次比较其函数值,逐步缩小寻查区间,以得出近似最优值点
②切线法又称牛顿法它也是针对单峰函数的其基本思想是在一个猜测点附近将目标函数的导函数线性化,用此线性函数的零点作为新的猜测点,逐步迭代去逼近最优点
③插值法又称多项式逼近法其基本思想是用多项式(通常用二次或三次多项式)去拟合目标函数此外,还有斐波那契法、割线法、有理插值法、分批搜索法等无约束最优化方法指寻求n元实函数f在整个n维向量空间Rn上的最优值点的方法这类方法的意义在于虽然实用规划问题大多是有约束的,但许多约束最优化方法可将有约束问题转化为若干无约束问题来求解无约束最优化方法大多是逐次一维搜索的迭代算法这类迭代算法可分为两类一类需要用目标函数的导函数,称为解析法另一类不涉及导数,只用到函数值,称为直接法这些迭代算法的基本思想是在一个近似点处选定一个有利搜索方向,沿这个方向进行一维寻查彳导出新的近似点然后对新点施行同样手续,如此反复迭代,直到满足预定的精度要求为止根据搜索方向的取法不同,可以有各种算法属于解析型的算法有
①梯度法又称最速下降法这是早期的解析法,收敛速度较慢
②牛顿法收敛速度快,但不稳定,计算也较困难
③共初梯度法收敛较快,效果较好
④变尺度法这是一类效率较高的方法其中达维登-弗莱彻-鲍威尔变尺度法,简称DFP法,是最常用的方法属于直接型的算法有交替方向法(又称坐标轮换法X模式搜索法、旋转方向法、鲍威尔共辗方向法和单纯形加速法等约束最优化方法指前述一般非线性规划模型的求解方法常用的约束最优化方法有4种
①拉格朗日乘子法它是将原问题转化为求拉格朗日函数的驻点
②制约函数法又称系列无约束最小化方法,简称SUMT法它又分两类,一类叫惩罚函数法,或称外点法;另一类叫障碍函数法,或称内点法它们都是将原问题转化为一系列无约束问题来求解
③可行方向法:这是一类通过逐次选取可行下降方向去逼近最优点的迭代算法如佐坦迪克法、弗兰克-沃尔夫法、投影梯度法和简约梯度法都属于此类算法
④近似型算法这类算法包括序贯线性规划法和序贯二次规划法前者将原问题化为一系列线性规划问题求解,后者将原问题化为一系列二次规划问题求解凸规划这是一类特殊的非线性规划在前述非线性规划数学模型中,若f是凸函数,诸gi都是凹函数,诸hj都是一次函数,则称之为凸规划所谓f是凸函数,是指f有如下性质它的定义域是凸集,且对于定义域中任意两点x和y及任一小于1的正数a,下式都成立fl-ax+ay a1-a fx+af y将上述不等式中的不等号反向即得凹函数的定义所谓凸集,是指具有如下性质的集合连结集合中任意两点的直线段上的点全部属于该集合对于一般的非线性规划问题,局部解不一定是整体解但凸规划的局部解必为整体解,而且凸规划的可行集和最优解集都是凸集二次规划一类特殊的非线性规划它的目标函数是二次函数,约束条件是线性的求解二次规划的方法很多较简便易行的是沃尔夫法它是依据库恩-塔克条件,在线性规划单纯形法的基础上加以修正而成的此外还有莱姆基法、毕尔法、凯勒法等几何规划几何规划一类特殊的非线性规划它的目标函数和约束函数都是正定多项式(或称正项式\几何规划本身一般不是凸规划,但经适当变量替换,即可变为凸规划几何规划的局部最优解必为整体最优解求解几何规划的方法有两类一类是通过对偶规划去求解;另一类是直接求解原规划,这类算法大多建立在根据几何不等式将多项式转化为单项式的思想上应用问题在经营管理、工程设计、科学研究、军事指挥等方面普遍地存在着最优化问题例如如何在现有人力、物力、财力条件下合理安排产品生产,以取得最高的利润;如何设计某种产品,在满足规格、性能要求的前提下,达到最低的成本;如何确定一个自动控制系统的某些参数,使系统的工作状态最佳;如何分配一个动力系统中各电站的负荷,在保证一定指标要求的前提下,使总耗费最小;如何安排库存储量,既能保证供应,又使储存费用最低;如何组织货源,既能满足顾客需要,又使资金周转最快等对于静态的最优化问题,当目标函数或约束条件出现未知量的非线性函数,且不便于线性化,或勉强线性化后会招致较大误差时,就可应用非线性规划的方法去处理参考书目席少霖、赵凤治《最优化计算方法》,上海科学技术出版社,上海,1983阿佛里耳著,李元熹等译《非线性规划一分析与方法》,上海科学技术出版社,上海,1979M.Avriel,Nonlinear Programminganalysis andmethods,Prentice-Hall,
1976.赫梅布劳著,张义集等译《实用非线性规划》,科学出版社,北京,1981D.M.Himmelblau,Applied NonlinearProgramming,McGraw-Hill NewYork,
1972.z。