USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

INITIAL BASIC SOLUTION BY NW CORNER METHOD

 

Project

Plant

A

B

C

Plant capacity

W

4

56

8

8

56

X

17

16

24

66

16

82

Y

16

36

24

41

77

72

102

41

215

 

Total cost of initial solution

Since the stone squares are 5 as against the nm requirements m+1-1

3+3-1 =5

The above solution is non degenerate

Now we proceed to test its optimality by stepping stone method.

We have traced a closed loop or path for each of unused square i.e., opportunity cost of square is determined next

To

From

Project

A

Project

B

Project

C

Plant

Capacity

W

4

56

8

8

56

X

16

16

24

60

16

82

Y

8

16

36

24

41

77

Project Requirement

72

102

41

215

On the basis of closed loop

WC =WC-WA+XA-XB+4I3-4C

=8-4+ 16-24+ 16-24= -12.

Now tracing a closed loop for cell XC

To

From

A

B

C

W

4

56

8

8

56

X

16

16

24

66

16

82

Y

8

16

36

24

41

77

72

102

41

215

 

WC = WC- WA + XA-XB + YB – YC

=8-4 + 16-24 + 16- 24 =-12.

Now the IInd improved table is as under

To

From

Project

A

Project

B

Project

C

W

4

56

8

8

56

X

16

24

25

16

41

82

77

Y

8

16

77

24

72

102

41

215

 

Associated transportation costs is

56 × 4 + 16 × 16 + 25 × 24 + 41 × 16 + 77 × 16 = 2968.

Closed paths and improvement index, for unused square

WB      8 – 4 + 16 – 24 =-4

WC      8-4+16-16=4

YA       8 – 16 + 24 – 16 = 0

YC       M-16+M-16=16

The most –ve opportunity cost is – 4 in the cell WB

The closed path

WB

56

WB

←                                                                +

16+

↓                                                                  ↑

25

 

To

From

A

B

C

Plant capacity

W

4

4

8

56

8 56

X

16

41

24

0

16

41

82

Y

8

31

16

46

24

16

77

72 102 41 215

Closed path

WA     4-8+16+8=4

WC      8-16+16-8+16-8=8

XB       24 – 16 + 8 – 16 = 0

YC       24-16+16-8=16

Total cost of optimal solution

56 × 8+41 × 16+41× 16+31 × 8+46 × 16=2744

The opportunity cost of XB cell is zero it means there exists an alternative solution where shipping assignment will change.

WB 56 × 8 +41 × 24+41× 16 +72 × 8+5 × 16=2744.

Example 5.10. The above problem can also be solved with the help of MODI method.

Kj

Rj

K1

K2

K3

To

From

A

B

C

Plant capacity

R1

W 4

56

8 8

56

R2

X 16

16

24

66

16

82

R3

Y 8 16

36

24

41

77

  72 102 41

215

 

For each square we use the following formula to find its cost.

Ri+ Kj= Cij

Ri + K1 =4

R2 + K1 = 16

R2+ K2 = 24

R3+ K2 = 16

R3 + K3 = 24

R1 =0 then

R1 +K1 =4

0+ K1 =4

K1 =4

R1 + K1 = 16

R1+4 = 16

R2 = 12

Similarly R3 + K2 = 16

R3 + 12 = 16

R3 =4

R2 + K2 = 24

12 + K2 = 24

K2 = 12

R3+K3=24

4 + K3 = 24

K3=20

 

Kj

Rj

K1=4

K2=12

K3=20

To

From

Project

A

Project

B

Project

C

Plant capacity

R1=0

W 4

56

8 8

56

R2=12

X 16

16

24

66

16

82

R3=4

Y 8 16

36

24

41

77

  72 102 41

215

 

Unused squares

Cij-R1-K1

Improvement index

1 → 2

C12-R-K2

8-0-12

-4

1 → 3

C13-R1-K3

8-0-20

-12

2 → 3

C23-R2-K3

16-12-20

-16

3 → 1

C31 – R3 – K1

8-4-4

0

The value of water square 23 is most -ve we draw closed loop through this cell and the new table will be

 

Kj

Rj

K1=4

K2=12

K3=20

To

From

Project

A

Project

B

Project

C

Plant capacity

R1=0

W 4

56

8

-4

8

-12

56

R2=12

X 16

16

24

66

16+

-16

82

R3=4

Y 8

0

16

36

24

-41

77

Project requirement 72 102 41

215

 

Kj

Rj

K1=4

K2=12

K3=20

To

From

Project

A

Project

B

Project

C

Plant capacity

R1=0

W 4

56

8

-4

8

+4

56

R2=12

X 16

16

24

25

16

41

82

R3=4

Y 8

0

16

77

24

12

77

  72 102 41

215

Calculation of opportunity cost of water squares is as given

Unused squares

Cij=Ri-Kj

Improvement index

1 → 2

C12-R1-K2

8-0-12

-4

1 → 3

C13-R1-K3

8-0-4

+4

3 → 1

C31-R3-K1

8-4-4

0

3 → 3

C33-R3-K3

24-4-4

+ 16

The opportunity cost of cell I → 2 is –ve

 

Kj

Rj

K1=4

K2=8

K3=4

To

From

Project

A

Project

B

Project

C

Plant capacity

R1=0

W 4

31

8

25

8

+4

56

R2=12

X 16

41

24

4

16

41

82

R3=8

Y 8

-4

16

77

24

12

77

  72 102 41

215

The value of cell 3 → 1 is – ve in the improved solution.

 

Kj

Rj

K1=0

K2=8

K3=0

To

From

A

B

C

Plant capacity

R1=0

W 4

+4

8

56

8

8

56

R2=16

X 16

41

24

0

16

41

82

R3=8

Y 8

31

16

46

24

16

77

  72 102 41

215

 

Total cost of optimal solution

Shipping assignment

Quantities shipped

Limit cost

Total cost

WB

XA

XC

YA

YB

56

41

41

31

46

8

16

16

8

16

448

656

656

258

730

2744

 

Example 5.11. A company has 4 different locations in the country and 4 sales agencies in 4 other locations in the country. The cost of production, the sale price, shipping cost in the cells of the matrix, monthly capacities and monthly requirement are given below:

Factory

1

2

3

4

Capacity

Cost of production

A

B

C

D

7

3

4

8

5

5

6

7

6

4

4

6

2

2

5

5

10

15

20

15

10

15

16

15

Monthly requirement

8

12

18

22

Selling price

20

22

25

18

 

Find the monthly production and distribution schedule which will maximise profits.

Sol. By adding cost of production and shipping cost of each cell, the total cost of matrix is

I

II

III

IV

A

17

15

16

14

B

18

20

19

17

C

20

22

20

21

D

23

22

21

20

 

By deducting cost of production from sales price of each agency, of we get profit matrix.

Profit matrix

I

II

III

IV

A

B

C

D

3

2

0

-3

7

2

0

0

9

6

5

4

4

1

-3

-2

 

Let us convert the matrix into a minimization matrix by deducting each element from the maximum profit i.e. Rs. 9.

Sales

Factory

SI

SII

SIII

SIV

Capacity

FA

FB

FC

FD

6

7

9

12

2

7

9

9

0

3

4

5

5

8

12

11

10

15

20

15

Required

8

12

18

22

60

 

Initial Feasible Solution

Sales

Factory

S1

S2

S3

S4

Capacity

UP1

UP2

UP3

UP4

FA 6 2

10

0 5 10 2 - - -
FB 7 7 3 8

15

15 4 4 0 -
FC 9

2

9 4

18

12 20 5 5

0 0
FD 12

6

9

2

5 11

7

15 4 4 2 2
Req. 8 12 18 12 60        
UP1 1 5↑ 3 3          
UP2 2 2 1 3          
UP3 2 2 - 3 ↑          
UP4 3 ↑ 0 - -          

 

The stone squares, are equal to rim requirement.

The stone squares are 7 = Rim requirement 7

The above solution is non-degenerate, we proceed to test its optimality by MODI method.

The optimality by MODI method

Kj

Ri

K1=12

K2=9

K3=7

K4=11

Ag

Fact

S1

S2

S3

S4

Capacity

K1=-7 FA 6

1

2

10

0

0

5

1

10
K2=-3 FB 7

-2

7

1

3

1

8

15

15
K3=-3 FC 9+

2

9

3

4

18

12

4

20
K4=0 FD 12

-6

9

2

5

+   -2

11

7

 

 

 

Kj

Ri

K1=10

K2=9

K3=5

K4=11

Ag

Fact

1

2

3

4

Capacity

K1=-7 A 6

3

2

10

0

2

5

1

10
K2=-3 B 6

3

2

10

0

2

5

1

10
K3=-1 C 9

8

9

1

4

12

12

2

20
K4=0 D 12

2

9

2

5

6

11

7

15
    8 12 18 22 60

 

The final improved matrix is

S1

S2

S3

S4

Capacity

FA

3 7

10

9 4

10

FB

2 2 6 1

15

15

FC

0 0 5

12

-3

20

FD

-3 0

2

4

6

-2

7

15

Requirement

8

12

18

22

60

 

The opportunity cost of all water squares is +ve. So the solution is optimum

Factory → 7 Sales Agency = Total profit

FA→S2=7×10 =70

FB →S4=1 × 15 =15

FC → S1 = 0 × 8 = 0

FD → S3 = 5 × 12 = 60

FD→S2 = 0 × 2 = 0

FD →S3 = 4 × 4 = 24

FD → S4 =-2 × 7 =-14

Total profit = 155/-

Example 5.12 A transport corporation has trucks at 3 garages ABC in a city. The number of trucks available in each garage, the number of trucks required by each customer and the distance from garage to customer’s locations are given below:

Customers

1

2

3

4

Availabilities

Garages

A

B

C

7

8

10

6

6

7

9

7

8

12

10

12

12

8

10

Requirement

4

3

5

8

 

Just before sending the trucks, it is known that road from B to customers 2 is closed for traffic due to road block. How should the trucks be assigned to the customers in order to minimize the total distance to be covered due to road block?

Sol. The problem is unbalanced, we add dummy with 0 transportation cost and assign M prohibited cell

 

To

From

1

2

3

4

Dummy

Capacity

UP1

UP2

UP3

UP4

A

7

4

6

3

9

5

12 0

12

6

1

1

2

B

8 M 7 10

8

0

8

1

1

1

1

C

10 7 8 12 0

10

10

7

-

-

-

Req.

4

3

5

8

10

30

UP1

1

1

1

2

0

UP2

1

M-7↑

1

2

-

UP3

1

-

1

-

-

UP4

1

-

1

-

-

 

The stone square = 5

Rim requirement

m+n-1

3+5-1=7

The above problem is of degeneracy

We introduce e at two cells and list its optimality by MODI-method

Kj

Ri

K1=7

K2=6

K3=9

K4=12

K5=0

 

1 2 3 4 0 cap.
R1=0

A

7

4

6

3

9

5

12

0

0