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上找找線性規劃的題目來下寫寫。嘿嘿，