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