《优化问题求解》PPT课件.ppt

matlab应用（一）,主讲：杨圣红2011.8.,线性规划求解方法 无约束规划求解方法 约束非线性规划求解方法 多目标规划问题 非线性方程(组)求解,教学内容,生产炊事用具需要两种资源-劳动力和原材料,某公司制定生产计划,生产三种不同产品,生产管理部门提供的数据如下:,每天供应原材料200kg,每天可供使用的劳动力为150h,求各种产品的日产量为多少时,总收益最大?,线性规划求解方法,线性规划模型,1、确定决策变量.设生产A产品x1,B产品x2,C产品x32、确定目标函数.max Z=4x1+2x2+3x33、确定约束条件.劳动力:7x1+3x2+6x3150 原材料:4x1+4x2+5x3200 非负性约束:x10,x20,x30,线性规划求解方法,线性规划的一般形式:,得以上问题的数学模型为：,线性规划求解方法,线性规划问题模型的一般形式：,线性规划求解方法,线性规划问题模型的矩阵形式：,注：1 若没有等式约束:AeqX=beq,则令Aeq=,beq=2其中x0表示初始点,线性规划模型的Matlab求解命令：,线性规划求解方法,c=4 2 3;A=7 3 6;4 4 5;b=150;200;VUB=;Aeq=;beq=;VLB=0;0;0;x,f=linprog(c,A,b,Aeq,beq,VLB,VUB),例：,max Z=4x1+2x2+3x3s.t.7x1+3x2+6x3150 4x1+4x2+5x3200 x10,x20,x30,Matlab命令如下：,线性规划求解方法,思考：此程序正确吗？,正确结果输出如下：,x=0.0000 50.0000 0.0000f=-100.0000,当A、B、C产品的日产量分别为0件，50件，0件时，总收益为100元/件,线性规划求解方法,例 max,线性规划求解方法,程序见lpexp1.m,x=1.0e+004*3.5000 0.5000 3.0000 0.0000 0.0000 0.0000fval=-2.5000e+004,即：最优解为x=104(3.5,0.5,3,0,0,0),最优值为z=2.5104,线性规划求解方法,正确结果输出如下：,例,线性规划求解方法,程序见lpexp2.m,x=30.0000 50.0000 40.0000fval=490.0000即最优解为x=(30，50，40),最优值为z=490.,线性规划求解方法,正确结果输出如下：,某皮鞋公司每日8小时的皮鞋产量不低于1800双.为了进行质量控制，计划聘请两种不同水平的检验员.一级检验员的标准为速度25双/小时，正确率98%，计时工资4元/小时；二级检验员的标准为速度15双/小时，正确率95%，计时工资3元/小时.检验员每错检一次，企业要损失2元.为使总检验费用最省，该公司应聘一级、二级检验员各几名？,例:人员聘任问题,线性规划求解方法,解 设需要一级和二级检验员的人数分别为,人,则应付检验员的工资为,因检验员错检而造成的损失为,故目标函数为,约束条件为,线性规划求解方法,线性规划模型,x=9.0000 0.0000fval=360,lpexp3.m,即只需聘用9个一级检验员.,线性规划求解方法,无约束问题,无约束规划求解方法,无约束优化问题的标准型为：其中x为n维向量,无约束优化问题没有约束条件的优化问题，称之为无约束规划。自变量可取n维实空间中任意点。,fminbnd 求单变量函数最小值点 fminsearch 求多变量函数最小值点 fminunc 求多变量函数最小值点,matlab求解命令,一、fminbnd调用格式：,x=fminbnd(fun,x1,x2)x=fminbnd(fun,x1,x2,options)x=fminbnd(fun,x1,x2,options,P1,P2,.)x,fval=fminbnd(.)x,fval,exitflag=fminbnd(.)x,fval,exitflag,output=fminbnd(.),无约束规划求解方法,说明：fun 为目标函数，用M文件或Inline定义x1，x2为目标函数的自变量的取值范围 options是一个结构型的变量，用于指定优化参数，可通过optimset函数设置-help optimset,例：求解,x,fval=fminbnd(cos(4*x+5),0,pi/2),无约束规划求解方法,matlab求解命令,运行结果,x=1.1062fval=-1.0000,例：求解模型,该模型的最小值点，也就是原模型的最大值点。方法1：1、先建立目标函数文件2、调用fminbnd,首先转化为,无约束规划求解方法,方法1：,1、定义目标函数：funmin1.m文件function f=funmin1(x)f=x*(-x*x+8+15*x);,无约束规划求解方法,2、输入命令求解x,fval=fminbnd(funmin1,-10,10)x=-0.2599fval=-1.0484即当x-0.2599时，取得最大值1.0484。,运行结果,方法2：采用内联函数,定义内联函数用inline。输入命令：f=inline(-x*(x*x-15*x-8)x,fval=fminbnd(f,-10,10),无约束规划求解方法,二、fminsearch调用格式：,fminsearch用于求多变量函数的最小值点，它采用Neder-Mead单纯形算法。调用格式：（更多格式请查看help文件）x,fval,exitflag,output=fminsearch(fun,x0,options),无约束规划求解方法,说明：若参数exitflag0，表示函数收敛于x，若exitflag=0，表示超过函数估计值或迭代的最大数字，exitflag0表示函数不收敛于x；若参数output=iterations表示迭代次数，output=funccount表示函数赋值次数，output=algorithm表示所使用的算法。,例：,1、编写函数：fun1search.m文件function f=fun1search(x)f=2*(x(1)-1)2+3*(x(2)-3)2;2、输入命令求解：x,fval,exitflag=fminsearch(fun1search,0 0),无约束规划求解方法,结果：,x=1.0000 3.0000fval=3.1076e-009exitflag=1,无约束规划求解方法,无约束规划求解方法,演示用help/doc fminunc查看fminunc函数的用法。并用fminunc求解以下模型：,注意：当函数的阶数大于2时，使用fminunc比fminsearch更有效，但当所选函数高度不连续时，使用fminsearch效果较好。,min f(x)=100*(x(2)-x(1)2)2+(1-x(1)2,约束非线性规划求解方法,引例：,约束非线性规划求解方法,某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？,非线性规划模型,约束非线性规划求解方法,定义 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题,一般形式:其中，是定义在 En 上的实值函数，简记:,用MATLAB软件求解,其输入格式如下:1.x=quadprog(H,C,A,b);2.x=quadprog(H,C,A,b,Aeq,beq);3.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB);4.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0);5.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options);6.x,fval=quadprog(.);7.x,fval,exitflag=quadprog(.);8.x,fval,exitflag,output=quadprog(.);,1、二次规划,标准型为：,约束非线性规划求解方法,例 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t.x1+x22-x1+2x22 x10,x20,1、写成标准形式：,2、输入命令：H=1-1;-1 2;c=-2;-6;A=1 1;-1 2;b=2;2;Aeq=;beq=;VLB=0;0;VUB=;x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB),s.t.,约束非线性规划求解方法,1.首先建立M文件fun.m,定义目标函数F（X）:function f=fun(X);f=F(X);,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,VLB,VUB)(4)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon)(5)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options)(6)x,fval=fmincon(.)(7)x,fval,exitflag=fmincon(.)(8)x,fval,exitflag,output=fmincon(.),输出极值点,M文件,迭代的初值,参数说明,变量上下限,约束非线性规划求解方法,注意：1 fmincon函数提供了大型优化算法和中型优化算法。默认时，若在fun函数中提供了梯度（options参数的GradObj设置为on），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。2 fmincon函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hessian矩阵。3 fmincon函数可能会给出局部最优解，这与初值X0的选取有关。,约束非线性规划求解方法,1、写成标准形式：,2x1+3x2 6 s.t x1+4x2 5 x1,x2 0,例,约束非线性规划求解方法,s.t.,2、先建立M-文件 fun3.m:function f=fun3(x);f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2,3、再建立主程序youh2.m：x0=1;1;A=2 3;1 4;b=6;5;Aeq=;beq=;VLB=0;0;VUB=;x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB),4、运算结果为：x=0.7647 1.0588 fval=-2.0294,约束非线性规划求解方法,1先建立M文件 fun4.m,定义目标函数:function f=fun4(x);f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,例,2再建立M文件mycon.m定义非线性约束：function g,ceq=mycon(x)g=1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;ceq=;,约束非线性规划求解方法,3主程序youh3.m为:x0=-1;1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon),3.运算结果为：x=-1.2250 1.2250 fval=1.8951,约束非线性规划求解方法,例,1先建立M-文件fun.m定义目标函数:function f=fun(x);f=-2*x(1)-x(2);,2再建立M文件mycon2.m定义非线性约束：function g,ceq=mycon2(x)g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;,约束非线性规划求解方法,3.主程序fxx.m为:x0=3;2.5;VLB=0 0;VUB=5 10;x,fval,exitflag,output=fmincon(fun,x0,VLB,VUB,mycon2),约束非线性规划求解方法,4.运算结果为:x=4.0000 3.0000fval=-11.0000exitflag=1output=iterations:4 funcCount:17 stepsize:1 algorithm:1x44 char firstorderopt:cgiterations:,约束非线性规划求解方法,例：供应与选址,某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？,约束非线性规划求解方法,（一）、建立模型,记工地的位置为(ai，bi)，水泥日用量为di，i=1,6;料场位置为(xj，yj)，日储量为ej，j=1,2；从料场j向工地i的运送量为Xij。,当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj。,约束非线性规划求解方法,（二）使用临时料场的情形,使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题.线性规划模型为：,设X11=X1,X21=X 2,X31=X 3,X41=X 4,X51=X 5,X61=X 6X12=X 7,X22=X 8,X32=X 9,X42=X 10,X52=X 11,X62=X 12,约束非线性规划求解方法,通过matlab编程计算结果为：,x=3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000fval=136.2275,约束非线性规划求解方法,（三）改建两个新料场的情形,改建两个新料场,要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小.这是非线性规划问题。非线性规划模型为：,约束非线性规划求解方法,设 X11=X1,X21=X 2,X31=X 3,X41=X 4,X51=X 5,X61=X 6 X12=X 7,X22=X 8,X32=X 9,X42=X 10,X52=X 11,X62=X 12 x1=X13,y1=X14,x2=X15,y2=X16,（1）先编写M文件liaoch.m定义目标函数。,(2)取初值为线性规划的计算结果及临时料场的坐标:x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;编写主程序gying2.m.,约束非线性规划求解方法,(3)计算结果为：,x=3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867fval=105.4626exitflag=1,约束非线性规划求解方法,(4)若修改主程序gying2.m,取初值为上面的计算结果:x0=3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867,得结果为:x=3.0000 5.0000 0.3094 7.0000 0.0108 0.6798 0 0 3.6906 0 5.9892 10.3202 5.5369 4.9194 5.8291 7.2852fval=103.4760exitflag=1,总的吨千米数比上面结果略优.,(5)若再取刚得出的结果为初值,却计算不出最优解.,约束非线性规划求解方法,(6)若取初值为:x0=3 5 4 7 1 0 0 0 0 0 5 11 5.6348 4.8687 7.2479 7.7499,则计算结果为:x=3.0000 5.0000 4.0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6959 4.9285 7.2500 7.7500fval=89.8835exitflag=1总的吨千米数89.8835比上面结果更好.,约束非线性规划求解方法,多目标规划问题,多目标规划问题,多目标规划是指在一组约束下，对多个不同目标函数进行优化。它的一般形式为,其中：,在同一约束下，当目标函数处于冲突状态时，不存在最优解x使所有目标函数同时达到最优。此时，我们使用有效解，即如果不存在,，使得,，i=1,2,m,多目标规划模型,则称x*为有效解。,一种常用的方法是将多目标转化为单目标求解。,多目标规划问题,在MATLAB中，多目标问题的标准形式为,其中：x、b、beq、lb、ub是向量；A、Aeq为矩阵；C(x)、Ceq(x)和F(x)是返回向量的函数；F(x)、C(x)、Ceq(x)可以是非线性函数；weight为权值系数向量，用于控制对应的目标函数与用户定义的目标函数值的接近程度；goal为用户设计的与目标函数相应的目标函数值向量；F(x)为多目标规划中的目标函数向量。,多目标规划问题,函数 fgoalattain格式 x=fgoalattain(fun,x0,goal,weight)x=fgoalattain(fun,x0,goal,weight,A,b)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options)x,fval=fgoalattain()x,fval,attainfactor=fgoalattain()x,fval,attainfactor,exitflag=fgoalattain()x,fval,attainfactor,exitflag,output=fgoalattain()x,fval,attainfactor,exitflag,output,lambda=fgoalattain(),多目标规划问题,非线性方程(组)求解,非线性方程的解,非线性方程(组)求解,非线性方程组的解,非线性方程(组)求解,练习题,1、求解以下线性规划问题 某企业拟生产A、B两种产品，需利用一种原材料并经过车、铣两台机床加工，加工的工时定额、每天可用工时和原材料以及两种产品可能获得的利润如下表所示：要求：1）拟定一个获得利润最大的生产计划；2）若单价0.8元再购入少量原材料投入生产是 否合算？为什么？,练习题,练习题,3、求解下面规划问题,练习题,4、求解下面规划问题,