單純演算法
❶ 簡述單純形法和對偶單純形演算法的基本思想
單純形法是是保證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年來，雖有許多變形體已經開發，但卻保持著同樣的基本觀念。如果線性規劃問題的最優解存在，則一定可以在其可行區域的頂點中找到。
基於此，單純形法的基本思路是：先找出可行域的一個頂點，據一定規則判斷其是否最優；若否，則轉換到與之相鄰的另一頂點，並使目標函數值更優；如此下去，直到找到某最優解為止 。