规划数学 单纯形法和复形法

.,单纯形法（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*x12+x22-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=x12+2x22-4*x1-8*x2+15;g=9-x12-x22;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,。,.,（四）复合形法的优缺点,优点：计算简单，不需要求函数（偏）导