第二讲 非线性规划基本概念

1、1 第二讲第二讲 非线性规划模型非线性规划模型 一、非线性规划引例一、非线性规划引例 例例1 路灯照度问题路灯照度问题 在一条在一条20m宽的道路两侧，分别安装了一只宽的道路两侧，分别安装了一只2kw 和一只和一只3kw的路灯，它们离地面的高度分别为的路灯，它们离地面的高度分别为5m和和 6m。在漆黑的夜晚，当两只路灯开启时，两只路灯。在漆黑的夜晚，当两只路灯开启时，两只路灯 连线路面上最暗的点和最亮的点在哪里？如果连线路面上最暗的点和最亮的点在哪里？如果3kw路路 灯的高度可以在灯的高度可以在3m到到9m之间变化，如何使得路面上之间变化，如何使得路面上 最暗和最亮的点的位置？如果两只路灯的高

2、度均可以最暗和最亮的点的位置？如果两只路灯的高度均可以 在在3m到到9m之间变化，结果将如何？之间变化，结果将如何？ (只是涉及非线性规划的案例以及其解的相关概念，只是涉及非线性规划的案例以及其解的相关概念， 不涉及具体算法不涉及具体算法) 2 图图2-1 osx p1 p2 h1 h2 r1 r2 1 2 分析分析 如图如图2-1，p1,p2 表示两只灯的功率；表示两只灯的功率； 离地面的高度为离地面的高度为h1,h2； 两只灯的距离为两只灯的距离为s； 假设两只灯发出的光都可以看成点光源。假设两只灯发出的光都可以看成点光源。 预备知识预备知识 光源点光源点p1在点在点x处的照度处的照度i1

3、，i1与功率与功率p1成正例，与成正例，与 距离距离r1的平方成反比，与照射角度的平方成反比，与照射角度1 1的正弦成正比。即的正弦成正比。即 2 1 11 1 r sinp ki 其中，其中，k为比例系数，同时也是平衡量纲（单位）的量。为比例系数，同时也是平衡量纲（单位）的量。 3 解解所有的变量设置如图所有的变量设置如图2-1所示所示 两只灯在点两只灯在点x处的照度为处的照度为 21 iii 其中，其中， 2 2 22 2 2 1 11 1 r sinp ki , r sinp ki 变量之间的关系变量之间的关系 ， 2 1 2 1 1 hx h sin , )xs (h h sin 22

4、 2 2 2 .)xs (hr ,hxr 22 22 2 1 2 1 这个公式只是适合点光源，如果不是点光这个公式只是适合点光源，如果不是点光 源（比如竖着的日光灯，该怎么办？源（比如竖着的日光灯，该怎么办？ 4 问题一：灯高度不变，求路面照度最弱最强的位置问题一：灯高度不变，求路面照度最弱最强的位置x。 数学模型数学模型1 ;iiimax(min) 21 2 2 22 2 2 1 11 1 r sinp ki , r sinp ki ， 2 1 2 1 1 hx h sin , )xs (h h sin 22 2 2 2 .)xs (hr ,hxr 22 22 2 1 2 1 s.x0 s.

5、t. 也可以化简为也可以化简为 5 )h)xs( ph )hx( ph ki max(min) 2 3 2 2 2 22 2 3 2 1 2 11 sx0s.t. 代入已知参数，模型简化为代入已知参数，模型简化为 .20 x0. t . s )36)x20( 18 )25(x 10 ki(x)max(min) 2 3 2 2 3 2 即求一元函数即求一元函数i(x)在在0，20上的最大值与最小上的最大值与最小 值。值。 6 问题问题2：当：当3kw的灯的高度在的灯的高度在3m到到9m之间变化时，路之间变化时，路 面的最暗和最亮点。面的最暗和最亮点。 数学模型数学模型2 . 9h3 20,x0

6、. t . s ; )h)x20( h3 )25(x 10 k)hi(x,max(min) 2 2 3 2 2 2 2 2 3 2 2 即求二元函数即求二元函数i(x,h2)在所给条件下的上的最大在所给条件下的上的最大 值与最小值。值与最小值。 7 问题问题3：两只灯的高度都在：两只灯的高度都在3m到到9m之间变化时，求之间变化时，求 路面的最暗和最亮点。路面的最暗和最亮点。 数学模型数学模型3 . 9h3 , 9h3 20,x0 . t . s ; )h)x20( h3 )h(x 2h k)h,hi(x,max(min) 2 1 2 3 2 2 2 2 2 3 2 1 2 1 21 即求三元

7、函数即求三元函数i(x,h1,h2)在所给条件下的上的最大在所给条件下的上的最大 值与最小值。值与最小值。 像这种目标函数或者约束条件是决策变量的非像这种目标函数或者约束条件是决策变量的非 一次（非线性）的规划问题，称为非线性规划模型。一次（非线性）的规划问题，称为非线性规划模型。 8 二、非线性规划模型二、非线性规划模型 在建立规划模型时，若目标函数中决策变量或者在建立规划模型时，若目标函数中决策变量或者 约束方程（不等式）中某些变量为非一次（不是线约束方程（不等式）中某些变量为非一次（不是线 性），则称建立的数学模型为非线性规划模型。其数性），则称建立的数学模型为非线性规划模型。其数 学模

8、型一般为学模型一般为 12n i12n i12n min f(x ,x ,x ) g (x ,x ,x )0,i1,2,.,l s.t. h (x ,x ,x )0,il 1,.,m 1n1n i1ni1n maxf(x ,x )minf(x ,x ) g (x ,x )0g (x ,.,x )0 若若 1、非线性规划模型、非线性规划模型 1 9 2、非线性规划问题的解的相关概念、非线性规划问题的解的相关概念 一般来说，非线性规划的求解，比线性规划的求一般来说，非线性规划的求解，比线性规划的求 解困难得多。线性规划有统一的单纯形求解方法，而解困难得多。线性规划有统一的单纯形求解方法，而 非线性

9、规划目前还没有统一的一般算法。非线性规划目前还没有统一的一般算法。 1.1 可行集（可行域）可行集（可行域） 给定非线性规划问题给定非线性规划问题1 1 如果如果1中中m=0，表示没有约束，称为无约束优化，表示没有约束，称为无约束优化 问题，否则就是一般意义上的非线性规划模型。问题，否则就是一般意义上的非线性规划模型。 12n i12n i12n min f(x ,x ,x ) g (x ,x ,x )0,i1,2,.,l s.t. h (x ,x ,x )0,il 1,.,m 10 若若x满足满足1的约束条件，则称的约束条件，则称x为为1的一个可的一个可 行解。所有可行解的集合称为可行域（或

10、可行集），记行解。所有可行解的集合称为可行域（或可行集），记 i1n i1n g (x ,.,x )0,i1,2,.,l; dx h (x ,.,x )0,il1,.,m 1.2 局部极小点（局部最优解）局部极小点（局部最优解） 对于非线性规划对于非线性规划1，若存在，若存在d*x ，且对一切，且对一切 满足满足 |*xx|（即（即x为为x*附近的点），附近的点），都有都有 )x(f*)x(f 则称则称x*为为f(x)在在d上的局部极小点（局部最优解）。上的局部极小点（局部最优解）。 11 当当 *xx 时，若时，若 )x( f*)x( f，则称，则称x*为为f(x)在在 d上的严格局部最优解

11、。上的严格局部最优解。 1.3 全局最优解（全局极小值点）全局最优解（全局极小值点） 对于非线性规划对于非线性规划1，若存在，若存在 d*x ，且对一切，且对一切 都有都有 )x(f*)x(f 则称则称x*为为f(x)在在d上的全局极小点（全局局最优解）。上的全局极小点（全局局最优解）。 dx 注意：局部最优和全局最优实际就是高数中的极值注意：局部最优和全局最优实际就是高数中的极值 与最值问题。与最值问题。 12 x y=f(x) 0 ab x1x2x3x4x5 x6 x1,x3,x5为为f(x)的局部极小值点；的局部极小值点；x2,x4,x6为为f(x)的局的局 部极大值点；部极大值点；x4

12、为全局最大值点；为全局最大值点；x3是全局最小值点。是全局最小值点。 13 3、非线性规划的图解法、非线性规划的图解法 例例2 利用图解法，求解如下非线性规划问题利用图解法，求解如下非线性规划问题 0 x 0 x 05xx 05xxx ) 1x()2(x)x,f(xmin 2 1 21 2 2 21 2 2 2 121 分析分析：决策变量为：决策变量为x=(x1,x2)t。目标函数表示决策变。目标函数表示决策变 =(x1,x2)t到点到点(2,1)t的距离的平方（体现为圆周半径的距离的平方（体现为圆周半径 变化）；第一个约束是一条抛物线（开口朝左变化）；第一个约束是一条抛物线（开口朝左,x1为

13、横为横 轴）；第二个约束为直线；同时决策变量非负。轴）；第二个约束为直线；同时决策变量非负。 14 解解 以以x1和和x2分别为横轴和纵轴，建立直角坐标系，分别为横轴和纵轴，建立直角坐标系， 如图如图2-2： （1）绘制约束曲线）绘制约束曲线 （2）标出可行域：）标出可行域： 图图2-2 15 x1 x2 0 5xx 21 (右上右上) 2.5 4 25 ) 2 5 x(x 2 21 (在抛物线上在抛物线上) 1 2 22 2 2 1 r) 1x() 2(x a b c d 16 （3）绘制目标函数曲线）绘制目标函数曲线 该问题的目标曲线是圆，该问题的目标曲线是圆， 以以(2,1)t为圆心，半

14、径为圆心，半径 随着随着(x1,x2)t变化而变化，变化而变化， 当半径达到最小，则目当半径达到最小，则目 标函数也达到最小。让标函数也达到最小。让 目标曲线随着目标意愿目标曲线随着目标意愿 变化，本题的变化，本题的全局最优全局最优 点是点是d(4,1)，如图所示。如图所示。 另外，另外，b(2.9104,4.3275)t是局部最小点是局部最小点（严格局部（严格局部 最优解）最优解）;目标函数的目标函数的最大点是最大点是a(0,5),c(2.5,2.5)点点 是局部最大点。是局部最大点。 17 4.1 线性规划问题的最优解一定在可行域的边界的顶线性规划问题的最优解一定在可行域的边界的顶 点处达

15、到，任何一个最优解，就是全局最优解。点处达到，任何一个最优解，就是全局最优解。 4.2 非线性规划的最优解可以在可行域内任何一点处达非线性规划的最优解可以在可行域内任何一点处达 到，非线性规划求解出来的只是局部最优解。所以在到，非线性规划求解出来的只是局部最优解。所以在 针对非线性规划求解时，具体问题，有具体的搜索最针对非线性规划求解时，具体问题，有具体的搜索最 优解的方法，一般注意：优解的方法，一般注意： 4、建立规划模型的注意点、建立规划模型的注意点 （1）尽可能给出靠近全局最优解附近的初始可行解；）尽可能给出靠近全局最优解附近的初始可行解； （2）尽可能给出每个决策分量的比较准确的上下界

16、；）尽可能给出每个决策分量的比较准确的上下界； （3）能够线性化的表达式，尽量线性化；）能够线性化的表达式，尽量线性化； （4）尽量每个表达式连续可导（起码二阶）；）尽量每个表达式连续可导（起码二阶）； （5）非线性规划每次求解结果不一定相同。）非线性规划每次求解结果不一定相同。 18 4.3 在建立规划模型时，尽量做到：在建立规划模型时，尽量做到： 1、尽量用线性代替非线性；、尽量用线性代替非线性； 2、尽量用连续函数，若遇到分段函数，尽可能连续、尽量用连续函数，若遇到分段函数，尽可能连续 化或者用特殊手段处理；化或者用特殊手段处理； 3、尽量写成乘积而不是除法；、尽量写成乘积而不是除法；

17、4、尽量用实数变量，少用整数变量；、尽量用实数变量，少用整数变量； 5、尽量给出变量的准确上下界，有利于更快搜索到、尽量给出变量的准确上下界，有利于更快搜索到 最优解；最优解； 6、复杂的式子，尽量化简表达式。、复杂的式子，尽量化简表达式。 19 例例3 组合投资问题组合投资问题 假设某公司在下一个计划期内可用于投资的总资假设某公司在下一个计划期内可用于投资的总资 本为本为b万元，可供选择的投资项目为万元，可供选择的投资项目为n个，分别记为个，分别记为 1,2,n。已知对第。已知对第j项目的投资额为项目的投资额为aj万元，而收益总万元，而收益总 额为额为cj万元。问如何投资，才能使得利润率（单位投万元。问如何投资，才能使得利