规划数学 单纯形法和复形法ppt课件

单纯形法（0.5学时）复合形法（0.5学时）（1学时）重点：单纯形法、复合形法的及软件求解。非线性规划。难点:单纯形法、复合形法的思路基本要求：理解单纯形法和复合形法的步骤的思路，了解两种方法的联系及特点，掌握用软件实现单纯形法和复合形法。第10讲单纯形法、复合形法及习题课*单纯形法（一）单纯形法的思路单纯形定义：，线性独立为构成的凸包，则称单纯形。单纯形法的思路：单纯形法（simplexmethod），最直接法中最基本的方法。通过构造单纯形来逼近极小点，每构造一个单纯形，确定其最高点和最低点，然后通过扩展或压缩、反射构造新的单纯形，目的是使极小点能够包含于单纯形中。对于二维变量问题，单纯形为下图所示的由及六个点构成的多面体。（二）单纯形法的步骤用单纯形法求解无约束问题的算法步骤如下（1）选取初始单纯形反映系数紧缩系数扩展系数收缩系数精度置k=0；（2）将单纯形的n+1个顶点按目标函数的大小重新编号，使顶点的编号满足（3）令，若停止迭代，输出，否则转（4）；（4）计算若，转（5），否则当时转（6），若转（7）；（5）计算，若转（2），否则转（6）；（6）令，转（2）；（7）令，计算若，令，转（2），否则转（4）；（8）令，转（2）。单纯形法的计算框图（三）单纯形法的Matlab实现函数:minSimpSearch。功能：用单纯形法求解多维函数的极值。调用格式：[x,minf]=minSimpSearch(f,X,alpha,sita,gama,beta,var,eps)其中：f:目标函数；X：初始单纯形；alpha：反映系数；sita：紧缩系数；gama：扩展系数；beta：收缩系数；var：自变量向量；eps：自变量精度；x：目标函数取最小值的自变量值；minf：目标函数的最小值。单纯形法举例例1用单纯形法求解下面函数的极小值取初单纯形取参数。解：在Matlab命令窗口中输入>>symsx1x2;>>f=3*x1^2+x2^2-x1*x2+3*x2-5;>>x=[-1018;-1048];>>[x,mf]=minSimpSearch(f,x,1.2,0.5,2,0.3,[x1x2])所得结果为：x=-0.2729-1.6364mf=-7.4545。（四）单纯形法的优缺点优点：计算简单，不需要求函数（偏）导数，可以没有函数的解析式，只要有函数值即可应用。缺点：收敛速度慢。适合场合：各种无约束极值问题。复合形法（一）复合形法的思路复合形法来源于无约束问题的单纯形法，通过构造复合形来求得最优解，新的复合形通过替换旧的复合形中的坏点（目标函数值最大或次打的点）得到，替换方式仍然是单纯形的反射、压缩、扩展这几个基本方法。（二）复合形法的步骤用复合形法求解有约束极值问题的算法步骤如下（1）选取初始复合形反映系数紧缩系数扩展系数收缩系数精度置k=0；（2）将复合形的n+1个顶点按目标函数的大小重新编号，使顶点的编号满足（3）令，若停止迭代，输出，否则转（4）；转（5），否则当时转（6），当转（7）；（5）计算，检验是否在可行域内，若不在将扩展系数减小，直到在可行域内。若令，转（2），否则转（6）；（6）令，转（2）；（7）令，计算检查是否在可行域内，若不在，将压缩系数减小，直到在可行域内。若令，转（2）否则转（4）；（8）令，转（2）。（4）计算检查是否在可行域内，即是否满足若不在可行域，将反射系数减小，直到在可行域内。计算，若（三）复合形法的Matlab实现函数:minSimpSearch。功能：用复合形法求解多维函数的极值。调用格式：[x,minf]=minconSimpSearch(f,X,alpha,sita,gama,beta,var,eps)其中：f:目标函数；X：初始单纯形；alpha：反映系数；sita：紧缩系数；gama：扩展系数；beta：收缩系数；var：自变量向量；eps：自变量精度；x：目标函数取最小值的自变量值；minf：目标函数的最小值。复合形法举例例2用复合形法求解下有约束极值问题取初复合形取参数。解：在Matlab命令窗口中输入>>f=x1^2+2x2^2-4*x1-8*x2+15;>>g=[9-x1^2-x2^2;x1;x2];>>x=[121.2;21.52.5];>>[x,mf]=minSimpSearch(f,x,1.2,0.5,2,0.3,[x1x2])所得结果为：x=2.00001.9999mf=3.0000。（四）复合形法的优缺点优点：计算简单，不需要求函数（偏）导数，可以没有函数的解析式，只要有函数值即可应用。缺点：收敛速度慢。适合场合：各种有约束极值问题。非线性规划习题课一、非线性规划内容总结二、非线性规划习题3，习题4，习题5部分习题讲解三、课堂答疑此下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！*