Question

Solve a transportation problem using the method of multipliers.

Answer 1

The transportation problem is solved using vogel approximation method of multipliers-

Total number of supply constraints : 3
Total number of demand constraints : 3
Problem Table is

	D1	D2	D3		Supply
S1	4	8	9		150
S2	12	8	11		100
S3	10	6	9		250
Demand	50	150	300

Table 1

	D1	D2	D3		Supply	Row Penalty
S1	4	8	9		150	4=8-4
S2	12	8	11		100	3=11-8
S3	10	6	9		250	3=9-6
Demand	50	150	300
Column Penalty	6=10-4	2=8-6	0=9-9

The maximum penalty, 6, occurs in column D1.
The minimum cij in this column is c11 = 4.
The maximum allocation in this cell is min(150,50) = 50.
It satisfy demand of D1 and adjust the supply of S1 from 150 to 100 (150 - 50 = 100).

Table 2

	D1	D2	D3		Supply	Row Penalty
S1	4(50)	8	9		100	1=9-8
S2	12	8	11		100	3=11-8
S3	10	6	9		250	3=9-6
Demand	0	150	300
Column Penalty	--	2=8-6	0=9-9

The maximum penalty, 3, occurs in row S3.
The minimum cij in this row is c32 = 6.
The maximum allocation in this cell is min(250,150) = 150.
It satisfy demand of D2 and adjust the supply of S3 from 250 to 100 (250 - 150 = 100).

Table3

	D1	D2	D3		Supply	Row Penalty
S1	4(50)	8	9		100	9
S2	12	8	11		100	11
S3	10	6(150)	9		100	9
Demand	0	0	300
Column Penalty	--	--	0=9-9

The maximum penalty, 11, occurs in row S2.
The minimum cij in this row is c23 = 11.
The maximum allocation in this cell is min(100,300) = 100.
It satisfy supply of S2 and adjust the demand of D3 from 300 to 200 (300 - 100 = 200).

Table 4

	D1	D2	D3		Supply	Row Penalty
S1	4(50)	8	9		100	9
S2	12	8	11(100)		0	--
S3	10	6(150)	9		100	9
Demand	0	0	200
Column Penalty	--	--	0=9-9

The maximum penalty, 9, occurs in row S1.
The minimum cij in this row is c13 = 9.
The maximum allocation in this cell is min(100,200) = 100.
It satisfy supply of S1 and adjust the demand of D3 from 200 to 100 (200 - 100 = 100).

Table 5

	D1	D2	D3		Supply	Row Penalty
S1	4(50)	8	9(100)		0	--
S2	12	8	11(100)		0	--
S3	10	6(150)	9		100	9
Demand	0	0	100
Column Penalty	--	--	9

The maximum penalty, 9, occurs in row S3.

The minimum cij in this row is c33 = 9.

The maximum allocation in this cell is min(100,100) = 100.
It satisfy supply of S3 and demand of D3.


Initial feasible solution is

	D1	D2	D3		Supply	Row Penalty
S1	4(50)	8	9(100)		150	4 | 1 | 9 | 9 | -- |
S2	12	8	11(100)		100	3 | 3 | 11 | -- | -- |
S3	10	6(150)	9(100)		250	3 | 3 | 9 | 9 | 9 |
Demand	50	150	300
Column Penalty	6 -- -- -- --	2 2 -- -- --	0 0 0 0 9

The minimum total transportation cost =4×50+9×100+11×100+6×150+9×100=4000
Here, the number of allocated cells = 5 is equal to m + n - 1 = 3 + 3 - 1 = 5. This solution is non-degenerate