Answer to Question #203358 in Operations Research for Raghav

Question

Find the initial basic feasible solution of the following transportation problem using North- West corner method:

P₁ P₂ P₃ P₄ Requirement

M₁ 19 11 23 11 11

M₂ 15 16 12 21 13

M₃ 30 25 16 39 19

Availability 6 10 12 15 113

Also, find the optimal solution.

Answer 1

Solution.

The cost of delivery of a unit of cargo from each point of departure to the corresponding points of destination is specified by the tariff matrix

Let us check a necessary and sufficient condition for the solvability of the problem.

∑p = 11 + 13 + 19 = 43

∑m = 6 + 10 + 12 + 15 = 43

The balance condition is met. Stocks are equal to needs. Consequently, the transport problem model is closed.

Using the northwest corner method, we will construct the first basic plan of the transport problem.

The plan starts to fill in from the top left corner.

The required element is c11 = 19. For this element, stocks are 11, requirements are 6. Since the minimum is 6, we subtract it.

x11 = min (11.6) = 6.

The required element is equal to c12 = 11. For this element, stocks are 5, requirements are 10. Since the minimum is 5, we subtract it.

x12 = min (5,10) = 5.

The required element is c22 = 16. For this element, stocks are 13, requirements are 5. Since the minimum is 5, we subtract it.

x22 = min (13.5) = 5.

The required element is equal to c23 = 12. For this element, stocks are 8, requirements are 12. Since the minimum is 8, we subtract it.

x23 = min (8.12) = 8.

The required element is c33 = 16. For this element, stocks are 19, requirements are 4. Since the minimum is 4, we subtract it.

x33 = min (19.4) = 4.

The required element is c34 = 39. For this element, stocks are 15, requirements are 15. Since the minimum is 15, we subtract it.

x34 = min (15.15) = 15.

As a result, the first baseline plan was obtained, which is admissible, since all cargoes have been removed from the bases, the needs of the stores are satisfied, and the plan corresponds to the system of restrictions of the transport problem.

Let's count the number of occupied cells of the table, there are 6 of them, and there should be m + n - 1 = 6. Therefore, the support plan is non-degenerate.

The objective function value for this baseline is:

F (x) = 19 * 6 + 11 * 5 + 16 * 5 + 12 * 8 + 16 * 4 + 39 * 15 = 994.

We will check optimality of the basic plan by means of the computer program. We will have

The minimum costs will be: F (x) = 11 * 11 + 15 * 6 + 16 * 3 + 21 * 4 + 25 * 7 + 16 * 12 = 710.