|
|
<DIV class=postcolor>单纯型法的源程序
#include<stdio.h>
#include<string.h>
#define MAX 100
#define infinity 100000000
double c[MAX];
double g[MAX][MAX];
int B[MAX],mark[MAX];
// g[0] presents b;
// g[0] presents r;
int m,n;
int readdata()
{
int x,y;
memset(c,0,sizeof©);
memset(g,0,sizeof(g));
memset(mark,0,sizeof(mark));
scanf("%d %d",&n,&m);
for(y=1;y<=n;y++)scanf("%lf",&c[y]);
for(x=1;x<=m;x++)
{
scanf("%d",&B[x]);
for(y=1;y<=n;y++)
scanf("%lf",&g[x][y]);
scanf("%lf",&g[x][0]);
}
return 0;
}
int initial()
{
int x,y;
for(x=1;x<=m;x++){mark[B[x]]=1;}
for(x=1;x<=n;x++)
if(!mark[x])
{
g[0][x]=c[x];for(y=1;y<=m;y++)g[0][x]-=c[B[y]]*g[y][x];//r=c-Cb*B^(
-1)*P
}
for(x=1;x<=m;x++)g[0][0]+=c[B[x]]*g[x][0];
g[0][0]=-g[0][0];
return 0;
}
int guass(int a,int <!--emo&B)--><IMG><!--endemo-->
{
int x,y;
double mainelem,colelem;
mainelem=g[a];
for(x=0;x<=n;x++)g[a][x]/=mainelem;
for(x=0;x<=m;x++)
{
colelem=g[x];
if(x!=a)for(y=0;y<=n;y++)
{
g[x][y]-=colelem*g[a][y];
}
}
return 0;
}
int print(int a,int <!--emo&B)--><IMG><!--endemo-->
{
int x,y;
printf("-----------\n");
for(x=1;x<=m;x++)
{
printf("x%3d :",B[x]);
for(y=1;y<=n;y++)
{
if(x==a&&y==<!--emo&B)--><IMG><!--endemo--> printf("[%6.3lf]",g[x][y]);
else printf("%7.3lf ",g[x][y]);
}
printf("| %5.1lf\n",g[x][0]);
}
printf("criti:");
for(x=1;x<=n;x++)printf("%7.3lf ",g[0][x]);
printf("| %7.3lf\n",g[0][0]);
return 0;
}
int calc_max()
{
int x,y,i,j;
double max;int maxnum;
double min;int minnum;
int find;
while(1)
{
max=-infinity;
for(x=1;x<=n;x++)if(g[0][x]>max){max=g[0][x];maxnum=x;}//find
the max crit
erion
if(max<=0)
{
print(0,0);
printf("the optimal solution is :%lf.\n",-g[0][0]);
return 0;
}else//col[mmnum]is the main col
{
find=0;min=infinity;
for(y=1;y<=m;y++)
{
if(g[y][maxnum]>0){
find=1;
if(g[y][0]/g[y][maxnum]<min){min=g[y][0]/g[y][maxnum];minnum=y;}
}
}
if(!find){printf("no optimal solution!\n");return 0;}
mark[B[minnum]]=0;mark[maxnum]=1;
B[minnum]=maxnum;//the X[maxnum] enter the Base ,the
B[minnum] quit the B
ase;
print(minnum,maxnum);
guass(minnum,maxnum);
}
}
return 0;
}
int main()
{
freopen("sim.in","r",stdin);
freopen("sim.out","w",stdout);
readdata();
initial();
calc_max();
fclose(stdin);
fclose(stdout);
return 0;
}
数据文件格式：
6 3
-1 -1 4 0 0 0
4 1 1 2 1 0 0 9
5 1 1 -1 0 1 0 2
6 -1 1 1 0 0 1 4
第2行是价值系数
以后每行第一个是基变量，一定要有初始单位阵！
</DIV> |
|
发表于 2004-7-20 00:08:08
> </P><