单纯形法(指导书).cpp

这是一种改进的单纯型法

#include <iostream.h>
#include<stdio.h>
#include<math.h>
float matrix[100][100],x[100]; //单纯形表数组，解的数组
int a[100]; //记录基变量(1)与非基变量(0)状态的数组
int m,n,s,type; //原问题变量数,约束方程数,LP问题的类型,用0表示最小化,1表示最大化
int indexe,indexl,indexg;  //记录剩余变量,松弛变量与人工变量的个数

void Jckxj()  //构造基本可行解(此函数可简化改造)
{
  int i,j;
  for(i=0;i<n;i++)
     for(j=0;j<s;j++)
	 if(matrix[i][j]==1&&a[j]==1)
	  {
	   x[j]=matrix[i][s];
	   j=s;   //用此来结束内循环
	  }
  for(i=0;i<s;i++)
	   if(a[i]==0) x[i]=0;
}

int Rj()  //检验数状态判别
{
  int i;
  for(i=0;i<s;i++)
     if(fabs(matrix[n][i])>=0.000001)  //此处可以用!=0进行判别
       if(matrix[n][i]<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][i])
     {
       min=matrix[n][i];
       temp=i;
     }
   return temp;
}

void JustArtificial() //判断解中是否存在非零的人工变量
{
  int i;
  for(i=m+indexe+indexl;i<s;i++)
     if(fabs(x[i])>=0.000001)
       {
	     printf("No Answer\n");
	     return;
       }
}

int Check(int in)  //检查无界解情况(参数in对应入基列)
{
  int i;
  float maxl=-1;
  for(i=0;i<n;i++)
     if(fabs(matrix[i][in])>=0.000001&&maxl<matrix[i][s]/matrix[i][in])
	      maxl=matrix[i][s]/matrix[i][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[i][in])>=0.00001&&(matrix[i][s]/matrix[i][in]>=0)
		   &&min>matrix[i][s]/matrix[i][in])
       {
	     min=matrix[i][s]/matrix[i][in];
	     *temp=i;
       }
       for(i=0;i<s;i++)   //*temp,i为主元(此循环多余)
	    if(a[i]==1&&matrix[*temp][i]==1) return i;
	  return 0;
};

void Mto(int in,int temp)  //对主元行(出基变量行)进行处理
{
  int i;
  for(i=0;i<=s;i++)
    if(i!=in)  //此判断式可以省略
	 matrix[temp][i]=matrix[temp][i]/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[i][in]/matrix[temp][in];  
    if(i!=temp)  //对非主元行进行系数变换
     for(j=0;j<=s;j++)
	   matrix[i][j]=matrix[i][j]-matrix[temp][j]*c;
  }
}

void Achange(int in,int out)  //出基变量与入基变量状态调整
{
  int temp=a[in];
  a[in]=a[out];
  a[out]=temp;
  //可直接用 a[in]=1;a[out]=0;
}

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("X%d",k);
	   temp=k+1;
	   k=s;  //结束内循环
	 }
	 for(j=0;j<=s;j++)  //当j==s时,输出的是常数列
	   printf("%8.2f",matrix[i][j]);
	 printf("\n");
 }
    printf("Rj");
    for(j=0;j<=s;j++)    //输出检验数(在数组的第n行中)
       printf("%8.2f",matrix[n][j]);
    printf("\n");
}

void InitPrint()   //输出初始单纯形表(头)
{
  int i;
  printf(" X");
  for(i=0;i<s;i++)
      printf("    x[%d]",i);//(将原a数组改为x)
  printf("    b[]\n");
  //Print();  printf("\n");
}

void Result()  //输出当前解与目标函数值
{
  int i;
  printf(" (");
  for(i=0;i<s;i++)
     printf("%8.2f",x[i]);
  printf(")    ");
  if(type==1)
      printf("Zmax=%f\n\n",matrix[n][s]);
  else printf("Zmin=%f\n\n",matrix[n][s]);
}

void PrintResult()  //输出最终结果
{
  if(type==0)printf("The Minimal:%f\n",-matrix[n][s]);
  else printf("The Maximum:%f\n",matrix[n][s]);
}

void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])
{  //将剩余变量、松弛变量与人工变量的信息归并到单纯形数组中
  int i,j;
  for(i=0;i<n;i++)
  {
     for(j=m;j<m+indexe;j++)  //处理剩余变量
	   if(nget[i][j-m]!=-1)matrix[i][j]=0;
	   else matrix[i][j]=-1;
	 for(j=m+indexe;j<m+indexe+indexl;j++) //处理松弛变量
	   if(nlet[i][j-m-indexe]!=1)matrix[i][j]=0;
	   else matrix[i][j]=1;
	 for(j=m+indexe+indexl;j<s;j++)    //处理人工变量
	   if(net[i][j-m-indexe-indexl]!=1)matrix[i][j]=0;
	   else matrix[i][j]=1;
	 matrix[i][s]=b[i];
  }
  for(i=m;i<m+indexe+indexl;i++)  //对检验数进行处理，剩余变量是否合适？
     matrix[n][i]=0;
  for(i=m+indexe+indexl;i<s;i++)
     matrix[n][i]=100;
  matrix[n][s]=0;
}

void ProcessA()  //初始化基变量与非基变量状态数组
{
  int i;
  for(i=0;i<m+indexe;i++)
      a[i]=0;
  for(i=m+indexe;i<s;i++)  //初始时松弛变量与人工变量为基变量
      a[i]=1;
}

void Input(float b[],int code[])  //LP问题原始数据录入函数
{
  int i=0,j=0;
  printf("The equator Variable and Restrictor(变量与约束方程的个数)\n");
     cin>>m>>n;
  for(i=0;i<n;i++)  //输入各方程的常数项、约束类型(<=,=,>=)、与变量系数
  {
     printf("Input b[] and Restrictor code(输入方程常数项与约束类型) 0:<=1:=2:>=\n");
       cin>>b[i]>>code[i];
     printf("The XiShu方程各变量系数\n");
     for(j=0;j<m;j++)
	   cin>>matrix[i][j];
   }
  printf("The Type(问题的类型) 0:Min 1:Max\n");  //LP问题的类型(极大化或极小化)
  do{
     cin>>type;
     if(type!=0&&type!=1) printf("Error,ReInput\n");
     }while(type!=0&&type!=1);
  printf("The 输入目标函数Z的系数\n"); //输入目标函数系数
  for(i=0;i<m;i++)
     cin>>matrix[n][i];
  if(type==1)  //若极大化转化为极小化
    for(i=0;i<m;i++)
       matrix[n][i]=-matrix[n][i];
}

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[i][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++)
      if(i!=row)c[i][vol]=0;
}

void Sstart(float b[],int code[]) //根据约束类型,增加剩余变量、松弛变量与人工变量的信息
{
   int i;
   float nget[100][100],nlet[100][100],net[100][100]; //剩余变量数组、松弛变量数组与人工变量数组
   indexe=indexl=indexg=0;
   for(i=0;i<n;i++)
   {
      if(code[i]==0){nlet[i][indexl++]=1;Process(nlet,i,indexl-1);}
      if(code[i]==1){nlet[i][indexg++]=1;Process(nlet,i,indexg-1);}
      if(code[i]==2)
	  {
	    net[i][indexg++]=1;
	    nget[i][indexe++]=-1;
	    Process(net,i,indexg-1);Process(nget,i,indexe-1);
	  }
    }
    s=indexe+indexl+indexg+m;  //计算标准化后的变量个数
    Merge(nget,nlet,net,b);  //合并剩余变量、松弛变量与人工变量的信息
    ProcessA();  //初始化a[]
    InitPrint(); //输出初始单纯形表(头)
    Xartificial(); //消去人工变量
}

void Simplix()  //单纯形法
{
  int in,out,temp=0;
  while(1)
  {
    Jckxj();  //处理基本可行解
    Print();  //打印单纯形表
    Result();  //输出解与目标函数值
    if(!Rj()) in=Min();  //求换入基
    else{
	       if(indexg!=0)JustArtificial(); //判断人工变量非零
	        PrintResult();  //打印最终结果
	        return;
		}
    if(Check(in))  //判断无界解情况
	{
	  printf("No Delimition\n");
	  return;
	}
    out=SearchOut(&temp,in);  //求换出基
    Mto(in,temp);  //主元行处理
    Be(temp,in);   //初等变换 
    Achange(in,out);  //调整状态数组a[]的值
   } 
} 

void main()
{
  int code[100];  //约束方程类型标识数组
  float b[100];   //约束方程常数项数组
  Input(b,code);  //录入原始数据
  Sstart(b,code);  //化标准型
  Simplix();    //单纯形算法
}