optimization_procedures.txt

本程序是单纯形法

1、算法
/*本程序是单纯形法，参考书目:河海大学<吴凤平>运筹学方法与应用*/
#include<stdio.h>
#include<math.h>
#define X 5
#define Y 7
void xi_max(int *m2,int *mn1,float *c,int *is,int *ir,int *j0,float (*a)[X][Y])

  int j;
  *c=0;
  for(j=1;j<=*is;j++) 
    {
      if((*a)[*ir][j]-*c>0)
    {
      *c=(*a)[*ir][j];
      *j0=j;
    {}
     }
}

      /***************** 参数说明 **********************/
      /*   m_约束方程个数(基变量个数),n_非基变量个数   */
      /*   m2-m+2整个变量,(*a)[X][Y]存放初始数据       */
      /*   (*k)[]存放基变量脚标,(*x)存放基变量最优值   */
      /*********http://happyyangxu.home.sunbo.net*******/ 

int xi_sm(int m,int n,int m2,int mn1,int l1,float (*a)[X][Y],
       int(*k)[],float(*x)[])

  int i,m1,mn,j0,i0,j;
  float c,g;
  m1=m+1;
  mn=m+n;
  for(i=1;i<=m;i++)
    (*k)[i]=n+i;
leap1:
  if(l1-1==0)
     xi_max(&m2,&mn1,&c,&mn,&m1,&j0,a);
  else
     {
leap2:   if(l1-50==0)
      xi_max(&m2,&mn,&c,&n,&m2,&j0,a);
       else
      xi_max(&m2,&mn1,&c,&mn,&m2,&j0,a);
     {}
   c-=1e-8;
   if((c<=0)&&(l1==1)&&((*a)[m1][mn1]-1e-8>0))
      
    printf(" *********Not min&&No solution********** ");
    return(-1);
      {}
   if((c<0)&&(l1==1))
       
     l1=50;
     goto leap2;
       {}
    if(c<=0)
       
      for(i=1;i<=m;i++)
         (*x)[i]=(*a)[i][mn1];
         printf(" ********Optimal solution******** ");
      for(i=1;i<=m;i++)
         printf(" i=%d,x[i]=%f ",(*k)[i],(*x)[i]);
      printf(" F=%f ",(*a)[m2][mn1]);
      return 0;
    {}
     c=1e8;
     for(i=1;i<=m;i++)
       
     if((*a)[i][j0]>1e-8)
        {
          g=(*a)[i][mn1]/(*a)[i][j0];
          if(g-c<0);
         {
           c=g;
           i0=i;
          {}
         }
    }
      if(c==1e+8)
    
      printf(" *******Lp no solution******** ");
      return -3;
     {}
       (*k)[i0]=j0;
       for(j=1;j<=mn1;j++)
      
        if((j==j0)||(l1==50)&&(n<j)&&(j<mn1))
           continue;
         g=(*a)[i0][j]/(*a)[i0][j0];
           (*a)[i0][j]=g;
         for(i=1;i<=m2;i++)
           {
         if((i==i0)||(!(l1==1)&(i==m1)))
            continue;
         (*a)[i][j]=(*a)[i][j]-(*a)[i][j0]*g;
           {}
       }
       for(i=1;i<=m2;i++)
      (*a)[i][j0]=0;
       (*a)[i0][j0]=1;
       goto leap1;
}  
main()

  float a[5][7]={{0,0,0, 0,  0,0,0{},
                 0,3,-4,3,  1,0,12{},
                 0,3,0, 6,  0,1,12{},
                 0,0,0, 0,  0,0,0{},
                 0,69,0,144,0,0,300{}};
  int k[3];
  float x[3];
  clrscr();
  xi_sm(2,3,4,6,0,&a,&k,&x);
}

2、单纯型法的源程序 zz

#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("----------- "); 
        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 ",g[x][0]); 
        } 
        printf("criti:"); 
        for(x=1;x<=n;x++)printf("%7.3lf ",g[0][x]); 
        printf("| %7.3lf ",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. ",-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! ");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行是价值系数 
以后每行第一个是基变量，一定要有初始单位阵！