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