To implement Simplex method in LPP

//To implement Simplex method in LPP

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int main()
{
int m,n,i,j,k;
float **a,**B,*cj,*b,*zj,**t,*cb,*x,z=0,*sol;
int *basic,check=0;
void inverse(float **t,float **B,float *b,float *x,float **a,int *basic,int m,int n);
void findzj(float *zj,float **t,float *cb,float *cj,int m ,int n);
void print(float **t,float *zj,float *cj,float *cb, float *b,int *basic,int m,int n);
int checkoptmlty(float *zj,int *basic,float **t,int m,int n);
void gettingoptmlty(float **t,float *zj,float *b,float *cb,float *cj,int *basic,int m,int n);
int alternate(float **t,float *zj,float *b,float *cb,float *cj,int *basic,int m,int n);
printf("\nEnter the number of variable and number of constraints:");
scanf("%d%d",&n,&m);

/* allocating memory*/
  a=(float**)malloc(m*sizeof(int *));
  for(i=0;i<m;i++)
  a[i]=(float *)malloc(n*sizeof(float));

  t=(float**)malloc(m*sizeof(int *));
  for(i=0;i<m;i++)
  t[i]=(float *)malloc(n*sizeof(float));

  cj=(float*)malloc(n*sizeof(float));
  zj=(float*)malloc(n*sizeof(float));

  B=(float**)malloc(m*sizeof(int *));
  for(i=0;i<m;i++)
  B[i]=(float *)malloc(m*sizeof(float));

  b=(float*)malloc(m*sizeof(float));
  x=(float*)malloc(m*sizeof(float));
  cb=(float*)malloc(m*sizeof(float));
  basic=(int*)malloc(m*sizeof(int));
  sol=(float*)malloc(n*sizeof(float));
/*memory allocated*/

  printf("\nEnter the coefficients of variables in objective function\n");
  for(i=0;i<n;i++)
   scanf("%f",&cj[i]);

  for(i=0;i<m;i++)
  {
   printf("\nEnter the coefficients of variables in constraints\n");
   for(j=0;j<n;j++)
   scanf("%f",&a[i][j]);
   printf("\nEnter the RHS variables \n");
   scanf("%f",&x[i]);
  }


  printf("\nPlease enter %d the basic variables: you can enter only from ",m);
  for(i=0;i<n;i++)
   printf(" %d ",i+1);
   printf("\n");
  for(i=0;i<m;i++)
  {
  scanf("%d",&basic[i]);
  basic[i]=basic[i]-1;
  }

  for(i=0;i<m;i++)
  cb[i]=cj[basic[i]];

  for(i=0;i<n;i++)
   sol[i]=0;



inverse(t,B,b,x,a,basic,m,n);
findzj(zj,t,cb,cj,m,n);
print(t,zj,cj,cb,b,basic,m,n);

while(check==0)
{
check=checkoptmlty(zj,basic,t,m,n);    
if(check==0)
{
            printf("\nOptimility is not achieved.\n");  
            gettingoptmlty(t,zj,b,cb,cj,basic,m,n);
            inverse(t,B,b,x,a,basic,m,n);
            findzj(zj,t,cb,cj,m,n);
            print(t,zj,cj,cb,b,basic,m,n);
}
}
printf("\noptimal solution acheived is at :");
for(i=0;i<m;i++)
sol[basic[i]]=b[i];
for(i=0;i<n;i++)
{
  printf(" %.2f",sol[i]);
  z+=cj[i]*sol[i];
}
printf("\n and solution is :%f",z);
//checking alternate solution
if(alternate(t,zj,b,cb,cj,basic,m,n)==1)
{
            inverse(t,B,b,x,a,basic,m,n);
            findzj(zj,t,cb,cj,m,n);
            print(t,zj,cj,cb,b,basic,m,n);
            z=0;
            for(i=0;i<n;i++)
            sol[i]=0;
            printf("\noptimal solution acheived is at :");
            for(i=0;i<m;i++)
               sol[basic[i]]=b[i];
            for(i=0;i<n;i++)
            {
               printf(" %.2f",sol[i]);
               z+=cj[i]*sol[i];
            }
printf("\n and solution is :%f",z);
}
/* freeing allocated memory*/
  free(a);
  free(b);
  free(B);
  free(basic);
  free(cj);
  free(zj);
  free(t);
 
  getch();
}

void inverse(float **t,float **B,float *b,float *x,float **a,int *basic,int m,int n)
{
float *temp,temp1;
int i,j,k;
temp=(float*)malloc(m*sizeof(float));


  for(i=0;i<m;i++)
  {
   for(k=0;k<m;k++)
    {
      B[i][k]=a[i][basic[k]];
    }
   }
 
   for(i=0;i<m;i++)
  {
   b[i]=x[i];
  }
 
for(i=0;i<m;i++)
   for(j=0;j<n;j++)
    t[i][j]=a[i][j];
   
for(i=0;i<m;i++)
{
     for(k=0;k<m;k++)
     {
       if(k!=i)
       {
for(j=0;j<m;j++)
 {
   if(B[i][j]==B[k][j])
     continue;
   else
     break;
 }
if(j==m)
{
  printf("\nDuplicate row\n");
  getch();
  exit(0);
}
       }
     }

   if(B[i][i]==0)
   {
     for(k=i+1;k<m;k++)
     {
       if(B[k][i]!=0)
       {
for(j=0;j<m;j++)
{
temp1=B[i][j];
B[i][j]=B[k][j];
B[k][j]=temp1;
}
temp1=b[i];
b[i]=b[k];
b[k]=temp1;
for(j=0;j<n;j++)
{
temp1=t[i][j];
t[i][j]=t[k][j];
t[k][j]=temp1;
}
break;
      }
    }
     if(k==n)
     {
      printf("\nInvalid entry\n");
      getch();
      exit(0);
     }
   }

  temp1=B[i][i];
  b[i]=(float)b[i]/temp1;
  for(j=0;j<n;j++)
   {
    if(j<m)
    {
           B[i][j]=(float)B[i][j]/temp1;
    }
    t[i][j]=(float)t[i][j]/temp1;
   }

   for(j=0;j<m;j++)
   {
     if(j!=i)
     {
      temp[j]=B[j][i];
     }
   }

    for(k=0;k<m;k++)
    {
       for(j=0;j<n;j++)
        {
         if(k!=i)
         {
           if(j<m)
           { B[k][j]=B[k][j]-(temp[k]*B[i][j]); }
         t[k][j]=t[k][j]-(temp[k]*t[i][j]);
         }
        }
        if(k!=i)
        b[k]=b[k]-(temp[k]*b[i]);
     }
}
free(temp);
}

void findzj(float *zj,float **t,float *cb,float *cj,int m ,int n)
{
 int i,j ;
 for(i=0;i<n;i++)
 {
    zj[i]=0;
    for(j=0;j<m;j++)  
       zj[i]+=cb[j]*t[j][i];
    zj[i]=zj[i]-cj[i];
 }
}

void print(float **t,float *zj,float *cj,float *cb, float *b,int *basic,int m,int n)
{
  int i,j;
  printf("\n \t\t object func");
  for(i=0;i<n;i++)
    printf("\t%.2f",cj[i]);
  printf("\n");

  printf("\n \tCb\tbasis\txb");
  for(i=0;i<n;i++)
    printf("\tx%d",i+1);
  printf("\n");
 
  for(i=0;i<m;i++)
  {
  printf("\t%.2f\tx%d",cb[i],basic[i]+1);
  printf("\t%.2f",b[i]);
   for(j=0;j<n;j++)
   printf("\t%.2f",t[i][j]);
  printf("\n");
  }
  printf("\t\tzj-cj\t");
  for(i=0;i<n;i++)
  printf("\t%.2f",zj[i]);
}

int checkoptmlty(float *zj,int *basic,float **t,int m,int n)
{
   int i,j,check;
   // checking unboundedness
 for(i=0;i<n;i++)
 {
   check=0;
   for(j=0;j<m;j++)
   {
    if(i==basic[j])
    {
       check=1;
       break;
    }                  
   }
   if(check==1)
   continue;
   for(j=0;j<m;j++)
   {
    if(t[j][i]>0)
    break;              
   }
   if(j==m && zj[i]!=0)
   {
   printf("\n Feasible region is unbounded");
   if(zj[i]<0)
   {
      printf("\n solution is unbounded");      
   }    
     getch();
     exit(0);
   }            
 }
    for(i=0;i<n;i++)
   {
          if(zj[i]<0)
           return 0;        
   }
 //checking complete
   return 1;
}

void gettingoptmlty(float **t,float *zj,float *b,float *cb,float *cj,int *basic,int m,int n)
{
 float temp,*p,min,check=0;
 int i,j,loc,ploc=0;

 p=(float*)malloc(m*sizeof(float));
 

  min=0;
  loc=0;
  for(i=0;i<n;i++)
  {
       if(zj[i]==0)
        continue;
       else if(zj[i]<min)
       {
           min=zj[i];
           loc=i;
       }            
  }
  for(i=0;i<m;i++)
  {
      if(t[i][loc]<=0)
      p[i]=0;
      else
      p[i]=b[i]/t[i][loc];    
  }
  min=1000;
  for(i=0;i<m;i++)
  {
      if(p[i]==0)
      continue;
      else
      {
          min=p[i];
          ploc=i;
          check=1;
          break;
      }
  }
  if(check==0)
  {
    printf("\n Feasible region is unbounded");  
     getch();
     exit(0);      
  }
  for(i=0;i<m;i++)
  {  
      if(p[i]<min && p[i]!=0)
      {
      min=p[i];
      ploc=i;
      }        
  }
 
  printf("\n %.1f is selected as pivot element\n",t[ploc][loc]);
  basic[ploc]=loc;
  cb[ploc]=cj[loc];
}

int alternate(float **t,float *zj,float *b,float *cb,float *cj,int *basic,int m,int n)
{
     float temp,*p,min;
 int i,j,loc,ploc=0,check;

 p=(float*)malloc(m*sizeof(float));
 
 // checking alternate solution
 for(i=0;i<n;i++)
 {
   check=0;
   for(j=0;j<m;j++)
   {
    if(i==basic[j])
    {
       check=1;
       break;
    }                  
   }
   if(check==1)
   continue;
 
   if(zj[i]==0)
   {
     for(j=0;j<m;j++)
     {
       if(t[j][i]>0)
       break;              
     }
     if(j!=m)
     {
             printf("\nalternate solution exits;");
      loc=i;  
   
      for(i=0;i<m;i++)
       {
         if(t[i][loc]<=0)
         p[i]=0;
         else
         p[i]=b[i]/t[i][loc];          
       }
 
      min=0;
      for(i=0;i<m;i++)
      {
         if(p[i]==0)
         continue;
         else
         {
          min=p[i];
          ploc=i;
          break;
         }
      }  
      for(i=0;i<m;i++)
       {  
         if(p[i]<min && p[i]!=0)
         {
          min=p[i];
          ploc=i;
         }        
       }
       printf("\n %.1f is selected as pivot element\n",t[ploc][loc]);
       basic[ploc]=loc;
       cb[ploc]=cj[loc];  
       return 1;
     }
   }            

 }
 return 0;
}

Posted in: LPP

Tweet