算法.txt

偶数阶魔方和的算法 线性规划单纯形法VC源码

 else {
 if(indexg!=0) JustArtificial(); /* 判断人工变量 */
 PrintResult(); /* 打印最后结果 */
 return;
 }
 if(Check(in)){ /* 判断无界情况 */
 printf("No Delimition\n");
 return;
 }
 out=SearchOut(&temp,in); /* 求换出基 */
 Mto(in,temp); /* 主元化1 */
 Be(temp,in); /* 初等变换 */
 Achange(in,out); /* 改变a[]的值 */
 }
 }
 
 void main()
 {
 int code[100]; /* 输入符号标记 */
 float b[100]; /* 方程右值 */
 Input(b,code); /* 初始化 */
 Sstart(b,code); /* 化标准型 */
 Simplix(); /* 单纯型算法 */
 }
 
 
 实验报告：
 
 ***************************************************************************************
 *********************************运筹学单纯形法解线性规划问题（C＋＋实现,VC6.0中通过）**********************************
 函数列表：
 Jckxj
 Rj
 Min
 JustArtificial
 Check
 SearchOut
 Mto
 Be
 Achange
 Print
 InitPrint
 Result
 PrintResult
 Merge
 ProcessA
 Input
 Xartificial
 Process
 Sstart
 Simplix
 while
 main
 
 变量：
 float matrix[100][100],x[100]       记录总方程的数组,解的数组 
 int a[100]                          记录基础,非基础的解的情况,0:非基础,1:基础  
 int m,n,type                        方程变量,约束数,求最大最小值的类型,0:最小 1:最大  
 int indexe,indexl,indexg            剩余变量,松弛变量,人工变量  
 
 输入提示：
 equator Variable                    变量个数；
 Restrictor                          约束条件个数；（注：这里程序默认X(i)>0；否则对每个X(i)我们均要添加一个约束条件X(i)>0）
 b[]                                 约束条件右端项；
 Restrictor code                     约束条件不等式符号编码;(0表示<=；1表示=；2表示>=)
 The XiShu                           各约束条件中X(i)对应的系数
 The Type                            Z的最优方向（0表示MIN;1表示MAX）
 The Z                               目标函数的系数
 
 输入例子：
 MAX Z=4X(1)+3X(2)
  S.T.  2X(1)+3X(2)<=24
        3X(1)+2X(2)<=26
        X(1),X(2)>=0
 运行1000432.exe
 The equator Variable and Restrictor:
 2 2
 Input b[] and Restrictor code 0:<= 1:= 2:>=
 24 0
 The XiShu
 2 3
 Input b[] and Restrictor code 0:<= 1:= 2:>=
 26 0
 The XiShu
 3 2
 The Type 0:Min 1:Max
 1
 The Z
 4 3
 结果输出：
 X       a0      a1      a2      a3      b
 X2     2.00    3.00    1.00    0.00   24.00
 X3     3.00    2.00    0.00    1.00   26.00
 Rj    -4.00   -3.00    0.00    0.00    0.00
 
 X2     2.00    3.00    1.00    0.00   24.00
 X3     3.00    2.00    0.00    1.00   26.00
 Rj    -4.00   -3.00    0.00    0.00    0.00
  (    0.00    0.00   24.00   26.00 )  Zmax=0.000000
 
 X0     0.00    1.67    1.00   -0.67    6.67
 X2     1.00    0.67    0.00    0.33    8.67
 Rj     0.00   -0.33    0.00    1.33   34.67
  (    8.67    0.00    6.67    0.00 )  Zmax=34.666668
 
 X0     0.00    1.00    0.60   -0.40    4.00
 X1     1.00    0.00   -0.40    0.60    6.00
 Rj     0.00    0.00    0.20    1.20   36.00
  (    6.00    4.00    0.00    0.00 )  Zmax=36.000000
 
 The Maximum :36.000000
 
 从而可知：MAX Z=36,此时X(1)=6,X(2)=4.
 
 实验成功。
 
  
  wo 的程序有bug，约束条件右端不能出现负值，否则得不到结果。
 试验证该例：
 min w=2x1+7x2
 s.t. -x1+x2<=14
 5x1+2x2<=50
 -x1-2x2<=18


第二个 第一部分:
#include  <iostream.h>   
#include  <conio.h>   
#include  <math.h>   

typedef  int  BOOL;   
#define  TRUE  1   
#define  FALSE  0   
typedef  double  REAL;   
#define  ZERO  1e-10   

//矩阵求逆   
BOOL  Inv(  REAL  **  a,  int  n  );   
BOOL  Inv(REAL  *  a,int  n);   

//矩阵相乘   
void  Damul(REAL  *  a,REAL  *  b,size_t  m,size_t  n,size_t  k,REAL  *  c);   

//线形规划--修正的单纯形法,返回真表示计算成功，返回假表示计算失败   
BOOL  Line_Optimize(REAL  *  A,    REAL  *  B,  REAL  *  C,  int  m,  int  n,   
                      REAL  *  Result,  REAL  *  X,  int  *  Is);   
//A-----------等式约束的系数矩阵   
//B-----------等式约束右端常数   
//C-----------所求最小值表达式的各项系数   
//m-----------系数矩阵行数   
//n-----------系数矩阵列   
//Result------返回最小值   
//X-----------返回计算结果   
//Is----------作为基底的X索引,计算结束后返回各X值所在索引   

template  <class  T>   
inline  void  ExChange(  T&  a,  T&  b  )   
{   
          T  temp=a;   
          a  =  b;   
          b  =  temp;   
}   


BOOL  Inv(  REAL  **  a,  int  n  )   
{   
          REAL  d;   
          int  i,j,k;   
          int  success  =  FALSE;   
          int  *  is=new  int  [n];   
          int  *  js=new  int  [n];   

          for  (k=0;k<n;k++){   
                      d=0.0;   
                      for(i=k;i<n;i++){   
                                  for(j=k;j<n;j++){   
                                              if  (fabs(a[i][j])>d){   
                                                          d=fabs(a[i][j]);   
                                                          is[k]=i;   
                                                          js[k]=j;   
                                              }   
                                  }   
                      }   

                      if(  d<ZERO  )  goto  Clear;   

                      for(  j=0;  j<n;  j++  )ExChange(  a[k][j],  a[is[k]][j]  );   

                      for(  i=0;  i<n;  i++  )ExChange(  a[i][k],  a[i][js[k]]  );   

                      a[k][k]=1/a[k][k];   

                      for(  j=0;  j<n;  j++  ){   
                                  if(  j!=k  )a[k][j]*=a[k][k];   
                      }   

                      for(  i=0;  i<n;  i++){   
                                  if  (  i!=k  ){   
                                              for(  j=0;  j<n;  j++  )   
                                                          if(  j!=k  )a[i][j]-=a[i][k]*a[k][j];   
                                  }   
                      }   

                      for(  i=0;  i<n;  i++  ){   
                                  if  (  i!=k  ){   
                                              a[i][k]*=((-1.0)*a[k][k]);   
                                  }   
                      }   

          }  //end  for   

          for(  k=n-1;  k>=0;  k--  ){   
                      for(  j=0;  j<n;  j++  )ExChange(  a[k][j],  a[js[k]][j]  );   

                      for(  i=0;  i<n;  i++  )ExChange(  a[i][k],  a[i][is[k]]  );   
          }   
          success  =  TRUE;   
Clear:   
          delete  []  is;   
          delete  []  js;   
          return  success;   
}   


BOOL  Inv(REAL  *  a,int  n)   
{   
          REAL  **kma  =  new  REAL*[n];   
          for(int  i=0;i<n;i++){   
                      kma[i]=a+i*n;   
          }   
          BOOL  ret=Inv(  kma,n);   
          delete  []  kma;   
          return  ret;   
}   

void  Damul(REAL  *  a,REAL  *  b,size_t  m,size_t  n,size_t  k,REAL  *  c)   
{   
          int  i,j,l,u;   
          for  (i=0;  i<=m-1;  i++){   
                      for  (j=0;  j<=k-1;  j++){   
                                  u=i*k+j;   
                                  c[u]=0.0;   
                                  for  (l=0;  l<=n-1;  l++){   
                                              c[u]  +=  a[i*n+l]*b[l*k+j];   
                                  }   
                      }   
          }   
          return;   
}   



BOOL  Line_Optimize(REAL  *  A,    REAL  *  B,  REAL  *  C,  int  m,  int  n,   
                      REAL  *  Result,  REAL  *  X,  int  *  Is)   
{   
          REAL  r;   
          int  i,j,k;   
          int  Success  =  FALSE;   
          REAL*  b  =  new  REAL  [m*m];   
          REAL*  MatTmp  =  new  REAL  [m*m];   
          REAL*  Mat1  =  new  REAL  [m];   
          REAL*  Mat2  =  new  REAL  [m];   
          REAL*  E  =  new  REAL  [m*m];   

          for  (i=0;  i<m;  i++){   
                      for  (j=0;  j<m;  j++){   
                                  b[i*m+j]  =  A[i*n+Is[j]];   
                      }   
          }   

          if  (!Inv(b,m)){   
                      goto  Release;   
          }   

          Damul(b,B,m,m,1,X);