Transportation Problems Questions and Answers

Answer: A

The stepping stone method is used to optimise the initial feasible solution of a transportation problem. It checks the unused cells for an opportunity cost, by tracing a closed path of stones, and moves allocation to those cells if cost can be reduced. The initial solution itself is found by methods such as the north-west corner rule or the Vogel approximation method, so the fourth option is the wrong one, and unbalanced problems are handled by adding a dummy row or column.

Answer: A

The entering variable is \(x_{11}\) and the leaving variable is \(x_{24}\): \(x_{11}\) and \(x_{24}\).

Find \(u_{i}, v_{j}\) from \(u_{i} + v_{j} = c_{ij}\) on the basic cells, with \(u_{1} = 0\): \(v_{2} = 4\), \(u_{2} = -1\), \(v_{3} = 8\), \(v_{4} = 7\), \(u_{3} = -3\), \(v_{1} = 6\).

Reduced costs \(c_{ij} - u_{i} - v_{j}\) on the non-basic cells:

\[ \begin{aligned} x_{11} &: 3 - 0 - 6 = -3 \\ x_{33} &: 3 + 3 - 8 = -2 \\ x_{13}, x_{14} &: 0 \\ x_{21} &: 2,\quad x_{32}: 8 \end{aligned} \]

The most negative is \(x_{11}\), so it enters. Its loop is \(x_{11}(+), x_{12}(-), x_{22}(+), x_{24}(-), x_{34}(+), x_{31}(-)\). The minus cells hold 60, 20 and 40, so \(\theta = 20\) and \(x_{24}\) leaves.

The options entering \(x_{13}\) or \(x_{14}\) are wrong because those cells have zero reduced cost and would not lower the cost, and \(x_{33}\), at -2, is less negative than \(x_{11}\), at -3.

Answer: B

The answer is \(y = 6\) and \(d_{13} = 4\).

In the u-v (MODI) method the simplex multipliers satisfy \(\alpha_i + \beta_j = c_{ij}\) on the basic cells, and the relative cost of a non-basic cell is \(d_{ij} = c_{ij} - \alpha_i - \beta_j\). With \(x = 4\), cell (1,1) gives

\[ \begin{aligned} \alpha_1 + \beta_1 &= 4 + y = 10 \\ y &= 6 \end{aligned} \]

and the other three given cells agree: \(4 + 8 = 12\), \(5 + 6 = 11\), \(5 + 8 = 13\). Then \(\beta_3 = y + 5 = 11\), and

\[ d_{13} = 19 - 4 - 11 = 4. \]

\(d_{13} = 7\) comes from using \(\beta_2 = 8\) in place of \(\beta_3\), and \(y = 5\) fails the condition on cell (1,1). A positive \(d_{13}\) means bringing cell (1,3) into the basis would not lower the cost.

Answer: B

The given allocation is the Optimal solution.

It uses 6 cells, equal to m + n - 1 = 3 + 4 - 1, so it is a basic solution. Test it with the u-v (MODI) method, setting \(u_{1} = 0\) and using \(u_{i} + v_{j} = c_{ij}\) in the occupied cells:

\[ \begin{aligned} v_{1} &= 19,\ v_{4} = 10,\ u_{3} = 20 \\ v_{2} &= -12,\ u_{2} = 42,\ v_{3} = -2 \end{aligned} \]

The reduced costs \(c_{ij} - u_{i} - v_{j}\) of the empty cells are 42, 32, 9, 8, 1 and 52, all positive, so no reallocation can lower the cost and the solution is optimal (total cost 863). It is not the Vogel or least cost starting solution: both of those first fill cell (3, 2), the lowest-cost cell at 8, with all 8 units, not 6.

Answer: A

A basic feasible solution has \(m + n - 1\) basic variables.

A transportation problem with m sources and n destinations has \(m + n\) constraints (one per row total and one per column total). Because total supply equals total demand, one of these equations follows from the others, so only \(m + n - 1\) are independent, and a basic solution has that many basic variables, the allocated cells. A non-degenerate basic feasible solution has exactly \(m + n - 1\) positive allocations.

mn is the total number of cells, not the number in a basis. \(m + n\) ignores the redundant constraint, and \(m + n + 1\) has no basis at all.

Answer: C

Both statements are true.

If total supply equals total demand, a feasible solution always exists: for example \(x_{ij} = a_{i}b_{j}/T\) with \(T = \sum a_{i} = \sum b_{j}\) satisfies every row and column constraint and is non-negative. So (I) holds.

Conversely, with equality constraints, summing all row constraints gives \(\sum\sum x_{ij} = \sum a_{i}\) and summing all column constraints gives \(\sum\sum x_{ij} = \sum b_{j}\), so a feasible solution forces \(\sum a_{i} = \sum b_{j}\). Hence the condition is necessary as well as sufficient, and (II) holds too.

Answer: D

Vogel's method gives an initial cost of 114.

Supply 14 + 16 + 5 = 35 equals demand 6 + 10 + 15 + 4 = 35, so the problem is balanced. At each step, penalty = difference of the two lowest costs in a row or column; allocate to the cheapest cell of the line with the largest penalty.

1. Largest penalty 5 (row S2): cell S2-D3, cost 2, allocate 15; D3 done, S2 has 1 left.
2. Largest penalty 3 (column D4): cell S3-D4, cost 2, allocate 4; D4 done, S3 has 1 left.
3. Largest penalty 2 (row S1, tie with column D1): cell S1-D2, cost 4, allocate 10; D2 done, S1 has 4 left.
4. Only D1 remains (demand 6): S1 gives 4 at cost 6, S2 gives 1 at cost 8, S3 gives 1 at cost 4.

\[ \begin{aligned} \text{Cost} &= 15(2) + 4(2) + 10(4) \\ &\quad + 4(6) + 1(8) + 1(4) \\ &= 30 + 8 + 40 + 24 + 8 + 4 = 114 \end{aligned} \]

Breaking the tie in step 3 by column D1 instead leads to the same total. 124, 128 and 152 are what cruder starting rules such as the north-west corner method give.

Answer: D

The North-West Corner solution is degenerate, with cost ₹ 11,600.

Supply is 6 + 1 + 10 = 17 and demand is 7 + 5 + 3 + 2 = 17, so the problem is balanced. Starting at the top-left cell:

• P1 to D1: 6 (P1 exhausted, D1 needs 1 more)
• P2 to D1: 1 (P2 exhausted and D1 satisfied at the same time)
• P3 to D2: 5, P3 to D3: 3, P3 to D4: 2

\[ \begin{aligned} &6(2) + 1(1) + 5(8) + 3(15) + 2(9) \\ &= 12 + 1 + 40 + 45 + 18 = 116 \end{aligned} \]

The cost is 116 hundred rupees, ₹ 11,600. A basic solution needs \(m + n - 1 = 3 + 4 - 1 = 6\) occupied cells, but only 5 are used, because a row and a column were satisfied together at the second step. So the solution is degenerate, and the options calling it non-degenerate or costing ₹ 12,000 are wrong.

Answer: B

The solution is degenerate and optimal.

Supply (6 + 8 + 10 = 24) equals demand (4 + 6 + 8 + 6 = 24). A basic solution of a 3 × 4 problem needs m + n - 1 = 6 occupied cells, but this one has only 5: (F1, W2) = 6, (F2, W3) = 2, (F2, W4) = 6, (F3, W1) = 4 and (F3, W3) = 6. So it is degenerate.

To test optimality, place a zero allocation (epsilon) in cell (F1, W1) and solve \(u_i + v_j = c_{ij}\) on the six basic cells. Taking \(u_3 = 0\) gives \(v_1 = 0, v_3 = 2, u_2 = 0, v_4 = 0, u_1 = 1, v_2 = 1\).

The reduced costs \(c_{ij} - u_i - v_j\) of the empty cells are then 0 (F1, W3), 3 (F1, W4), 4 (F2, W1), 2 (F2, W2), 1 (F3, W2) and 1 (F3, W4). None is negative, so the solution is optimal, with total cost 12 + 4 + 0 + 0 + 12 = 28. Optimality can be tested once the degeneracy is resolved, so the last option is wrong too.

Answer: A

There are \(m + n - 1\) basic variables.

A transportation problem with \(m\) sources and \(n\) destinations has \(m + n\) supply and demand constraints, but because total supply equals total demand one of them is redundant. So only \(m + n - 1\) constraints are independent, and a basic feasible solution has \(m + n - 1\) basic variables (allocated cells).

\(m + n\) ignores the redundancy, \(m + n + 1\) has no basis, and \(mn\) is the total number of cells, most of which are non-basic. A solution with fewer than \(m + n - 1\) positive allocations is called degenerate.