单纯形法(指导书改进).cpp

这是一种改进的单纯型法

#include <iostream.h>
#include<stdio.h>
#include<math.h>
#define M 20
#define N 20
float matrix[M][N],x[M],c[N],b[N],Zm; 
          //单纯形表系数数组，解的数组，目标函数数组，常数项数组，目标函数值
int a[N],rg[N]; //记录基变量的数组与人工变量的数组
int m,n,s,type; //原问题变量数,约束方程数,LP问题的类型,用0表示最小化,1表示最大化
int indexe,indexl,indexg;  //记录剩余变量,松弛变量与人工变量的个数

void Jckxj()  //构造基本可行解
{
	int i;
    for(i=0;i<=s;i++) x[i]=0;
	for(i=0;i<n;i++) x[a[i]]=b[i];
}

int RjMin()  //检验数状态判别
{
  int i,j,temp=0;
  float sum,min;
  for(i=0;i<=s;i++)
  {   sum=0.0;
	  for(j=0;j<n;j++)
		  {sum+=matrix[j][i]*c[a[j]];}
       matrix[n][i]=c[i]-sum;
  }
  
  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,j;
  for(i=0;i<n;i++)
	  for(j=1;j<=indexg;j++)
       if(a[i]==rg[j])
       {
	     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<b[i]/matrix[i][in])
	      maxl=b[i]/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&&(b[i]/matrix[i][in]>=0)
		   &&min>b[i]/matrix[i][in])
       {
	     min=b[i]/matrix[i][in];
	     *temp=i;
       }
  return *temp;
};

void MtoBe(int temp,int in)  //基变换
{
  int i,j;float cs;
  Zm=0;
  for(i=0;i<=s;i++)  //对主元行(出基变量行)进行处理
  {
	  if(i!=in)
	      matrix[temp][i]=matrix[temp][i]/matrix[temp][in];
  }
  b[temp]=b[temp]/matrix[temp][in];
  matrix[temp][in]=1;
  for(i=0;i<n;i++)
  {
    cs=matrix[i][in];  
    if(i!=temp)    //对非主元行进行系数变换
	{
		for(j=0;j<=s;j++)
	     matrix[i][j]=matrix[i][j]-matrix[temp][j]*cs;
	    b[i]=b[i]-b[temp]*cs;
	}
  }
}

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

void Print()  //输出单纯形表函数
{
   int i,j,temp=0;
   for(i=0;i<n;i++)
   {      
      printf("X%d",a[i]);//基变量标识输出
	 for(j=0;j<=s;j++)  
	   printf("%8.2f",matrix[i][j]);
	 printf("%8.2f\n",b[i]);
   }
   printf("Rj");
    for(j=0;j<=s;j++)    //输出检验数(在数组的第n行中)
       printf("%8.2f",matrix[n][j]);
    printf("\n");
}

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

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

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

void Sstart(float b[],int code[]) //根据约束类型,增加剩余变量、松弛变量与人工变量的信息
{
   int i,j;
   s=m-1; 
   indexe=indexl=indexg=0;
   for(i=0;i<n;i++)  
   {
     if(code[i]==2)  //处理剩余变量
	  {
	    indexg++;indexe++;s=s+2;rg[indexg]=s; //记录人工变量所处的列号
        for(j=0;j<n;j++)  
			if(i!=j) { matrix[j][s-1]=0; matrix[j][s]=0;}
			else { matrix[j][s-1]=-1; matrix[j][s]=1;}
	  }
	   

	 if(code[i]==0) //处理松弛变量
	 {
		 indexl++;s++; 
	     for(j=0;j<n;j++) 
		 {
			 if(i!=j)matrix[j][s]=0;
	         else matrix[j][s]=1; 
		 }
	 }

     if(code[i]==1) //处理人工变量
	 {
		 indexg++;s++;rg[indexg]=s; 
	     for(j=0;j<n;j++)    
	     if(i!=j)matrix[j][s]=0;
	      else matrix[j][s]=1;
	 }
	 a[i]=s;
	}
    for(i=m;i<=s;i++) c[i]=0; //对目标函数系数进行处理
    for(i=1;i<=indexg;i++)  c[rg[i]]=100;  //再对人工变量的系数进行处理
    for(i=0;i<=s;i++) matrix[n][i]=0;  //检验数行进行初始化
    InitPrint(); //输出初始单纯形表(头)
}

void Simplix()  //单纯形法
{
  int in,out,temp=0;
  while(1)
  {
    Jckxj();  //处理基本可行解
    in=RjMin(); //计算检验数及确定换入基
    Print();  //打印单纯形表
    Result();  //输出解与目标函数值
	if(matrix[n][in]>=0)   
	{
	       if(indexg!=0)JustArtificial(); //判断人工变量非零
	        PrintResult();  //打印最终结果
	        return;
	}
	printf("———————————————————————————————————\n");
    if(Check(in))  //判断无界解情况
	{
	  printf("No Delimition\n");
	  return;
	}
    out=SearchOut(&temp,in);  //求换出基
    MtoBe(temp,in);  //初等变换
    a[out]=in;  //调整基变量数组a[]的值
   } 
} 

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