Question

Explain Vogel’s approximation method by obtaining initial feasible solution of the following transportation problem.

	D1	D2	D3	D4	Supply
O1	2	3	11	7	6
O2	1	0	6	1	1
O3	5	8	15	9	10
Demand	7	5	3	2

Answer 1

Let ‘a_i‘ denote the supply and ‘b_j‘ denote the demand `sum"a"_"i"` = 6 + 1 + 10 = 17 and `sum"b"_"j"` = 7 + 5 + 3 + 2 = 17

`sum"a"_"i" = sum"b"_"j"`

i.e Total supply = Total demand.

The given problem is a balanced transportation problem. Hence there exists a feasible solution to the given problem.

First, we find the difference (penalty) between the first two smallest costs in each row and column and write them in brackets against the respective rows and columns.

First allocation:

	D1	D2	D3	D4	(ai)	Penalty
O1	2	3	11	7	6	(1)
O2	1	0	6	(1)1	1/10	(1)
O3	5	8	15	9	10	(3)
(bj)	7	5	3	2/1
Penalty	(1)	(3)	(5)	(6)

The largest difference is 6 corresponding to column D₄.

In this column least cost is (O₂, D₄).

Allocate min (2, 1) to this cell.

Second allocation:

	D1	D2	D3	D4	(ai)	Penalty
O1	2	(5)3	11	7	6/1	(1)
O3	5	8	15	9	10	(3)
(bj)	7	5/0	3	2/1
Penalty	(3)	(5)	(4)	(2)

The largest difference is 5 in column D₂.

Here the least cost is (O₁, D₂).

So allocate min (5, 6) to this cell.

Third allocation:

	D1	D3	D4	(ai)	Penalty
O1	(1)2	11	7	1/0	(5)
O3	5	15	9	10	(4)
(bj)	7/6	3	1
Penalty	(3)	(4)	(2)

The largest penalty is 5 in row O₁.

The least cost is in (O₁, D₁).

So allocate min (7, 1) here.

Fourth allocation:

	D1	D3	D4	(ai)	Penalty
O3	(6)5	15	9	10/4	(4)
(bj)	6/0	3	1
Penalty	–	–	–

Fifth allocation:

	D3	D4	(ai)	Penalty
O3	(3)15	(1)9	4/3/0	(6)
(bj)	3/0	1/0
Penalty	–	–

We allocate min (1, 4) to (O₃, D₄) cell since it has the least cost.

Finally the balance we allot to cell (O₃, D₃).

Thus we have the following allocations:

	D1	D2	D3	D4	(ai)
O1	(1)2	(5)3	11	7	6
O2	1	0	6	(1)1	1
O3	(6)5	8	(3)15	(1)9	10
(bj)	7	5	3	2

Transportation schedule:

O₁ → D₁

O₁ → D₂

O₂ → D₄

O₃ → D₁

O₃ → D₃

O₃ → D₄

i.e x₁₁ = 12

x₁₂ = 5,

x₂₄ = 1

x₃₁ = 6

x₃₃ = 3

x₃₄ = 1

Total cost = (1 × 2) + (5 × 3) + (1 × 1) + (6 × 5) + (3 × 15) + (1 × 9)

= 2 + 15 + 1 + 30 + 45 + 9

= 102