transportation problem using Heuristic method-1 calculator

SolutionHelp

Solution

Solution provided by AtoZmath.com

1. A Company has 3 production facilities S1, S2 and S3 with production capacity of 7, 9 and 18 units (in 100's) per week of a product, respectively. These units are tobe shipped to 4 warehouses D1, D2, D3 and D4 with requirement of 5,6,7 and 14 units (in 100's) per week, respectively. The transportation costs (in rupees) per unit between factories to warehouses are given in the table below.

	D₁	D₂	D₃	D₄	Capacity
S₁	19	30	50	10	7
S₂	70	30	40	60	9
S₃	40	8	70	20	18
Demand	5	8	7	14	34

Find initial basic feasible solution for given problem by using
(a) North-West corner method
(b) Least cost method
(c) Vogel's approximation method
(d) obtain an optimal solution by MODI method
if the object is to minimize the total transportation cost.

2. Find an initial basic feasible solution for given transportation problem by using
(a) North-West corner method
(b) Least cost method
(c) Vogel's approximation method

	D₁	D₂	D₃	D₄	Supply
S₁	11	13	17	14	250
S₂	16	18	14	10	300
S₃	21	24	13	10	400
Demand	200	225	275	250

Example

1. Find Solution using Heuristic method-1
D1 D2 D3 D4 Supply
S1 19 30 50 10 7
S2 70 30 40 60 9
S3 40 8 70 20 18
Demand 5 8 7 14

Solution:
TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 4
Problem Table is

	`D_1`	`D_2`	`D_3`	`D_4`	Supply
`S_1`	19	30	50	10	7
`S_2`	70	30	40	60	9
`S_3`	40	8	70	20	18

Demand	5	8	7	14

Table-1

	`D_1`	`D_2`	`D_3`	`D_4`	Supply	Row Penalty (P)	Total (T)	P`xx`T
`S_1`	19	30	50	10	7	`9=19-10`	109	`981=9xx109`
`S_2`	70	30	40	60	9	`10=40-30`	200	`2000=10xx200`
`S_3`	40	8	70	20	18	`12=20-8`	138	`1656=12xx138`

Demand	5	8	7	14
Column Penalty (P)	`21=40-19`	`22=30-8`	`10=50-40`	`10=20-10`
Total (T)	129	68	160	90
P`xx`T	`2709=21xx129`	`1496=22xx68`	`1600=10xx160`	`900=10xx90`

The lowest PT = 900, occurs in column `D_4`.

The minimum `c_(ij)` in this column is `c_14` = 10.

The maximum allocation in this cell is min(7,14) = 7.
It satisfy supply of `S_1` and adjust the demand of `D_4` from 14 to 7 (14 - 7 = 7).

Table-2

	`D_1`	`D_2`	`D_3`	`D_4`	Supply	Row Penalty (P)	Total (T)	P`xx`T
`S_1`	19	30	50	10(7)	0	--	109	--
`S_2`	70	30	40	60	9	`10=40-30`	200	`2000=10xx200`
`S_3`	40	8	70	20	18	`12=20-8`	138	`1656=12xx138`

Demand	5	8	7	7
Column Penalty (P)	`30=70-40`	`22=30-8`	`30=70-40`	`40=60-20`
Total (T)	129	68	160	90
P`xx`T	`3870=30xx129`	`1496=22xx68`	`4800=30xx160`	`3600=40xx90`

The lowest PT = 1496, occurs in column `D_2`.

The minimum `c_(ij)` in this column is `c_32` = 8.

The maximum allocation in this cell is min(18,8) = 8.
It satisfy demand of `D_2` and adjust the supply of `S_3` from 18 to 10 (18 - 8 = 10).

Table-3

	`D_1`	`D_2`	`D_3`	`D_4`	Supply	Row Penalty (P)	Total (T)	P`xx`T
`S_1`	19	30	50	10(7)	0	--	109	--
`S_2`	70	30	40	60	9	`20=60-40`	200	`4000=20xx200`
`S_3`	40	8(8)	70	20	10	`20=40-20`	138	`2760=20xx138`

Demand	5	0	7	7
Column Penalty (P)	`30=70-40`	--	`30=70-40`	`40=60-20`
Total (T)	129	68	160	90
P`xx`T	`3870=30xx129`	--	`4800=30xx160`	`3600=40xx90`

The lowest PT = 2760, occurs in row `S_3`.

The minimum `c_(ij)` in this row is `c_34` = 20.

The maximum allocation in this cell is min(10,7) = 7.
It satisfy demand of `D_4` and adjust the supply of `S_3` from 10 to 3 (10 - 7 = 3).

Table-4

	`D_1`	`D_2`	`D_3`	`D_4`	Supply	Row Penalty (P)	Total (T)	P`xx`T
`S_1`	19	30	50	10(7)	0	--	109	--
`S_2`	70	30	40	60	9	`30=70-40`	200	`6000=30xx200`
`S_3`	40	8(8)	70	20(7)	3	`30=70-40`	138	`4140=30xx138`

Demand	5	0	7	0
Column Penalty (P)	`30=70-40`	--	`30=70-40`	--
Total (T)	129	68	160	90
P`xx`T	`3870=30xx129`	--	`4800=30xx160`	--

The lowest PT = 3870, occurs in column `D_1`.

The minimum `c_(ij)` in this column is `c_31` = 40.

The maximum allocation in this cell is min(3,5) = 3.
It satisfy supply of `S_3` and adjust the demand of `D_1` from 5 to 2 (5 - 3 = 2).

Table-5

	`D_1`	`D_2`	`D_3`	`D_4`	Supply	Row Penalty (P)	Total (T)	P`xx`T
`S_1`	19	30	50	10(7)	0	--	109	--
`S_2`	70	30	40	60	9	`30=70-40`	200	`6000=30xx200`
`S_3`	40(3)	8(8)	70	20(7)	0	--	138	--

Demand	2	0	7	0
Column Penalty (P)	`70`	--	`40`	--
Total (T)	129	68	160	90
P`xx`T	`9030=70xx129`	--	`6400=40xx160`	--

The lowest PT = 6000, occurs in row `S_2`.

The minimum `c_(ij)` in this row is `c_23` = 40.

The maximum allocation in this cell is min(9,7) = 7.
It satisfy demand of `D_3` and adjust the supply of `S_2` from 9 to 2 (9 - 7 = 2).

Table-6

	`D_1`	`D_2`	`D_3`	`D_4`	Supply	Row Penalty (P)	Total (T)	P`xx`T
`S_1`	19	30	50	10(7)	0	--	109	--
`S_2`	70	30	40(7)	60	2	`70`	200	`14000=70xx200`
`S_3`	40(3)	8(8)	70	20(7)	0	--	138	--

Demand	2	0	0	0
Column Penalty (P)	`70`	--	--	--
Total (T)	129	68	160	90
P`xx`T	`9030=70xx129`	--	--	--

The lowest PT = 9030, occurs in column `D_1`.

The minimum `c_(ij)` in this column is `c_21` = 70.

The maximum allocation in this cell is min(2,2) = 2.
It satisfy supply of `S_2` and demand of `D_1`.

Initial feasible solution is

	`D_1`	`D_2`	`D_3`	`D_4`	Supply	Row Penalty (P)	Total (T)	P`xx`T
`S_1`	19	30	50	10(7)	7	9 \| -- \| -- \| -- \| -- \| -- \|	109	981 \| -- \| -- \| -- \| -- \| -- \|
`S_2`	70(2)	30	40(7)	60	9	10 \| 10 \| 20 \| 30 \| 30 \| 70 \|	200	2000 \| 2000 \| 4000 \| 6000 \| 6000 \| 14000 \|
`S_3`	40(3)	8(8)	70	20(7)	18	12 \| 12 \| 20 \| 30 \| -- \| -- \|	138	1656 \| 1656 \| 2760 \| 4140 \| -- \| -- \|

Demand	5	8	7	14
Column Penalty (P)	21 30 30 30 70 70	22 22 -- -- -- --	10 30 30 30 40 --	10 40 40 -- -- --
Total (T)	129	68	160	90
P`xx`T	2709 3870 3870 3870 9030 9030	1496 1496 -- -- -- --	1600 4800 4800 4800 6400 --	900 3600 3600 -- -- --

The minimum total transportation cost `= 10 xx 7 + 70 xx 2 + 40 xx 7 + 40 xx 3 + 8 xx 8 + 20 xx 7 = 814`

Here, the number of allocated cells = 6 is equal to m + n - 1 = 3 + 4 - 1 = 6
`:.` This solution is non-degenerate