注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

XYP的博客

枫染红尘谁看透

 
 
 

日志

 
 

线性规划口胡  

2016-02-20 23:05:05|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
非对偶形:
ans=max(c1x1+cc2+c3x3+...)
限制: xi+aij*xj(j!=i)=bi
基变量:在式子左边的x,系数为1。
首先,我们找到一个c[e]>0,可以发现,如果增加了x[e],答案会增加。
接着,找到一个式子l,使得e在这个式子中出现且不是基变量。
我们用式子l剩下的部分来表示xe,显然,xe=(1/ale)*(bl-alj*xj(j!=e))
用这堆式子把所有限制中的xe都带掉,就可以得到一个新的限制。同时,再把ce也带掉。可以发现,经过这次操作后,ans会加上一个常数。
这样做一定次数后,就会发现所有ci<0,这时就可以退出了。

怎么实现呢?
发现每次操作后,x[e]在l式中变为了基变量,在其余式子和c中则消失了。
而l式原来的基变量则代替了e的全部位置。
于是,我们可以把所有e的系数的位置改变为l原来的基变量的位置,由于所有基变量的系数都为1,e在a中的系数也是可以忽略的了。
某一个时刻时的aij并不表示i式中j的系数!

inline void Pivot(int l,int e)
{
b[l]/=A[l][e];
for (int i=1;i<=n;i++) if (i!=e) A[l][i]/=A[l][e];
A[l][e]=1/A[l][e];
for (int i=1;i<=m;i++)
if (fabs(A[i][e])>eps&&i!=l)
{
b[i]-=b[l]*A[i][e];
for (int j=1;j<=n;j++) if (j!=e) A[i][j]-=A[l][j]*A[i][e];
A[i][e]=-A[i][e]*A[l][e];
}
v+=c[e]*b[l];
for (int i=1;i<=n;i++) if (i!=e) c[i]-=c[e]*A[l][i];
c[e]=-c[e]*A[l][e];
inline db Simplex()
{
int i,l,e;
int deb=0;
while (1)
{
for (i=1;i<=n;i++) if (c[i]>eps) break;
if ((e=i)==n+1) return(v);
db tmp=inf;
for (i=1;i<=m;i++) if (A[i][e]>eps)
if (b[i]/A[i][e]<tmp) tmp=b[i]/A[i][e],l=i;
if (tmp==inf) return(inf);
Pivot(l,e);
}
}
  评论这张
 
阅读(48)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018