《《优化问题求解》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《优化问题求解》PPT课件.ppt（63页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、matlab应用（一）主讲：杨圣红主讲：杨圣红2011.8.线性规划求解方法线性规划求解方法 无约束规划求解方法无约束规划求解方法 约束非线性规划求解方法约束非线性规划求解方法 多目标规划问题多目标规划问题 非线性方程非线性方程(组组)求解求解教学内容教学内容 生产炊事用具需要两种资源生产炊事用具需要两种资源-劳动力和原材料劳动力和原材料,某公司某公司制定生产计划制定生产计划,生产三种不同产品生产三种不同产品,生产管理部门提供的数据生产管理部门提供的数据如下如下:产品产品A产品产品B产品产品C资源限量资源限量劳动力劳动力(h/件件)原材料原材料(kg/件件)743 465150h200kg利润
2、元利润元/件件423每天供应原材料每天供应原材料200kg,每天可供使用的劳动力为每天可供使用的劳动力为150h,求求各种产品的日产量为多少时各种产品的日产量为多少时,总收益最大总收益最大?线性规划求解方法线性规划求解方法线性规划模型线性规划模型产品产品A产品产品B产品产品C资源限量资源限量劳动力劳动力(h/件件)原材料原材料(kg/件件)743 465150h200kg利润利润(元元/kg)4231、确定决策变量、确定决策变量.设生产设生产A产品产品x1,B产品产品x2,C产品产品x32、确定目标函数确定目标函数.max Z=4x1+2x2+3x33、确定约束条件确定约束条件.劳动力劳动力:
3、7x1+3x2+6x3150 原材料原材料:4x1+4x2+5x3200 非负性约束非负性约束:x10,x20,x30线性规划求解方法线性规划求解方法线性规划的一般形式:得以上问题的数学模型为：得以上问题的数学模型为：线性规划求解方法线性规划求解方法线性规划问题模型的一般形式：线性规划问题模型的一般形式：线性规划求解方法线性规划求解方法线性规划问题模型的矩阵形式：线性规划问题模型的矩阵形式：模型模型命令命令min z=cX，s.t.AXBx,f=linprog(c,A,b)min z=cX，s.t.AXB,AeqX=beqx,f=linprog(c,A,b,Aeq,beq)min z=cX，s
4、.t.AXB,AeqX=beq VLBXVUB1 x=linprog(c,A,b,Aeq,beq,VLB,VUB)2 x，f=linprog(c,A,b,Aeq,beq,VLB,VUB,x0)注：注：1 若没有等式约束若没有等式约束:AeqX=beq,则令则令Aeq=,beq=2其中其中x0表示初始点表示初始点 线性规划模型的线性规划模型的MatlabMatlab求解命令：求解命令：线性规划求解方法线性规划求解方法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)
5、例：例：max Z=4x1+2x2+3x3s.t.7x1+3x2+6x3150 4x1+4x2+5x3200 x10,x20,x30MatlabMatlab命令如下：命令如下：线性规划求解方法线性规划求解方法思考：此程序正确吗？思考：此程序正确吗？正确结果输出如下：正确结果输出如下：x=0.0000 50.0000 0.0000f=-100.0000当当A、B、C产品的日产量分别为产品的日产量分别为0件，件，50件，件，0件时，件时，总收益为总收益为100元元/件件线性规划求解方法线性规划求解方法例例 max 线性规划求解方法线性规划求解方法程序见程序见lpexp1.mlpexp1.mx=1.
6、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.mlpexp2.mx=30.0000 50.0000 40.0000fval=490.0000即最优解为即最优解为x=(30，50，40),最优值为最优值为z=490.线性规划求解方法线性规划求解方法正确结果输出如下：正确结果输出如下
7、：某皮鞋公司每日某皮鞋公司每日8小时的皮鞋产量不低于小时的皮鞋产量不低于1800双双.为了进行质量控制，计划聘请两种不同水平的检验员为了进行质量控制，计划聘请两种不同水平的检验员.一级检验员的标准为速度一级检验员的标准为速度25双双/小时，正确率小时，正确率98%，计时工资计时工资4元元/小时；二级检验员的标准为速度小时；二级检验员的标准为速度15双双/小时，正确率小时，正确率95%，计时工资，计时工资3元元/小时小时.检验员每错检检验员每错检一次，企业要损失一次，企业要损失2元元.为使总检验费用最省，该公司为使总检验费用最省，该公司应聘一级、二级检验员各几名？应聘一级、二级检验员各几名？例例
8、:人员聘任问题人员聘任问题线性规划求解方法线性规划求解方法解解 设需要一级和二级检验员的人数分别为 人,则应付检验员的工资为因检验员错检而造成的损失为故目标函数为约束条件为线性规划求解方法线性规划求解方法线性规划模型线性规划模型x=9.0000 0.0000fval=360lpexp3.m即只需聘用即只需聘用9个一级检验员个一级检验员.线性规划求解方法线性规划求解方法无约束问题无约束问题无约束规划求解方法无约束规划求解方法 无约束优化问题的标准型为：无约束优化问题的标准型为：其中其中x x为为n n维向量维向量 无约束优化问题没有约束条件的优化问题，称之为无无约束优化问题没有约束条件的优化问题
9、，称之为无约束规划。自变量可取约束规划。自变量可取n n维实空间中任意点。维实空间中任意点。q fminbnd 求单变量函数最小值点求单变量函数最小值点q fminsearch 求多变量函数最小值点求多变量函数最小值点q fminunc 求多变量函数最小值点求多变量函数最小值点matlabmatlab求解命令求解命令一、一、fminbndfminbnd调用格式：调用格式：x=fminbnd(fun,x1,x2)x=fminbnd(fun,x1,x2,options)x=fminbnd(fun,x1,x2,options,P1,P2,.)x,fval=fminbnd(.)x,fval,exitf
10、lag=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)无约束规划求解方法无约束规划求解方法matlabmatlab求解命令求解命
11、令运行结果运行结果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时，取得最大值时，取得
12、最大值1.0484。运行结果运行结果方法方法2 2：采用内联函数：采用内联函数定义内联函数用定义内联函数用inline。输入命令：输入命令：f=inline(-x*(x*x-15*x-8)x,fval=fminbnd(f,-10,10)无约束规划求解方法无约束规划求解方法 二、二、fminsearchfminsearch调用格式：调用格式：fminsearchfminsearch用用于于求求多多变变量量函函数数的的最最小小值值点点，它它采采用用NederNeder-MeadMead单纯形算法。单纯形算法。调用格式调用格式：（更多格式请查看：（更多格式请查看helphelp文件）文件）x,fva
13、l,exitflag,outputx,fval,exitflag,output=fminsearchfminsearch(fun,x0,options)(fun,x0,options)无约束规划求解方法无约束规划求解方法说明说明：若参数：若参数exitflag0，表示函数收敛于，表示函数收敛于x，若，若exitflag=0，表示超过函数估计值或迭代的最大数字，表示超过函数估计值或迭代的最大数字，exitflag0表示函数不收敛于表示函数不收敛于x；若参数；若参数output=iterations表示迭代次数，表示迭代次数，output=funccount表表示函数赋值次数，示函数赋值次数，ou
14、tput=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函数的用法
15、。并用函数的用法。并用fminunc求解以下模型：求解以下模型：注意：当函数的阶数大于注意：当函数的阶数大于2 2时，使用时，使用fminuncfminunc比比fminsearchfminsearch更有效，但当所选函数更有效，但当所选函数高度不连续时，使用高度不连续时，使用fminsearchfminsearch效果较好。效果较好。min f(x)=100*(x(2)-x(1)2)2+(1-x(1)2约束非线性规划求解方法引例：引例：约束非线性规划求解方法约束非线性规划求解方法 某公司有某公司有6个建筑工地要开工，每个工地的位置（用平面坐个建筑工地要开工，每个工地的位置（用平面坐标系标系a
16、，b表示，距离单位：千米表示，距离单位：千米）及水泥日用量）及水泥日用量d(吨吨)由下表由下表给出。目前有两个临时料场位于给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有，日储量各有20吨。假设从料场到工地之间均有直线道路相连。吨。假设从料场到工地之间均有直线道路相连。（1）试制定每天的供应计划，即从）试制定每天的供应计划，即从A，B两料场分别向各工两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。地运送多少吨水泥，使总的吨千米数最小。（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为建两个新的，
17、日储量各为20吨，问应建在何处，节省的吨千米吨，问应建在何处，节省的吨千米数有多大？数有多大？非线性规划模型非线性规划模型约束非线性规划求解方法约束非线性规划求解方法 定义定义 如果目标函数或约束条件中至少有一个是非线性函数如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做时的最优化问题就叫做非线性规划问题非线性规划问题 一般形式一般形式:其中其中 ，是定义在是定义在 E En n 上的实值函数上的实值函数，简记，简记:用MATLAB软件求解,其输入格式输入格式如下:1.x=quadprog(H,C,A,b);2.x=quadprog(H,C,A,b,Aeq,beq);3.x=
18、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
19、 -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求
20、解上述问题，基本步骤分三步：约束非线性规划求解方法约束非线性规划求解方法标准型为：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
21、)x,fval,exitflag=fmincon(.)(8)x,fval,exitflag,output=fmincon(.)输出极值点M文件迭代的初值参数说明变量上下限约束非线性规划求解方法约束非线性规划求解方法注意：注意：1 fmincon函数提供了大型优化算法和中型优化算法。默认时，若在fun函数中提供了梯度（options参数的GradObj设置为on），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。2 fmincon函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hes
22、sian矩阵。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)23、再建立主程序youh2.m：x0=1;1;A=2 3;1 4;b=6;5;Aeq=;beq=;VLB=0;0;VUB=;x,fval=fmincon(fun3,x0
23、,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=;约束非线性规划求
24、解方法约束非线性规划求解方法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=my
25、con2(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 firstor
26、deropt:cgiterations:约束非线性规划求解方法约束非线性规划求解方法例例：供应与选址供应与选址 某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？约束非线性规划求解方法约束非线性规划求解方法（一）、建
27、立模型（一）、建立模型 记工地的位置为记工地的位置为(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，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题.线性规划
28、模型为：设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约束非线性规划求解方法约束非线性规划求解方法（三）改建两个新料场的情形（三）改建两个新料场的情形 改建两个
29、新料场,要同时确定料场的位置(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;编写
30、主程序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
31、 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.0
32、000 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,多目标规划模型
33、多目标规划模型则称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=fgoalatt
34、ain(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
35、()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、求解下面规划问题