Go4Expert

Go4Expert (http://www.go4expert.com/)
-   Engineering Concepts (http://www.go4expert.com/articles/engineering-concepts-tutorials/)
-   -   Vogel Approximation Method (http://www.go4expert.com/articles/vogel-approximation-method-t14840/)

Nadr 28Oct2008 11:00

Vogel Approximation Method
 
1 Attachment(s)
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: C

#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.

shabbir 16Nov2008 18:45

Re: Vogel Approximation Method
 
Vote for this article for Article of the month - October 2008


All times are GMT +5.5. The time now is 12:31.