Least Cost Entry Method in Transportation Problem

 //Least Cost Entry Method in Transportation Problem
#include<stdio.h>
main()
{
int res,des,*s,*d,**cell,**cost,i,j,p,q,t1,t2,min,sumreq=0,sumdes=0,count=0,total=0;
printf("Enter number of resources: ");
scanf("%d",&res);
printf("Enter the number of destinations: ");
scanf("%d",&des);

//memory allocation
s=(int *)malloc(res*sizeof(int));
d=(int *)malloc(des*sizeof(int));
cell=(int **)malloc(res*sizeof(int *));
for(i=0;i<res;i++)
cell[i]=(int *)malloc(des*sizeof(int));
cost=(int **)malloc(res*sizeof(int *));
for(i=0;i<res;i++)
cost[i]=(int *)malloc(des*sizeof(int));

for(i=0;i<res;i++)
for(j=0;j<des;j++)
cell[i][j]=-1;
//memory allocated

//data entering
for(i=0;i<res;i++)
{
printf("Enter the %dth resource availability: ",i+1);
scanf("%d",&s[i]);
sumreq+=s[i];
}

for(i=0;i<des;i++)
{
printf("Enter the %dth destination requirement: ",i+1);
scanf("%d",&d[i]);
sumdes+=d[i];
}

for(i=0;i<res;i++)
for(j=0;j<des;j++)
{
printf("Enter the cost %d %d :",i,j );
scanf("%d",&cost[i][j]);
}
//data entry complete

//lcem method starts
if(sumreq==sumdes)
{
  i=j=0;
  while(count<res+des-1)
  {
  min=10000;            
  for(p=0;p<res;p++)
  {
    if(s[p]==0)
    continue;
    for(q=0;q<des;q++)
    {
       if(d[q]==0)
       continue;
         if(min>cost[p][q])
         {
           min=cost[p][q];
           i=p;
           j=q;                
         }
         else if(min==cost[p][q]) //handling Same cost
         {
          t1=s[i]<d[j]?s[i]:d[j];
          t2=s[p]<d[q]?s[p]:d[q];
                 
          if(t2>t1)
          {
            min=cost[p][q];
            i=p;
            j=q;      
          }
         }    
    }              
  }
   if(s[i]<d[j])
   {
    if(s[i]!=-1)
    {
      cell[i][j]=s[i];
      d[j]=d[j]-s[i];
      s[i]=s[i]-s[i];
    }
    else //Degenrate Basic Variable
    {
      cell[i][j]=0;
      s[i]=0;
    }
   }
   else if(s[i]==d[j]) //Degenracy Problem Exit
   {
     cell[i][j]=s[i];
     d[j]=d[j]-s[i];
     s[i]=-1;   //Handling Degenrate Problem
   }
   else
   {
    cell[i][j]=d[j];
    s[i]=s[i]-d[j];
    d[j]=d[j]-d[j];
   }
    count++;
   }
//method completed

//output
for(i=0;i<res;i++)
for(j=0;j<des;j++)
{
  if(cell[i][j]!=-1)
  {
  printf("x[%d][%d]=%d ",i,j,cell[i][j]);
  total+=cell[i][j]*cost[i][j];
  }
}
printf("\nTotal transportation cost is %d",total);

}
else
printf("Not a balanced problem");
getch();
}

Posted in: LPP

Tweet