一般非线性规划

线性规划第8章最优化方法无约束规划非线性规划实验目的实验内容2、掌握用数学软件包求解线性规划问题。1、了解线性规划的基本内容。3、实验作业。2、用数学软件包求解线性规划问题。1、两个引例。问题一：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？单位工件所需加工台时数单位工件的加工费用车床类型工件1工件2工件3工件1工件2工件3可用台时数甲0.41.11.013910800乙0.51.21.311128900两个引例解设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：6543218121110913minxxxxxxz6,,2,1,09003.12.15.08001.14.0500600400x..654321635241ixxxxxxxxxxxxtsi解答问题二：某厂生产甲、乙两种产品，已知制成一吨产品甲需用资源A3吨资源B4m3；制成一吨产品乙需用资源A2吨，资源B6m3，资源C7个单位。若一吨产品甲和乙的经济价值分别为7万元和5万元，三种资源的限制量分别为90吨、200m3和210个单位。试应生产这两种产品各多少吨才能使创造的总经济价值最高？（p153，例8-2）解：这是个最优化问题，其目标为经济价值最高，约束条件为三种资源的数量有限，决策为生产甲、乙产品的数量。令生产产品甲的数量为x1，生产产品乙的数量为x2。由题意可以建立如下的线性规划模型。故目标函数为：2157maxxxz约束条件为：0,021072006490232122121xxxxxxx问题2线性规划模型：解答返回2157maxxxz0,02107200649023..2122121xxxxxxxts1.线性规划的标准形式：xminz=)(xf..ts)(xgi0（),,2,1mi其中目标函数)(xf和约束条件中)(xgi都是线性函数minf=cxs.t.Ax=b（1）x0这里A=(ija)m,n,x=T21nxxxb=T21nbbb,c=nccc21用单纯法求解时，常将标准形式化为：2.线性规划的基本算法——单纯形法线性规划的基本算法——单纯形法例minz=10x1+9x2s．t．6x1+5x2≤6010x1+20x2≥150x1≤8x1,x2≥0引入松弛变量x3,x4,x5,将不等式化为等式,即单纯形标准形:minz=10x1+9x2s．t．6x1+5x2+x3=6010x1+20x2-x4=150x1+x5=8xi≥0(i=1,2,3,4,5)系数矩阵为:65100A=10200-10=(P1P2P3P4P5)10001b=(60,150,8)T用MATLAB优化工具箱解线性规划minz=cXbAXts..1、模型：命令：x=linprog（c，A，b）2、模型：minz=cXbAXts..beqXAeq命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=[]，b=[].bAX3、模型：minz=cXbAXts..beqXAeqVLB≤X≤VUB命令：[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）[2]x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）注意：[1]若没有等式约束:,则令Aeq=[],beq=[].[2]其中X0表示初始点beqXAeq4、命令：[x,fval]=linprog(…)返回最优解ｘ及ｘ处的目标函数值fval.解编写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=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)例1max6543216.064.072.032.028.04.0xxxxxxz85003.003.003.001.001.001.0..654321xxxxxxts70005.002.041xx10005.002.052xx90008.003.063xx6,2,10jxj解:编写M文件如下：c=[-7-5];A=[32;46;07];b=[90;200;210];Aeq=[];beq=[];vlb=[0,0];vub=[inf,inf];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)21)57(minxxz2100xx21020090706423..21xxts2157maxxxz0,02107200649023..2122121xxxxxxxts问题2解答S.t.Xz8121110913min9008003.12.15.000000011.14.0X500600400100100010010001001X，0654321xxxxxxX改写为：例3问题一的解答问题编写M文件如下:f=[1391011128];A=[0.41.110000000.51.21.3];b=[800;900];Aeq=[100100010010001001];beq=[400600500];vlb=zeros(6,1);vub=[];[x,fval]=linprog(f,A,b,Aeq,beq,vlb,vub)结果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800。结果为：x=14.000024.0000fval=-218.0000注：有些实际问题可能会有一个约束条件：决策变量只能取整数，如x1、x2取整数。这类问题实际上是整数线性规划问题。如果把它当成一个线性规划来解，求得其最优解刚好是整数时，故它就是该整数规划的最优解。若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解（如割平面法、分支定界法）。实验作业某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克,工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20名,可获利9万元.今工厂共有原料60千克,工人150名,又由于其他条件所限甲饮料产量不超过8百箱.问如何安排生产计划,即两种饮料各生产多少使获利最大.进一步讨论:1)若投资0.8万元可增加原料1千克,问应否作这项投资.2)若每百箱甲饮料获利可增加1万元,问应否改变生产计划.返回无约束最优化数学实验电子科技大学应用数学学院实验目的实验内容2、掌握用数学软件包求解无约束最优化问题。1、了解无约束最优化基本算法。1、无约束优化基本思想及基本算法。4、实验作业。3、用MATLAB求解无约束优化问题。2、MATLAB优化工具箱简介无约束最优化问题求解无约束最优化问题的的基本思想*无约束最优化问题的基本算法返回XfnEXmin其中1:EEfn标准形式：求解无约束最优化问题的基本思想求解的基本思想(以二元函数为例)1x2x)(21xxf01x2x05310X1X2X)(0Xf)(1Xf)(2Xf连续可微XfnEXmax=][minXfnEX多局部极小298.0f0f298.0f唯一极小(全局极小)2122212121322)(xxxxxxxxf搜索过程21221221)1()(100)(minxxxxxf最优点(11)初始点(-11)1x2xf-114.00-0.790.583.39-0.530.232.60-0.180.001.500.09-0.030.980.370.110.470.590.330.200.800.630.050.950.900.0030.990.991E-40.9990.9981E-50.99970.99981E-8返回⑴给定初始点nEX0，允许误差0,令k=0；⑵计算kXf；⑶检验是否满足收敛性的判别准则：kXf，若满足，则停止迭代，得点kXX*，否则进行⑷；⑷令kkXfS，从kX出发，沿kS进行一维搜索，即求k使得：kkkkkSXfSXf0min；⑸令kkkkSXX1，k=k+1返回⑵.无约束优化问题的基本算法最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法.1．最速下降法（共轭梯度法）算法步骤：2．牛顿法算法步骤：(1)选定初始点nEX0，给定允许误差0，令k=0；(2)求kXf,12kXf,检验：若kXf,则停止迭代,kXX*.否则,转向(3)；(3)令kkkXfXfS12][（牛顿方向）；(4)kkkSXX1,1kk,转回(2).如果f是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收敛速度还是很快的.牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量.3．拟牛顿法为克服牛顿法的缺点，同时保持较快收敛速度的优点，利用第k步和第k+1步得到的kX，1kX，)(kXf，)(1kXf，构造一个正定矩阵1kG近似代替)(2kXf,或用1kH近似代替12))((kXf，将牛顿方向改为：1kG1kS=-)(1kXf，1kS=-1kH)(1kXf从而得到下降方向.通常采用迭代法计算1kG，1kH，迭代公式为:BFGS（Boryden-Fletcher-Goldfarb-Shanno）公式kkTkkTkkkkTkTkkkkxGxGxxGxfffGG)()()()(1kTkTkkkTkkkTkkkxfxxxffHfHH)()()()(11kTkTkkkkTkkxfxfHHfx)()()(DFP（Davidon-Fletcher-Powell）公式：kTkTkkkTkkkTkkkXffffXXGXGG)()()()(11kTkTkkkkTkkfXfXGGXf)()()(kkTkkTkkkkTkTkkkkfHfHffHXfXXHH)()()()(1计算时可置IH1（单位阵），对于给出的1X利用上面的公式进行递推.这种方法称为拟牛顿法.返回Matlab优化工具箱简介1.MATLAB求解优化问题的主要函数类型模型基本函数名一