UV Method For Finding Optimal Solution of TP

Step 1

First, construct a transportation table entering the origin capacities $a_i$, the destination requirements $b_j$ and the cost $c_{ij}$. (If the TP is unbalanced convert it into a balanced TP by adding a dummy row or dummy column as per the requirement taking zero costs).

Step 2

Find an initial basic feasible solution by any one method (preferably Vogel's Approximation Method).

Step 3

If the number of allocations are $(m+n-1)$ then the solution is non-degenerate. Goto next step. If the number of allocations are $< (m+n-1)$ then the solution is degenerate. Then allocate $\varepsilon$ in a row or column which cross off simultaneously. And make the number of allocation equals $(m+n-1)$. Go to next step.

Step 4

For all the basic cells (i.e., allocated cells), solve the system of equations $u_i +v_j = c_{ij}$, for all $i,j$ for which cell $(i,j)$ is the allocated cell, starting initially with some $u_i=0$. Enter these values of $u_i$ and $v_j$ on the transportation table.

Step 5

For all the non-basic (i.e., non-allocated cells) calculate cost difference $d_{ij} = c_{ij} -(u_i + v_j)$ and enter them in the upper left corners of the corresponding cells in brackets i.e., $(; )$.

Step 6

Apply optimality test :

  • if all $d_{ij} \geq 0$, the current basic feasible solution is optimal.
  • if at least one $d_{ij} < 0$, select the most negative $d_{ij}$ (say, $d_{rs}$ is most negative), then the variable $x_{rs}$ enters into the basis.

Step 7

Construct a closed loop that starts and ends at the cell $(r,s)$. Allocate an unknown quantity $+;\theta$, to the cell $(r,s)$ and assign $-\theta$ alternately at each corner of the loop.

Step 8

Obtain $\theta = \min \{ \text{ Allocation having }-\theta\}$. Prepare a new transportation table and allocate the amount $\theta$ depending upon the sign $(+$ or $-$) at each corner of the loop.

Step 9

Go to Step 4 and repeat the process until an optimal solution is obtained.