網路單純形演算法

㈠ 單純形法 b怎麼算

b列 x1列 x2列 x3 列 x4列 進行矩陣變換例如 ：6是這樣求出來的：第一次迭代時5作為換入變數，就要求5在矩陣變換時變為1,3在矩陣變換時變為0。

所以需要第四行除CB列都乘以1/5，而第三行除CB列都乘以1/3再減去第7行，即12乘以1/3再減去2，結果應該是2，不是6。

由George Dantzig發明的單純形法（simplexalgorithm）在數學優化領域中常用於線性規劃問題的數值求解。

Nelder-Mead 法或稱下山單純形法，與單純形法名稱相似，但二者關聯不大。該方法由Nelder和Mead於1965年發明。

是用於優化多維無約束問題的一種數值方法，屬於更普遍的搜索演算法的類別。這兩種方法都使用了單純形的概念。

單純形是維中的個頂點的凸包，是一個多胞體：直線上的一個線段，平面上的一個三角形，三維空間中的一個四面體等等，都是單純形。

㈡ 單純形法的計算步驟

單純形法計算分為下面幾個步驟：①初始基可行解的確定，②求出基可行解，③最優性檢驗，④換基變數⑤迭代運算。

㈢ 簡述單純形法和對偶單純形演算法的基本思想

單純形法是是保證b>=0，通過轉軸，使得檢驗數r>=0來求得最優解，而使用對偶單純形法的前提是r<=0，通過轉軸，使得達到b>=0。

㈣ LP問題進階 Part 1 | 單純形法

為方便查閱，再link一下 教材 。

假設我們討論的LP問題有 個變數與 個限制條件。

基本概念部分大概就是這些。第一次看不用要求自己完全理解，不妨先繼續往下學習再慢慢理解這些概念罩培。

單純形方法的示意圖如下：

我們先從一下四點直觀的認識入手。

由於書上根本就沒有優化操作的概念，所以在此我自己給出其定義：

我們稱增加的這個非基本變數為 輸入變數 ，變為0的這個基本變數為 輸出變數 。因為輸入變數取代了輸出變數成為新的基。（基的定義可以在前面找到。）
通俗一點地說就是選擇一個非基本變數，讓其不斷增加，要求：

回到主題。之前提到單純形法即對一個基本解實施若干次優化操作後得到最優解的過程。我們先不考慮最優解的存在性，且斷言： 任意非基本變數增加不使得目標函數增加等價於目標函數取得最大值。 這是因為由於符號的限制，非基本變數只能增加，而所有的變數都可以被非基本變數表示。因此非基本變數的增加包含了所有變數的各種變化。

當無法再進行優化操作時有兩種可能。一種是任意非基本變數的增加不使得態悶咐目標函數增加。此時目標函數取最大值。另外一種情況是任意非基本變數的增加不使得某一基本變數變為0。注意， LP問題的標准形式中對於變數的所有限制最終都會歸結於符號限制 ，因此若基本變帆純量不會變為0，則非基本變數可以無限地增加。 此時LP問題無界。

還有一點需要注意的是優化操作一定會在有限步後結束，之後會講到這一點。

經過上述討論我們對單純形演算法的核心步驟應該有一個大致的了解了。

下面是一個小小的總結

單純形演算法到此結束

㈤ 圖解法和單純形法的優缺點，分別適用於哪些類型的線性規劃問題

一、單純形法：

1、優點：把線性規劃問題的約束方程組表達成典範型方程組，找出基本可行解作為初始基本可行解。用於優化多維無約束問題的一種數值方法，屬於更普遍的搜索演算法的類別。

2、缺點：約束條件中存在大於或等於約束：將約束兩邊取負。

二、圖解法：

1、優點：原理簡單，易掌握，會數格子就可以用。

2、缺點：精度有限，要精確確計算用求積儀或者高數裡面的積分最好，圖解法適合在一些精度要求不高的場合使用。

(5)網路單純形演算法擴展閱讀：

注意事項：

平常的線性規劃的裡面，當線性方程組的數量大於這個方程的個數，就會有不定數量的解。

在單純形法要是基本可行，那麼解不存在的話，就是這個約束的條件有矛盾了。

單純形法是要把表達成典範型方程組是要變數的轉換，還有就是目標的轉換，是要找出可行解作為初始基可。如果單純形法是能讓解存在，是從初始作起點，找到目標函數值就是更好的一個基本可行解。

㈥ 單純形方法

單純形法是求解線性規劃問題最常用、最有效的演算法之一。

單純形法最早由 George Dantzig於1947年提出，近70年來，雖有許枯歷脊多變形體已經開發，但卻保持著同樣的基本觀念。如果線性規劃問題的最優解存在，則一定可以在其可行區域的頂點中找到。基於此，單純形法的基本思路是：先找出可行域的一個頂點，據一定規則判斷其是否最優；若否，則轉換到與之相鄰的另一頂點，並使目標函數值更優；如沒滲此下去，直到找到某最優解為止。

為了用選代法求出線性規劃的最優解，需要解決以下三個問題：

(1)最優解判別准則，即迭代終止的判別標准；

(2)換基運算，即從一個基可行解迭代出另一個基可行解的方法；

(3)進基列的選擇，即選擇合適的列以進行換基運算，可以使目標函數值有較大下降。

改進單純形法：
原單純形法不是很經濟的演算法。1953年美國數學家G.B.丹捷格為了改進單純形法每次迭代中積累起來的進位誤差，提出改進單純形法。其基本步驟和單純形法大致相同，主要區別是在逐次迭代中不再以高斯消去法為基礎，而是由舊基陣的逆去直接計算新基陣的逆，再由此確定檢驗數。這樣做可以減少迭代中的累積誤差，提高計算精度，同時也減少了爛純在計算機上的存儲量。

㈦ 如何用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);
}

㈧ 單純形法的原理

單純形法的原理如下：

首先設法找到一個（初始）基可行解，然後再根據最優性理論判斷這個基可行解是否最優解。若是最優解，則輸出結果，計算停止。

若不是最優解，則設法由當前的基可行解產生一個目標值更搜跡優的新的基可行解，再利用最優性理論對所得的新基可行解進行判斷，看其是否最優解，這樣就構成一個迭代演算法。

由於基可行解只有有限個，而每次目標值都有所改進，因而必可在有限步內終止。如果原問題確有最優解，必可在有限步內達到，且計算量大大少於窮舉法；若原問題無最優解，也可根據最優性理論及時發現，停止計算，避免錯誤及無效運算。坦納"

單純讓漏沒形法是求解線性規劃問題最常用、最有效的演算法之一。單純形法最早由 George Dantzig於1947年提出，近70年來，雖有許多變形體已經開發，但卻保持著同樣的基本觀念。如果線性規劃問題的最優解存在，則一定可以在其可行區域的頂點中找到。

基於此，單純形法的基本思路是：先找出可行域的一個頂點，據一定規則判斷其是否最優；若否，則轉換到與之相鄰的另一頂點，並使目標函數值更優；如此下去，直到找到某最優解為止 。

㈨ 單純形法的計算步驟

第一步：基於約束條件物念方程組的系數矩陣，通過尋找或構造單位矩陣的方法，確定基變數，從而求出初始基本可行解，再利用初始基本可行解及線襲孝性規劃模型提供的拍螞稿信息，編制初始單純形表。

第三步：繼續迭代，求解下一個使目標函數更優的基本可行解。