第11讲 数模 非线性规划.ppt

1、1.第11讲：非线性规划，目的；3.掌握如何用数学软件解决优化问题；1.理解非线性规划的基本内容；2.巧妙地建立非线性规划的数学模型；1.非线性规划的基本概念和解法；4.家庭作业；2.用数学软件求解非线性规划；3.建立模型和解决实例。定义了如果目标函数或约束条件中至少有一个是非线性函数，优化问题称为非线性规划问题。不存在的编程的基本概念，一般形式： (1)，是在En上定义的实函数，缩写为：在其他情况下，当目标函数或约束条件的最大值小于或等于零时，可以通过取其逆将其转化为上述一般形式。3，定义2对于问题(1)，假设，如果有，那么对于所有事物，都有，那么X*是D上f(X)的局部最小点(局部最优解)

2、，特别是当它是3360时，那么X*是D上f(X)的严格局部最小点(严格局部最优解)，定义3对于问题，X*被认为是D上f(X)的全局最小点(全局最优解)，特别是当，如果， 则称X*为d上f(X)的严格全局最小点(严格全局最优解)，定义1称满足问题(1)中条件的解为可行解(或可行点)，所有可行点的集合称为可行集。 SUTM外点法，SUTM内点法(障碍罚函数法)，1。罚函数法，2。近似编程方法。罚函数法。罚函数法的基本思想是通过构造罚函数将约束问题转化为一系列无约束优化问题，然后用无约束优化方法求解。这种方法称为序列无约束最小化方法，简称SUMT方法。T(X，M)称为罚函数，M称为罚因子，M项称为罚

3、项。这里，惩罚函数只惩罚不满足约束的点：当所有条件都满足时，惩罚项=0，当没有惩罚时，必须有约束，所以惩罚项是0，所以必须惩罚。SUTM外点法，7。罚函数法的缺点是每个近似最优解。在求解一系列无约束问题时，计算量太大，特别是随着Mk的增加，可能会导致误差。1.给定任何初始点X0，取M11，给定允许误差，让K=1；2.找到无约束极值问题的最优解，并将其设置为Xk=X(Mk)，即3。如果存在，让MkM()使k=k 1返回到(2)，否则，停止迭代以获得最优解。收敛标准也可以更改为。SUTM外点法(罚函数法)的迭代步骤，8。内点法。近似规划法的基本思想是：将问题(3)中的目标函数和约束条件近似为线性函

4、数，并限制变量的取值范围，从而得到一个近似线性规划问题，然后用单纯形法求解，并将满足原条件的最优解作为问题(3)解的近似。近似编程方法从这一点开始，并在获得每个近似解后重复上述步骤。，11，近似规划法的算法步骤如下，12，13，用MATLAB求解非线性规划，2，一般非线性规划，1，二次规划，14，用Matlab软件求解，其输入格式如下： 1.x=四次规划(H，C，A，B)；2.x=四进制程序(H、C、A、b、Aeq、beq)；3.x=四进制程序(H、C、A、B、Aeq、beq、VLB、VUB)；4.x=四进制程序(H、C、A、B、Aeq、beq、VLB、VUB、X0)；5.x=四进制程序(H、

5、C、A、B、Aeq、beq、VLB、VUB、X0、选项)；6.x，fval=quaprog(.)；7.x，fval，exitflag=quaprog(.)；8.x，fval，exitflag，output=quaprog(.)；1。二次规划，标准形式是：15，例如1分钟f (x1，x2)=-2x 1-6x2x 12-2x1x 22x 22s . t . x1x 22-x1 2x 22x 10，x20，MATLAB(you 1)，1。写标准表格。输入命令：h-12；c=-2；-6；A=1 1-12；b=2；2 .aeq=；beq=；VLB=0；0；VUB=；x，z=四进制程序(h，c，a，b，a

6、eq，beq，vlb，vub)，3。运算结果为：x=0.6667 1.3333z=-8.2222，s.t .16，1。首先，建立m文件格式。2.一般非线性规划，其中X是n维变量向量，G(X)和Ceq(X)是由非线性函数组成的向量，其他变量的含义与线性规划和二次规划中的相同。用Matlab解决上述问题，基本步骤分为三步：标准类型是：3。建立主程序。求解非线性规划的函数是fmincon。命令的基本格式如下：(1) x=fmincon (fun，x0，A，b) (2) x=fmincon (fun，x0，A，b，aeq，beq) (3) x=fmincon (fun，x0，A，b，aeq，beq)

7、VLB，VUB，非lcon) (5)x=fmincon(fun，X0，A，b，Aeq，beq，VLB，VUB，非lcon，选项)(6) x，fval=fmincon(.)(7) x，fval，exitflag=fmincon(.)(8)x，fval，Exitflag，output=fmincon(.)，输出极值点，m文件，迭代初始值，参数描述，变量的上下限，18，注：1 fmincon函数提供大优化算法和中优化算法。默认情况下，如果在fun函数中提供梯度(选项的GradObj参数设置为on)，并且只存在上下限或等式约束，fmincon函数将选择大算法。当等式约束和梯度约束同时存在时，使用中等大

8、小的算法。2 fmincon函数的中型算法使用序列二次规划。二次规划子问题在每次迭代中求解，拉格朗日海森矩阵用BFGS方法更新。3 fmincon函数可以给出与初始值X0的选择相关的局部最优解。，19，1。用标准格式写：s.t .20，2。首先创建M文件fun3.m:函数f=fun 3(x)；f=-x(1)-2 * x(2)(1/2)* x(1)2(1/2)* x(2)2，MATLAB(you 2)，3。构建主程序you 2 . m:x0=1=1；1 .a=2 3；1 4；b=6；5 .aeq=；beq=；VLB=0；0；VUB=；x，fval=fmincon (fun3，x0，a，b，aeq

9、，beq，vlb，vub)，4。计算结果为：x=0.7647 1.0588 fval=-2.0294，21，1。首先，建立m文件fun4.m并定义目标函数33366。f=exp(x(1)*(4 * x(1)2 2 * x(2)2 4 * x(1)* x(2)2 * x(2)1)；在情况3和2中，m文件定义了非线性约束：函数g，CEQ=m(x)g=x(1)x(2)；1.5 x(1)* x(2)-x(1)-x(2)；-x(1)* x(2)-10；CEQ=；22，3主程序youh3.m为： x0=-1；1 .a=；b=；Aeq=1 1beq=0；vlb=；vub=；x，fval=fmincon (f

10、un.m，x0，a，b，aeq，beq，vlb，vub，mycon)，MATLAB(you 3)，3。计算结果为：x=-1.2250 1.2250 fval=1.8951，23，1。首先建立移动文件。f=-2 * x(1)-x(2)；2。然后建立M文件，M定义非线性约束：函数g，CEQ=M N2(x)g=x(1)2 x(2)2-25；x(1)2-x(2)2-7；CEQ=；示例4，24，MATLAB(fxx(fun)，3。主程序fxx.m为：x0=3；2.5；VLB=0 0；VUB=5 10；x，fval，exitflag，output=fmincon(fun，x0，VLB，VUB，mycon2

11、)，25，结果是： x=4.0000 3.0000 fval=-11.0000 exit flag=1 output=1迭代3360 4函数计数3360 17步长3360 1算法3360 1x44 char一阶opt : CG迭代3360，26，示例5，函数y=08 * x(1)14 * x(2)7 * x(3)-56；c=；1。首先创建M文件fun5.m来定义目标函数：然后创建M文件myc 2 . M来定义非线性约束：27，3。主程序是：x0=1；1 .1 .XM=0；0；0；XM=；a=；b=；aeq=；beq=；x，f，c，d=fmincon (fun5，x0，a，b，aeq，beq，X

12、M，XM，mycon5)，4。运算结果为：x=3.5231 0.2161 3.5413 f=961.7621 c=1d=迭代： 8函数计数： 46步长： 1算法：中尺度： SQP，准牛顿，线搜索火星表Opt : 9.3926e-006 CG迭代3360，应用示例：供应和站点目前，甲(5，1)和乙(2，7)有两个临时堆场，日储量各为20吨。假设从料场到施工现场有一条笔直的道路。(1)尽量制定每日供应计划，即从a、b料场向每个施工现场运送多少吨水泥，以尽量减少总吨数和公里数。(2)为了进一步减少吨公里数，计划放弃两个临时堆场，重建两个新堆场，每个堆场日储备量为20吨。它应该建在哪里，能节省多少吨和

13、公里？(1)建立模型，将施工现场的位置记为(ai，bi)，每日水泥消耗量记为di，i=1，6；堆场位置为(xj，yj)，日储量为ej，j=1，2；从j场到I场的运输数量为Xij。决策变量为：使用临时堆场时为Xij，不使用临时堆场时为Xij、xj和yj。(2)当使用临时堆料场时，使用两个临时堆料场A(5，1)和B(2，7)。将堆场J至施工现场I的运输量设为Xij，在每个堆场的运输量必须满足日储备量的情况下，将总吨数和总公里数最小化。这是一个线性规划问题。线性规划模型是：让X11=X1，X21。X51=x 5，x61=x6x12=x 7，x22=x 8，x32=x 9，x42=x 10，x52=x

14、 11，x62=x 12。编写程序ying 1.m，MATLAB (ying 1)，清零a=1.25 8.75 0.5 b=1.25 0.75 4.75 5 6.5 7.75；d=3 5 4 7 6 11x=5 2；y=1 7；e=20 20对于i=1:6，对于j=1:2 aa(i，j)=sqrt(x(j)-a(I)2(y(j)-b(I)2)；结束端，CC=aa(:1)；aa(:2)；a=1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1B=20。20；aeq=1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1；beq=d(1)；d(2)；d(3)；d(4)；d(5)；d(6)；VLB=0 0 0 0 0 0 0 0 0 0 0 0；VUB=；x0=1 2 3 0 1 0 0 1 0 1 0 1Xx，fval=linprog