单纯算法
❶ 简述单纯形法和对偶单纯形算法的基本思想
单纯形法是是保证b>=0，通过转轴，使得检验数r>=0来求得最优解，而使用对偶单纯形法的前提是r<=0，通过转轴，使得达到b>=0。
❷ 如何用C或C++语言编写单纯形算法，怎样编写谢谢！
求多维函数极值的一种算法，由Nelder和Mead提出，又叫单纯形算法，但和线性规划中的单纯肢唤形算法是不同的，由于未利用任何求导运算，算法比较简单，但收敛速度较慢，适合变元数不是很多的方程求极值，算法的基本思想如下：
给定n个特征，可以构造一个具有n+1个顶点的单纯形，初始化时需(n+1)*n维矩阵(看成是有n+1个顶点的单纯形) ，矩阵的每一行为n元向量，x0为第一行，xi=x0+r*ei，r为对问题的特征长度大小的估计值，ei为单位向量，x0可初始化为全为1的向量，即认为每个特征权重是相同的，然后选取其余的，在选取过程中，r可以取相同的值也可以取不同的值（r可以看作是对第i个特征权重的调整） 。
算法运行过程（以机器翻译中的rerank为例）：
假定BLEU=f(特征的和)，对n+1个顶点（n维向量）分别计算BLEU值（取相反数），然后从中选出BLEU(相反数)最大，次大和最小的三个点，算法每次都是把其中的最大点对应的各权重进行调整，使其变小向最小点靠拢，调整完毕后，计算其对应的BLEU，再从这些BLEU中选出BLEU(相反数)最大，次大和最小的三个点，一直迭代下去，直到最高点到最低点羡罩的比率范围合适或达到最大迭代次数为止。
源码：
double famoeb(double x[],vector<double> feat)
{//计算所有特征*权重的和
double y=0.0;
for(int i=0;i<FeatNum;i++)
{
y+=x[i+1]*feat[i];
}
return y;
}
//单纯形算法
void amoeba(double p[],double y[],int mp,int np,int ndim,double ftol,int& iter)
{
int i,j,ihi,inhi,mpts,nmax=20;
double ypr,yprr,rtol,alpha=1.0;
double beta=0.5;
double gamma=2.0;
int itmax=500;
double pr[21],prr[21],pbar[21];
mpts=ndim+1;
iter=0;
do
{
int ilo=1;
if(y[1]>y[2])
{
ihi=1;
inhi=2;
}
else
{
ihi=2;
inhi=1;
}
for(i=1;i<=mpts;i++)
{//寻找函数值中的最大，最小和次大值
if(y[i]<y[ilo])
{
ilo=i;
}
if(y[i]>y[ihi])
{
inhi=ihi;
ihi=i;
}
else
{
if(y[i]>y[inhi])
{
if(i!=ihi)
{
inhi=i;
}
}
}
}//结束寻找各种函数极值
rtol=2.0*fabs(y[ihi]-y[ilo])/(fabs(y[ihi])+fabs(y[ilo]));//计算从最高点到最低点的比率范围，如合适则返回
if(rtol<ftol)
{
erase(pbar,prr,pr);
return;
}
if(iter==itmax)//如到了最大的迭代次数，历派凯则返回
{
cout<<"amoeba exceeding maximum iterations."<<endl;
return;
}
iter=iter+1;//进行下一次迭代
for(j=1;j<=ndim;j++)
{
pbar[j]=0.0;
}
for(i=1;i<=mpts;i++)
{
if(i!=ihi)
{
for(j=1;j<=ndim;j++)
{
pbar[j]=pbar[j]+p[(i-1)*np+j];
}
}
}
for(j=1;j<=ndim;j++)
{
pbar[j]=pbar[j]/ndim;
pr[j]=(1.0+alpha)*pbar[j]-alpha*p[(ihi-1)*np+j];//求反射点
}
vector<int> BestNo;
ChooseOneBest(pr,numSentences,alldata,StartEndIndices,BestNo);
//开始计算BLEU值
vector<pairnum> initialScore(N_gram);
double referenceLength=0.0;//参考翻译总长度
for(int k=0;k<numSentences;k++)
{
int sent=BestNo[k];//当前句子的最好候选翻译的序号
for(int l=0;l<N_gram;l++)
{
initialScore[l].left+=alldata[sent].ngram_data[l].left;
initialScore[l].right+=alldata[sent].ngram_data[l].right;
}
referenceLength+=alldata[sent].closest_length;
}
ypr=-BLEU(initialScore,referenceLength);//计算本轮lamda所对应的bleu
if(ypr<=y[ilo])
{//得到一个比最佳点稍好的结果，用gamma做一次外推
for(j=1;j<=ndim;j++)
{
prr[j]=gamma*pr[j]+(1.0-gamma)*pbar[j];
}
vector<int> BestNo1;
ChooseOneBest(prr,numSentences,alldata,StartEndIndices,BestNo1);
//开始计算BLEU值
vector<pairnum> initialScore1(N_gram);
double referenceLength1=0.0;//参考翻译总长度
for(int m=0;m<numSentences;m++)
{
int sent=BestNo1[m];//当前句子的最好候选翻译的序号
for(int n=0;n<N_gram;n++)
{
initialScore1[n].left+=alldata[sent].ngram_data[n].left;
initialScore1[n].right+=alldata[sent].ngram_data[n].right;
}
referenceLength1+=alldata[sent].closest_length;
}
yprr=-BLEU(initialScore1,referenceLength1);//计算本轮lamda所对应的bleu
if(yprr<y[ilo])
{//以扩张点prr作为新的单纯形中的点
for(j=1;j<=ndim;j++)
{
p[(ihi-1)*np+j]=prr[j];
}
y[ihi]=yprr;
}
else
{//以反射点pr作为单纯形中得点
for(j=1;j<=ndim;j++)
{
p[(ihi-1)*np+j]=pr[j];
}
y[ihi]=ypr;
}
}
else
{//反射点不如最佳点，同次高点比较
if(ypr>=y[inhi])
{//反射点不如次高点，取一个中等程度低的点作一次一维收缩
if(ypr<y[ihi])
{
for(j=1;j<=ndim;j++)
{
p[(ihi-1)*np+j]=pr[j];
}
}
y[ihi]=ypr;
for(j=1;j<=ndim;j++)
{
prr[j]=beta*p[(ihi-1)*np+j]+(1.0-beta)*pbar[j];
}
vector<int> BestNo2;
ChooseOneBest(prr,numSentences,alldata,StartEndIndices,BestNo2);
//开始计算BLEU值
vector<pairnum> initialScore2(N_gram);
double referenceLength2=0.0;//参考翻译总长度
for(int s=0;s<numSentences;s++)
{
int sent=BestNo2[s];//当前句子的最好候选翻译的序号
for(int t=0;t<N_gram;t++)
{
initialScore2[t].left+=alldata[sent].ngram_data[t].left;
initialScore2[t].right+=alldata[sent].ngram_data[t].right;
}
referenceLength2+=alldata[sent].closest_length;
}
yprr=-BLEU(initialScore2,referenceLength2);//计算本轮lamda所对应的bleu
if(yprr<y[ihi])
{//以prr作为新单纯形中的点
for(j=1;j<=ndim;j++)
{
p[(ihi-1)*np+j]=prr[j];
}
y[ihi]=yprr;//更新当前最高点出的函数值
}
else
{//单纯性太大，缩小原来的单纯形
for(i=1;i<=mpts;i++)
{
if(i!=ilo)
{
for(j=1;j<=ndim;j++)
{
pr[j]=0.5*(p[(i-1)*np+j]+p[(ilo-1)*np+j]);
p[(i-1)*np+j]=pr[j];
}
vector<int> BestNo3;
ChooseOneBest(pr,numSentences,alldata,StartEndIndices,BestNo3);
//开始计算BLEU值
vector<pairnum> initialScore3(N_gram);
double referenceLength3=0.0;//参考翻译总长度
for(int u=0;u<numSentences;u++)
{
int sent=BestNo3[u];//当前句子的最好候选翻译的序号
for(int v=0;v<N_gram;v++)
{
initialScore3[v].left+=alldata[sent].ngram_data[v].left;
initialScore3[v].right+=alldata[sent].ngram_data[v].right;
}
referenceLength3+=alldata[sent].closest_length;
}
y[i]=-BLEU(initialScore3,referenceLength3);//计算本轮lamda所对应的bleu
}
}
}
}
else
{//反射点好于次高点，以反射点pr作为单纯形中得点
for(j=1;j<=ndim;j++)
{
p[(ihi-1)*np+j]=pr[j];
}
y[ihi]=ypr;
}
}
}while(1);
}
❸ 那位大神帮我用matlab写个运筹学单纯性算法的程序，最好带注释，急求！！！
下面是我多年前学习最优化课程时编写的单纯形法程序，100%原创。
单纯形算法的基本思想是，从多面体的某个顶点出发，移动到使得目标函数有所改进的相邻顶点；然后，从相邻顶点出发，移动到另一个更隐册好的顶点，直至到达最优的顶点。从代数的观点看，也就是从一个基本可行解出发，求出使目标函数得到改进的相邻的基本可行解，循环往复，直至求得最优的基本可行解，或者判断最优解不可能存在。
从一个基本可行解得到另一个与之相邻的基本可行解的过程称为转轴过程（pivoting process，简称转轴），就是以某个灶源宏非基变量代替另一个基变量。如何确定换入和换出变量（即所谓的转轴法则）是不同单纯形方法的主要差别。
我所编写程序的主要特色在于，不仅能够给出最优解，而且还能够给出迭代过程中各步的单裂斗纯形表（simplex tableau），这对于理解单纯形法的求解过程非常有帮助。
程序自带调用实例，使用了符号数学工具箱，所以显得有点繁琐，好好读一读对你会有帮助。
function [G, BasisSet] = simplex_table(A, b, c, idxB)
if ~nargin
A=[
3 3 1 0 0;
4 -4 0 1 0;
2 -1 0 0 1
];
b=[30 16 12]';
c=[-3 -1 0 0 0];
idxB = 3 : 5;
simplex_table(A, b, c, idxB)
return
end
if nargin == 2
G = A;
BasisSet = b;
m = size(G, 1) - 1;
n = size(G, 2) - 1;
else
m = size(A,1);
n = size(A,2);
BasisSet = idxB;
idxN = true(1, n);
idxN(idxB) = ~idxN(idxB);
idxB = ~idxN;
B = sym( A(:, BasisSet) );
cB = c(BasisSet);
w = cB * B^-1;
G = sym( zeros( size(A)+1 ) );
G(1:end-1, 1:end-1) = B^-1 * A;
G(1:end-1, end) = B^-1 * b;
G(end, 1:end-1) = w * A -c;
G(end, end) = w * b;
end
output_stars(n*16);
count = 0;
fprintf('\n initial table:\n');
output_table(G, BasisSet);
while count <= 100,
last_row = G(end, 1:end-1);
try
[d, in] = max( double( last_row ) );
catch
syms M
lim = limit(last_row, M, inf);
[d, in] = max( double(lim) );
if d ==inf
lim = limit(last_row / M, M, inf);
[d, in] = max( double(lim) );
end
end
if d <= 0,
disp(' ***** success');
x = sym(zeros(1, n));
x(BasisSet) = G(1:end-1, end)';
fprintf(' Optimal solution is: x = %s, ', symvec2str(x));
fprintf(' fmin = %s', char( G(end,end) ) );
break,
end
b_ = G(1:end-1, end);
yi = G(1:end-1, in);
if max( double(yi) ) <= 0, disp(' ***** No solution'); break, end
r = double(b_ ./ yi);
r( double(yi) <= 0 ) = NaN;
if 1
[yir, out] = min( r );
else
[yir, out] = min( r(end:-1:1) );
out = length(r) + 1 - out;
end
yir = yi(out);
count = count + 1;
fprintf(' The #%i iteration:\n', count);
fprintf(' Pivoting: x%i out, x%i in\n', BasisSet(out), in);
BasisSet(out) = in;
G(out, :) = G(out, :) / yir;
for i = 1 : m + 1
if i ~= out
G(i, :) = G(i, :) - G(out, :) * G(i, in);
end
end
G = simple(G);
output_table(G, BasisSet);
end
output_stars(n*16);
function output_table(G, BasisSet)
n = size(G, 2);
m = size(G, 1);
fprintf('\n ');
for j = 1 : n - 1
fprintf('\t%9s%i', 'x', j );
end
fprintf('\n');
for i = 1 : m
if i < m,
fprintf(' x%i', BasisSet(i));
else
fprintf(' ');
end
for j = 1 : n
fprintf('\t%10s', char( G(i,j) ) );
end
fprintf('\n');
end
fprintf('\n');
function output_stars(n)
fprintf('\n');
for i=1:n, fprintf('-'); end
fprintf('\n');
function s = symvec2str(x)
n=length(x);
s = '[ ';
for i=1:n-1
s = [s char(x(i)) ', ' ];
end
s = [s char(x(n)) ' ]'];
❹ 单纯形方法
单纯形法是求解线性规划问题最常用、最有效的算法之一。
单纯形法最早由 George Dantzig于1947年提出，近70年来，虽有许枯历脊多变形体已经开发，但却保持着同样的基本观念。如果线性规划问题的最优解存在，则一定可以在其可行区域的顶点中找到。基于此，单纯形法的基本思路是：先找出可行域的一个顶点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一顶点，并使目标函数值更优；如没渗此下去，直到找到某最优解为止。
为了用选代法求出线性规划的最优解，需要解决以下三个问题：
(1)最优解判别准则，即迭代终止的判别标准；
(2)换基运算，即从一个基可行解迭代出另一个基可行解的方法；
(3)进基列的选择，即选择合适的列以进行换基运算，可以使目标函数值有较大下降。
改进单纯形法：
原单纯形法不是很经济的算法。1953年美国数学家G.B.丹捷格为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了烂纯在计算机上的存储量。
❺ 单纯形法的原理
单纯形法的原理如下：
首先设法找到一个（初始）基可行解，然后再根据最优性理论判断这个基可行解是否最优解。若是最优解，则输出结果，计算停止。
若不是最优解，则设法由当前的基可行解产生一个目标值更搜迹优的新的基可行解，再利用最优性理论对所得的新基可行解进行判断，看其是否最优解，这样就构成一个迭代算法。
由于基可行解只有有限个，而每次目标值都有所改进，因而必可在有限步内终止。如果原问题确有最优解，必可在有限步内达到，且计算量大大少于穷举法；若原问题无最优解，也可根据最优性理论及时发现，停止计算，避免错误及无效运算。坦纳"
单纯让漏没形法是求解线性规划问题最常用、最有效的算法之一。单纯形法最早由 George Dantzig于1947年提出，近70年来，虽有许多变形体已经开发，但却保持着同样的基本观念。如果线性规划问题的最优解存在，则一定可以在其可行区域的顶点中找到。
基于此，单纯形法的基本思路是：先找出可行域的一个顶点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一顶点，并使目标函数值更优；如此下去，直到找到某最优解为止 。