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.
