单纯形法cnmd

2024-02-26 17:58

文章标签 单纯形法 cnmd

本文主要是介绍单纯形法cnmd，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

单纯形法

在这里插入图片描述
C-Cheese, If You Please
关键词：线性规划；
思路：
令第 i 种商品的数量为，共 m 种商品。有 n 种原料，每种原料的数量为 w[i] ，第 j 种
商品使用第 i 种原料的比例为 p[i][j] ，每种商品的单价为 t[j] 。可得如下约束条件：
目标是最大化：
可用单纯形法解线性规划。
在这里插入图片描述
我们之前都是求最小花费且约束条件是大于
现在这道题是求最大利润且约束条件是小于
两者区别就在于pivot函数和b【】，c【】这两个数组
n是方程个数，m是未知数x的个数
1.目标最小化的时候（如花费，开销，资源
b数组表示答案系数
c数组表示约束条件
pivot函数是n-m-n-n

2.目标最小化的时候（如利润，好感度这些什么的
c数组表示答案系数
b数组表示约束条件
pivot函数是m-n-m-m


#include<bits/stdc++.h>
using namespace std;
const int MAXN=1500;
const int MAXM=15000;
const double INF=1e10;
const double eps=1e-7;
typedef long long ll;int N,M,n,m;
double a[MAXM][MAXN];//A[i][j]表示第i个方程，Xj的系数是多少
double c[MAXN];//第i个方程需要<=的常数
double b[MAXM];//目标方程Xj的系数是多少
double v;void pivot(int l,int e){b[l]/=a[l][e];for(int j=1;j<=m;j++)if(j!=e)a[l][j]/=a[l][e];//这里的n是方程个数a[l][e]=1/a[l][e];for(int i=1;i<=n;i++)if(i!=l&&fabs(a[i][e])>0){b[i]-=a[i][e]*b[l];for(int j=1;j<=m;j++) if(j!=e) a[i][j]-=a[i][e]*a[l][j];a[i][e]=-a[i][e]*a[l][e];}v+=c[e]*b[l];for(int j=1;j<=m;j++)if(j!=e)c[j]-=c[e]*a[l][j];c[e]=-c[e]*a[l][e];
}double Simplex()
{int i,l,e;while(true){for(i=1;i<=M;i++)if(c[i]>eps)break;if((e=i)==M+1)return v;//答案double tmp=INF;for(i=1;i<=N;i++)if(a[i][e]>eps && b[i]/a[i][e]<tmp)tmp=b[i]/a[i][e],l=i;if(tmp==INF)return INF;//无界pivot(l,e);}
}
int main()
{scanf("%d%d",&N,&M);n=N,m=M;for(int i=1;i<=N;i++){scanf("%lf",&b[i]);b[i]*=100;}for(int i=1;i<=M;i++){for(int j=1;j<=N;j++){scanf("%lf",&a[j][i]);}scanf("%lf",&c[i]);}double ans=Simplex();printf("%.2lf\n",ans);return 0;
}

解决上面这种题的话这个代码就ok了
如果要对偶的话

志愿者招募那道题

#include<bits/stdc++.h>
using namespace std;
const int M=10001,N=1001,INF=1e9;
const double eps=1e-6;
inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
int n,m;
double a[M][N];//有m个变量n个方程
double b[M];//m个x系数也就是答案系数
double c[N];//n个约束
double v;//答案
void pivot(int l,int e){b[l]/=a[l][e];for(int j=1;j<=n;j++)if(j!=e)a[l][j]/=a[l][e];//这里的n是方程个数a[l][e]=1/a[l][e];for(int i=1;i<=m;i++)if(i!=l&&fabs(a[i][e])>0){b[i]-=a[i][e]*b[l];for(int j=1;j<=n;j++) if(j!=e) a[i][j]-=a[i][e]*a[l][j];a[i][e]=-a[i][e]*a[l][e];}v+=c[e]*b[l];for(int j=1;j<=n;j++)if(j!=e)c[j]-=c[e]*a[l][j];c[e]=-c[e]*a[l][e];
}
double simplex(){while(true){int e=0,l=0;for(e=1;e<=n;e++) if(c[e]>eps) break;if(e==n+1) return v;double mn=INF;for(int i=1;i<=m;i++)if(a[i][e]>eps&&mn>b[i]/a[i][e]) mn=b[i]/a[i][e],l=i;if(mn==INF) return INF;//unboundedpivot(l,e);}}
int main(){n=read();m=read();//n个方程，m个待求解的未知数for(int i=1;i<=n;i++)c[i]=read();for(int i=1;i<=m;i++){int l=read(),r=read();for(int j=l;j<=r;j++)a[i][j]=1;b[i]=read();}printf("%d",int(simplex()+0.5));
}

#include<bits/stdc++.h>
using namespace std;
const int M=10001,N=10001;
#define INF 1e10
const double eps=1e-6;
inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
int n,m;
double a[M][N];//有m个变量n个方程
double b[M];//m个x系数也就是答案系数
double c[N];//n个约束
double v;//答案
void pivot(int l,int e){b[l]/=a[l][e];for(int j=1;j<=n;j++)if(j!=e)a[l][j]/=a[l][e];//这里的n是方程个数a[l][e]=1/a[l][e];for(int i=1;i<=m;i++)if(i!=l&&fabs(a[i][e])>0){b[i]-=a[i][e]*b[l];for(int j=1;j<=n;j++) if(j!=e) a[i][j]-=a[i][e]*a[l][j];a[i][e]=-a[i][e]*a[l][e];}v+=c[e]*b[l];for(int j=1;j<=n;j++)if(j!=e)c[j]-=c[e]*a[l][j];c[e]=-c[e]*a[l][e];
}
double simplex(){while(true){int e=0,l=0;for(e=1;e<=n;e++) if(c[e]>eps) break;if(e==n+1) return v;double mn=INF;for(int i=1;i<=m;i++)if(a[i][e]>eps&&mn>b[i]/a[i][e]) mn=b[i]/a[i][e],l=i;if(mn==INF) return INF;//unboundedpivot(l,e);}}
signed main(){n=read();m=read();swap(n,m);//n个方程，m个待求解的未知数//5个答案系数，3个方程for(int i=1;i<=m;i++)b[i]=read();// for(int i=1;i<=m;i++)cout<<b[i]<<" ";// cout<<endl;for(int i=1;i<=n;i++){int l=read(),r=read();for(int j=l;j<=r;j++)a[j][i]=1;c[i]=read();}printf("%d",(long long)(simplex()+0.5));
}