单纯形法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;//unbounded pivot(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;//unbounded pivot(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)); } 

今天的文章
单纯形法cnmd_什么是单纯形法分享到此就结束了，感谢您的阅读。