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;
}

Read More

Tweet

Find the inverse of given matrix using malloc function

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int main()
{
float **a,*temp,temp1;
int i,j,k,n;
float **b;
printf("enter the order of matrix:");
scanf("%d",&n);

a=(float**)malloc(n*sizeof(float *));
for(i=0;i<n;i++)
a[i]=(float *)malloc(n*sizeof(float));
b=(float**)malloc(n*sizeof(float *));
for(i=0;i<n;i++)
b[i]=(float *)malloc(n*sizeof(float));
temp=(float *)malloc(n*sizeof(float));
for(i=0;i<n;i++)
{
 for(j=0;j<n;j++)
 {
  if(j==i)
  b[i][i]=1;
  else
  b[i][j]=0;
 }
}

printf("\n Enter the matrix\n");
for(i=0;i<n;i++)
{
 printf("\nEnter the %dth row \n",i);
 for(j=0;j<n;j++)
 {
  scanf("%f",&a[i][j]);
 }
}

printf("\nEntered a matrix:\n");
for(i=0;i<n;i++)
{
 for(j=0;j<n;j++)
 {
  printf(" %.2f",a[i][j]);
 }
 printf("\n");
}

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

break;
       }
     }
     if(k==n)
     {
 printf("\nInvalid entry\n");
 getch();
 exit(0);
     }
}

temp1=a[i][i];
  for(j=0;j<n;j++)
   {
    a[i][j]=a[i][j]/temp1;
    b[i][j]=b[i][j]/temp1;
   }

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

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

}

printf("\n Inverse matrix:\n");
for(i=0;i<n;i++)
{
 for(j=0;j<n;j++)
 {
  printf("  %.2f",b[i][j]);
 }
 printf("\n");
}
printf("\n matrix A after calculation:\n");
for(i=0;i<n;i++)
{
 for(j=0;j<n;j++)
 {
  printf("  %.2f",a[i][j]);
 }
 printf("\n");
}

getch();
}

Read More

Tweet

Write a code to solve josephus problem in linked list.

//Write a code to solve josephus problem in linked list.
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
struct node
{
int data;
struct node *next;
};
main()
{
struct node *start=NULL;
int n;
void create(struct node **, int);
void josephus(struct node *);
printf("Enter the number of elements you want in your linked list :");
scanf("%d",&n);
create(&start,n);
josephus(start);
getch();  
}

void create(struct node **start,int n)
{
int i;
struct node *lst;
struct node *p;
lst=NULL;
for(i=1;i<=n;i++)
{
 p=(struct node *)malloc(sizeof(struct node));
 printf("Enter the %d element :",i);
 scanf("%d",&(p->data));
 if(*start==NULL)
    *start=p;
 else
   lst->next=p;
   lst=p;
   p->next=*start;
}
}


void josephus(struct node *start)
{
     struct node *temp,*p;
     int n,count;
     printf("\nwhich element you want to delete in josephus problem");
     scanf("%d",&n);
     while(start->next!=start)
     {
      count=1;
      p=start;
      while(count<=n-2)
      {
        p=p->next;
        count++;
      }
      temp=p->next;
      p->next=temp->next;
      free(temp);
      start=p->next;
      }
      printf("the last item in josephus problem is %d",start->data);
   
}

   

Read More

Tweet