复形法.docVIP

2012-2013（1）专业课程实践论文 复形法 高强强，0818180202，数学08-2班 李祥南，0818180222，数学08-2班 袁野， 0818180209，数学08-2班 一、算法理论 复合形法概述 复合形法是单纯形法的扩展，是适用于不等式约束的一种直接算法。它的基本思路是在设计空间的可行域内，构造具有k个顶点的多面体，按顶点函数值大小排队，找出函数值最小的最好点和函数值最大的最坏点，并计算出最坏点的反射点，一般反射点都优于最坏点，故以反射点代替最坏点，构成新的复形，这样不断调整多面体的顶点，使多面体不断向最优点靠拢，最后有哪些信誉好的足球投注网站到最优点。 其算法步骤是： 1．确定初始可行点 可以人为给定输入一个可行点；也可由计算机随机选点。随机选点按公式： 式中，为第i个设计变量的下界、上界；为随机数。 得到的各顶点，应是可行点，即 2．随机产生其它顶点 顶点个数k可按范围来确定。其它顶点也是随机取。 3．构成复形 要求所有点都是可行点，要对除点外的个顶点检验。如有个点满足约束，而等个顶点未满足约束时，此时先求个顶点的中点，即 然后使等顶点向点靠拢，即 再检验点是否满足约束条件，如仍不满足，再继续缩小，直至满足为止。一次对等个顶点进行收缩，直到全部满足约束，即完成了第一轮的复形构造。 4．排队 找出最好点、最坏点和次坏点，即 最好点： 最坏点： 次坏点： 5．计算中点按公式 判断： 满足，转6求反射点； 不满足，以为第一个顶点，重新设定上下界，转2： 6．求反射点 判断： 满足，转7；不满足，转9 7．比较 满足，判断 满足，转8；不满足，转4 不满足，判断 满足，转4；不满足，转9 8．求延伸点 判断： 满足，判断 满足，继续求8；不满足，转4 不满足，转4 9．缩小，改变有哪些信誉好的足球投注网站方向。令 判断： 满足，转5；不满足转6 复合形法的收敛终止准则可按下式之一决定 或 二、算法框图 三、算法程序 1.razor的最终构成如下（razor.h）： #pragma once #include iostream #include time.h #includemath.h #include razor.h using namespace std; #define RANDOM_H 10000 //随机选取到不合格顶点的次数上限 #define MINIMUM(x,y) (x)(y)?(y):(x) //求较小值 #define MAXIMUM(x,y) (x)(y)?(x):(y) //求较大值 #define DELTA 0.0000001 //误差限 #define NUMLIMUP 10000 //最多求取次数,避免陷入死循环 typedef struct g_node { double (*g)(double*); //函数指针，指向约束函数 g_node *next; }g_node; class razor { public: razor(int dimens,int num); ~razor(void); public: int dimension; //优化维数 int vertex_num; //算法中使用的顶点数 g_node *g_function; //约束函数链表 double (*targetFunc)(double*); //目标函数指针 double *x,*l,*h; //变量数组、自变量取值下、上限数组 int g,b,s; //最好点g、最坏点b、次坏点s的顶点序号 double *xc,*xr,*xe; //记录Xc、