单纯形算法程序

天亮

zhyi,你好.我有一问题请你指教阿.有一个10维的有约束的函数,现在我已经有了一些可行点,其数目可能大于或者小于10,可行点之间的关系不知道,请问怎样运用单纯行法求函数的最小值.

chenbilian158

试试

luom

还有其他算法吗关于仿生算法的谢谢

jixian

顶

海云边缘

有C語言的嗎？我要C語言的

suolunga

[em01][em01][em01]

sfhnlgdx

谢谢，我正在找这个程序，终于找到了！

chz0829

看不懂

hustyangyang

楼上的的确是位高手，这两天由于写论文要用到单纯形法的程序，就拿来用了，但是发现有些错误，没有结果或者得出的答案有问题，于是我仔细看了一下这个程序，将楼上的笔误，和一些其他的小错误改正如下，
注意： 我不是用纯 VC++  我的输出函数用的是 printf (),这样可以动态观察结果输出，以便于修改，这个程序是我花了一天的时间改的，太长也太烦琐，我看的也不是很清楚，只对 限制条件是 <= 的情况进行了详细的察看，和修改，其他的情况就没有看了，程序中相应的部分有比较详细的注解，如果有需要可以和我联系，我们一起共同探讨。谢谢！QQ：116490942

 

#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 且置成相应的标记
   rocess(nlet,i,indexl-1);//传 net, 行号，indexl-1 过去
  }
  if(code==1)
  {
   net[indexg++]=1;           //人工变量数+1且置成相应的标记
   rocess(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);
 rocessA();
 InitPrint();
 Xartificial();
}

void Simplix()//单纯形法
{
 int in,out,temp=0;
 while(1)
 {
  jckxj();
  rint();
        Result();
        if(!rj()) in=Min();
  else
  {
   if(indexg!=0)
    JustArtificial();
   rintResult();
   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
*/

999mmg

呵呵&nbsp; 绝对的好东西&nbsp; 我喜欢