LinerProgramming，线性规划。是运筹学的一个重要分支。
1947年单捷格（G.B.Dantzing）提出了一般LP规划问题的求解方法———单纯型法（simplex algorithm）。
这里是用到没有改进的单纯型法，输入数据的标准型^..^
该学学改进的单纯型法了。
线性规划问题还是有很多用的，是个好模型！！！
#include<stdio.h>
#include<string.h>
#include<math.h>
#define inf 10000000.0
int n,m;
int g[1005],q[1005],p[1005];
double b[1005],c[1005],x[1005],a[1005][1005];
//********数据输入、初始化*************
int init()
{
int i,j;
//********数组初始化**********
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
memset(x,0,sizeof(x));
memset(q,0,sizeof(q));
printf("请输入单纯型表的标准型:\n");
//********输入数据************
scanf("%d%d",&m,&n);
for (i=1; i<=n ; i++ )
scanf("%lf",&c[i]);
for (i=1; i<=n ; i++ )
scanf("%d",&p[i]);
for (i=1; i<=m ; i++ )
{
for (j=1; j<=n ; j++ )
scanf("%lf",&a[i][j]);
scanf("%lf",&b[i]);
}
//**********初始化单纯型表****
for (i=1; i<=m ; i++ )
g[i]=i,q[i]=1,a[i][n+1]=b[i],x[i]=b[i];
for (j=1; j<=n ; j++ )
a[m+1][j]=c[j];
for (j=n+1; j>m ; j-- )
{
for (i=1; i<=m ; i++ )
a[m+1][j]-=c[i]*a[i][j];
}
}
//**********结果输出********************
int print(int result)
{
int i;
double sum;
if (result==-1)
{
printf("无可行解\n");
return ;
}
if (result==-2)
{
printf("无界解\n");
return ;
}
if (result==-3)
{
printf("无穷多最优解。其中一个是：\n");
sum=0.0;
for (i=1; i<=n ; i++ )
sum+=x[i]*c[i];
for (i=1; i<n ; i++ )
printf("%.4lf ",x[i]);
printf("%.4lf\n",x[n]);
return ;
}
printf("有最优解：\n");
sum=0.0;
for (i=1; i<=n ; i++ )
sum+=x[i]*c[i];
printf("%.4lf\n",sum);
for (i=1; i<n ; i++ )
printf("%.4lf ",x[i]);
printf("%.4lf\n\n",x[n]);
return ;
}
//***********检查单纯型表***************
int check()
{
int i,j,flag,flg,mj;
double max;
flag=0;
flg=0;
for (j=1; j<=n ; j++ )
{
if (a[m+1][j]>0.0)
{
flag=1;
max=0.0;
for (i=1; i<=m ; i++ )
if (a[i][j]>max)
max=a[i][j],mj=j;
if (max>0.0)
flg=1;
}
}
if (!flag)
{
for (i=1; i<=m ; i++ ) //判断是否无可行解
{
if (p[g[i]]&&a[i][n+1]!=0.0)
return -1;
}
for (j=1; j<=n ; j++ ) //判断是否有无穷多最优解
if (!q[j]&&a[m+1][j]==0.0)
return -3;
return 0;//唯一最优解
}
if (!flg)
return -2;//无界解
return mj;//找到最大的那个a[m+1][j]作为换入变量
}
//*********找到最小的那个数*************总是能找到的？？？？
int f_min(int r)
{
int i,mi;
double min;
min=inf;
for (i=1; i<=m ; i++ )
if (a[i][r]!=0.0&&a[i][n+1]/a[i][r]>0&&a[i][n+1]/a[i][r]<min)
min=a[i][n+1]/a[i][r],mi=i;
printf("%.4lf ",min);
return mi;//确定为换出变量
}
//********guass消元法进行迭代***********
int guass(int k,int r)
{
int i,j;
for (j=n+1; j>=1 ; j-- ) //行变换
if (j!=r)
a[k][j]/=a[k][r];
a[k][r]=1.0;
for (i=1; i<=m+1 ; i++ ) //每一行进行变换
if (i!=k)
{
for (j=1; j<=n+1 ; j++ )
if (j!=r)
a[i][j]-=a[k][j]*a[i][r];
a[i][r]=0.0;
}
q[g[k]]=0;
g[k]=r;
q[r]=1;
memset(x,0,sizeof(x));
for (i=1; i<=m ; i++ )
x[g[i]]=a[i][n+1];
}
int work()
{
int i,j,r,k;
while (1)
{
for (i=1; i<=m+1 ; i++ )
{
for (j=1; j<=n+1 ; j++ )
printf("%.4lf ",a[i][j]);
printf("%d\n",g[i]);
}
for (j=1; j<=n ; j++ )
printf("%.4lf ",x[j]);
printf("%.4lf\n",x[j]);
r=check();
if (r<=0)
return r;
k=f_min(r);
printf("%d %d\n\n",k,r);
guass(k,r);
}
}
int main()
{
int result;
init();
result=work();
print(result);
return 0;
}
有时间得去poj，zoj上找找线性规划的题目来下写写。嘿嘿，