《规划数学 单纯形法和复形法.ppt》由会员分享，可在线阅读，更多相关《规划数学 单纯形法和复形法.ppt（18页珍藏版）》请在三一文库上搜索。
1、,单纯形法 （0.5学时） 复合形法 （0.5学时） （1学时）,重 点：单纯形法、复合形法的步骤及 软件求解。非线性规划方法总结。 难 点: 单纯形法、复合形法的思路 基本要求：理解单纯形法和复合形法的步骤的思路，了解两种方法的联系及特点，掌握用软件实现单纯形法和复合形法。,第10讲 、复合形法及习题课,单纯形法,（一）单纯形法的思路,单纯形定义： ， 线性独立,为 构成的凸包，则称,单纯形。,单纯形法的思路： 单纯形法（simplex method），最直接法中最基本的方法。通过构造单纯形来逼近极小点，每构造一个单纯形，确定其最高点和最低点，然后通过扩展或压缩、反射构造新的单纯形，目的是使
2、极小点能够包含于单纯形中。,对于二维变量问题，单纯形为下图所示的由,及,六个点构成的多面体。,（二）单纯形法的步骤,用单纯形法求解无约束问题 的算法步骤如下,（1）选取初始单纯形 反映系数 紧缩系数 扩展系数 收缩系数 精度 置k=0；,（2）将单纯形的n+1个顶点按目标函数的大小重新编号，使顶点的编号满足,（3）令 ， 若,停止迭代，输出 ，否则转（4）；,（4）计算 若 ，转（5）， 否则当 时转（6），若 转（7）；,（5）计算 ，若 转（2）， 否则转（6）；,（6）令 ，转（2）；,（7）令 ，计算,若 ，令 ，转（2），否则转（4）；,（8）令 ， 转（2）。,单纯形法的计算框图,
3、（三）单纯形法的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命令窗口 中输入, syms x1 x2; f=3*
4、x12+x22-x1*x2+3*x2-5; x=-10 1 8;-10 4 8; x,mf=minSimpSearch(f,x,1.2,0.5,2,0.3,x1 x2),所得结果为： x=-0.2729 -1.6364 mf=-7.4545,。,（四）单纯形法的优缺点,优 点： 计算简单，不需要求函数（偏）导数，可以没有函数的解析式，只要有函数值即可应用。 缺 点： 收敛速度慢。 适合场合：各种无约束极值问题。,复合形法,（一）复合形法的思路,复合形法来源于无约束问题的单纯形法，通 过构造复合形来求得最优解，新的复合形通过替换旧的复合形中的坏点（目标函数值最大或次打的点）得到，替换方式仍然是单
5、纯形的反射、压缩、扩展这几个基本方法。,（二）复合形法的步骤,用复合形法求解有约束极值问题 的算法步骤如下,（1）选取初始复合形 反映系数 紧缩系数 扩展系数 收缩系数 精度 置k=0；,（2）将复合形的n+1个顶点按目标函数的大小重新编号，使顶点的编号满足,（3）令 ， 若,停止迭代，输出 ，否则转（4）；,转（5），否则当 时转（6），当 转（7）；,（5）计算 ，检验 是否在可行域内，若不在将扩展系数减小，直到 在可行域内。若 令 ，转（2），否则转（6）；,（6）令 ，转（2）；,（7）令 ， 计算 检查 是否 在可行域内，若不在，将压缩系数减小，直到 在可行域内。若 令 ，转（2）否
6、则转（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：目标函数的最
7、小值。,复合形法举例,例2 用复合形法求解下有约束极值问题,取初复合形,取参数,。,解：在Matlab命令窗口 中输入,f=x12+2x22-4*x1-8*x2+15; g=9-x12-x22;x1;x2; x=1 2 1.2;2 1.5 2.5; x,mf=minSimpSearch(f,x,1.2,0.5,2,0.3,x1 x2),所得结果为： x=2.0000 1.9999 mf=3.0000,。,（四）复合形法的优缺点,优点： 计算简单，不需要求函数（偏）导数，可 以没有函数的解析式，只要有函数值即可应用。 缺点： 收敛速度慢。 适合场合：各种有约束极值问题。,非线性规划习题课,一、非线性规划内容总结 二、非线性规划习题3，习题4，习题5部分习题讲解 三、课堂答疑,