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

1、单纯形法单纯形法 （0.5学时）学时）复合形法复合形法 （0.5学时）学时）（1学时）学时）重重 点：单纯形法、复合形法的步骤及点：单纯形法、复合形法的步骤及 软件求解。非线软件求解。非线性规划方法总结。性规划方法总结。难难 点点: 单纯形法、复合形法的思路单纯形法、复合形法的思路基本要求：理解基本要求：理解单纯形法和复合形法的步骤的思路，了解两种单纯形法和复合形法的步骤的思路，了解两种方法的联系及特点，掌握用软件实现单纯形法和复合形法。方法的联系及特点，掌握用软件实现单纯形法和复合形法。第第10讲讲 、复合形法及习题课、复合形法及习题课单纯形法单纯形法（一）单纯形法的思路（一）单纯形法的思路

2、单纯形定义：单纯形定义： ， 线性独立线性独立nkexxx121,.,111312,.,xxxxxxk),.,(121kxxxh为 构成的凸包，则称121,.,kxxx),.,(121kxxxh单纯形。单纯形法的思路：单纯形法的思路： 单纯形法（simplex method），最直接法中最基本的方法。通过构造单纯形来逼近极小点，每构造一个单纯形，确定其最高点和最低点，然后通过扩展或压缩、反射构造新的单纯形，目的是使极小点能够包含于单纯形中。 对于二维变量问题，单纯形为下图所示的由21,kkkxxx及)(),(),(21kkkxfxfxf六个点构成的多面体。（二）单纯形法的步骤（二）单纯形法的步

3、骤用单纯形法求解无约束问题 的算法步骤如下nexxf),(min（1）选取初始单纯形 反映系数 紧缩系数 扩展系数 收缩系数 精度 置k=0；,.,10nxxx, 1),1 , 0(, 1),1 , 0(, 0（2）将单纯形的n+1个顶点按目标函数的大小重新编号，使顶点的编号满足)(.)()(10nxfxfxf（3）令 ， 若1011njinxnx2/12110)()(11nnjjxfxfn停止迭代，输出 ，否则转（4）；0x（4）计算 若 ，转（5），否则当 时转（6），若 转（7）；,112nnnnxxxx（5）计算 ，若 转（2），否则转（6）；2nnxx)()(02xfxfn)()(1

4、2nnxfxf)()(12nnxfxf1213nnnnxxxx)()(03xfxfn（6）令 ，转（2）；（7）令 ，计算)(),(min()(2nniinxfxfxfxx114nnnnxxxx若 ，令 ，转（2），否则转（4）；)()(4nnxfxf4nnxx（8）令 ， 转（2）。njxxxxjj,.,1 , 0,00单纯形法的计算框图单纯形法的计算框图 （三）单纯形法的（三）单纯形法的matlab实现实现函 数: minsimpsearch。功 能：用单纯形法求解多维函数的极值。调用格式：x,minf=minsimpsearch(f,x,alpha,sita,gama,beta,var,

5、eps)其中：f:目标函数；x：初始单纯形；alpha：反映系数；sita：紧缩系数；gama：扩展系数；beta：收缩系数；var：自变量向量；eps：自变量精度；x：目标函数取最小值的自变量值；minf：目标函数的最小值。单纯形法举例单纯形法举例例例1 用单纯形法求解下面函数的极小值533),(221222121xxxxxxxf取初单纯形tttxxx)8 , 8(,)4 , 1 (,)10,10(210取参数3 . 0, 2, 5 . 0, 2 . 1。解：解：在matlab命令窗口 中输入 syms x1 x2; f=3*x12+x22-x1*x2+3*x2-5; x=-10 1 8;-

6、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。（四）单纯形法的（四）单纯形法的优缺点优缺点 优 点： 计算简单，不需要求函数（偏）导数，可以没有函数的解析式，只要有函数值即可应用。 缺 点： 收敛速度慢。 适合场合：各种无约束极值问题。复合形法复合形法（一）复合形法的思路（一）复合形法的思路 复合形法来源于无约束问题的单纯形法，通 过构造复合形来求得最优解，新的复合形通过替换旧的复合形中的坏点（目标函数值最大或次打的点）得到，替换方式仍然是单纯形的反射、压缩、扩展这几

7、个基本方法。（二）复合形法的步骤（二）复合形法的步骤用复合形法求解有约束极值问题 的算法步骤如下pjxgxfj,.,2 , 1, 0)(),(min（1）选取初始复合形 反映系数 紧缩系数 扩展系数 收缩系数 精度 置k=0；,.,10nxxx, 1),1 , 0(, 1),1 , 0(, 0（2）将复合形的n+1个顶点按目标函数的大小重新编号，使顶点的编号满足)(.)()(10nxfxfxf（3）令 ， 若1011njinxnx2/12110)()(11nnjjxfxfn停止迭代，输出 ，否则转（4）；0x转（5），否则当 时转（6），当 转（7）；,112nnnnxxxx（5）计算 ，检验

8、 是否在可行域内，若不在将扩展系数减小，直到 在可行域内。若 令 ，转（2），否则转（6）；2nnxx)()(02xfxfn)()(12nnxfxf2nx1213nnnnxxxx)()(03xfxfn（6）令 ，转（2）；（7）令 ， 计算 检查 是否 在可行域内，若不在，将压缩系数减小，直到 在可行域内。若 令 ，转（2）否则转（4）； )(),(min()(2nniinxfxfxfxx114nnnnxxxx)()(4nnxfxf4nnxx（8）令 ， 转（2）。njxxxxjj,.,1 , 0,00（4）计算 检查 是否在可行域内，即 是否满足 若不在可行域，将反射系数减小，直到 在可行域

9、内。计算 ，若 2nx0)(2nxg)(2nxf)()(12nnxfxf3nx3nx3nnxx4nx4nx（三）复合形法的（三）复合形法的matlab实现实现函 数: minsimpsearch。功 能：用复合形法求解多维函数的极值。调用格式：x,minf=minconsimpsearch(f,x,alpha,sita,gama,beta,var,eps)其中：f:目标函数；x：初始单纯形；alpha：反映系数；sita：紧缩系数；gama：扩展系数；beta：收缩系数；var：自变量向量；eps：自变量精度；x：目标函数取最小值的自变量值；minf：目标函数的最小值。复合形法举例复合形法举例

10、例例2 用复合形法求解下有约束极值问题0,09. .15842),(min21222121222121xxxxtsxxxxxxf取初复合形tttxxx)5 . 2 , 2 . 1 (,)5 . 1 , 2(,)2 . 1 , 1 (210取参数3 . 0, 2, 5 . 0, 2 . 1。解：解：在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。（四）复合形法的（四）复合形法的优缺点优缺点 优点： 计算简单