单纯形替换法 1.单纯形替换法: Spendley、Hext和 hImsworth 于1962年提出; Ne|der和Mead1965年改进 2.问题: min f(x) x∈RM f(x是R"上连续函数 即f(x)∈CR
单纯形替换法 1.单纯形替换法: Spendley、Hext 和Himsworth 于1962年提出; Nelder 和Mead 1965年改进 2. 问 题: min f ( x ) n xR f ( x )是R n 上连续函数 f ( x ) C( R ) n 即
3.算法思想 (1)集合迭代的思想 S0→>S1→>…→>Sk→Sk+1→ 这里S1(i=1,2,…)为单纯形 (2)下降迭代的思想 使S,中顶点的目标函数值降
(1) 集合迭代的思想。 这 里 S (i , , )为单纯形 S S S S i k k 1 2 0 1 1 = → → → → + → 3.算法思想 (2) 下降迭代的思想。 使Si 中顶点的目标函数值下降
4.单纯形概念 1)例: R:线段 R2:三角形 R3:四面体
4. 单纯形概念 例：R 2 : 三角形 (1) R 3 : 四面体 R 1 : 线段 0 V 1 V 0 V 0 V 1 V 1 V 2 V 2 V 3 V
(2)单纯形的定义 设V°,V,…,V"∈R",如果V-V°(j=1,2,…,n)线性无关, 则°,V,…,V的凸组合称为由,V,,"构成的 单纯形,记为S=[v0,,…,V"],即 {x1∑aV,其中∑a1=1,a1>0} 称V°,V,…,V"为该单纯形的顶点
V , V , , V R , n n 设 0 1 ( 1,2, , ) , 如果 V j −V 0 j = n 线性无关 单纯形 记 为 即 则 的凸组合称为由 构成的 , [ , , , ] , , , , , , , 0 1 0 1 0 1 n n n S V V V V V V V V V = [ , , , ] 0 1 n S = V V V 称V 0 , V 1 , , V n为该单纯形的顶点。 （2）单纯形的定义 { | , 1 , 0} 0 0 = = = = j n j j n j j x j V 其中
5如何构造单纯形? 对于给定的点x和正数δ,有两种方式构造单绝形: (1)=x V=yo+se =+8e V2-"=8e1+e2) Vn=vn-+se V"-V=8(e1+e2 则S=°,V1,…,"]成一个单纯形
对于给定的点x 0和正数，有两种方式构造单纯形 ： V V e V V ( e e e ) V V e V V ( e e ) V V e V V e V x n n n n n = + − = + + = + − = + = + − = = − 1 2 1 0 1 2 2 0 2 2 1 1 1 0 1 1 0 0 0 (1) 5.如何构造单纯形? 则 S = [V 0 , V 1 , , V n ]构成一个单纯形