Assignment Problem Solve by Hungarian Method with Algorithm and solution in c++

Assignment Problem Solve by Hungarian Method with Algorithm and solution in c++

Here i have post Assignment problem solved by Hungarian Method  with algorithm, example and program written in c++

Hungarian Method Algorithm:

Step 1: develop the cost table from the give problem

     If no of rows does not equal to the no of columns and vise a versa, then a dummy row or column    must be added. The assignment cost for a dummy cells are 0.

Step 2: find the opportunity cost table;

1. . Locate the smallest element in each row of the given cost table and then subtract that from each element of the rows. 
2.  In the reduced matrix obtain from 2.1. locate the smallest element in  each columns and then subtract that from each element of that column each row and column now have at least one zero value

Step 3: make assignment in the opportunity cost matrix

1. Examine rows successively until a row with exactly one unmarked zero is obtained make an assignment to this single zero by making a square around it.
2. For each zero value that becomes assigned eliminate(X) strike off all other zero in the same row and/or column.
3.  Repeat step 3.1. and 3.2. for column also with exactly single zero value cell that has not been assigned or eliminated.
4.  If a row and/or columns has two or more unmarked zeros and one can not be chosen by inspection, then choose the assigned zero cell arbitrarily.
5.  Continue this process until all zeros in row/columns are either enclosed(assigned) or strike off(X).

Step 4: optimality criterion

• If the number of assignment cell is equal to the no. of row/columns then it is an optimal solution the total cost associated with this solution is obtained by adding original cost figure in the occupied cells
• If a zero cell was chosen arbitrarily in step 3 there exists an alternative optimal solution but if no optimal solution is found then go to step 5.

Step 5: revise the opportunity cost table

Draw a set of horizontal and vertical lines to cover all the zeros in the revised cost obtained from step3 by using the following procedure.

1. For each row in which no allocation was made mark a tick.
2. Examine the marked row, if any zero in tick to the respective columns that contain zero.
3. Examine marked column. If any assigned zero occurs in those columns then tick the respective rows that contain those assigned zero.
4. Repeat this process until no more row or columns can be marked
5. Draw a straight line through each marked column and each unmarked rows

If the no of line drawn is equal to the no. of rows  then the current solution is the optimal solution otherwise go to step 6.

Step 6: develop the new revised opportunity cost table

1. From among the cells not covered by any line, choose the smallest element call this value k.
2. Subtract k from every element in the cell not covered by a line.
3. Add k to every element in the cell covered by the two lines i.e. intersection of two line.
4. Elements in cell covered by one line remain unchanged

Step 7: repeat steps

Repeat step 3 to 6 until an optimal solution is obtained.

Vogel's Approximation Method with Algorthim and Example using c++

Vogel's Approximation Method with Algorithm and Example using c++

Algorithm:

Vogel's Approximation Method of Allocation.

This method also takes costs into account in allocation. Five steps are involved in applying this heuristic:

Step 1: Determine the difference between the lowest two cells in all rows and columns, including dummies.

Step 2: Identify the row or column with the largest difference. Ties may be broken arbitrarily.

Step 3: Allocate as much as possible to the lowest-cost cell in the row or column with the highest difference. If two or more differences are equal, allocate as much as possible to the lowest-cost cell in these rows or columns.

Step 4: Stop the process if all row and column requirements are met. If not, go to the next step.

Step 5: Recalculate the differences between the two lowest cells remaining in all rows and columns. Any row and column with zero supply or demand should not be used in calculating further differences. Then go to Step 2.  

Data:

Solution:

Program:

 #include<iostream.h>
#include<stdio.h>
#include<conio.h>
#include<iomanip.h>
#include<stdlib.h>
#define MAX 50
enum boolean{FALSE,TRUE};
class voggelsmethod{
    int data[MAX][MAX];
    int requered[MAX];
    int capacity[MAX];
    int allocation[MAX][MAX];
    int no_of_rows,no_of_columns,no_of_allocation;
    public:
        lcmethod(){
            for(int i=0;i<MAX;i++){
                capacity[i]=0;
                requered[i]=0;
                for(int j=0;j<MAX;j++){
                    data[i][j]=0;
                    allocation[i][j]=0;
                }
            }
            no_of_rows=no_of_columns=no_of_allocation=0;
        }
        void setColumn(int no){no_of_columns=no;};
        void setRow(int no){no_of_rows=no;}
        void getData();
        void getCapacity();
        void getRequiredValue();
        void makeAllocation();
        boolean checkValue(int [],int);
        int getMinVal(int [],int);
        int getTotalMinVal(int [],int,int);
        int getMinValsPos(int,int [],int);
        void display();
        int getPanalty(int [],int);
};
int voggelsmethod::getPanalty(int array[],int no){
    int i,j,temp;
    for(i=0;i<no;i++)
        for(j=i+1;j<no;j++)
            if(array[i]>array[j]){
                temp=array[i];
                array[i]=array[j];
                array[j]=temp;
            }
    return array[1]-array[0];
}
int voggelsmethod::getMinVal(int array[],int no){
    int min=array[0];
    for(int i=0;i<no;i++)
        if(array[i]<min)
            min=array[i];
    return min;
}
int voggelsmethod::getMinValsPos(int value,int temp_data[],int no){
    int k=0;
    for(int i=0;i<no;i++)
        if(temp_data[i]==value)
            return i;
    return -1;
}
int voggelsmethod::getTotalMinVal(int array[],int n,int value){
    int no=0;
    for(int i=0;i<n;i++)
        if(array[i]==value)
                no++;
    return no;
}
boolean voggelsmethod::checkValue(int arr[],int no){
    for(int i=0;i<no;i++)
        if(arr[i]!=0)
            return FALSE;
    return TRUE;
}
void arrayCopy(int start,int end,int array1[],int start1,int array2[]){
    for(int i=start,j=start1;i<end;i++,j++)
        array2[j]=array1[i];
}
int getTotal(int array[],int no){
    int sum=0;
    for(int i=0;i<no;i++)
        sum+=array[i];
    return sum;
}
void copy2DArray(int startRow,int startCol,int endRow,int endCol,int array[][MAX],int start1Row,int start1Col,int ans[][MAX]){
    for(int i=startRow,k=start1Row;i<endRow;i++,k++)
        for(int j=startCol,l=start1Col;j<endCol;j++,l++)
            ans[k][l]=array[i][j];
}
int getMaxVal(int array[MAX],int no){
    int max=0;
    for(int i=0;i<no;i++)
        if(array[i]>max)
            max=array[i];
    return max;
}
int getMaxValPos(int array[MAX],int no,int value){
    for(int i=0;i<no;i++)
        if(value==array[i])
            return i;
    return -1;
}
void voggelsmethod::makeAllocation(){
    int i=0,j=0,min,total_min;
    int temp_requered[MAX]={0};
    int temp_capacity[MAX]={0};
    int temp_data[MAX][MAX]={0};
    int position[MAX]={0};
    int dataPos[MAX]={0};
    int sum_of_cap,sum_of_req;
    sum_of_cap=getTotal(capacity,no_of_rows);
    sum_of_req=getTotal(requered,no_of_columns);
    if(sum_of_cap!=sum_of_req){
        if(sum_of_cap>sum_of_req){
            for(j=0;j<no_of_rows;j++)
                data[j][no_of_columns]=0;
            requered[no_of_columns]=sum_of_cap-sum_of_req;
            no_of_columns++;
        }
        else{
            for(j=0;j<no_of_columns;j++)
                data[no_of_rows][j]=0;
            capacity[no_of_rows]=sum_of_req-sum_of_cap;
            no_of_rows++;
        }
    }
    i=j=0;
    arrayCopy(0,no_of_rows,capacity,0,temp_capacity);
    arrayCopy(0,no_of_columns,requered,0,temp_requered);
    copy2DArray(0,0,no_of_rows,no_of_columns,data,0,0,temp_data);
    int rowPanalty[MAX]={0};
    int colPanalty[MAX]={0};
    int panaltyData[MAX]={0},n=0;
    while(!checkValue(temp_capacity,no_of_rows) || !checkValue(temp_requered,no_of_columns)){

        for(i=0;i<no_of_rows;i++){
            arrayCopy(0,no_of_columns,temp_data[i],0,panaltyData);
            if(temp_capacity[i]!=0)
                rowPanalty[i]=getPanalty(panaltyData,no_of_columns);
            else
                rowPanalty[i]=0;
        }
        for(i=0;i<no_of_columns;i++){
            for(j=0;j<no_of_rows;j++)
                panaltyData[j]=temp_data[j][i];
            if(requered[i]!=0)
                colPanalty[i]=getPanalty(panaltyData,no_of_rows);
            else
                colPanalty[i]=0;
        }
        int maxRowPanalty=getMaxVal(rowPanalty,no_of_rows);
        int maxColPanalty=getMaxVal(colPanalty,no_of_columns);
        int maxPanRow[MAX]={0};
        int maxPanCol[MAX]={0};
        if(maxRowPanalty>maxColPanalty){
            i=getMaxValPos(rowPanalty,no_of_rows,maxRowPanalty);
            for(j=0;j<no_of_columns;j++)
                maxPanRow[j]=temp_data[i][j];
            min=getMinVal(maxPanRow,no_of_columns);
            j=getMinValsPos(min,maxPanRow,no_of_columns);
        }
        else{
            j=getMaxValPos(colPanalty,no_of_columns,maxColPanalty);
            for(i=0;i<no_of_rows;i++)
                maxPanCol[i]=temp_data[i][j];
            min=getMinVal(maxPanCol,no_of_rows);
            i=getMinValsPos(min,maxPanCol,no_of_rows);
        }

        if(temp_capacity[i]>temp_requered[j]){
            allocation[i][j]=temp_requered[j];
            for(int k=0;k<no_of_rows;k++)
                temp_data[k][j]=9999;
            temp_capacity[i]-=temp_requered[j];
            temp_requered[j]=0;
        }
        else if(temp_capacity[i]<temp_requered[j]){
            allocation[i][j]=temp_capacity[i];
            for(int k=0;k<no_of_columns;k++)
                temp_data[i][k]=9999;
            temp_requered[j]-=temp_capacity[i];
            temp_capacity[i]=0;
        }
        else{
            int k;
            allocation[i][j]=temp_capacity[i];
            for(k=0;k<no_of_rows;k++)
                temp_data[k][j]=9999;
            for(k=0;k<no_of_columns;k++)
                temp_data[i][k]=9999;
            temp_requered[j]=temp_capacity[i]=0;
        }
        n++;
    }
    no_of_allocation=n;
}
void voggelsmethod::getCapacity(){
    cout<<"enter capacity for each source : \n";
    for(int i=0;i<no_of_rows;i++){
        cout<<"s"<<i+1<<" : ";
        cin>>capacity[i];
    }
}
void voggelsmethod::getRequiredValue(){
    cout<<"enter required unit value for each destination : \n";
    for(int i=0;i<no_of_columns;i++){
        cout<<"d"<<i+1<<" : ";
        cin>>requered[i];

    }
}
void voggelsmethod::display(){
    int i;
    cout<<"\ngiven data :\n";
    cout<<setw(9);
    for(i=0;i<no_of_columns;i++)
        cout<<"D"<<i+1<<setw(4);
    cout<<setw(5)<<"cap"<<endl<<setw(0);
    for(i=0;i<no_of_rows;i++){
        cout<<setw(3)<<"S"<<i+1;
        for(int j=0;j<no_of_columns;j++)
            cout<<setw(5)<<data[i][j];
        cout<<setw(5)<<capacity[i]<<endl;
    }
    cout<<setw(4)<<"req";
    for(i=0;i<no_of_columns;i++)
        cout<<setw(5)<<requered[i];

    cout<<"\n\n after allocation :\n";
    for(i=0;i<no_of_rows;i++){
        for(int j=0;j<no_of_columns;j++){
            if(allocation[i][j]!=0)
                cout<<setw(5)<<data[i][j]<<"*"<<setw(2)<<allocation[i][j];
            else
                cout<<setw(8)<<data[i][j];
        }
        cout<<endl;
    }
    int k=0,sum=0;
    for(i=0;i<no_of_rows;i++){
        for(int j=0;j<no_of_columns;j++){
            if(allocation[i][j]!=0){
                cout<<"("<<data[i][j]<<" * "<<allocation[i][j]<<")";
                if(k<no_of_allocation-1){
                    cout<<"+";
                    k++;
                }
                sum+=data[i][j]*allocation[i][j];
            }
        }
    }
    cout<<"\nanswer : "<<sum;
    if((no_of_rows+no_of_columns-1)==no_of_allocation){
        cout<<"\nhere "<<no_of_rows<<"+"<<no_of_columns<<"-1 ="<<no_of_allocation<<" no. of allocations";
        cout<<"\n so this problem is non-degenarated solution";
    }
    else{
        cout<<"\nhere "<<no_of_rows<<"+"<<no_of_columns<<"-1 !="<<no_of_allocation<<"no of allocations";
        cout<<"\n so this problem is degenarated solution";
    }
}
void voggelsmethod::getData(){
    cout<<"enter source to destination data:"<<endl;
    for(int i=0;i<no_of_rows;i++){
        cout<<"enter "<<i<<"th row : ";
        for(int j=0;j<no_of_columns;j++){
            cin>>data[i][j];
        }
    }
}
void main(){
    clrscr();
    voggelsmethod v;
    int r,c;
    cout<<"enter no of Rows : ";
    cin>>r;
    cout<<"enter no of columns : ";
    cin>>c;

    v.setColumn(c);
    v.setRow(r);

    v.getData();
    v.getCapacity();
    v.getRequiredValue();
    v.makeAllocation();
    clrscr();
    v.display();
    getch();
} 

output:

provide data:

 

 Allocation:

 

Least Cost Method with algorithm and Example in c++

Least Cost Method with algorithm and Example in c++

Algorithm: 

Step1: select smallest cost value in the given cost matrix of transportation problem say C_ij then allocation will be min(a_i,b_j)

Step2: (a) if allocation is equal to supply(a_i) cross the i^th row and decrease b_j (emand) by a_i.

                (B) if allocation is equals to demand (b_j) cross the j^th column and decrease a_i by b_j.

                (C)if allocation is equal to both demand and supply cross any one of them (either column  or row)

Step3: repeat the above step for finally reduced transportation table.

Example:

 Solution:

Example program in C++

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
#include<iomanip.h>
#include<stdlib.h>
#define MAX 50
enum boolean{FALSE,TRUE};
class lcmethod{
    int data[MAX][MAX];
    int requered[MAX];
    int capacity[MAX];
    int allocation[MAX][MAX];
    int no_of_rows,no_of_columns,no_of_allocation;
    public:
        lcmethod(){
            for(int i=0;i<MAX;i++){
                capacity[i]=0;
                requered[i]=0;
                for(int j=0;j<MAX;j++){
                    data[i][j]=0;
                    allocation[i][j]=0;
                }
            }
            no_of_rows=no_of_columns=no_of_allocation=0;
        }
        void setColumn(int no){no_of_columns=no;};
        void setRow(int no){no_of_rows=no;}
        void getData();
        void getCapacity();
        void getRequiredValue();
        void makeAllocation();
        boolean checkValue(int [],int);
        int getMinVal(int [][MAX]);
        int getTotalMinVal(int [][MAX],int);
        void getMinValsPos(int,int [][MAX],int[][2],int [][2]);
        void display();
};
void lcmethod::getMinValsPos(int value,int temp_data[][MAX],int ans[][2],int pos[][2]){
    int k=0;
    for(int i=0;i<no_of_rows;i++)
        for(int j=0;j<no_of_columns;j++)
            if(temp_data[i][j]==value){
                ans[k][0]=i;
                ans[k][1]=j;
                pos[k][0]=requered[j];
                pos[k++][1]=capacity[i];
            }
}
int lcmethod::getTotalMinVal(int temp_data[][MAX],int value){
    int no=0;
    for(int i=0;i<no_of_rows;i++)
        for(int j=0;j<no_of_columns;j++)
            if(temp_data[i][j]==value)
                no++;
    return no;
}
int lcmethod::getMinVal(int temp_data[][MAX]){
    int min=temp_data[0][0];

    for(int i=0;i<no_of_rows;i++)
        for(int j=0;j<no_of_columns;j++)
            if(temp_data[i][j]<min)
                min=temp_data[i][j];

    return min;
}
boolean lcmethod::checkValue(int arr[],int no){
    for(int i=0;i<no;i++)
        if(arr[i]!=0)
            return FALSE;
    return TRUE;
}
void arrayCopy(int start,int end,int array1[],int start1,int array2[]){
    for(int i=start,j=start1;i<end;i++,j++)
        array2[j]=array1[i];
}
int getTotal(int array[],int no){
    int sum=0;
    for(int i=0;i<no;i++)
        sum+=array[i];
    return sum;
}
void copy2DArray(int startRow,int startCol,int endRow,int endCol,int array[][MAX],int start1Row,int start1Col,int ans[][MAX]){
    for(int i=startRow,k=start1Row;i<endRow;i++,k++)
        for(int j=startCol,l=start1Col;j<endCol;j++,l++)
            ans[k][l]=array[i][j];
}
int getMaxVal(int array[MAX],int no){
    int max=0;
    for(int i=0;i<no;i++)
        if(array[i]>max)
            max=array[i];
    return max;
}
int getMaxValPos(int array[MAX],int no,int value){
    for(int i=0;i<no;i++)
        if(value==array[i])
            return i;
    return -1;
}
void lcmethod::makeAllocation(){
    int i=0,j=0,min,total_min;
    int temp_requered[MAX]={0};
    int temp_capacity[MAX]={0};
    int temp_data[MAX][MAX]={0};
    int position[MAX][2]={0};
    int dataPos[MAX][2]={0};
    int sum_of_cap,sum_of_req;
    sum_of_cap=getTotal(capacity,no_of_rows);
    sum_of_req=getTotal(requered,no_of_columns);
    if(sum_of_cap!=sum_of_req){
        if(sum_of_cap>sum_of_req){
            for(j=0;j<no_of_rows;j++)
                data[j][no_of_columns]=0;
            requered[no_of_columns]=sum_of_cap-sum_of_req;
            no_of_columns++;
        }
        else{
            for(j=0;j<no_of_columns;j++)
                data[no_of_rows][j]=0;
            capacity[no_of_rows]=sum_of_req-sum_of_cap;
            no_of_rows++;
        }
    }
    i=j=0;
    arrayCopy(0,no_of_rows,capacity,0,temp_capacity);
    arrayCopy(0,no_of_columns,requered,0,temp_requered);
    copy2DArray(0,0,no_of_rows,no_of_columns,data,0,0,temp_data);
    while(!checkValue(temp_capacity,no_of_rows) || !checkValue(temp_requered,no_of_columns)){
        min=getMinVal(temp_data);
        total_min=getTotalMinVal(temp_data,min);
        getMinValsPos(min,temp_data,position,dataPos);
        int minPosValue[MAX]={0};
        for(i=0;i<no_of_rows;i++){
            if(dataPos[i][0]<dataPos[i][1])
                minPosValue[i]=dataPos[i][0];
            else
                minPosValue[i]=dataPos[i][1];
        }
        int max=getMaxVal(minPosValue,total_min);
        int maxvalPos=getMaxValPos(minPosValue,total_min,max);
        i=position[maxvalPos][0];
        j=position[maxvalPos][1];
        if(temp_capacity[i]>temp_requered[j]){
            allocation[i][j]=temp_requered[j];
            for(int k=0;k<no_of_rows;k++)
                temp_data[k][j]=9999;
            temp_capacity[i]-=temp_requered[j];
            temp_requered[j]=0;
        }
        else if(temp_capacity[i]<temp_requered[j]){
            allocation[i][j]=temp_capacity[i];
            for(int k=0;k<no_of_columns;k++)
                temp_data[i][k]=9999;
            temp_requered[j]-=temp_capacity[i];
            temp_capacity[i]=0;
        }
        else{
            int k;
            allocation[i][j]=temp_capacity[i];
            for(k=0;k<no_of_rows;k++)
                temp_data[k][j]=9999;
            for(k=0;k<no_of_columns;k++)
                temp_data[i][k]=9999;
            temp_requered[j]=temp_capacity[i]=0;
        }
        no_of_allocation++;
    }
}
void lcmethod::getCapacity(){
    cout<<"enter capacity for each source : \n";
    for(int i=0;i<no_of_rows;i++){
        cout<<"s"<<i+1<<" : ";
        cin>>capacity[i];
    }
}
void lcmethod::getRequiredValue(){
    cout<<"enter required unit value for each destination : \n";
    for(int i=0;i<no_of_columns;i++){
        cout<<"d"<<i+1<<" : ";
        cin>>requered[i];

    }
}
void lcmethod::display(){
    int i;
    cout<<"\ngiven data :\n";
    cout<<setw(9);
    for(i=0;i<no_of_columns;i++)
        cout<<"D"<<i+1<<setw(4);
    cout<<setw(5)<<"cap"<<endl<<setw(0);
    for(i=0;i<no_of_rows;i++){
        cout<<setw(3)<<"S"<<i+1;
        for(int j=0;j<no_of_columns;j++)
            cout<<setw(5)<<data[i][j];
        cout<<setw(5)<<capacity[i]<<endl;
    }
    cout<<setw(4)<<"req";
    for(i=0;i<no_of_columns;i++)
        cout<<setw(5)<<requered[i];

    cout<<"\n\n after allocation :\n";
    for(i=0;i<no_of_rows;i++){
        for(int j=0;j<no_of_columns;j++){
            if(allocation[i][j]!=0)
                cout<<setw(5)<<data[i][j]<<"*"<<setw(2)<<allocation[i][j];
            else
                cout<<setw(8)<<data[i][j];
        }
        cout<<endl;
    }
    int k=0,sum=0;
    for(i=0;i<no_of_rows;i++){
        for(int j=0;j<no_of_columns;j++){
            if(allocation[i][j]!=0){
                cout<<"("<<data[i][j]<<" * "<<allocation[i][j]<<")";
                if(k<no_of_allocation-1){
                    cout<<"+";
                    k++;
                }
                sum+=data[i][j]*allocation[i][j];
            }
        }
    }
    cout<<"\nanswer : "<<sum;
    if((no_of_rows+no_of_columns-1)==no_of_allocation){
        cout<<"\nhere "<<no_of_rows<<"+"<<no_of_columns<<"-1 ="<<no_of_allocation<<" no. of allocations";
        cout<<"\n so this problem is non-degenarated solution";
    }
    else{
        cout<<"\nhere "<<no_of_rows<<"+"<<no_of_columns<<"-1 !="<<no_of_allocation<<"no of allocations";
        cout<<"\n so this problem is degenarated solution";
    }
}
void lcmethod::getData(){
    cout<<"enter source to destination data:"<<endl;
    for(int i=0;i<no_of_rows;i++){
        cout<<"enter "<<i<<"th row : ";
        for(int j=0;j<no_of_columns;j++){
            cin>>data[i][j];
        }
    }
}
void main(){
    clrscr();
    lcmethod lcm;
    int r,c;
    cout<<"enter no of Rows : ";
    cin>>r;
    cout<<"enter no of columns : ";
    cin>>c;

    lcm.setColumn(c);
    lcm.setRow(r);

    lcm.getData();
    lcm.getCapacity();
    lcm.getRequiredValue();
    lcm.makeAllocation();
    clrscr();
    lcm.display();
    getch();
}

output: