非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划是20世纪50年代才开始形成的一门新兴学科。70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。
中文名非线性规划
应用工程、管理、经济
所属学科运筹学
外文名nonlinear programming
意义为最优设计提供了有力的工具
概述
非线性规划
nonlinear programming
具有非线性 约束条件或 目标函数的数学规划，是 运筹学的一个重要分支。非线性规划研究一个 n元实函数在一组等式或不等式的约束条件下的极值问题，且 目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是 线性函数的情形则属于线性规划。
简史
非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年H.W.库恩和A.W.塔克发表的关于最优性条件（后来称为库恩－塔克条件）的论文是非线性规划正式诞生的一个重要标志。在50年代还得出了可分离规划和 二次规划的n种解法，它们大都是以G.B.丹齐克提出的 解线性规划的 单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效的 算法，70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。20世纪80年代以来，随着计算机技术的快速发展，非线性规划方法取得了长足进步，在信赖域法、稀疏 拟牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果。
深入解析
例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（ 定义域）上的实值函数，且至少有一个是非 线性函数。
上述模型可简记为：
min f(x)
s.t. gi(x）≥0 i=1，…，m
hj(x)=0 j=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， Applied Nonlinear Programming， McGraw-Hill，New York，1972.)
相关推荐
最新文章