Big-M Method.cpp

#include<iostream>

#define M 1000
#define MAX 100
using namespace std;

long double A[MAX][MAX];

void print1(int m,int n,int p)
{
  int i,j;
  for(i=0;i<=m+1;i++)
    {
      for(j=1;j<=n+p+2;j++)
	{
	  cout<<"  "<<A[i][j];
	}
      cout<<endl;
    }
}

void simpfunc(int m,int n,int p)
{
  int j,i;
  for(j = 1; j<=n+p+1; j++)
    {
      for(i =1; i<=m; i++)
	{
	  A[m+1][j] = A[m+1][j] - M*A[i][j];
	}
    }
}

void input(int m,int n,int p)
{
  int i,j,count=1,t=1;
  char r;
  double x;
  cout<<"\nMaximize (Y/N)  :  ";
  cin>>r;
  if((r == 'Y')|| (r == 'y'))
    {
      t=-1;
    }
  for (i=1;i<=m;i++) 
    {
      cout<<"\nCONSTRAINT "<<i<<"  :  \n";
      cout<<"\nWhether type \">=\" (Y/N)   :  ";
      cin>>r;
      for (j = 1; j<=n; j++) {
	cout<<"Coefficient of x"<<j<<"  :  "; 
	cin>>x;
	A[i][j] = x;
      }
      if(r=='y'||r=='Y')
	{
	  for(j = 1; j<=p; j++)
	    {
	      A[i][n+j]=0;
	    }
	  A[i][n+count]=-1;
	  count++;
	}
      else
	{
	  for(j = 1; j<=p; j++)
	    {
	      A[i][j+n]=0;
	    }
	}
      cout<<"Constant  :  "; 
      cin>>A[i][n+p+1];
    }
  
  cout<<"\nInput for the function  :  \n";
  for (j=1;j<=n;j++) 
    {
      cout<<"Coefficient of x"<<j<<"  :  "; 
      cin>>x;
      A[m+1][j] = x*t;
    }
  for(j = 1; j<=p; j++)
    {
      A[i][j+n]=0;
    }
  cout<<"Value of d  :  "; 
  cin>>A[m+1][n+1];
  print1(m,n,p);
  simpfunc(m,n,p);
}
int pivcol(int m,int n,int p)
{
  int i,pos=1;
  double min=A[m+1][1];
  for(i=1;i<=n+p;i++)
    {
      if(min>A[m+1][i])
	{
	  min = A[m+1][i];
	  pos = i;
	}
    }
  return pos;
}
int pivrow(int m,int n,int p,int pos)
{
  int i,piv = 1;
  double min = (A[1][n+p+1]/A[1][pos]);
  for(i=1;i<=m;i++)
    {
      if(min>(A[i][n+p+1]/A[i][pos]))
	{
	  if(A[i][pos]>0)
	    {
	      piv = i;
	    }
	}
    }
  return piv;
}
int optimise(int m,int n,int p)
{
  print1(m,n,p);
  int i,j,pivr,pivc;
  pivc = pivcol(m,n,p);
  pivr = pivrow(m,n,p,pivc);
  for(i=1;i<=m+1;i++)
    {
      for(j=1;j<=n+p+1;j++)
	{
	  if((i!=pivr)&&(j!=pivc))
	    {
	      A[i][j] = (((A[i][j]*A[pivr][pivc])-(A[i][pivc]*A[pivr][j]))/A[pivr][pivc]);
	    }
	}
    }
  
  for(i=1;i<=m+1;i++)
    {
      if(pivr!=i)
	{
	  A[i][pivc] = -A[i][pivc]/A[pivr][pivc];
	}
    }
  for(j=1;j<=n+p+1;j++)
    {
      if(pivc!=j)
	{
	  A[pivr][j] = A[pivr][j]/A[pivr][pivc];
	}
    }  
  
  A[pivr][pivc] = 1/A[pivr][pivc];
  double temp = A[pivr][n+p+2];
  A[pivr][n+p+2] = A[0][pivc];
  A[0][pivc] = temp;
}

void result(int m,int n,int p)
{
  cout<<"\nThe Basic Variables  :  \n";
  for(int i=1;i<=m;i++)
    {
      cout<<"\nx"<<A[i][n+p+2]<<"  =  "<<A[i][n+p+1];
    }
  cout<<"\n\nMax Value  :  "<<A[m+1][n+p+1]<<endl<<endl;
}

void altsimplex(int m,int n,int p)
{
  int i,j,z=1;
  for(j = 1; j<=n+p ; j++)
    {
      if(A[m+1][j]==0)
	{
	  z=0;
	}
    }
  if(z==0)
    {
      optimise(m,n,p);
      print1(m,n,p);
      cout<<"\n\nAlternate Solution   : \n";
      result(m,n,p);
    }
  
}

int simplex(int m,int n,int p)
{
  int j,x,z=0;
  for(j=1;j<=n+p;j++)
    {
      if(A[m+1][j]<=0)
	{
	  z=1;
	}
    }
  while(z==1)
    {
      optimise(m,n,p);
      z=0;
      for(j=1;j<=n+p;j++)
	{
	  if(A[m+1][j]<0)
	    {
	      z=1;
	    }
	}
    }
  print1(m,n,p);
  result(m,n,p);
  altsimplex(m,n,p);
  return 0;
}

int main()
{
  int i,j,n,m,p;
  cout<<"\nEnter the no. of variables of the function  :  ";
  cin>>n;
  cout<<"\nEnter the no. of constraints  :  ";
  cin>>m;
  cout<<"\nEnter the no. of >= sign  :  ";
  cin>>p;
  input(m,n,p);
  print1(m,n,p);
  for(i=1;i<=n+p;i++)
    {
      A[0][i]=i;
    }
  for(j=1;j<=m;j++)
    {
      A[j][n+p+2]=i++;
    }
  print1(m,n,p);
  simplex(m,n,p);
  return 0;
}