修正单纯型.zip.txt

修正单纯型方法程序

#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(c)); 
        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 b) 
{ 
        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 b) 
{ 
        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==b)  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行是价值系数 
以后每行第一个是基变量，一定要有初始单位阵！ 


-----------------------------------------------------------
马上到http://www.126.com申请260M全国最大免费邮箱!
提供新邮件到达手机短信提醒功能, 随时掌握邮件信息!