Travelling Salesman Problem (TSP)

Assuming the salesman has to visit 'n' cities.He wishes to start from a particular city visit each city once and return to his starting point.His objective is to select a sequence in which the total travelling time is minimized.

MATHEMATICAL FORMULATION:
Let Cij be the distance or time or cost of going from city 'i' to city 'j'.
Let the decision variable Xij=1, if the salesman travels from city'i' to city 'j', otherwise 0.
The objective is to minimize the travelling time.

Hungarian Method- Unbalanced Assignment Problem

Q1.
                   Machines
                 A        B          C          D        E
Jobs   1[    4         3          6           2         7
          2[     10       12       11          14       16
          3[    4          3         2            1        5
          4[    8          7         6            9         6]

Soln:
STEP I:
The given matrix is unbalanced matrix.Hence add a row of "0"

[ 4    3     6      2       7
  10  12   11    14      16
  4      3    2     1        5
  8     7      6    9        6
  0     0      0     0       0]

STEP II:
Process row wise.
[ 2     1      4     0     5
  0     2      1     4     6
  3     2      1     0     4
  2     1       0     3     1
  0     0       0     0     0]

Number of straight lines N=4
Order of matrix n=5
N<n

Therefore the smallest value   in the previous matrix is  "1" subtract from the remaining values and add in the intersecting points.
[ 2   0  3  0  4
  0   1   0  4  5
  3   1   0  0  3
  3   1   0  4  1
  1   0   0  1   0]

Number of Straight Lines N =5
Order of Matrix n=5
N=n

Assign the jobs to machines.
      A        B         C         D         E
1[  2          0         3          0         4
2[  0            1        0          4         5
3 [ 3            1        0          0         3
4 [3            1        0           4        1
5[ 1           0         0           1         0]


1----->B  ; 2-->A ; 3-->D;  4---> C ; 5-->E

Cost= 3+10+1+6+0
       =Rs.20

      

Hungarian Method

Q1. Using the following Cost matrix determine (i) Optimal Job Assignment
                                                                       (ii)The cost of the assignment


                                       Jobs
                              1          2           3           4          5
Mechanic    A[     10          3            3           2          8
                   B       9            7           8           2           7
                   C       7            5           6           2           4
                   D       3            5           8           2           4
                   E       9            10          9           6         10


Soln:
STEP I:
Since the given matrix is a square Matrix (5 x 5) its balanced.
STEP II:

Process row wise

[ 8  1   1   0  6
  7  5   6   0  5
  5  3   4   0  2
  1  3   6   0  2
  3  4   3   0  4]

STEP III:

Process  Column wise for the above matrix

[ 7   0   0    0    4
  6   4   5    0    3
  4   2   3    0    0
  0   2   5    0    0
  2   3   2    0    2]

STEP IV:
Now we have drawn horizontal and vertical lines in such a way that most of the zeros are covered.
The number of Straight lines N=4
The order of matrix n=5
N<n

STEP V:
Since N<n
Therefore find out the smallest value from the above matrix .The smallest value is "2". Now subtract 2 fro the remaining values . Add "2" in the intersecting places "&" and "$" in the first row are the intersecting points.

[ 9  0   0  2   6
 6   2   3   0   3
 4   0   1   0   0
 0   0   3   0   0
 2   1   0   0   2]

Here all the columns are striked out as we have to cover most of the zeros.
Number of Straight lines N =5
Order of matrix n=5
Thus we get the optimal solution.

STEP VI:
Now we have to assign the jobs to the persons:
      1       2        3         4          5
A[  9       0        0         2          6
B   6        2        3        0           3
C   4        0        1        0           0
D   0        0        3        0           0
E   2        1        0         0           2]

1--> D ;  2-->A ;  3--->E ;  4--> B; 5--> C

Now we have to consider the original matrix and assign the values (ie., in each row we have "0" the value being assigned to the jobs) find the corresponding value in the original matrix

Minimum Cost= 3+3+9+2+4=Rs.21(this value no need to be unique as each of us will assign in different method)

Assignment Problem (AP)

Assignment Problem can be stated in the form of n x n matrix Cij of real numbers as given in the following table.

                        Jobs
                      1       2        3               ..............n
Person   1 [    c11   c12    c13..........................c1n
              2        c21   c22    c23..........................c2n
               .
               .

               .
              n        cn1     cn2   cn3............................cnn]

Mathematical Formulation :

An Assignment problem can be stated as

Hungarian Method:
These are the steps to be followed in Hungarian Method for Optimal Job Assignment and for cost assignmnet.
STEP I: Check whether the given matrix is a square matrix.If its so then its balanced.If not balanced add "0" in either the row/column based on the matrix.
STEP II: Process row wise entries.Find out the smallest value and subtract the entire row value.
STEP III:Process  column wise entries.Find out the smallest value and subtract the entire column value.
STEP IV:Draw horizontal/vertical lines in such a way that they cover all the zeros ie., it should be crossed in minimum number of straight lines.
STEP V:Check whether Number of Straight lines(N) = Order of Matrix(n).
If N=n then we get the optimal solution.
If N<n then again find out the smallest value from the above matrix and subtract with the other values in the matrix.Leave the rows and columns that are being striked out.In the intersection point add the smallest value.
STEP VI:Finally assign the jobs to the correct person by assigning "0".Find the minimum cost.

MODI Method / Modification Distribution

Q1.Solve the TP.

                 D1       D2      D3       D4       Supply
O1            11        20       7           8           50
O2            21        16      20         12          40
O3             8         12       8            9          70
Demand    30        25      35          40


Soln:
STEP I:
Eai=160 Ebj=130.The given TP is unbalnced Therefore add a Destination Column.

               D1     D2       D3      D4     D5      Supply
O1          11      20         7         8       0           50
O2          21      16        20       12      0           40
O3            8       12         8         9      0           70
Demand   30      25        35       40    30

Eai=Ebj=160.Now the TP is Balanced.

STEP II:
Now calculate the IBFS using VAM .
The Solution will be,

                      35
11     20      7        8     0
                               10    30
21     16     20      12     0
   30      25   15        15
8       12     8         9       0


In the above table we have 7 independent non negative allocation and m=n-1=7. non degenerate Basic feasible solution is obtained.

Total Cost= Rs.1160

STEP III:
Now select the row or column which has the maximum number of allocations.
Here in the above table we have the maximum number of allocations in the 3rd row.
Therefore assign u3=0
-----------------------------------------
4            9                  35      0         4
  11          20            7            8           0            u1=-1
------------------------------------------
10          1             9                 10        30
   21         16           20          12          0           u2=3
------------------------------------------
   30            25           15          15     3
8              12           8             9           0             u3=0
--------------------------------------------
v1=8       v2=12     v3=8      v4=9     v5=-3


c31=u3+v1=8      c32=u3+v2=12      c33=u3+v3=8      c34=u3+v4=9

c24=u2+v4=12    c25=u2+v5=0        c13=u1+v3=7
         u2=3               v5=-3                         u1=-1


Now calculate

This should be calculated for all the cells which where not allocated.(This should be calculated for the cells in the table which was obtained as a result of applying VAM)

Now (Delta)ij >=0 .Therefore Optimal Solution with Total Cost= Rs.1160.

Vogel's Approximation Method / Unit Cost Penalty Method

Q1.Find the IBFS for the following TP by VAM.


                D1        D2         D3          D4          Supply
O1            11        13          17           14            250
O2            16        18          14           10            300
O3            21        24          13           10            400
Demand   200       225       275          250

Soln:
STEP I:
The given TP is a balanced one. Since Eai=Ebj=950.Therefore there exists a Feasible Solution.

STEP II:
Calculate Penalty (The difference between the Smallest and next smallest cost in each row and column).

        D1       D2     D3     D4          Supply        P1
        ------------------------
          200
O1  11        13      17        14         250              2(13-11)
O2  16        18       14        10        300              4
O3  21        24      13         10       400               3
      200     225     275        250
P2   5         5         1            0

Among the Penalty calculated Select the highest value and choose the cell which has the lowest cost.

                                                  P1
     50
13           17       14         250     1(14-13)
18           14       10          300    4
24           13       10         400     3
225        275      250
5               1         0   P2


Similarly if we calculate the final one will be      

    125
10       250
125


Solution is given by

   200       50
11        13        17     14
                175               125
16        18        14      10
                             275    125
21        24        13       10

The values are independent ie., the number of closed cycles is m+n-1=3+4-1=6

There are six positive independent allocation which equals to m+n-1=6.This ensures that the solution is non-degenerate Basic Feasible solution.

Transportation Cost=(11 x 200)+(13 x 50)+(18 x 175)+(10 x 125)+(13 x 275)+( 10 X 125)
                              =Rs.12075

Least Cost Method / Matrix Minima Method

Q1.Obtain the initial feasible solution for the following TP using Matrix Minima Method.


                 D1          D2        D3        D4       Supply
O1             1            2            3            4          6
O2             4            3            2            0          8
O3             0            2            2            1         10
Demand     4             6           8             6

Soln:  
STEP I:
Sum up Demand and Supply.
Since Eai=Ebj=24. There exists a feasible solution for TP.

STEP II:
In the Least Cost Method, we have to find out the least value in the given problem and start from there.
In this problem the least value is "0", so start from there,

------------------
1      2      3      4        6
4      3      2      0        8
   4
0      2       2     1       10
------------------
4      6       8      6



-----------------
2        3         4          6
                         6
3         2         0          8
2         2         1          6
------------------
6         8         6

------------
    6
2           3           6
3           2           2
2           2           6
------------
6           8


----------
3        2        2
    0
2         2        6
---------
0         8

Here we have subtracted the demand and supply values , in the previous steps the least values were "0" therefore we did not subtract it .

----
   2
2        2
2        6
---
8

-----
    6
2           6
-----
6

STEP III:
The Solution is given by:

                   6
1             2            3             4
                                 2              6
4              3            2             0
   4               0            6
0               2            2             1


Total Cost = (2 x 6)+(2 x 2)+(0 x 6)+(0 x 4)+(2  x 0)+(2 x 6)
                 = Rs.28