实验数学六：MATLAB在优化中的应用.ppt

1,MATLAB在优化中的应用,2.1实验目的,在研究与解决具体问题中，经常遇到有关优化问题，本实验的目的是学会用MATLAB软件求解一些优化问题，包括求解线性规划和非线性规划等问题。,2.2实验内容,1、线性规划求解,线性规划是运筹学的一个重要分支，它起源于工业生产组织管理的决策问题。在数学上它用来确定多变量线性函数在变量满足线性约束条件下的最优值；随着计算机的发展，出现了如单纯形法等有效算法，它在工农业、军事、交通运输、决策管理与规划等领域中有广泛的应用。,2,问题一：,任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可工作时间分别为800和900，三种工件的数量分别为400、600和500，且已知车床甲加工单位数量三种工件所需的时间和加工费分别为0.4、1.1、1和13、9、10，车床乙加工单位数量三种工件所需的时间和加工费分别为0.5、1.2、1.3和11、12、8。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,3,解设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。,可建立以下线性规划模型：,4,问题二：某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？,解设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：,因检验员错检而造成的损失为：,故目标函数为：,5,约束条件为：,线性规划模型：,6,一般线性规划问题的数学表达式：,max(min)f=,s.t,.,用矩阵向量符号表示：,max(min)f=cX,7,其中,max(min)f=cX,8,用MATLAB优化工具箱解线性规划的命令如下：,1、模型：minz=cXs.tAXb,命令：x=linprog（c，A，b）,2、模型：minz=cX,命令：x=linprog(c,A,b,Aeq,beq),如果没有不等式：,存在，则令A=,b=.,9,3、模型：minz=cX,命令：x=linprog(c,A,b,Aeq,beq,vlb,vub),如果没有等式约束：,则令Aeq=,beq=.,存在，,4、命令：x=linprog(c,A,b,Aeq,beq,vlb,vub，x0),也用于求模型3，其中x0表示初始值。,5、命令：x,fval=linprog(),返回最优解及处的目标函数值fval.,10,解用命令3，编写M文件xxgh1.m如下：,c=-0.4-0.28-0.32-0.72-0.64-0.6;,A=0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.08;,b=850;700;100;900;,Aeq=;beq=;,vlb=0;0;0;0;0;0;vub=;,11,x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),结果：,x=1.0e+004*3.50000.50003.00000.00000.00000.0000,fval=-2.5000e+004,12,例2,s.t,0,i=1,2j=1,2,3.,解用命令3，编写M文件xxgh2.m如下：,c=10564812;,A=;,b=;,Aeq=111000;000111;100100;010010;001001;,13,beq=60;100;50;70;40;,vlb=0;0;0;0;0;0;vub=;,x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),结果：,x=0.000020.000040.000050.000050.00000.0000,fval=940.0000,14,例3用MATLAB求问题一：,编写M文件xxgh3.m如下:,c=1391011128;,A=0.41.11000；0000.51.21.3;,b=800;900;,Aeq=100100；010010；001001;,15,beq=400;600;500;,vlb=0;0;0;0;0;0;,vub=;,x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),结果:,x=0.0000600.00000.0000400.00000.0000500.0000,fval=1.3800e+004,即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800。,16,例4用MATLAB求解问题二：,编写M文件xxgh4.m如下：,c=40;36;,A=-5-3;,b=-45;,Aeq=;,beq=;,vlb=0;0;,vub=9;15;,17,x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),结果为：,x=9.00000.0000,fval=360,即只需聘用9个一级检验员。,注：本问题应还有一个约束条件：x1、x2取整数。故它是一个整数线性规划问题。这里把它当成一个线性规划来解，求得其最优解刚好是整数：x1=9，x2=0，故它就是该整数规划的最优解。若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解。,18,例5厂址选择问题,考虑A，B，C，三地，每地都出产一定数量的原材料，也消耗一定数量的产品（见下表6.1）。已知制成每吨产品需3吨原料，各地之间的距离为：A-B：150km，A-C:100km，B-C：200km.假定每万吨原料运输1km的运价是5000元，每万吨产品运输1km的运价是6000元。由于地区条件的差异，在不同地点设厂的生产费用也不同。问究竟在哪些地方设厂，规模多大，才使总费用最小？另外，由于其它条件的限制，在B处建厂的规模（生产的产品数量）不能超过5万吨。,19,解：,根据题意，可以建立问题的数学模型（其中目标函数包括原材料运输费、产品运输费和生产费）：,20,首先输入下列系数,c=75755050100100150240210120160220;,A=1-11-100330000-11001-100330000-11-110000330000000001100;,b=20;16;24;5;,Aeq=000000101010000000010101;,beq=7;13;,vlb=zeros(12,1);,x,fval=linprog(c,A,b,Aeq,beq,vlb,),21,x=0.00001.00000.00000.00000.00000.00007.00000.00000.00005.00000.00008.0000,fval=3.4850e+003,要使总费用最小，需要B地向A地运送1万吨；A，B，C三地建厂规模分别为7万吨、5万吨和8万吨；最小总费用为3485万元。,22,2、无约束优化问题求解,（1）一元函数无约束优化问题求解,在实验二中，我们已介绍过求一元函数的极值问题，实际上它是一元函数无约束优化问题。,一元函数无约束优化问题:minf（x）,常用格式如下：,1）x,fval=fminbnd(fun,x1,x2)：表示在x1,x2上函数fan的最小值点及最小值，fan为目标函数的表达式字符串。,2）x,fval=fminbnd(fun,x1,x2，options)：其中options为指定优化参数选项。,函数fminbnd的算法基于黄金分割法和二次插值法，要求目标函数必须连续函数，并可能只给出局部最优解。,23,例6求f=2,在0f=2*exp(-x)*sin(x);,xmin,ymin=fminbnd(f,0,8),xmin=3.9270ymin=-0.0279,画出函数图形:,fplot(f,0,8);,结果如图,如何求最大值？,24,下面求函数最大值:,f1=-2*exp(-x)*sin(x);,xmin,ymin=fminbnd(f1,0,8),xmin=0.7854ymin=-0.6448,结果：xmin=3.9270ymin=-0.0279xmax=0.7854ymax=0.6448,25,(2)无约束多元函数优化问题求解,标准型为：minf(X),其中X为向量。,命令格式为:,（1）x,fval=fminsearch（fun,x0）:其中x0为初始值，fan为目标函数的表达式字符串。,（2）x,fval=fminsearch（fun,x0，options）：其中options为指定优化参数选项。,例7,先作曲面的图形及等高线图,X,Y=meshgrid(-10:0.2:10,-10:0.2:10);,Z=4*X.2+25*Y.2-2*X+10*Y+2;,mesh(X,Y,Z),26,axis(-10,10,-10,10,-100,100);,contour(X,Y,Z,40);,grid,结果见图6.1(a)(b),由图可知，取x0=00,fun=inline(4*x(1)2+25*x(2)2-2*x(1)+10*x(2)+2,x);,27,X,fval=fminsearch(fun,0,0),X=0.2500-0.2000,fval=0.7500,28,3、二次规划的求解,标准型为：,MinZ=,XTHX+cTXs.t.AX=b,VLBXVUB,用MATLAB软件求解,其输入格式如下:,1）x,fval=quadprog(H,C,A,b);,2）x,fval=quadprog(H,C,A,b,Aeq,beq);,3)x,fval=quadprog(H,C,A,b,Aeq,beq,VLB,VUB);,4)x,fval=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0);,29,例8,写成标准形式：,输入命令：,H=2-2;-24;,30,c=-2;-6;,A=11;-12;,b=2;2;,Aeq=;beq=;VLB=0;0;VUB=;,x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB),运算结果为：,x=0.80001.2000,z=-7.2000,31,4、一般非线性规划求解,非线性规划标准型为：,minF(X)s.tAX=b,G(X),Ceq(X)=0VLB,X,VUB,其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用MATLAB求解上述问题，基本步骤分三步：,1.首先建立M文件fun.m,定义目标函数F（X）:,functionf=fun(X);,f=F(X);,32,2、若约束条件中有非线性约束:G(X),则建立M文件nonlcon.m定义函数G(X)与Ceq(X):,或Ceq(X)=0,functionG,Ceq=nonlcon(X),G=.,Ceq=.,3.建立主程序.非线性规划求解的函数是fmincon,命令的基本格式如下：,(1)x,fval=fmincon(fun,X0,A,b),(2)x,fval=fmincon(fun,X0,A,b,Aeq,beq),(3)x,fval=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB),(4)x,fval=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon),33,(4)x,fval=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon),说明：fan为目标函数的表达式字符串；如果没有不等式：AXb存在，则令A=,b=；如果没有等式约束：AeqX=beq存在，则令Aeq=,beq=；如果没有不等式：vlbxvub约束，则令vlb=,ulb=；nonlcon的作用是通过接收的向量x来计算非线性不等约束G(x)0和等式约束Ceq(x)=0分别在x处的估计G和Ceq,通过指定函数柄来使用；函数可能会出现局部最优解，这与初值x0的选取有关。,34,例9,1）先建立M文件fun4.m,定义目标函数:,functionf=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定义非线性约束：,functiong,ceq=mycon(x),g=1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;,ceq=;,35,3）主程序youh3.m为:,x0=-1;1;,A=;b=;,Aeq=11;beq=0;,vlb=;vub=;,x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon),3.运算结果为：,x=-1.22501.2250,fval=1.8951,36,例10供应与选址,某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？,37,（一）、建立模型,记工地的位置为(ai，bi)，水泥日用量为di，i=1,6;料场位置为(xj，yj)，日储量为ej，j=1,2；从料场j向工地i的运送量为Xij。,目标函数为：,约束条件为：,当用临时料场时决策变量为：Xij，,当不用临时料场时决策变量为：Xij，xj，yj。,38,（二）使用临时料场的情形,使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题.线性规划模型为：,其中,，i=1,2,6,j=1,2,为常数。,39,设X11=X1,X21=X2,X31=X3,X41=X4,X51=X5,X61=X6,X12=X7,X22=X8,X32=X9,X42=X10,X52=X11,X62=X12,编写程序gying1.m,clear,a=1.258.750.55.7537.25;b=1.250.754.7556.57.75;d=3547611;x=52;y=17;e=2020;fori=1:6forj=1:2aa(i,j)=sqrt(x(j)-a(i)2+(y(j)-b(i)2);endend,40,CC=aa(:,1);aa(:,2);A=111111000000000000111111;B=20;20;Aeq=100000100000010000010000001000001000000100000100000010000010000001000001;beq=d(1);d(2);d(3);d(4);d(5);d(6);VLB=000000000000;VUB=;x0=123010010101;xx,fval=linprog(CC,A,B,Aeq,beq,VLB,VUB,x0),41,计算结果为：x=3.00005.00000.00007.00000.00001.00000.00000.00004.00000.00006.000010.0000fval=136.2275,即由料场A、B向6个工地运料方案为：,总的吨千米数为136.2275。,42,（三）改建两个新料场的情形,改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小。这是非线性规划问题。非线性规划模型为：,设X11=X1,X21=X2,X31=X3,X41=X4,X51=X5,X61=X6X12=X7,X22=X8,X32=X9,X42=X10,X52=X11,X62=X12,x1=X13,y1=X14,x2=X15,y2=X16,43,（1）先编写M文件liaoch.m定义目标函数。,functionf=liaoch(x)a=1.258.750.55.7537.25;b=1.250.754.7556.57.75;d=3547611;e=2020;f1=0;fori=1:6s(i)=sqrt(x(13)-a(i)2+(x(14)-b(i)2);f1=s(i)*x(i)+f1;endf2=0;fori=7:12s(i)=sqrt(x(15)-a(i-6)2+(x(16)-b(i-6)2);f2=s(i)*x(i)+f2;endf=f1+f2;,44,(2)取初值为线性规划的计算结果及临时料场的坐标:,x0=35070100406105127;,编写主程序gying2.m.,clearx0=35070100406105127;,A=11111100000000000000001111110000;B=20;20;,Aeq=100000100000000001000001000000000010000010000000000100000100000000001000001000000000010000010000;,45,beq=3547611;v