无约束最优化直接方法之单纯形法解析.docx

数学与计算科学学院实验报告实验项目名称无约束最优化直接方法之单纯形法所属课程名称最优化方法实验类型算法编程实验日期 2015.11.20班级学号 2姓名成绩一、实验概述：【实验目的】加深了解无约束最优化直接方法中的单纯形有哪些信誉好的足球投注网站法培养matlab编程与上机调试能力【实验原理】设是某一单纯形的n+1个顶点向量, 则：对于任意给定初始点z1和正数l，按如下公式取定的单纯形是一个以为z1顶点棱长为l的正规单纯形。。其中n 维向量z(i)= ，如:z(2)= ，…，z(n-1)=，其中正规单纯形是一种特殊的单纯形，还有一种特殊的单纯形取法：其中=在中此特殊单纯形即为等腰直角三角形。单纯形替换法的基本思想就是按上面取特殊单纯形的方法形成初始单纯形。然后从此出发，每次迭代都设法构造新的以替代旧的，使新单纯形不断向目标函数的极小点靠近，直到有哪些信誉好的足球投注网站到满意的极小点为止。单纯形替换法由两步构成：形成初始单纯形和迭代。而迭代过程又包括四项操作：反射，延伸，收缩和减小棱长。【实验环境】Windows7；MATLAB7.0二、实验内容：【实验方案】1）设初始单纯形顶点的位置向量为.计算：,其中分别为此单纯形的最好和最坏顶点。(取正规单纯形作为初始单纯形比取后一种形式好)若把顶点去掉，则剩下的n个顶点 (不含)构成n-1维空间中的单纯形，按下面公式求其中心：2）反射。按如下公式通过反射: , 称为的反射点。因是坏点，则一般有f()f()，从而得到比更好的点,这时应按3进行伸延，否则进入3进行收缩工作。3）延伸。经过反射，若不仅有f()f(),且进一步有f()f()，则说明沿方向还可以向前迈一步，因此计算: = +r()称为的延伸点，r1是延伸系数，常取r=2,也可用直线有哪些信誉好的足球投注网站技术确定r.此时若有f() f(),则以替换，而其余n个顶点不变, 构成新单纯形，转4）收缩。（如在R中，由图a知以、、为顶点的新单纯形已向极小点靠近了一步。）否则，以反射点替换构成单纯形，转6步（如R中，由图19.1.1 b可知以、、为顶点的新单纯形向极小点靠近了一步）图19.1.1a 图19.1.1b若f()f()，即反射点并不比原单纯形的最好点好，则分下列两种情况处理：若存在一个标点i，使得f()f()，,即除最坏点外，反射点比其他一个顶点好，因而可以用将替换构成新的单纯形，转6步（如中，图c所示，以、、为顶点的新单纯形向极小点迈进了一步）4.2 若对i=1,2,3--n+1(但)均有f()=f(),则要进行收缩。收缩分以下两种情况4.2.1 若f() =f(),即反射点比原来单纯形的坏点还坏，则舍弃，对方向-v0进行收缩。如图d计算公式为；其中是的收缩点，而收缩常数常取为：若f()f()，即收缩点比原单纯形最坏点还坏，因此放弃点，转5步进行棱长减半工作。否则以替换构成新单纯形，转6。4.2.2若f()f()，则对向量--进行收缩（如图19.1.1e），计算公式为若f()f(),即收缩点比反射点还坏，则放弃收缩点，转5进行棱长减半工作，否则以替换构成新单纯形，转6。图19.1.1c 图19.1.1b 图19.1.1e5）减小棱长。将原单纯形的最好点保持不动，各棱长减半，计算公式为6）终止原则。计算，若，则v*为极小点，终止；否则，转1【实验结论】（结果）取初始点。为计算方便不取等边三角形为初始单纯形，而取直角三角形为初始单纯形，其顶点为：相应函数值=45 , =125, =65故其中心先做反射运算（为方便，取=1）因满足延伸条件，进行延伸实验（延伸系数r=2）因延伸成功。取此时得三个顶点及函数值为下面开始第二次迭代中心反射延伸故以=（4，6）代替。f( )=4代替。转入下一次迭代。如此迭代下去最后可得极小点。【实验小结】（收获体会）通过本次试验，是我更深的了解了无约束最优化问题的直接解决方法。一般来说，直接方法与使用导数的方法相比，但是其迭代比较简单，编制程序也比较容易。同一个问题从不同的思考角度出发就会发现更多的解决方案。三、指导教师评语及成绩：评语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确. 成绩：指导教师签名：批阅日期：附录1：源程序#includeiostream.h????#includemath.h????int?const?n=2;????static?double?Mk=1;????double?fun_original(double?x[n]);//既是主函数，也是F(X,Mk)之一????d