UOJ179 - 线性规划

78 阅读 0 评论 52 点赞

我是靠谱客的博主忧虑乌冬面，这篇文章主要介绍UOJ179 - 线性规划，现在分享给大家，希望可以做个参考。

Portal

Description

求解一个标准型线性规划：
有(n)个实数变量(x_1,x_2,...,x_n)和(m)条约束，其中第(i)条约束形如 (sum_{j=1}^na_{ij}x_jleq b_i)。
此外这(n)个变量需要满足非负性限制，即(x_j≥0)。
在满足上述所有条件的情况下，你需要指定每个变量(x_j)的取值，使得目标函数 (F=sum_{j=1}^nc_jx_j)的值最大。
其中(1≤n,m≤20, 0≤|a_{ij}|,|b_i|,|c_j|≤100)。

Solution

线性规划模板题，用单纯形可解。墙裂推荐看看这篇论文：2 Solving LPs: The Simplex Algorithm of George Dantzig。

Code

复制代码

//线性规划
#include <cstdio>
#include <algorithm>
using namespace std;
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||'9'<ch) f=(ch^'-')?f:-1,ch=getchar();
while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
int const N=30;
double const EPS=1e-8;
bool equal0(double x) {return -EPS<x&&x<EPS;}
int n,m,T;
double a[N][N];
int b[N],id[N<<1];
void pivot(int x,int y)
{
swap(id[n+x],id[y]);
double t=a[x][y]; a[x][y]=1;
for(int i=0;i<=n;i++) a[x][i]/=t;
for(int i=0;i<=m;i++)
{
if(i==x||equal0(a[i][y])) continue;
t=a[i][y],a[i][y]=0;
for(int j=0;j<=n;j++) a[i][j]-=a[x][j]*t;
}
}
bool simplex()
{
while(true)
{
int x=0,y=0;
for(int j=1;!y&&j<=n;j++) if(a[0][j]>EPS) y=j;
if(!y) return true;
double minX=1e18;
for(int i=1;i<=m;i++)
if(a[i][y]>EPS&&minX>a[i][0]/a[i][y]) minX=a[i][0]/a[i][y],x=i;
if(!x) {puts("Unbounded"); return false;}
pivot(x,y);
}
}
bool solve()
{
for(int i=1;i<=n;i++) id[i]=i;
while(true)
{
int x=0,y=0;
for(int i=1;i<=m;i++) if(a[i][0]<-EPS&&(!x||rand()&1)) x=i;
if(!x) return simplex();
for(int j=1;j<=n;j++) if(a[x][j]<-EPS&&(!y||rand()&1)) y=j;
if(!y) {puts("Infeasible"); return false;}
pivot(x,y);
}
}
double ans[N];
int main()
{
n=read(),m=read(),T=read();
for(int i=1;i<=n;i++) a[0][i]=read();
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++) a[i][j]=read();
a[i][0]=read();
}
if(solve())
{
printf("%.10lfn",-a[0][0]);
if(!T) return 0;
for(int i=1;i<=m;i++) ans[id[n+i]]=a[i][0];
for(int i=1;i<=n;i++) printf("%.10lf ",ans[i]);
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//线性规划
#include <cstdio>
#include <algorithm>
using namespace std;
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||'9'<ch) f=(ch^'-')?f:-1,ch=getchar();
while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
int const N=30;
double const EPS=1e-8;
bool equal0(double x) {return -EPS<x&&x<EPS;}
int n,m,T;
double a[N][N];
int b[N],id[N<<1];
void pivot(int x,int y)
{
swap(id[n+x],id[y]);
double t=a[x][y]; a[x][y]=1;
for(int i=0;i<=n;i++) a[x][i]/=t;
for(int i=0;i<=m;i++)
{
if(i==x||equal0(a[i][y])) continue;
t=a[i][y],a[i][y]=0;
for(int j=0;j<=n;j++) a[i][j]-=a[x][j]*t;
}
}
bool simplex()
{
while(true)
{
int x=0,y=0;
for(int j=1;!y&&j<=n;j++) if(a[0][j]>EPS) y=j;
if(!y) return true;
double minX=1e18;
for(int i=1;i<=m;i++)
if(a[i][y]>EPS&&minX>a[i][0]/a[i][y]) minX=a[i][0]/a[i][y],x=i;
if(!x) {puts("Unbounded"); return false;}
pivot(x,y);
}
}
bool solve()
{
for(int i=1;i<=n;i++) id[i]=i;
while(true)
{
int x=0,y=0;
for(int i=1;i<=m;i++) if(a[i][0]<-EPS&&(!x||rand()&1)) x=i;
if(!x) return simplex();
for(int j=1;j<=n;j++) if(a[x][j]<-EPS&&(!y||rand()&1)) y=j;
if(!y) {puts("Infeasible"); return false;}
pivot(x,y);
}
}
double ans[N];
int main()
{
n=read(),m=read(),T=read();
for(int i=1;i<=n;i++) a[0][i]=read();
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++) a[i][j]=read();
a[i][0]=read();
}
if(solve())
{
printf("%.10lfn",-a[0][0]);
if(!T) return 0;
for(int i=1;i<=m;i++) ans[id[n+i]]=a[i][0];
for(int i=1;i<=n;i++) printf("%.10lf ",ans[i]);
}
return 0;
}