• Loading
    • Program Code for Vogel's Approximation Method (VAM)

      Algorithm For Vogel's Approximation Method (VAM)



      step 1:- for each row of the transportation table identify the smallest and next-to-smallest costs. determine the difference between them for each row. now display them alongside the transportation table by enclosing them in parenthesis against the respective rows. similarly, compute the difference for each column.

      step 2:- identify the row or column with the largest difference among all the rows n columns. if a tie occurs, use any arbitrary tie-breaking choice. let the greatest difference correspond to the ith row and let c(ij) be the smallest cost in the ith row. allocate the maximum feasible amount x(ij)=min (ai,bi) in d (i,j)th cell and cross off either the ith row or the jth column in the usual manner.

      step 3:- recompute the column and row difference for the reduced transportation table and go 2 step 2 . repeat the procedure untill all the rim requirements are satisfied .


      remarks :-
      1:- a row or column "difference" indicates the minimum unit penalty incurred by failing to make an allocation to the smallest cost cell in that row or column.
      2:- it will b seen later that vam determines an initial basic feasible solution which is very close to the optimum solution, that is, the number of iteration required to reach the optimum solution is smaller in this case .
      Code:
      #include<stdio.h>
      #include<conio.h>
      void sort(int a[],int n)
      { int temp,j,k;
        for(j=0;j<n;j++)
        { for(k=j+1;k<n;k++)
          { if(a[j]>a[k])
            { temp=a[j];
      	a[j]=a[k];
      	a[k]=temp;
            }
          }
        }
      }
      void main()
      { int i,j,b,p,d,k,m,n,c[20][20],cf[20],rf[20],a[20],cp[20],rp[20];
        int sup[20],dem[20],max,min,s,t,sum=0;
        clrscr();
        printf("\nEnter the row & column:");
        scanf("%d%d",&m,&n);
        printf("\nEnter the cost:");
        for(i=0;i<m;i++)
        { for(j=0;j<n;j++)
           scanf("%d",&c[i][j]);
        }
        printf("\nEnter the demand:");
        for(i=0;i<n;i++)
         scanf("%d",&dem[i]);
        printf("\nEnter the supply:");
        for(i=0;i<m;i++)
         scanf("%d",&sup[i]);
        printf("\nMatrix:\n");
        for(i=0;i<m;i++)
        { for(j=0;j<n;j++)
           printf(" %d ",c[i][j]);
          printf("%d",sup[i]);
          printf("\n");
        }
        for(j=0;j<n;j++)
         printf("%d ",dem[j]);
        for(i=0;i<m;i++)
         rf[i]=0;
        for(i=0;i<n;i++)
         cf[i]=0;
        b=m,d=n;
        while(b>0&&d>0)
        { for(i=0;i<m;i++)
           rp[i]=-1;
          for(i=0;i<n;i++)
           cp[i]=-1;
          for(i=0;i<m;i++)
          { k=0;
            if(rf[i]!=1)
            { for(j=0;j<n;j++)
      	{ if(cf[j]!=1)
      	    a[k++]=c[i][j];
      	}
      	if(k==1)
      	 rp[i]=a[0];
      	else
      	{ sort(a,k);
      	  rp[i]=a[1]-a[0];
      	}
            }                     
          }
          for(i=0;i<n;i++)
          { k=0;
            if(cf[i]!=1)
            { for(j=0;j<m;j++)
      	{ if(rf[j]!=1)
      	   a[k++]=c[j][i];
      	}
              if(k==1)
      	 cp[i]=a[0];
      	else
      	{ sort(a,k);
      	  cp[i]=a[1]-a[0];
      	}
            }
          }
          for(i=0;i<m;i++)
           a[i]=rp[i];
          for(j=0;j<n;j++)
           a[i+j]=cp[j];
          max=a[0];
          p=0;
          for(i=1;i<m+n;i++)
          { if(max<a[i])
            {	max=a[i];
      	p=i;
            }
          }
          printf("\n\n     %d %d",max,p);
          min=1000;
          if(p>m-1)
          { p=p-m;
            if(cf[p]!=1)
            { for(i=0;i<m;i++)
      	{ if(rf[i]!=1)
      	  { if(min>c[i][p])
      	    { min=c[i][p];
      	      s=i;
      	      t=p;
      	    }
      	  }
      	}
            }
          }
          else
          { if(rf[p]!=1)
            { for(i=0;i<n;i++)
      	{ if(cf[i]!=1)
      	  { if(min>c[p][i])
      	    { min=c[p][i];
      	      s=p;
      	      t=i;
      	    }
      	  }
      	}
            }
          }
          printf("\n\n      %d %d %d",min,s,t);
          if(sup[s]<dem[t])
          { sum+=c[s][t]*sup[s];
            dem[t]-=sup[s];
            rf[s]=1;
            b--;
          }
          else
          if(sup[s]>dem[t])
          { sum+=c[s][t]*dem[t];
            sup[s]-=dem[t];
            cf[t]=1;
            d--;
          }
          else
          if(sup[s]==dem[t])
          { sum+=c[s][t]*dem[t];
            cf[t]=1;
            rf[s]=1;
            b--;
            d--;
          }
        }
        printf("\n\n     %d ",sum);
        getch();
      }



    Disclaimer: Users of techforum4u.com are responsible for ensuring that any material they post (article, blog posts, images or other mulitimedia content) does not violate or infringe upon the copyright, patent, trademark, or any personal or proprietary rights of any third party, and is posted with the permission of the owner of such rights.Anyone who violates these rules may have their access privileges removed without warning.