网络单纯形算法

㈠ 单纯形法 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年来，虽有许多变形体已经开发，但却保持着同样的基本观念。如果线性规划问题的最优解存在，则一定可以在其可行区域的顶点中找到。

基于此，单纯形法的基本思路是：先找出可行域的一个顶点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一顶点，并使目标函数值更优；如此下去，直到找到某最优解为止 。

㈨ 单纯形法的计算步骤

第一步：基于约束条件物念方程组的系数矩阵，通过寻找或构造单位矩阵的方法，确定基变量，从而求出初始基本可行解，再利用初始基本可行解及线袭孝性规划模型提供的拍蚂稿信息，编制初始单纯形表。

第三步：继续迭代，求解下一个使目标函数更优的基本可行解。