Vogel Approximation Method

Discussion in 'Engineering Concepts' started by Nadr, Oct 28, 2008.

  1. Nadr

    Nadr New Member

    Joined:
    Oct 16, 2007
    Messages:
    165
    Likes Received:
    1
    Trophy Points:
    0
    It tries to solve the demand supply matrix with Vogel Approximation method.

    The code



    The code I have tried to keep is pretty self explanatory to the person who knows what VAM is all about.
    Code:
    #include <stdio.h>
    #include <conio.h>
    
    #define TRUE 1
    #define FALSE 0
    #define INFINITY 1111
    #define N 3
    #define M 4
    
    void input(void);
    void display(void);
    void displayfinal(void);
    void diffmin(void);
    void table(void);
    int max(int *,int *,int);
    int min(int,int);
    int mini(int *,int *,int);
    int condition(void);
    
    int arr[N][M];
    int arrcopy[N][M];
    int value[N][M];
    int u[N];
    int v[M];
    int rowdiffmin[N];
    int coldiffmin[M];
    int decide[M+N];
    int x[N],y[M];  /* x is u y is v */
    
    void main()
    {
    	int i,j;
    	table();
    	x[0]=0;
    	for(i=0;i<3;i++)
    	{
    		for(j=0;j<4;j++)
    		{
    			if(value[i][j]!=0)
    				printf("U[%d] + V[%d] = %d\n",i+1,j+1,arr[i][j]);
    		}
    	}
    	getch();
    }
    
    void table(void)
    {
    	int rowdiffminmaxpos;
    	int coldiffminmaxpos;
    	int decidemaxpos;
    	int temp;
    	int temparr[M];
    	int i;
    
    	clrscr();
    	input();
    	diffmin();
    	display();
    	while(condition())
    	{
    		max(decide,&decidemaxpos,M+N);
    		if(decidemaxpos>=0 && decidemaxpos<N)
    		{
    			rowdiffminmaxpos=decidemaxpos;
    			for(i=0;i<M;i++)
    				temparr[i]=arr[decidemaxpos][i];
    			mini(temparr,&coldiffminmaxpos,M);
    		}
    		else if(decidemaxpos>=N && decidemaxpos<M+N)
    		{
    			coldiffminmaxpos=decidemaxpos-N;
    			for(i=0;i<N;i++)
    				temparr[i]=arr[decidemaxpos][i];
    			temparr[i]=INFINITY;
    			mini(temparr,&rowdiffminmaxpos,M);
    		}
    		temp=min(u[rowdiffminmaxpos],v[coldiffminmaxpos]);
    		value[rowdiffminmaxpos][coldiffminmaxpos]=temp;
    		if(temp==u[rowdiffminmaxpos])
    		{
    			for(i=0;i<M;i++)
    				arr[rowdiffminmaxpos][i]=INFINITY;
    			u[rowdiffminmaxpos]-=temp;
    			v[coldiffminmaxpos]-=temp;
    		}
    		else if(temp==v[coldiffminmaxpos])
    		{
    			for(i=0;i<N;i++)
    				arr[i][coldiffminmaxpos]=INFINITY;
    			u[rowdiffminmaxpos]-=temp;
    			v[coldiffminmaxpos]-=temp;
    		}
    		diffmin();
    		getch();
    		display();
    	}
    	getch();
    	displayfinal();
    	getch();
    }
    
    void input(void)
    {
    	int i,j;
    	for(i=0;i<N;i++)
    		for(j=0;j<M;j++)
    			arr[i][j]=arrcopy[i][j]=-1;
    	/* Demand supply matrix */
    	arr[0][0]=arrcopy[0][0]=5;
    	arr[0][1]=arrcopy[0][1]=3;
    	arr[0][2]=arrcopy[0][2]=6;
    	arr[0][3]=arrcopy[0][3]=2;
    	arr[1][0]=arrcopy[1][0]=4;
    	arr[1][1]=arrcopy[1][1]=7;
    	arr[1][2]=arrcopy[1][2]=9;
    	arr[1][3]=arrcopy[1][3]=1;
    	arr[2][0]=arrcopy[2][0]=3;
    	arr[2][1]=arrcopy[2][1]=4;
    	arr[2][2]=arrcopy[2][2]=7;
    	arr[2][3]=arrcopy[2][3]=5;
    	/* Supply */
    	u[0]=19;
    	u[1]=37;
    	u[2]=34;
    	/* Demand */
    	v[0]=16;
    	v[1]=18;
    	v[2]=31;
    	v[3]=25;
    	/**************************************************\
    	5       3       6       2               19      (1)
    	4       7       9       1               37      (3)
    	3       4       7       5               34      (1)
    
    	16      18      31      25
    	(1)     (1)     (1)     (1)
    	----------------------------------------------------
    	5       3       6       1111            19      (2)
    	4       7       9       1111            12      (3)
    	3       4       7       1111            34      (1)
    
    	16      18      31      0
    	(1)     (1)     (1)     (0)
    	----------------------------------------------------
    	5       3       6       1111            19      (2)
    	1111    1111    1111    1111            0       (0)
    	3       4       7       1111            34      (1)
    
    	4       18      31      0
    	(2)     (1)     (1)     (0)
    	----------------------------------------------------
    	5       1111    6       1111            1       (1)
    	1111    1111    1111    1111            0       (0)
    	3       1111    7       1111            34      (4)
    
    	4       0       31      0
    	(2)     (0)     (1)     (0)
    	---------------------------------------------------
    	1111    1111    6       1111            1       (1105)
    	1111    1111    1111    1111            0       (0)
    	1111    1111    7       1111            30      (1104)
    
    	0       0       31      0
    	(0)     (0)     (1)     (0)
    	---------------------------------------------------
    	1111    1111    1111    1111            0       (0)
    	1111    1111    1111    1111            0       (0)
    	1111    1111    7       1111            30      (1104)
    
    	0       0       30      0
    	(0)     (0)     (1104)  (0)
    	---------------------------------------------------
    	1111    1111    1111    1111            0       (0)
    	1111    1111    1111    1111            0       (0)
    	1111    1111    1111    1111            0       (0)
    
    	0       0       0       0
    	(0)     (0)     (0)     (0)
    	---------------------------------------------------
    	---------------------------------------------------
    	5       3|18    6|1     2
    	4|12    7       9       1|25
    	3|4     4       7|30    5
    	1111    1111    7       1111            30      (1104)
    
    	X[1][2] = 18
    	X[1][3] = 1
    	X[2][1] = 12
    	X[2][4] = 25
    	X[3][1] = 4
    	X[3][3] = 30
    	/**************************************************/
    }
    
    void displayfinal(void)
    {
    	int i,j;
    	printf("\n");
    	for(i=0;i<N;i++)
    		for(j=0;j<M;j++)
    			arr[i][j]=arrcopy[i][j];
    	for(i=0;i<N;i++)
    	{
    		for(j=0;j<M;j++)
    			if(value[i][j]==0)
    				printf("%d\t",arr[i][j]);
    			else
    				printf("%d|%d\t",arr[i][j],value[i][j]);
    		printf("\n");
    	}
    	printf("\n");
    	for(i=0;i<N;i++)
    		for(j=0;j<M;j++)
    			if(value[i][j]!=0)
    				printf("X[%d][%d] = %d\n",i+1,j+1,value[i][j]);
    }
    
    int condition(void)
    {
    	int i;
    	int flag;
    	int temp[M+N];
    	flag=1;
    	for(i=0;i<N;i++)
    		temp[i]=u[i];
    	for(;i<M+N;i++)
    		temp[i]=v[i];
    	for(i=0;i<M+N;i++)
    	{
    		if(temp[i]!=0)
    			flag=0;
    	}
    	if(flag==0)
    		return(TRUE);
    	else
    		return(FALSE);
    }
    
    int min(int a,int b)
    {
    	if(a>b)
    		return(b);
    	else
    		return(a);
    }
    
    int mini(int *a,int *aminpos,int n)
    {
    	int i;
    	int amin;
    	amin=a[0];
    	*aminpos=0;
    	for(i=0;i<n;i++)
    	{
    		if(a[i]<amin)
    		{
    			amin=a[i];
    			*aminpos=i;
    		}
    	}
    	return(amin);
    }
    
    int max(int *a,int *amaxpos,int n)
    {
    	int i;
    	int amax;
    	amax=a[0];
    	*amaxpos=0;
    	for(i=0;i<n;i++)
    	{
    		if(a[i]>amax)
    		{
    			amax=a[i];
    			*amaxpos=i;
    		}
    	}
    	return(amax);
    }
    
    void diffmin(void)
    {
    	int min1,min2;
    	int arrmin1pos,arrmin2pos;
    	int i,j;
    
    	for(i=0;i<N;i++)
    	{
    		min1=arr[i][0];
    		arrmin1pos=0;
    		for(j=0;j<M;j++)
    		{
    			if(arr[i][j]<min1)
    			{
    				min1=arr[i][j];
    				arrmin1pos=j;
    			}
    		}
    		if(arrmin1pos==1)
    		{
    			min2=arr[i][0];
    			arrmin2pos=0;
    		}
    		else
    		{
    			min2=arr[i][1];
    			arrmin2pos=1;
    		}
    		for(j=0;j<M;j++)
    		{
    			if(arr[i][j]<min2 && j!=arrmin1pos)
    			{
    				min2=arr[i][j];
    				arrmin2pos=j;
    			}
    		}
    		rowdiffmin[i]=min2-min1;
    		decide[i]=rowdiffmin[i];
    	}
    
    	for(i=0;i<M;i++)
    	{
    		min1=arr[0][i];
    		arrmin1pos=0;
    		for(j=0;j<N;j++)
    		{
    			if(arr[j][i]<min1)
    			{
    				min1=arr[j][i];
    				arrmin1pos=j;
    			}
    		}
    		if(arrmin1pos==1)
    		{
    			min2=arr[0][i];
    			arrmin2pos=0;
    		}
    		else
    		{
    			min2=arr[1][i];
    			arrmin2pos=1;
    		}
    		for(j=0;j<N;j++)
    		{
    			if(arr[j][i]<min2 && j!=arrmin1pos)
    			{
    				min2=arr[j][i];
    				arrmin2pos=j;
    			}
    		}
    		coldiffmin[i]=min2-min1;
    		decide[i+N]=coldiffmin[i];
    	}
    }
    
    void display(void)
    {
    	int i,j;
    	printf("\n");
    	for(i=0;i<N;i++)
    	{
    		for(j=0;j<M;j++)
    			printf("%d\t",arr[i][j]);
    		printf("\t%d\t(%d)\t",u[i],rowdiffmin[i]);
    		printf("\n");
    	}
    	printf("\n");
    	for(i=0;i<M;i++)
    		printf("%d\t",v[i]);
    	printf("\n");
    	for(i=0;i<M;i++)
    		printf("(%d)\t",coldiffmin[i]);
    	printf("\n\n");
    }
    
    Here is the sample output
    Code:
    	Output of Vogel Approximation Method
    	------------------------------------
     5       3       6       2               19      (1)
     4       7       9       1               37      (3)
     3       4       7       5               34      (1)
    
     16      18      31      25
     (1)     (1)     (1)     (1)
    ----------------------------------------------------
     5       3       6       1111            19      (2)
     4       7       9       1111            12      (3)
     3       4       7       1111            34      (1)
    
     16      18      31      0
     (1)     (1)     (1)     (0)
    ----------------------------------------------------
     5       3       6       1111            19      (2)
     1111    1111    1111    1111            0       (0)
     3       4       7       1111            34      (1)
    
     4       18      31      0
     (2)     (1)     (1)     (0)
    ----------------------------------------------------
    5       1111    6       1111            1       (1)
    1111    1111    1111    1111            0       (0)
    3       1111    7       1111            34      (4)
    
    4       0       31      0
    (2)     (0)     (1)     (0)
    ---------------------------------------------------
    1111    1111    6       1111            1       (1105)
    1111    1111    1111    1111            0       (0)
    1111    1111    7       1111            30      (1104)
    
    0       0       31      0
    (0)     (0)     (1)     (0)
    ---------------------------------------------------
    1111    1111    1111    1111            0       (0)
    1111    1111    1111    1111            0       (0)
    1111    1111    7       1111            30      (1104)
    
    0       0       30      0
    (0)     (0)     (1104)  (0)
    ---------------------------------------------------
    1111    1111    1111    1111            0       (0)
    1111    1111    1111    1111            0       (0)
    1111    1111    1111    1111            0       (0)
    
    0       0       0       0
    (0)     (0)     (0)     (0)
    ---------------------------------------------------
    ---------------------------------------------------
    5       3|18    6|1     2
    4|12    7       9       1|25
    3|4     4       7|30    5
    1111    1111    7       1111            30      (1104)
    
    X[1][2] = 18
    X[1][3] = 1
    X[2][1] = 12
    X[2][4] = 25
    X[3][1] = 4
    X[3][3] = 30
    
    I hope I have tried to make it as clear as possible but would appreciate any positive criticism.
     

    Attached Files:

    Last edited by a moderator: Aug 14, 2010
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice