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

《第二讲 非线性规划基本概念.ppt》由会员分享，可在线阅读，更多相关《第二讲 非线性规划基本概念.ppt（20页珍藏版）》请在优知文库上搜索。

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

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

3、方成反比，与照射角度的平方成反比，与照射角度1 1的正弦成正比。即的正弦成正比。即21111rsinPkI其中，其中，k为比例系数，同时也是平衡量纲（单位）的量。为比例系数，同时也是平衡量纲（单位）的量。3解解所有的变量设置如图所有的变量设置如图2-1所示所示两只灯在点两只灯在点x处的照度为处的照度为21III其中，其中，2222221111rsinPkI,rsinPkI变量之间的关系变量之间的关系，21211hxhsin,)xs(hhsin22222.)xs(hr,hxr22222121这个公式只是适合点光源，如果不是点光这个公式只是适合点光源，如果不是点光源（比如竖着的日光灯，该怎么办？源

4、（比如竖着的日光灯，该怎么办？4问题一：灯高度不变，求路面照度最弱最强的位置问题一：灯高度不变，求路面照度最弱最强的位置x。数学模型数学模型1;IIImax(min)212222221111rsinPkI,rsinPkI，21211hxhsin,)xs(hhsin22222.)xs(hr,hxr22222121s.x0s.t.也可以化简为也可以化简为5)h)xs(Ph)hx(PhkI max(min)23222222321211sx0s.t.代入已知参数，模型简化为代入已知参数，模型简化为.20 x0.t.s)36)x20(18)25(x10kI(x)max(min)232232 即求一元函数

5、即求一元函数I(x)在在0，20上的最大值与最小上的最大值与最小值。值。6问题问题2：当：当3kw的灯的高度在的灯的高度在3m到到9m之间变化时，路之间变化时，路面的最暗和最亮点。面的最暗和最亮点。数学模型数学模型2.9h320,x0.t.s;)h)x20(h3)25(x10k)hI(x,max(min)22322222322 即求二元函数即求二元函数I(x,h2)在所给条件下的上的最大在所给条件下的上的最大值与最小值。值与最小值。7问题问题3：两只灯的高度都在：两只灯的高度都在3m到到9m之间变化时，求之间变化时，求路面的最暗和最亮点。路面的最暗和最亮点。数学模型数学模型3.9h3,9h32

6、0,x0.t.s;)h)x20(h3)h(x2hk)h,hI(x,max(min)2123222223212121 即求三元函数即求三元函数I(x,h1,h2)在所给条件下的上的最大在所给条件下的上的最大值与最小值。值与最小值。像这种目标函数或者约束条件是决策变量的非像这种目标函数或者约束条件是决策变量的非一次（非线性）的规划问题，称为非线性规划模型。一次（非线性）的规划问题，称为非线性规划模型。8二、非线性规划模型二、非线性规划模型 在建立规划模型时，若目标函数中决策变量或者在建立规划模型时，若目标函数中决策变量或者约束方程（不等式）中某些变量为非一次（不是线约束方程（不等式）中某些变量为非

7、一次（不是线性），则称建立的数学模型为非线性规划模型。其数性），则称建立的数学模型为非线性规划模型。其数学模型一般为学模型一般为12ni12ni12nmin f(x,x,x)g(x,x,x)0,i1,2,.,Ls.t.h(x,x,x)0,iL 1,.,m1n1ni1ni1nmaxf(x,x)minf(x,x)g(x,x)0g(x,.,x)0若若1、非线性规划模型、非线性规划模型192、非线性规划问题的解的相关概念、非线性规划问题的解的相关概念 一般来说，非线性规划的求解，比线性规划的求一般来说，非线性规划的求解，比线性规划的求解困难得多。线性规划有统一的单纯形求解方法，而解困难得多。线性规划有

8、统一的单纯形求解方法，而非线性规划目前还没有统一的一般算法。非线性规划目前还没有统一的一般算法。1.1 可行集（可行域）可行集（可行域）给定非线性规划问题给定非线性规划问题11如果如果1中中m=0，表示没有约束，称为无约束优化，表示没有约束，称为无约束优化问题，否则就是一般意义上的非线性规划模型。问题，否则就是一般意义上的非线性规划模型。12ni12ni12nmin f(x,x,x)g(x,x,x)0,i1,2,.,Ls.t.h(x,x,x)0,iL 1,.,m10 若若x满足满足1的约束条件，则称的约束条件，则称x为为1的一个可的一个可行解。所有可行解的集合称为可行域（或可行集），记行解。所

9、有可行解的集合称为可行域（或可行集），记i1ni1ng(x,.,x)0,i1,2,.,L;Dxh(x,.,x)0,iL1,.,m1.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上的严格局部最优解。上的严格局部最优解。1.3 全局最优解（全局极小值点）全局最优解（全局

10、极小值点）对于非线性规划对于非线性规划1，若存在，若存在D*x，且对一切，且对一切都有都有)x(f*)x(f则称则称x*为为f(x)在在D上的全局极小点（全局局最优解）。上的全局极小点（全局局最优解）。Dx 注意：局部最优和全局最优实际就是高数中的极值注意：局部最优和全局最优实际就是高数中的极值与最值问题。与最值问题。12xy=f(x)0abx1x2x3x4x5x6 x1,x3,x5为为f(x)的局部极小值点；的局部极小值点；x2,x4,x6为为f(x)的局的局部极大值点；部极大值点；x4为全局最大值点；为全局最大值点；x3是全局最小值点。是全局最小值点。133、非线性规划的图解法、非线性规划

11、的图解法例例2 利用图解法，求解如下非线性规划问题利用图解法，求解如下非线性规划问题0 x0 x05xx05xxx)1x()2(x)x,f(xmin21212221222121分析分析：决策变量为：决策变量为x=(x1,x2)T。目标函数表示决策变。目标函数表示决策变=(x1,x2)T到点到点(2,1)T的距离的平方（体现为圆周半径的距离的平方（体现为圆周半径变化）；第一个约束是一条抛物线（开口朝左变化）；第一个约束是一条抛物线（开口朝左,x1为横为横轴）；第二个约束为直线；同时决策变量非负。轴）；第二个约束为直线；同时决策变量非负。14解解 以以x1和和x2分别为横轴和纵轴，建立直角坐标系，

12、分别为横轴和纵轴，建立直角坐标系，如图如图2-2：（1）绘制约束曲线）绘制约束曲线（2）标出可行域：）标出可行域：图图2-215x1x205xx21(右上右上)2.5425)25x(x221(在抛物线上在抛物线上)1222221R)1x()2(xABCD16（3）绘制目标函数曲线）绘制目标函数曲线该问题的目标曲线是圆，该问题的目标曲线是圆，以以(2,1)T为圆心，半径为圆心，半径随着随着(x1,x2)T变化而变化，变化而变化，当半径达到最小，则目当半径达到最小，则目标函数也达到最小。让标函数也达到最小。让目标曲线随着目标意愿目标曲线随着目标意愿变化，本题的变化，本题的全局最优全局最优点是点是D

13、(4,1)，如图所示。如图所示。另外，另外，B(2.9104,4.3275)T是局部最小点是局部最小点（严格局部（严格局部最优解）最优解）;目标函数的目标函数的最大点是最大点是A(0,5),C(2.5,2.5)点点是局部最大点。是局部最大点。174.1 线性规划问题的最优解一定在可行域的边界的顶线性规划问题的最优解一定在可行域的边界的顶点处达到，任何一个最优解，就是全局最优解。点处达到，任何一个最优解，就是全局最优解。4.2 非线性规划的最优解可以在可行域内任何一点处达非线性规划的最优解可以在可行域内任何一点处达到，非线性规划求解出来的只是局部最优解。所以在到，非线性规划求解出来的只是局部最优

14、解。所以在针对非线性规划求解时，具体问题，有具体的搜索最针对非线性规划求解时，具体问题，有具体的搜索最优解的方法，一般注意：优解的方法，一般注意：4、建立规划模型的注意点、建立规划模型的注意点（1）尽可能给出靠近全局最优解附近的初始可行解；）尽可能给出靠近全局最优解附近的初始可行解；（2）尽可能给出每个决策分量的比较准确的上下界；）尽可能给出每个决策分量的比较准确的上下界；（3）能够线性化的表达式，尽量线性化；）能够线性化的表达式，尽量线性化；（4）尽量每个表达式连续可导（起码二阶）；）尽量每个表达式连续可导（起码二阶）；（5）非线性规划每次求解结果不一定相同。）非线性规划每次求解结果不一定相

15、同。184.3 在建立规划模型时，尽量做到：在建立规划模型时，尽量做到：1、尽量用线性代替非线性；、尽量用线性代替非线性；2、尽量用连续函数，若遇到分段函数，尽可能连续、尽量用连续函数，若遇到分段函数，尽可能连续化或者用特殊手段处理；化或者用特殊手段处理；3、尽量写成乘积而不是除法；、尽量写成乘积而不是除法；4、尽量用实数变量，少用整数变量；、尽量用实数变量，少用整数变量；5、尽量给出变量的准确上下界，有利于更快搜索到、尽量给出变量的准确上下界，有利于更快搜索到最优解；最优解；6、复杂的式子，尽量化简表达式。、复杂的式子，尽量化简表达式。19例例3 组合投资问题组合投资问题 假设某公司在下一个

16、计划期内可用于投资的总资假设某公司在下一个计划期内可用于投资的总资本为本为b万元，可供选择的投资项目为万元，可供选择的投资项目为n个，分别记为个，分别记为1,2,n。已知对第。已知对第j项目的投资额为项目的投资额为aj万元，而收益总万元，而收益总额为额为cj万元。问如何投资，才能使得利润率（单位投万元。问如何投资，才能使得利润率（单位投资获得的收益）最高？资获得的收益）最高？解：设投资决策变量为解：设投资决策变量为n,.,2,1jj0j,1xj，个项目不投资，若对第个项目投资若对第20n,.,2,1j;1,0 x,bxa.t.sxaxc)x,.,x(fmaxjn1jjjn1jjjn1jjjn1 注意：此问题的目标函数不是一次（线性），且注意：此问题的目标函数不是一次（线性），且决策变量是决策变量是0-1决策变量，称为决策变量，称为0-1非线性规划。非线性规划。数学模型为数学模型为