//Vogel approximation method (VAM) in transportation problem#include<stdio.h>
main()
{
int res,des,*s,*d,**cell,**cost,i,j,r1,c1,r2,c2,p,q,a1,a2,max1,max2,min1,min2,sumreq=0,count=0,sumdes=0,total=0,*rowpanl,*colpanl;
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));
rowpanl=(int *)malloc(res*sizeof(int));
d=(int *)malloc(des*sizeof(int));
colpanl=(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
//vam method starts
if(sumreq==sumdes)
{
while(count<res+des-1&&sumdes!=0)
{
//Finding row panalties
for(i=0;i<res;i++)
{
if(s[i]==0)
{
rowpanl[i]=-2;
continue;
}
min1=min2=10000;
for(j=0;j<des;j++)
{
if(d[j]==0)
continue;
if(min1>=cost[i][j])
{
min1=cost[i][j];
p=j;
}
}
for(j=0;j<des;j++)
{
if(d[j]==0||p==j)
continue;
if(min2>=cost[i][j])
{
min2=cost[i][j];
}
}
if(min2!=10000)
rowpanl[i]=min2-min1;
else
rowpanl[i]=min1;
}
//row panalties founded\
//Finding column panalties
for(j=0;j<des;j++)
{
if(d[j]==0)
{
colpanl[j]=-2;
continue;
}
min1=min2=10000;
for(i=0;i<res;i++)
{
if(s[i]==0)
continue;
if(min1>=cost[i][j])
{
min1=cost[i][j];
p=i;
}
}
for(i=0;i<res;i++)
{
if(s[i]==0||p==i)
continue;
if(min2>=cost[i][j])
{
min2=cost[i][j];
}
}
if(min2!=10000)
colpanl[j]=min2-min1;
else
colpanl[j]=min1;
}
//column panalties founded
//maximum Row Panality
max1=p=-1;
for(i=0;i<res;i++)
{
if(max1<rowpanl[i])
{
max1=rowpanl[i];
p=i;
}
else if(max1==rowpanl[i])//if tie in maximum panalty
{
min1=min2=10000;
for(j=0;j<des;j++)
{
if(d[j]==0)
continue;
if(min1>cost[i][j])
{
min1=cost[i][j];
r1=i;
c1=j;
}
if(min2>cost[p][j])
{
min2=cost[p][j];
r2=p;
c2=j;
}
}
//Comparing minimum cost
if(min2>min1)
{
max1=rowpanl[i];
p=i;
}
else if(min1==min2)// Tie in minimum costs
{
a1=s[r1]<d[c1]?s[r1]:d[c1];
a2=s[r2]<d[c2]?s[r2]:d[c2];
if(a2<a1) // choosing maximum allocation
{
max1=rowpanl[i];
p=i;
}
else if(a2==a1)//tie in allocation
{
if(r1+c1<r2+c2) //breaking tie
{
max1=rowpanl[i];
p=i;
}
}
}
}
}
//max row panality founded
//maximum Column Panality
max2=q=-1;
for(i=0;i<des;i++)
{
if(max2<colpanl[i])
{
max2=colpanl[i];
q=i;
}
else if(max2==colpanl[i])//if tie in maximum panalty
{
min1=min2=10000;
for(j=0;j<res;j++)
{
if(s[j]==0)
continue;
if(min1>cost[j][i])
{
min1=cost[j][i];
r1=j;
c1=i;
}
if(min2>cost[j][q])
{
min2=cost[j][q];
r2=j;
c2=q;
}
}
//Comparing minimum cost
if(min2>min1)
{
max2=colpanl[i];
q=i;
}
else if(min1==min2)// Tie in minimum costs
{
a1=s[r1]<d[c1]?s[r1]:d[c1];
a2=s[r2]<d[c2]?s[r2]:d[c2];
if(a2<a1) // choosing maximum allocation
{
max2=colpanl[i];
q=i;
}
else if(a2==a1)//tie in allocation
{
if(r1+c1<r2+c2) //breaking tie
{
max2=colpanl[i];
q=i;
}
}
}
}
}
//max column panality founded
//comparing row and column panalties to find maximum panalty
if(max1>max2)
{
min1=10000;
q=0;
for(j=0;j<des;j++)
{
if(d[j]==0)
continue;
if(min1>cost[p][j])
{
min1=cost[p][j];
q=j;
}
}
}
else if(max1==max2)
{
min1=min2=10000;
r1=p;
c2=q;
for(i=0;i<des;i++)
{
if(d[i]==0)
continue;
if(min1>cost[p][j])
{
min1=cost[p][j];
c1=j;
}
}
for(j=0;j<res;j++)
{
if(s[j]==0)
continue;
if(min2>cost[j][q])
{
min2=cost[j][q];
r2=j;
}
}
if(min1<min2)
{
p=r1;
q=c1;
}
else if(min2<min1)
{
p=r2;
q=c2;
}
else //tie condition
{
a1=s[r1]<d[c1]?s[r1]:d[c1];
a2=s[r2]<d[c2]?s[r2]:d[c2];
if(a1>a2) // choosing maximum allocation
{
p=r1;
q=c1;
}
else if(a2>a1)
{
p=r2;
q=c2;
}
else if(a2==a1)//tie in allocation
{
if(r1+c1<r2+c2) //breaking tie
{
p=r1;
q=c1;
}
else
{
p=r2;
q=c2;
}
}
}
}
else // when max1<max2
{
min1=10000;
p=0;
for(j=0;j<res;j++)
{
if(s[j]==0)
continue;
if(min1>cost[j][q])
{
min1=cost[j][q];
p=j;
}
}
}
// comparing Complete
if(s[p]<d[q])
{
cell[p][q]=s[p];
d[q]=d[q]-s[p];
sumdes=sumdes-s[p];
s[p]=0;
}
else
{
cell[p][q]=d[q];
s[p]=s[p]-d[q];
sumdes=sumdes-d[q];
d[q]=0;
}
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();
}
