查看: 5175|回复: 4

[分享][原创]单纯形法的程序代码，程序中不是用纯粹的VC++，输出函数用的是printf(

字体大小: 正常放大

1 主题	0 听众	18 积分

升级 13.68%

该用户从未签到

电梯直达

1^#

发表于 2006-7-19 15:05 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

#include<stdio.h> #include<iostream.h> #include<math.h> float matrix[100][100],x[100]; int a[100]; int m,n,s,type; int indexe,indexl,indexg; ///////////////////////////////// void jckxj()//基础可行解 {  int i,j;                        //基础可行解即为非基变量对应的x=b, 基变量对应的解为0  for(i=0;i<n;i++)   for(j=0;j<s;j++)    if(matrix[j]==1&&a[j]==1)    {     x[j]=matrix;     j=s;    }    for(i=0;i<s;i++)     if(a==0)x=0; }int rj()//基解矩阵 {  int i;  for(i=0;i<s;i++)   if(fabs(matrix[n])>=0.000001)    if(matrix[n]<0)return 0;    return 1; }int Min()//求最小的 {     int i,temp=0;  float min=matrix[n][0];  for(i=1;i<s;i++)   if(min>matrix[n])   {    min=matrix[n];    temp=i;   }  return temp; } ///////////////////////////////// void JustArtificial()//人工变量 {  int i;  for(i=m+indexe+indexl;i<s;i++)   if(fabs(x)>=0.000001)   {    cout<<"NO Answer\n";    return;   } } ///////////////////// int Check(int in)//检验 {  int i;  float maxl=-1;  for(i=0;i<n;i++)   if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])    maxl=matrix/matrix[in];   if(maxl<0)    return 1;   return 0; }int SearchOut(int *temp,int in)//出基变量 {  int i;  float min=10000;  for(i=0;i<n;i++)   if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0)    &&min>matrix/matrix[in])   {    min=matrix/matrix[in];    *temp=i;   }    for(i=0;i<s;i++)   if(a=1&&matrix[*temp]==1)  return i; } ///////////////////////////////// void Mto(int in,int temp) {  int i;  for(i=0;i<=s;i++)   if(i!=in)    matrix[temp]=matrix[temp]/matrix[temp][in];   matrix[temp][in]=1; } ///////////////////////////// void Be(int temp,int in)//初等变换 {  int i,j;  float c;  for(i=0;i<=n;i++)  {   c=matrix[in]/matrix[temp][in];   if(i!=temp)    for(j=0;j<=s;j++)     matrix[j]=matrix[j]-matrix[temp][j]*c;  } } ////////////////////////// void Achange(int in,int out)//出基入基转换 {  int temp=a[in];  a[in]=a[out];  a[out]=temp; } //////////////////////// void Print() {  int i,j,k,temp=0;  for(i=0;i<n;i++)  {   for(k=temp;k<s;k++)    if(a[k]==1)    {     printf(" %d ",k);     temp=k+1;     k=s;    }   for(j=0;j<=s;j++)    printf( " %.0f ",matrix[j]  );   printf("\n");  }  printf("Rj\n");  for(j=0;j<=s;j++)   printf(" %.0f ",matrix[n][j] );  printf("\n"); } //////////////////////// void InitPrint() {  int i;  printf(" X ");  for(i=0;i<s;i++)   printf(" %d ",i);     printf(" b \n" );  printf("  " );  printf("\n" ); } ////////////////// void Result() {  int i;  printf( "(" );  for(i=0;i<s;i++)   printf( "%.0f",x );  printf( ")" );  if(type==1)   printf("\nZmax= %.0f\n" ,matrix[n] );  else printf("\nZmin=%.0f\n", matrix[n] ); } ////////////////////// void PrintResult() {  if(type==0)   printf("the Minimal: %.2f\n", matrix[n] );  else   printf("the Maximum: %.2f\n", matrix[n] ); } //////////////////////////////// void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 {                                                                                         //置成我们需要的矩阵，最后一列置成0                                                              // 1  2  1  0  0  0                                                              // 4  0  0  1  0  0                                                              // 0  4  0  0  1  0                                                              //-2 -3  0  0  0  0  int i,j;                                               for(i=0;i<n;i++)  {   for(j=m;j<m+indexe;j++)    if(nget[j-m]!=-1)matrix[j]=0;    else matrix[j]=-1;   for(j=m+indexe;j<m+indexe+indexl;j++)     if(nlet[j-m-indexe]!=1)matrix[j]=0;     else matrix[j]=1;   for(j=m+indexe+indexl;j<s;j++)     if(net[j-m-indexe-indexl]!=1)matrix[j]=0;     else matrix[j]=1;  }  for(i=m;i<m+indexe+indexl;i++)  //将目标函数中人工变量的系数补为0   matrix[n]=0;  for(i=m+indexe+indexl;i<s;i++)   matrix[n]=100;              //置成M  for(i=0;i<n;i++)                   //把b[]的值赋给matrix　      matrix=b;  matrix[n]=0; } /////////////////////////// void ProcessA()//初始a[]    a[]是标记基变量，若为基变量则为0，若为非基变量则为1 {  int i;  for(i=0;i<m+indexe;i++)   a=0;  for(i=m+indexe;i<s;i++)   a=1; }//////////////////////////////// void Input(float b[],int code[]) {  int i=0;int j=0;  cout<<"The equator variable and Restrictor\n";  cin>>m>>n;  for(i=0;i<n;i++)  {   cout<<"Inputb[] and Restrictor code 0:<= 1:= 2:>=\n";//输入b[]和限制符号 <= ,= ,>=   cin>>b>>code;           //分别输入到b 和  code 中   cout<<"The 系数  \n";         //提示输入每个限制条件的系数   for(j=0;j<m;j++)             cin>>matrix[j];  }  cout<<"the type 0:Min 1:max\n";//输入要求是类型极大还是极小 0:Min 1:max  do{   cin>>type;   if(type!=0&&type!=1)    cout<<"error,ReInput!\n";  }while(type!=0&&type!=1);  cout<<"the Z\n";  for(i=0;i<m;i++)   cin>>matrix[n];  if(type==1)                    //如果是求极大，把它转化为极小来做，系数全部反号   for(i=0;i<m;i++)    matrix[n]=-matrix[n]; }                                            //////////////////    void Xartificial()//消去人工变量 {  int i,j,k;    if(indexg!=0)  {   for(i=m+indexe+indexl;i<s;i++)   {    for(j=0;j<n;j++)     if(matrix[j]==1)     {      for(k=0;k<=s;k++)       matrix[n][k]=matrix[n][k]-matrix[j][k]*100;      j=n;     }   }  } }//////////////////////////////////////////////// void Process(float c[][100],int row,int vol) {  int i;  for(i=0;i<n;i++)     //i =0 时置第一列为 1  0  0     i=1 时置第2列为 0  1  0    if(i!=row)c[vol]=0; } ////////////////////// void Start(float b[],int code[]) {  int i;  float nget[100][100],nlet[100][100],net[100][100];  indexe=indexl=indexg=0;               //indexl 表示松弛变量数   indexg 表示人工变量数， indexe表示减去的松弛变量数  for(i=0;i<n;i++)  {   if(code==0)    //如果是<=   {    nlet[indexl++]=1;         //松弛变量数+1 且置成相应的标记   &nbsprocess(nlet,i,indexl-1);//传 net, 行号，indexl-1 过去   }   if(code==1)   {    net[indexg++]=1;           //人工变量数+1且置成相应的标记   &nbsprocess(net,i,indexg-1);      //将刚加入的列单位化   }   if(code==2)   {    net[indexg++]=1;         //人工变量数+1 且置成相应的标记    nget[indexe++]=-1;       //剩余变量数+1 且置成相应的标记             Process(net,i,indexg-1)rocess(nlet,i,indexe-1);   }  }  s=indexe+indexl+indexg+m;   //变量总个数  Merge(nget,nlet,net,b); &nbsprocessA();  InitPrint();  Xartificial(); }void Simplix()//单纯形法 {  int in,out,temp=0;  while(1)  {   jckxj();  &nbsprint();         Result();         if(!rj()) in=Min();   else   {    if(indexg!=0)     JustArtificial();   &nbsprintResult();    return;   }   if(Check(in))   {    cout<<"No Delimition\n";    return;   }   out=SearchOut(&temp,in);   Mto(in,temp);   Be(temp,in);   Achange(in,out);  } }void main() {  int code[100];//输入符号标记  float b[100];  Input(b,code);//初始化  Start(b,code);//标准化行  Simplix(); } /*模拟输入数据  max z=2 x1 + 3 x2       s.t {         x1 + 2 x2 <=8      4 x1      <=16            4 x2<=12             x1,x2>=0    }2 3 8 0 1 2 16 0 4 0 12 0 0  4 */