第一章非线性规划理论（1）
第一节非线性优化规划模型及其解的概念, 第二节凸函数与凸规划, 第三节下降迭代算法
第四节一维搜索方法
第一节非线性优化规划模型及其解的概念
线性规划的目标函数和约束条件都是其自变量的线性函数，如果目标函数或约束条件中含有自变量的非线性函数，则这样的规划问题就是非线性规划。有些实际问题可以表示成线性规划，但有些实际问题则需要用非线性规划模型来表达。
例1 求，使得
（1）
该数学模型中目标函数是一个二次函数，因此它是一个非线性规划。
又如：求，使得
（2）
是一个非线性规划。
1.1 非线性规划问题的数学模型
非线性规划数学模型的一般形式为
（3）
其中是维欧氏空间中的向量（点），是目标函数，为约束条件，、都是元实函数。
说明：
（1）由于我们有，当需使目标函数极大化时，只需使其负值极小化即可，因而仅考虑极小化的情况不失一般性。
（2）若某约束条件是“”不等式，仅需要在约束两端乘以“－1”，即可将这个约束变为“”。又由于约束等价于
因而我们可以将非线性规划模型写成下面的形式：
（4）
或
（5）
模型中的称为非线性规划的可行域，而中的元素称为可行解。
1.2 二维问题的图解法
当只有两个决策变量时，求解非线性规划也可以像线性规划那样用图解法。
例2
解：先画出可行域
X2
A
B
C
D
O x1
可行域
等值线
最优解
画出抛物线
，
即图中的曲线，再画出
直线，即图中的
直线，得可行域。
画出等值线
，图中有一条等值线与抛物线
交于B点，当动点从A点出发延
抛物线移动时，动点从A移向B时，目标函数值下降，动点从B移向C 时，目标函数值上升，所以在可行域范围内B点的函数值最小，所以B 点是一个极小点。当动点由C点向D点移动时，目标函数再次下降，在D（4，1）点目标函数值最小，所以D点是最优解。
本例中，B点称为局部极小点，而D点称为全局极小点，即最小点。
1.3 非线性规划的基本概念
1.3.1关局部极小和全局极小的定义
设为定义在维欧氏空间的某一个区域上的元实函数，对于，如果存在某一个使得所有与距离小于的都有，则称为在上的局部极小点，而为局部极小值。如果当时，有，则称为在上的严格局部极小点，而为严格局部极小值。
设为定义在维欧氏空间的某一个区域上的元实函数，如果存在，对于所有，都有，则称为在上的全局极小点，而为全局极小值。如果当时，有，则称为在上的严格全局极小点，而为严格全局极小值。
若将上述的不等式反向，即可得到相应极大点和极大值的定义。
1.3.2 多元函数极值点存在的条件
我们知道对于二阶可微的一元函数极值点存在的条件为
必要条件：
充分条件：对于极小点：且
对于极大点：且
对于无约束多元函数，其极值点存在的必要条件和充分条件与一元函数类似。
1、极值点存在的必要条件
下面的定理1给出了元实函数在点取得极值的必要条件。
定理1 设是维欧氏空间的上的某一个开集，在上有连续的一阶偏导数，且在取得局部极值，则必有
（6）
或写成（7）
此处（8）
为在点处的梯度。满足条件
的称为的驻点或稳定点。
注：由数学分析知识可知，函数的梯度有两个重要性质：
（1）函数在某点的梯度与函数过该点的等值面（或等值线）正交；
（2）梯度向量的方向是函数值增加最快的方向，而负梯度向量的方向是函数值减少最快的方向。
2、二次型
二次型是的二次齐次函数
（9）
式中，即矩阵
（10）
为对称矩阵。
一个二次型唯一对应一个对称矩阵，反之一个对称矩阵也唯一确定一个二次型。
若对于任意，实二次型，则称二次型是正定的，也称对称矩阵为正定的；
若对于任意，实二次型，则称二次型是负定的，也称对称矩阵为负定的；
若对于任意，实二次型，则称二次型是半正定的，也称对称矩阵为半正定的；
若对于任意，实二次型，则称二次型是半负定的，也称对称矩阵为半负定的。
由线性代数知道，实二次型是正定（对称矩阵为正定）的充要条件是对称矩阵左上角各阶主子式都大于零，即
（11）
实二次型是负定（对称矩阵为负定）的充要条件是对称矩阵左上角各阶主子式负正相间，即
（12）
（13）
3、极值点存在的充分条件
下面的定理2给出了元实函数在点取得极小值的充分条件。
定理2 设是维欧氏空间的上的某一个开集，在上具有连续的二阶偏导数，若，且正定，则为的严格局部极小点。
其中（14）
为在点处的海赛（Hesse）矩阵。
第二节凸函数与凸规划
2.1 凸函数与凹函数
1、定义
设是定义在维欧氏空间的上的某一个凸集上的函数，若，，恒有
（15）
则称为定义在的凸函数。
若，，恒有
（16）
则称为定义在的严格凸函数。
若将式子（15）和（16）中不等号反向，即可得出凹函数和严格凹
函数的概念。容易看出，若是凸函数（严格凸函数），则为凹函数（严格凹函数），凸函数和凹函数的几何意义如图所示。
O
O
凸函数凹函数
2、性质
性质1 设是定义在上的凸函数，，则也是凸函数。
性质2 设在凸集上的函数，是任意实数，则水平集
是凸集。
3、凸函数的判别
要判定一个函数是否为凸函数，可以直接使用凸函数的定义，也可以采用下面的判别法。
（1）一阶条件
设是维欧氏空间的上的某一个开凸集，在上可微，则为上的凸函数的充要条件是：恒有
（17）
而为上的严格凸函数的充要条件是：，恒有
（18）
若将式子（17）和（18）中不等号反向，即可得出凹函数和严格凹函数的充要条件。
（2）二阶条件
设是维欧氏空间的上的某一个开凸集，在上二阶可微，则为上的凸函数（凹函数）的充要条件是：，其海赛矩阵是半正定（半负定）的。
而，的海赛矩阵是正定（负定）的，则为上的严格凸函数（严格凹函数）。
4、凸函数的极值
函数的局部极值并不一定是最小值，它只反映了函数的局部性质，而最优化的目的往往是求出函数在整个区域中的最小值（或最大值）。为此，必须求出所有的极小值加以比较（有时还需考虑其边界值），以便从中选出最小值。然而，对于定义在凸集上的凸函数而言，则用不着进行这种麻烦的工作，它的极小值就等于其最小值，而且它的极小点形成一个凸集。由一阶条件可得：
设是维欧氏空间的上的某一个开凸集，是上的可微凸函数，如果使得对于所有的都有
，（19）
则就是在上的最小点（全局极小点）。
2.2 凸规划
现在考虑非线性规划（4）：
（4）
或
（5）
若其中的为凸函数，全是凹函数（即全是凸函数），则称这种规划为凸规划。
凸规划具有下面很好的性质：
（1）凸规划的可行域为凸集；
（2）凸规划的最优解集是凸集；
（3）凸规划的任何局部最优解也是全局最优解；
（4）若目标函数为严格凸函数，且最优解存在，则最优解是唯一的。
由于线性函数既可视为凸函数，又可视为凹函数，故线性规划是凸规划。
例3 试分析非线性规划
解：函数和的海赛矩阵的行列式为
知为严格凸函数，为凹函数，由于其他约束是线性函数，所以这个非线性规划是一个凸规划，C点是它的唯一最优点：
。
C
O
第三节下降迭代算法
由前面的讨论可知，对于可微函数，为了求其最优解，可以令其梯度等于零，求出驻点，然后再用充分条件判别，以求得最优解。从表面上看，似乎问题已经解决，但是对于一般的元函数来说，由条件得到的常常是一个非线性方程组，求解它相当困难。此外，许多实际问题往往很难求出或根本求不出目标函数对各个自变量的偏导数，从而使一阶必要条件难以应用。为了解决非线性规划的计算问题本节介绍迭代法。迭代法的基本思想为：我们并不一下子就能找出函数的最优点，而是从最优点的某一个初始估计出发，按照一定的规则（即所谓算法），先找出一个比更好的点（对于极小化问题来说，比更小；对于极大化问题来说，比更大），再找出比更好的点，…….如此下去，就产生了一个解的序列。若该点列有一个极限点，即
（20）
就称该点列收敛于。
对于极小化问题，我们要求选取的某一种算法所产生的解的序列其对应的目标函数值应是逐步减小的，即要求
具有这种性质的算法称为下降迭代法。
下降迭代法的一般迭代格式为：
（1）选取某一个初始点，令（表示将0赋值于变量）；
（2）确定搜索方向：若已得出某一个迭代点，且不是极小点，从出发确定一个搜索方向，沿这个方向应能找到使的目标函数下降的点（对约束问题，有时还要求这样的点是可行的点）。
（3）确定步长。沿方向前进一个步长，得新的点。即在由出发的射线
上，通过选定步长（因子），得下一个迭代点
使得
（4）检验新得到点是否为要求的极小点或近似的极小点，如果满足要求，迭代停止，否则，令，返回（2）部继续迭代。
注：在以上步骤中选定搜索方向对算法起着关键的性的作用，各种算法的区分主要在于搜索方向的方法不同。
在许多算法中，步长的选取是由使目标函数值沿搜索方向下降最多（极小问题）为依据的，即沿射线求的极小，即选取使
（21）
由于这一工作是求以为变量的一元函数的极小点，故称这一过程为（最优）的一维搜索，由此确定的步长称为最佳步长。这种搜索有一个重要性质，就是在搜索方向上所得最优点处的梯度和该搜索方向正交，即有下面的定理。
定理3 设目标函数具有连续的一阶偏导数，按下述规则产生
则有
（22）
如图所示。
由于真正的极值点事先
并不知道，故在实际只能根据
相继两次迭代得到的计算结果
来判断是否已达到要求，从而
需要有下面的终止迭代计算准图1
则，常用的准则有：
（1）根据相继两次迭代结果的绝对误差：
（2）根据相继两次迭代结果的相对误差：
（3）根据函数梯度的模足够小：
其中为足够小的正数。
第四节一维搜索方法
当用到上述迭代法求函数极小点时常常要用到一维搜索，即沿某个一直方向求目标函数的极小点。一维搜索的方法很多，试探法（斐波那契法（Fibonacci分数法、0.618法），插值法等。
1、斐波那契法（Fibonacci）
设是区间上的下单峰函数，在此区间内有唯一的极小点，在的左侧函数是严格下降的，而在的右侧函数是严格上升的，若在此区间内任取
O a0 t* t1s1b0
O a0 t1s1t* b0
图2 图3
两个点，计算函数值，，则可能出现一下两种情况：
（1）（图2），此时极小点必在区间内；称为保留区间，此时称为保留点。
（2）（图3），此时极小点必在区间内。此时为保留区间，而为保留点。
即将区间原来缩小为仍包括极小点的区间或。若再继续下去，为了利用已计算的函数值或，将前一次的保留点作为一个试算点，只需在或内选取一个新的试算点即可。
例如假如在区间内，取试算点（保留点），再选一个作为另一个试算点，一般可以取
，
即，在区间上与对称，如图4所示)，只需计算出，即可与比较。如此继续下去，最终可以得到满足一定误差要求的的近似解。我们称这种方法为序惯试验法。
0 a1 t2 s2b1
试问如何选取试算点，通过计算次函数值能将长度的区间缩成长度为一个单位的区间呢？
假设是斐波那契（Fibonacci）数列，即
，
（23）
利用上述公式可以计算出各个的值如下表1
012345678910111213…
1123581321345589144233377…
若经过次函数值计算，将长度为的区间缩成长度为一个单位的区间，则缩短后的区间长度1与原来区间的长度之比称为缩短率。若事先给定缩短率，或给定区间缩短的绝对精度：
则应有（24）
可以证明，当我们从经过次函数值的计算得到后，缩短到第步的试算点可以用下面的公式计算：
（25）
其中。例如，从，，我们可以选取如下：
（26）
应用这个方法缩短区间的步骤如下：
（1）确定试算点的个数：
根据缩短率，由公式算出，然后由表1确定出最小的。
（2）由公式（26）选出两个试算点。
（3）计算函数值，，并比较它们的大小。若，为保留区间，取，（保留点），再选一个作为另一个试算点：
若，此时为保留区间，而为保留点。取，（保留点），再选一个作为另一个试算点：
（4）计算函数值或（其中有一个已经算出），并比较它们的大小。像第三步那样继续迭代。第步的试算点用公式(25)。
（5）当时，
此时无法通过比较函数值和的大小确定最终的区间，为此，取
（27）
其中为任意小的正数，在中，以函数值较小的的作为近似的极小点，相应的函数值作为近似的极小值，并得最终的区间或
。
由以上的分析可知，斐波那契（Fibonacci）法使用对称搜索的方法，逐步缩短所考察的区间，它能以尽量少的函数求值次数，达到预定
的某一缩短率。
2、0.618法
从斐波那契法的公式（25）
可以看出，将区间缩短为，其缩短率为
将上述数列分为奇数项和偶数项，可以证明这两个数列具有相同的极限。现在以不变的区间缩短率0.618代替斐波那契法每次不同的缩短率就得到了0.618法，即将公式（25）改写为
，（28）
它可以被看成斐波那契法的近似，效果很好。
3.6：线性规划 目录： （1）线性规划的基本概念 （2）线性规划在实际问题中的应用 【知识点1：线性规划的基本概念】 (1)如果对于变量x 、y 的约束条件，都是关于x 、y 的一次不等式，则称这些约束条件为__线性约束条件__(),z f x y =是欲求函数的最大值或最小值所涉及的变量x 、y 的解析式，叫做__目标函数_，当(),f x y 是x 、y 的一次解析式时，(),z f x y =叫做_线性目标函数__. (2)求线性目标函数在线性约束条件下的最大值或最小值问题，称为__线性规划问题__ ；满足线性约束条件的解(),x y 叫做__可行解_；由所有可行解组成的集合叫做__可行域_；使目标函数取得最大值或最小值的可行解叫做_最优解__ 例题：若变量x 、y 满足约束条件2 10x y x y +≤?? ≥??≥? ，则z x y =+的最大值和最小值分别为 ( B ) A. 4和3 B. 4和2 C. 3和2 D. 2和0 分析：本题考查了不等式组表示平面区域，目标函数最值求法. 解：画出可行域如图 作020l x y +=： 所以当直线2z x y =+过()20A ， 时z 最大，过()1,0B 时z 最小max min 4, 2.z z == 变式1：已知2z x y =+，式子中变量x 、y 满足条件11y x x y y ≤?? +≤??≥-? ，则z 的最大值是__3___ 解：不等式组表示的平面区域如图所示.
作直线0:20l x y +=，平移直线0l ，当直线0l 经过 平面区域的点()21A -，时，z 取最大值2213?-=. 变式2：设2z x y =+，式中变量x 、y 满足条件43 35251x y x y x -≤-?? +≤??≥? ，求z 的最大值和最小值 分析：由于所给约束条件及目标函数均为关于x 、y 的一次式，所以此问题是简单线性 规划问题，使用图解法求解 解：作出不等式组表示的平面区域(即可行域)，如图所示． 把2z x y =+变形为2y x z =-+，得到斜率为-2，在y 轴上的截距为z ，随z 变化的一族平行直线． 由图可看出，当直线2z x y =+经过可行域上的点A 时，截距z 最大，经过点B 时，截距z 最小． 解方程组430 35250x y x y -+=??+-=?，得A 点坐标为()5,2， 解方程组1 430x x y =??-+=? ，得B 点坐标为()1,1 所以max min 25212,211 3.z z =?+==?+= 变式3：若变量x 、y 满足约束条件6 321x y x y x +≤?? -≤-??≥? ，则23z x y =+的最小值为( C ) A. 17 B. 14 C. 5 D. 3
第一章非线性规划理论（1） 第一节非线性优化规划模型及其解的概念, 第二节凸函数与凸规划, 第三节下降迭代算法 第四节一维搜索方法 第一节非线性优化规划模型及其解的概念 线性规划的目标函数和约束条件都是其自变量的线性函数，如果目标函数或约束条件中含有自变量的非线性函数，则这样的规划问题就是非线性规划。有些实际问题可以表示成线性规划，但有些实际问题则需要用非线性规划模型来表达。 例1 求，使得 （1） 该数学模型中目标函数是一个二次函数，因此它是一个非线性规划。 又如：求，使得 （2） 是一个非线性规划。 1.1 非线性规划问题的数学模型 非线性规划数学模型的一般形式为 （3） 其中是维欧氏空间中的向量（点），是目标函数，为约束条件，、都是元实函数。 说明： （1）由于我们有，当需使目标函数极大化时，只需使其负值极小化即可，因而仅考虑极小化的情况不失一般性。 （2）若某约束条件是“”不等式，仅需要在约束两端乘以“－1”，即可将这个约束变为“”。又由于约束等价于 因而我们可以将非线性规划模型写成下面的形式： （4） 或 （5） 模型中的称为非线性规划的可行域，而中的元素称为可行解。 1.2 二维问题的图解法 当只有两个决策变量时，求解非线性规划也可以像线性规划那样用图解法。 例2
解：先画出可行域 X2 A B C D O x1 可行域 等值线 最优解 画出抛物线 ， 即图中的曲线，再画出 直线，即图中的 直线，得可行域。 画出等值线 ，图中有一条等值线与抛物线 交于B点，当动点从A点出发延 抛物线移动时，动点从A移向B时，目标函数值下降，动点从B移向C 时，目标函数值上升，所以在可行域范围内B点的函数值最小，所以B 点是一个极小点。当动点由C点向D点移动时，目标函数再次下降，在D（4，1）点目标函数值最小，所以D点是最优解。 本例中，B点称为局部极小点，而D点称为全局极小点，即最小点。 1.3 非线性规划的基本概念 1.3.1关局部极小和全局极小的定义 设为定义在维欧氏空间的某一个区域上的元实函数，对于，如果存在某一个使得所有与距离小于的都有，则称为在上的局部极小点，而为局部极小值。如果当时，有，则称为在上的严格局部极小点，而为严格局部极小值。 设为定义在维欧氏空间的某一个区域上的元实函数，如果存在，对于所有，都有，则称为在上的全局极小点，而为全局极小值。如果当时，有，则称为在上的严格全局极小点，而为严格全局极小值。
非线性规划模型 在上一次作业中，我们对线性规划模型进行了相应的介绍及优缺点，然而在实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都可以归结为一个非线性规划问题，即如果目标函数和约束条件中包含有非线性函数，则这样的问题称为非线性规划问题。一般来说，解决非线性的问题要比线性的问题难得多，不像线性规划有适用于一般情况的单纯形法。对于线性规划来说，其可行域一般是一个凸集，只要存在最优解，则其最优解一定在可行域的边界上达到；对于非线性规划，即使是存在最优解，却是可以在可行域的任一点达到，因此，对于非线性规划模型，迄今为止还没有一种适用于一般情况的求解方法，我们在本文中也只是介绍了几个比较常用的几个求解方法。 一、非线性规划的分类 1无约束的非线性规划 当问题没有约束条件时，即求多元函数的极值问题，一般模型为 ()min 0 x R f X X ∈??? ≥?? 此类问题即为无约束的非线性规划问题 1.1无约束非线性规划的解法 1.1.1一般迭代法 即为可行方向法。对于问题()min 0x R f X X ∈??? ≥?? 给出)(x f 的极小点的初始值)0(X ，按某种规律计算出一系列的 ),2,1()( =k X k ，希望点阵}{)(k X 的极限*X 就是)(x f 的一个极小点。 由一个解向量) (k X 求出另一个新的解向量)1(+k X 向量是由方向和长度确定的，所以),2,1()1( =+=+k P X X k k k k λ 即求解k λ和k P ，选择k λ和k P 的原则是使目标函数在点阵上的值逐步减小，即 .)()()(10 ≥≥≥≥k X f X f X f 检验}{)(k X 是否收敛与最优解，及对于给定的精度0>ε，是否 ε≤?+||)(||1k X f 。 1.1.2一维搜索法 当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有： （1）试探法（“成功—失败”，斐波那契法，0.618法等）； （2）插值法（抛物线插值法，三次插值法等）；
《区域分析与区域规划》要点 第一章绪论 1、区域概念：是一个空间概念，是地球表面上占有一定空间的、以不同的物质客体为对象的地域结构形式。其基本属性有四点：（1）地球表面的一部分，并占有一定的空间；（2）具有一定的围和界线；（3）具有一定的体系结构形式；（4）区域是客观存在的。 2、区域的高度相关性：一是区域部间特性的一致性和相似性，并以这种一致性或相似性区别于其他区域，称为匀质区域；二是结节区，或称功能区、枢纽区，它是由区域的核心以及与其功能上紧密相连，具有共同利益的外围地区所组成。 3、区域的本质特性：有两点：一是整体性，使区域部某一局部的变化会导致整个区域的变化。二是结构性，区域的构成单元，按一定的联系产生结构。具有层次性、自组织性、稳定性。 4、区域科学：是用各种近代计量分析和传统区位分析相结合的方法，由区域或空间的诸要素及其组合所形成的差异和变化的分析入手，对不同等级和类型区域的社会、经济发展等问题进行研究的一门应用学科，是一门有关区域或空间系统的治理、开发、管理的具有地域性、综合性和实践性的学科。研究对象：区域是一个能动的机体或区域系统。 5、区域科学研究的容和任务：（1）对影响区域发展的各种要素及其综合效益进行分析，从而研究各种社会经济现象的时空规律；（2）研究区位、聚落、城市化地区和全球性区域系统以及人类居住方式、经济活动、资源有效利用在自然环境背景下所有活动的地域差异；（3）对存在于区域的各种行为单位利益及价值观念的矛盾和冲突以及区域的社会、政治、经济活动与生态环境间的相互影响进行分析，并系统地探讨解决区域发展中出现的各类问题的方法，提出区域发展的优化模式。 6、区域研究的三大新动向：（1）改变区域资源的观念：信息资源和人才观念；（2）扩大区域研究围：从参与市场竞争的角度和运用新国际劳动分工的理论，强化区域的基础设施和创造良好的投资环境，吸引区外、国外的资源、资金、技术、人才，建立起外结合的经济运转系统，促进区域的发展；（3）确立可持续发展思想：成为区域研究的主题，其基本原则是实现人口、资源、环境的协调发展是区域发展的主要目的。 7、区域分析：对区域发展的自然条件和社会经济条件背景特征及其对区域社会经济发展的影响进行分析，探讨区域部各自然及人文要素间和区域间相互联系的规律。主要容包括：（1）区域发展的自然条件和社会经济条件的分析；（2）区域经济分析；（3）区域发展分析。8、区域分析方法：（1）地理学的比较法：常用实际考察法、统计图表法、地图和遥感技术法等；（2）经济学的分析法：均衡分析、动态分析、静态分析、比较静态分析、投入产出分析、边际分析、实物分析、价值分析、结构分析等；（3）数学的模拟法：数理统计（回归分析、趋势分析、主成分分析和随机过程分析）、运筹学（线性规划、非线性规划、图论）。 9、区域规划：我国规划体系分三级三类，三类指国民经济和社会发展总体规划、专项规划、区域规划；三级指国家、省（区、市）级、市（县）级规划。区域规划的一般定义是指对一定地域围未来国民经济和社会发展建设及土地利用的总体部署。我国的区域规划特指跨行政区的空间发展协调规划。国外区域规划的主要任务是：（1）区域资源开发和生态环境保护；（2）城乡、区域协调发展的重大问题和重要地区规划；（3）可持续发展的重大问题规划。 第二章区域资源环境基础分析 10、区域发展的资源环境基础分析：包括自然资源、自然环境分析及生态环境保护问题分析。人口与劳动力、技术条件。 11、自然资源：存在于自然界，能被人类利用并能产生经济或社会价值的自然条件。其特
第五章 非线性规划的概念和原理 非线性规划的理论是在线性规划的基础上发展起来的。1951年，库恩（H.W.Kuhn ）和塔克（A.W.Tucker ）等人提出了非线性规划的最优性条件，为它的发展奠定了基础。以后随着电子计算机的普遍使用，非线性规划的理论和方法有了很大的发展，其应用的领域也越来越广泛，特别是在军事，经济，管理，生产过程自动化，工程设计和产品优化设计等方面都有着重要的应用。 一般来说，解非线性规划问题要比求解线性规划问题困难得多，而且也不像线性规划那样有统一的数学模型及如单纯形法这一通用解法。非线性规划的各种算法大都有自己特定的适用范围。都有一定的局限性，到目前为止还没有适合于各种非线性规划问题的一般算法。这正是需要人们进一步研究的课题。 5.1 非线性规划的实例及数学模型 [例题6.1] 投资问题： 假定国家的下一个五年计划内用于发展某种工业的总投资为b 亿元，可供选择兴建的项目共有几个。已知第j 个项目的投资为j a 亿元，可得收益为j c 亿元，问应如何进行投资，才能使盈利率（即单位投资可得到的收益）为最高？ 解：令决策变量为j x ，则j x 应满足条件() 10j j x x -= 同时j x 应满足约束条件 1 n j j j a x b =≤∑ 目标函数是要求盈利率()1121 ,,,n j j j n n j j j c x f x x x a x === ∑∑L 最大。 [例题6.2] 厂址选择问题： 设有n 个市场，第j 个市场位置为() ,j j p q ，它对某种货物的需要量为j b ()1,2,,j n =L 。 现计划建立m 个仓库，第i 个仓库的存储容量为i a ()1,2,,i m =L 。试确定仓库的位置，使各仓库对各市场的运输量与路程乘积之和为最小。 解：设第i 个仓库的位置为(),i i x y ()1,2,,i m =L ，第i 个仓库到第j 个市场的货物供应量为i j z ()1,2,,,1,2,,i m j n ==L L ，则第i 个仓库到第j 个市场的距离为
简单的线性规划问题 [学习目标] 1.了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念.2.了解线性规划问题的图解法，并能应用它解决一些简单的实际问题． 知识点一 线性规划中的基本概念 知识点二 1．目标函数的最值 线性目标函数z ＝ax ＋by (b ≠0)对应的斜截式直线方程是y ＝－a b x ＋z b ，在y 轴上的截距是z b ，当z 变化时，方程表 示一组互相平行的直线． 当b >0，截距最大时，z 取得最大值，截距最小时，z 取得最小值； 当b <0，截距最大时，z 取得最小值，截距最小时，z 取得最大值． 2．解决简单线性规划问题的一般步骤 在确定线性约束条件和线性目标函数的前提下，解决简单线性规划问题的步骤可以概括为：“画、移、求、答”四步，即， (1)画：根据线性约束条件，在平面直角坐标系中，把可行域表示的平面图形准确地画出来，可行域可以是封闭的多边形，也可以是一侧开放的无限大的平面区域． (2)移：运用数形结合的思想，把目标函数表示的直线平行移动，最先通过或最后通过的顶点(或边界)便是最优解． (3)求：解方程组求最优解，进而求出目标函数的最大值或最小值． (4)答：写出答案． 知识点三 简单线性规划问题的实际应用 1．线性规划的实际问题的类型 (1)给定一定数量的人力、物力资源，问怎样运用这些资源，使完成的任务量最大，收到的效益最大； (2)给定一项任务，问怎样统筹安排，使完成这项任务耗费的人力、物力资源量最小． 常见问题有： ①物资调动问题 例如，已知两煤矿每年的产量，煤需经两个车站运往外地，两个车站的运输能力是有限的，且已知两煤矿运往两个车站的运输价格，煤矿应怎样编制调动方案，才能使总运费最小？
第八章城乡规划管理基本知识 第一节城乡规划管理概述 一城乡规划管理的概念 （1）城乡规划管理是城市政府的一项行政职能。 十二届三中全会《关于经济体制改革的决议》中明确指出，城市人民政府的主要职能是搞好城乡的规划、建设和管理。 （2）城乡规划管理的核心。根据对城乡规划管理的概念的解释，城乡规划管理核心包括三方面： 第一，城乡规划的组织编制和审批； 第二，城乡规划实施管理； 第三，城乡规划实施的监督检查。 二城乡规划管理的基本特征 一般特征：综合性、整体性、系统性、时序性、地方性、政策性、技术性、艺术性等诸多特征。 特殊特征：引导与控制的特性、宏观和微观管理特性、专业性和综合性属性、阶段性和连续属性
第二节城乡规划管理系统 一城乡规划管理系统 城乡规划管理是一个系统。 系统的特点：一是系统是由若干部分以一定的结构组成的互相联系的整体；二是系统整体具有层次性，每个层次的系统可以分解为若干基本要素；三是系统整体有不同于各组成部分的新功能。 城乡规划编制、审批、实施和监督检查是一个实践过程。 （1）决策系统：城乡规划的组织编制与审批管理 （2）执行系统：城乡规划实施管理 建设工程、道路交通工程、市政管线工程进行建设项目选址、建 （3）反馈系统：城乡规划监督检查 （4）保障系统：城乡规划法律规范
二城乡规划管理系统要素 1.管理目标 最终目标P115 2.管理者 管理的水平与成败在相当大的程度上取决于管理者的素质及其能力。如基层规划管理人员所扮演的角色和所起的作用：（1）（2）（3）3.管理对象 城市规划区内的土地的利用和各项建设活动。 4.被管理者 一是城乡规划项目（政府内部管理行为），二是建设用地或建设工程（政府外部管理行为）。 5.管理中介 （1）权力 审批权：审批城乡规划，审批“一书两证” 惩治权：查处违法建设和违法用地 执行权：执行城市政府方针、正常和重大决策 参议权：向城市政府反映情况，提出建议 表彰权：表彰实施城乡规划优秀建设项目 其他权：其他法律授权或因需制定管理规范的权力 （2）规则 批准的城乡规划文本、图纸，各种有关法律、法规及技术规范。
6 非线性规划 1、判断函数的凸凹性 （1）3 )4()(x x f -=，4≤x （2）2 2212132)(x x x x X f ++= （3）21)(x x X f = （1）解：' 2 f (x)3(4)0x =--<=， x<=4,故f(x)在（-∞，4]上是不减函数， ''f (x)6(4)0x =->=，故f(x)在（-∞，4]上是凸函数。 （2）解：f(x)的海赛矩阵22()26H x ?? =?? ?? ，因H （x ）正定，故f （x ）为严格的凸函数。 （3）解：取任意两点(1) 11(,)X a b =、),(22)2(b a X =，从而 (1)11().f X a b =，(2)22().f X a b =，(1)11()(,)T f X b a ?= 看下式是否成立： (2)(1)(1)(2)(1)()()().()f X f X f X X X >+?- 2211112121..(,)(,)T a b a b b a a a b b >+-- 2121().()0a a b b --> 1212,,,a a b b 是任意点，并不能保证上式恒成立，故 所以12()f X x x =既非凸函数，也非凹函数。 2、分别用斐波那契法和黄金分割法求下述函数的极小值，初始的搜索区间为]15,1[∈x ，要求5.0|)()(|1≤--n n x f x f 。 x x x x X f 1357215)(234-+-= 解：斐波那契法 已知δ = 0.5/(15-1)=1/28、a = 1、b = 15，有1 28n F δ≥ =，即8n =。
求解非线性规划
————————————————————————————————作者：————————————————————————————————日期：
非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。 1.2 线性规划与非线性规划的区别 如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。 1.3 非线性规划的Matlab 解法 Matlab 中非线性规划的数学模型写成以下形式 )(min x f ???????=≤=?≤0 )(0)(x Ceq x C Beq x Aeq B Ax , 其中)(x f 是标量函数，Beq Aeq B A ,,,是相应维数的矩阵和向量，)(),(x Ceq x C 是非线性向量函数。 Matlab 中的命令是 X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS) 它的返回值是向量x ，其中FUN 是用M 文件定义的函数)(x f ；X0是x 的初始值；A,B,Aeq,Beq 定义了线性约束Beq X Aeq B X A =≤*,*，如果没有等式约束，则A=[],B=[],Aeq=[],Beq=[]；LB 和UB 是变量x 的下界和上界，如果上界和下界没有约束，则LB=[]，UB=[]，如果x 无下界，则LB=-inf ，如果x 无上界，则UB=inf ；NONLCON 是用M 文件定义的非线性向量函数)(),(x Ceq x C ；OPTIONS 定义了优化参数，可以使用Matlab 缺省的参数设置。 例2 求下列非线性规划问题
非线性最优化理论与算法 第一章引论 本章首先给出了一些常见的最优化问题和非线性最优化问题解的定义，并且根据不同的条件对其进行了划分。接着给出了求解非线性优化问题的方法，如图解法等，同时又指出一个好的数值方法应对一些指标有好的特性，如收敛速度与二次终止性、稳定性等。随后给出了在非线性最优化问题的理论分析中常用到的凸集和凸函数的定义和有关性质。最后给出了无约束优化最优性条件。 第二章线搜索方法与信赖域方法 无约束优化的算法有两类，分别是线搜索方法和信赖域方法。本章首先给出了两种线搜索方法即精确线搜索方法和非精确线搜索方法。线搜索方法最重要的两个要素是确定搜索方向和计算搜索步长，搜索步长可确保下降方法的收敛性，而搜索方向决定方法的收敛速度。 精确线搜索方法和非精确线搜索方法 对于精确线搜索方法，步长ακ满足 αk=arg min ?x k+αd k α≥0 这一线搜索可以理解为αk是f(x k+αd k)在正整数局部极小点，则不论怎样理解精确线搜索，它都满足正交性条件： d k T??(x k+αk d k)=0 但是精确搜索方法一般需要花费很大的工作量，特别是当迭代点远离问题的解时，精确的求解问题通常不是有效的。而且有些最优化方法，其收敛速度并不依赖于精确搜索过程。对于非精确搜索方法，它总体希望收敛快，每一步不要求达到精确最小，速度快，虽然步数增加，则整个收敛达到快速。书中给出了三种常用的非精确线搜索步长规则，分别是Armijo步长规则、Goldstein步长规则、Wolfe步长规则。第一个步长规则的不等式要求目标函数有一个满意的下降量，第二个不等式控制步长不能太小，这一步长规则的第二式可能会将最优步长排除在步长的候选范围之外，也就是步长因子的极小值可能被排除在可接受域之外。但Wolfe步长规则在可接受的步长范围内包含了最优步长。在实际计算时，前两种步长规则可以用进退试探法求得，而最后一种步长规则需要借助多项式插值等方法求得。紧接着，又介绍了Armijo和Wolfe步长规则下的下降算法的收敛性。 信赖域方法 线性搜索方法都是先方向再步长，即先确定一个搜索方向d k，然后再沿着这个搜索方向d k选择适当的步长因子αk，新的迭代点定义为x k+1=x k+αk d k。与线搜索方法不同，信赖域方法是先步长再方向,此方法首先在当前点附近定义目标函数的一个近似二次模型，然后利用目标函数在当前点的某邻域内与该二次模型的充分近似，取二次模型在该邻域内的最优值点来产生下一迭代点。它把最优化
第三章城市规划布局结构的基本概念 现代城市规划学在其形成和发展过程中，先后吸收了经济学、社会学、地理学和生态学等方面的成果，并以传统的工程技术学科和建筑艺术理论为基础，不断选择、融合逐步形成了具有广阔理论基础和特点的综合性学科。 由于城市规划的目标明确，任务具体，所形成的理论和方法具有明显的实用性。在其发展过程中，根据不同时期城市发展的实际需要，从诸多相关学科中不断选取并进行实用化和现代化处理，实现了理论结合实际的过渡，并不断充实发展城市规划学的理论和方法，成为指导城市建设发展的实用技术学科。例如，经济学、社会学、地理学中关于城市化的理论，社会学中关于人口与劳动资源形成的学说、关于社会基础结构和居民生活方式的学说，经济地理学中关于生产和人口空间分布的学说，城市地理学中关于地域结构的学说、生态学中关于保护自然环境和创造人工环境以及人—技术—环境协调的思想等，都对充实、深化城市规划的理论基础作出了贡献，而现代工程技术诸学科的迅速发展，现代数学和计算技术的应用，为不断充实、发展、更新城市规划的理论和方法，开创了良好前景。现代城市规划学是在多种学科结合实践的过程中形成了具有特色的实用性很强的综合学科，在指导当代城市和空间发展中发挥着不可替代的作用。 一、城市形成因素 这一概念是建立在“城市的形成和发展源于社会经济发展”的历史唯物论的观点之上的。城市是在社会劳动分工过程中形成的地域性经济综合体，是国家和地区经济中心和组成部分。随着社会经济的发展，城市的功能和物质要素越来越复杂。但对城市的发展、衰退起决定作用的要素是构成城市许多物质因素中的一部分。理论工作者称这部分因素为“城市形成的因素”（以下称形成因素），其特点是因素所产生的效果和作用主要不表现于本市，而超越于本市的范围。它的产生和存在主要不决定于本市而决定于超越本市的经济的、社会的或政治的因素。在实行计划经济的条件下，主要取决于人口和生产力的布局和计划的平衡。在市场经济的条件下，则取决于因素所能形成的利润率和所需要的市场区（服务区）。如果它的市场区小
非线性规划报告 一、什么是非线性规划？ 因为在实际问题求解中，很多情况下，目标函数以及约束条件不可能都是线 性的，往往包含非线性函数，那么这时就是非线性规划问题。简单概括，非线性规划研究一个n 元实函数在一组等式或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。 二、非线性规划和线性规划的区别是什么？ 除了目标函数和约束条件的形式不同外，线性规划的最优解只可能在可行域 的边界达到（特别是顶点处），而非线性规划可能在可行域的任意一点达到。 三、非线性规划的一般模型： m i n f (x ) ()0,j 1,...q s .t . ()0, i 1,... j i h x g x p ≤=???==?? 其中：1,2,,[...]n x x x x =称为决策变量，f 为目标函数，j h 和i g 称为约束函数， ()0i g x =称为等式约束，()0j h x ≤称为不等式约束。 四、非线性规划的两类问题 1、无约束的极值问题 我们一般都将求解的非线性规划问题都转化为无约束的最优化问题。这里主 要介绍求解无约束问题的解析法，解析法就是通过计算()f x 的一阶，二阶偏 导数及其函数的解析性质来实现极值的求解方法。这里介绍牛顿法（详见手写稿 件）。 2、有约束的极值问题 带有约束条件的极值问题称为约束极值问题，求解约束极值问题要比求解无 约束极值问题困难得多。为了简化优化工作，通常采取以下解题思路： （1） 将约束极值问题转化为无约束极值问题。 （2） 将非线性规划问题转化为线性规划问题。 （3） 将复杂的问题分解为若干简单问题。 这里主要介绍二次规划模型。 二次规划的显著特征是“目标函数”是二次函数，且约束条件又是线性的。 在matlab 中二次规划模型表示如下：
LP （Linear Programming）
Alex 有一个家庭农场。除了农场上的农作物以外，他还饲养了一些猪拿到市场上出售，猪可获得的饲料及其所含成分如下表：Alex如何喂养猪更好？ 成分/每公斤 玉米槽料苜蓿每日最小需求量碳水化合物 蛋白质 维他命 成本(美分)903010842080207240606060200180150 问题1：科学养猪线性规划建模（猪饲料的配方）饲养成本最小
--- 每天玉米、槽料、苜蓿各喂多少公斤？ --- 必须满足要求12--- 追求成本最低 Min. 84x 1+ 72x 2+ 60x 3 3x 1x 2x 3 知识点 建模三要素 决策变量约 束目标 90x 1+ 20x 2+ 40x 3 ≥ 20030x 1+ 80x 2+ 60x 3 ≥ 18010x 1+ 20x 2+ 60x 3 ≥ 150 x i ≥0 , i =1，2，3 成分/每公 斤 玉米槽料苜蓿每日最小需求量碳水化合物 蛋白质 维他命 成本(美分)903010842080207240606060200180150
s.t. 90x 1+ 20x 2+ 40x 3 ≥ 200 30x 1 + 80x 2+ 60x 3 ≥ 180 10x 1+ 20x 2+ 60x 3 ≥ 150 x i ≥0 , i =1,2,3 Min . 84x 1+ 72x 2+ 60x 3 目标函数约束函数符号中必含等号符号的右侧为常数线性--变量均为1次方 Max. 或 Min.线性--所有变量均为1次方常规约束：变量非负！知识点 模型表示
？线性规划模型能求解出来吗？ 能！--- 万能的单纯形法 结合软件 QSB应用
场地设计的基本概念 （一）场地： 狭义基地内的室外场地 广义基地内一个整体的系统 基地中包含的全部内容所组成的整体、如建筑物、构筑物、交通设施、室外活动设施等绿化及环境景观设施和工程系统等 （二）场地构成要素 1.建筑物、构筑物 2.交通设施 3.室外活动设施 4. 绿化环境景观设施 5.工程系统 （三）场地类型的划分 1．按使用特征划分为：工业建设场地和民用建筑场地 2．按地形条件划分为：平坦场地和坡地场地 （四）场地设计概念 针对基地内建设项目的总平面设计，依据建设项目的使用功能要求和规划设计条件，在基地内外的现状条件和有关法规、规范的基础上，人为地组织与安排场地中各构成要素之间关系的活动。 （五）场地设计工作的目的 1、达到场地各构成要素之间关系的正确组织 2、使场地中的各项内容与基地形成良好的关系，提高基地利用的科学性，充分发挥用地的效益。 （六）场地设计的内容 现状分析场地布局交通组织竖向布置管线综合环境设计与保护技术经济分析 场地设计原则 珍惜土地、保护耕地 符合城市规划的要求 满足功能要求、技术经济合理 注意与环境保护、考虑可持续发展 ①珍惜、合理利用土地和切实保护耕地 ②符合当地城市规划要求 ③满足使用功能要求 ④技术经济合理 ⑤满足规范要求 ⑥满足交通组织要求 ⑦竖向布置合理 ⑧管线综合合理 ⑨合理进行绿化景观设计和环境保护 ⑩考虑可持续发展的要求 场地设计的表达方法 等高线法标高控制法坡面法方格网法
场地设计的依据 ①工程项目的依据 ②有关法律、法规、规范 东西不同的场地处理观念 基本观念 东：人工建造对自然的尊重与谦让。（天人合一背山面水负阴抱阳） 西：人工建造对自然的超越 基地条件 东：重视与环境的关系，场地处理上善于结合、利用基地的现有条件。 西：强调对基地的改造，更多地表现出将人为的秩序施加到基地上的倾向。 场地要素 东：重视场地中建筑物之外的部分，重视场地中各组成要素的平衡与协调关系，而不是单独调建筑物。 西：在西方的传统建筑中，相对于场地中的其他要素，建筑物受到了更多的重视。 如果说中国建筑是“虚”、“实”相生，以“虚”为主，那么西方建筑则可以说是“虚”、“实”自立，以“实”为主 场地设计工作的特点 综合性政策性地方性预见性与阶段性全局性技术性与艺术性 场地设计的两个阶段 第一阶段——场地布局设计 第二阶段——场地详细设计 场地分区 按功能来分区：动静分区公共性分区空间主次分区内外关系分区洁污分区 按基地利用分区：集中式分区均衡式分区 （十四）影响建筑布局的基本要素 日照因素风向因素用地条件 几种建筑布局方式： 集中式布局：节约用地，增加层数，烘托高大体量 空间式布局，建筑围合空间，形成中庭或内院，特点：交通在中间组织，形成向心形式，增加整体感和围合感。 穿插式布局：建筑与其他内容分散布局，形成建筑与空间相互穿插，彼此交错。特点：灵活具变化，场地空间更丰富、更有层次。建筑形象亲切近人。 场地设计的相关领域：1.生态 2.建筑设计 3.城市规划 场地设计的制约因素 场地设计的制约因素主要包括 前提条件：城市规划和相关的法规、规范对场地建设的公共限制 直接依据：设计任务书 客观基础：自然条件、建设条件 公共限制条件的实现 公共限制条件是通过对场地设计中的一系列技术经济指标的控制来实现的。 公共限制的内容 用地控制：场地界限、用地性质 交通控制：基地交通出入口方位、停车空间、道路 密度控制
非线性规划的实例与定义 如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。 1.2 线性规划与非线性规划的区别 如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。 1.3 非线性规划的Matlab 解法 Matlab 中非线性规划的数学模型写成以下形式 )(min x f ???????=≤=?≤0 )(0)(x Ceq x C Beq x Aeq B Ax , 其中)(x f 是标量函数， Beq Aeq B A ,,,是相应维数的矩阵和向量，)(),(x Ceq x C 是非线性向量函数。 Matlab 中的命令是 X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS) 它的返回值是向量x ，其中FUN 是用M 文件定义的函数)(x f ；X0是x 的初始值；A,B,Aeq,Beq 定义了线性约束Beq X Aeq B X A =≤*,*，如果没有等式约束，则A=[],B=[],Aeq=[],Beq=[]；LB 和UB 是变量x 的下界和上界，如果上界和下界没有约束，则LB=[]，UB=[]，如果x 无下界，则LB=-inf ，如果x 无上界，则UB=inf ；NONLCON 是用M 文件定义的非线性向量函数)(),(x Ceq x C ；OPTIONS 定义了优化参数，可以使用Matlab 缺省的参数设置。 例2 求下列非线性规划问题
4 1 基于MATLAB 的非线性0-1规划的求解 学 生：易棉生 指导教师：宋来忠 三峡大学理学院 摘要：本文主要研究非线性0-1整数规划的解法。首先，通过对传统求解方法的研究，提出从0-1整数规划的变量只取值0和1这个特点来求解，为利用好这个特点，构造了一种数据结构——组合树，还根据目标函数和约束条件所含的变量是否被包含在解中取值为1的变量集中，将0-1整数规划的解细分为目标特殊解和约束特殊解。然后，把这个特点具体化为4条性质。根据这些性质，设计出合理的算法，并用MATLAB 实现该算法。实验表明，该算法是有效的。 Abstract: In this paper, the problem about solving nonlinear 0-1 integer programming is studied. Firstly the view that we can use the feature that the variables of 0-1 integer programming only have two values 0 and 1 is raised after discussing some traditional algorithms. To express the feature, a new tree structure, called combination tree in the paper is given and also object-satisfied solution and constrain-satisfied solution is defined, based on whether the variables with the value 1 in objective function and constrained condition belong to the variables with the value 1 in solution. Then it can be specified by 4 properties. According to these properties, a new algorithm is designed and implemented with MATLAB language. From the experiment, it is proved that the algorithm is effective. 关键词：0-1规划 非线性 组合树 解的标记 MATLAB key words: 0-1 integer programming; nonlinear; combination tree; the mark of solution; MA TLAB 前言 本文研究的模型可是： 111min () ..()0()0{0,1}f x Ax b A x b s t C x C x x ≤=??≤=??∈?，，，， (1) 其中，()f x 都是非线性函数，A 、b 、1A 、1b 是矩阵，1()()C x C x 、非线性矩阵函数。 可以看到，本模型实际上代表了一般的0-1整数规划问题。显然，如果一个算法能求解非线性0-1整数规划，也必然能求解一般的0-1整数规划。要完满地解决这个问题，一个算法应具备两个基本条件：1.求解速度较快，即能在较短的时间内计算出答案；2.能够判断出所求解的0-1整数规划的解的情况，即计算出的答案要么是无解要么是全局最优解。 但是，目前对这类问题的许多研究都只局限于线性0-1整数规划，利用线性性质来设计一些算法，如隐枚举法和匈牙利法等（详见参考文献5 ~16）；有些算法虽然可以求解任何0-1整数规划，但是不能肯定所求的解是全局最优解，如遗传算法和模拟退火算法等。求解非线性0-1整数规划的算法，肯定不能再依赖于具体函数的性质了，因为非线性函数的性质是无法预料的。从理论上将，穷举法不依赖于目标函数和约束条件的性质，能够获得全局最优解，但实际上却不可行。这就给我们指明了一个方向，求解非线性0-1整数规划的算法可以基于穷举法，但需要对其做大量的优化。 1 解的定义
非线性规划 线性规划及其扩展问题的约束条件和目标函数都是关于决策变量的一次函数。虽然大量的实际问题可以简化为线性规划及其扩展问题来求解，但是还有相当多的问题很难用线性函数加以描述。如果目标函数或约束条件中包含有非线性函数，就称这样的规划问题为非线性规划问题。由于人们对实际问题解的精度要求越来越高，非线性规划自20世纪70年代以来得到了长足的发展；目前，已成为运筹学的一个重要分支，在管理科学、最优设计、系统控制等许多领域得到了广泛的应用。 一般来讲，非线性规划问题的求解要比线性规划问题的求解困难得多；而且也不象线性规划问题那样具有一种通用的求解方法（单纯形法）。非线性规划没有能够适应所有问题的一般求解方法，各种方法都只能在其特定的范围内发挥作用。 本章在简要介绍非线性规划基本概念和一维搜索的基础上，重点介绍无约束极值问题和约束极值问题的求解方法。 §1非线性规划的数学模型 1.1 非线性规划问题 [例1] 某商店经销A 、B 两种产品，售价分别为20和380元。据统计，售出一件A 产品的平均时间为0.5小时，而售出一件B 产品的平均时间与其销售的数量成正比，表达式为n 2.01+。若该商店总的营业时间为1000小时，试确定使其营业额最大的营业计划。 解：设1x 和2x 分别代表商店经销A 、B 两种产品的件数，于是有如下数学模型： 2138020)(m ax x x x f += 10002.05.02 221≤++x x x 0,021≥≥x x 1.2 非线性规划问题的数学模型 同线性规划问题的数学模型一样，非线性规划问题的数学模型可以具有不同的形式；但由于我们可以自由地实现不同形式之间的转换，因此我们可以用如下一般形式来加以描述： n E X X f ∈),(m in ),,2,1(,0)(m i X h i == ),,2,1(,0)(l j X g j =≥ 其中T n x x x X ),,,(21 =是n 维欧氏空间n E 中的向量点。
非线性规划（nonlinear programming） 1.非线性规划概念 非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件都是线性函数的情形则属于线性规划。 2.非线性规划发展史 公元前500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为0.618,称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。例如阿基米德证明：给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。但是最优化方法真正形成为科学方法则在17世纪以后。17世纪，I.牛顿和G.W.莱布尼茨在他们所创建的微积分中，提出求解具有多个自变量的实值函数的最大值和最小值的方法。以后又进一步讨论具有未知函数的函数极值，从而形成变分法。这一时期的最优化方法可以称为古典最优化方法。 最优化方法不同类型的最优化问题可以有不同的最优化方法，即使同一类型的问题也可有多种最优化方法。反之,某些最优化方法可适用于不同类型的模型。最优化问题的求解方法一般可以分成解析法、直接法、数值计算法和其他方法。 (1)解析法：这种方法只适用于目标函数和约束条件有明显的解析表达式的情况。求解方法是：先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用求导数的方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法。 (2)直接法：当目标函数较为复杂或者不能用变量显函数描述时，无法用解析法求必要条件。此时可采用直接搜索的方法经过若干次迭代搜索到最优点。这种方法常常根据经验或通过试验得到所需结果。对于一维搜索(单变量极值问题)，主要用消去法或多项式插值法；对于多维搜索问题(多变量极值问题)主要应用爬山法。 (3)数值计算法：这种方法也是一种直接法。它以梯度法为基础，所以是一种解析与数值计算相结合的方法。 (4)其他方法：如网络最优化方法等。
非线性规划模型 在上一次作业中，我们对线性规划模型进行了相应的介绍及优缺点，然而在实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都可以归结为一个非线性规划问题，即如果目标函数和约束条件中包含有非线性函数，则这样的问题称为非线性规划问题。一般来说，解决非线性的问题要比线性的问题难得多，不像线性规划有适用于一般情况的单纯形法。对于线性规划来说，其可行域一般是一个凸集，只要存在最优解，则其最优解一定在可行域的边界上达到；对于非线性规划，即使是存在最优解，却是可以在可行域的任一点达到，因此，对于非线性规划模型，迄今为止还没有一种适用于一般情况的求解方法，我们在本文中也只是介绍了几个比较常用的几个求解方法。 一、非线性规划的分类 1无约束的非线性规划 当问题没有约束条件时，即求多元函数的极值问题，一般模型为 ()min 0 x R f X X ∈??? ≥?? 此类问题即为无约束的非线性规划问题 1.1无约束非线性规划的解法 1.1.1一般迭代法 即为可行方向法。对于问题()min 0x R f X X ∈??? ≥?? 给出)(x f 的极小点的初始值)0(X ，按某种规律计算出一系列的),2,1()(Λ=k X k ，希望点阵}{)(k X 的极限*X 就是)(x f 的一个极小点。 由一个解向量) (k X 求出另一个新的解向量)1(+k X 向量是由方向和长度确定的，所以),2,1()1(Λ=+=+k P X X k k k k λ 即求解k λ和k P ，选择k λ和k P 的原则是使目标函数在点阵上的值逐步减小，即
.)()()(10ΛΛ≥≥≥≥k X f X f X f 检验}{)(k X 是否收敛与最优解，及对于给定的精度0>ε，是否ε≤?+||)(||1k X f 。 1.1.2一维搜索法 当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有： （1）试探法（“成功—失败”，斐波那契法，0.618法等）； （2）插值法（抛物线插值法，三次插值法等）； （3）微积分中的求根法（切线法，二分法等）。 考虑一维极小化问题 )(min t f b t a ≤≤ 若)(t f 是],[b a 区间上的下单峰函数，我们介绍通过不断地缩短],[b a 的长度，来搜索得)(min t f b t a ≤≤的近似最优解的两个方法。通过缩短区间],[b a ，逐步搜索得 )(min t f b t a ≤≤的最优解*t 的近似值 2.1.3梯度法 选择一个使函数值下降速度最快的的方向。把)(x f 在) (k X 点的方向导数最小的方向 作为搜索方向，即令)(k k X f P -?=. 计算步骤： （1）选定初始点0 X 和给定的要求0>ε，0=k ； （2）若ε