Machine-translated by Google. Questions are authored in English.
Top

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.

Please log in or register to report this question.

2.

The following table gives the unit transportation costs, the supply at each origin and the demand of each destination for a transportation problem.

Origin / DestinationD1D2D3D4Supply
O1348760
O2737680
O33934100
Demand40705080

Let \(x_{ij}\) denote the number of units to be transported from origin \(i\) to destination \(j\). If the u-v method is applied to improve the basic feasible solution given by \(x_{12} = 60,\ x_{22} = 10,\ x_{23} = 50,\ x_{24} = 20,\ x_{31} = 40\) and \(x_{34} = 60\), then the variables entering and leaving the basis, respectively, are

Exam Year(s)

GATE Mathematics - 2012,

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.

Please log in or register to report this question.

3.

For a transportation problem, let \(c_{ij}\) denote the unit cost of the cell \((i, j)\). Assume that \(c_{11} = 10\), \(c_{12} = 12\), \(c_{21} = 11\) and \(c_{22} = 13\). Let \(\alpha_i\) and \(\beta_j\), \(i, j = 1, 2, 3\), represent the simplex multipliers associated with any basis corresponding to the unit cost \(c_{ij}\). Assume that \(\alpha_1 = x\), \(\alpha_2 = x + 1\), \(\beta_1 = y\) and \(\beta_2 = y + 2\). The relative cost coefficient \(d_{ij}\) is the difference between the current solution and the new improved solution.

If \(x = 4\), \(c_{13} = 19\) and \(\beta_3 = y + 5\), then which one of the following is TRUE?

Exam Year(s)

GATE Mathematics - 2026,

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.

Please log in or register to report this question.

4.

Consider the following tansportation problem :

F1F2F3F4
W1193030107
W2703040609
W3408703018
5871434

(Columns: Factory F1 to F4; rows: Warehouse W1 to W3.)

Let Xij be the allocation in the (i, j)th cell. The solution (x11 = 5, x14 = 2, x22 = 2, x23 = 7, x32 = 6, x34 = 12) is :

Exam Year(s)

MH SET - 2018, SET Exam - 2018,

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.

Please log in or register to report this question.

5.

The number of non-negative variables in a basic feasible solution to a \(m \times n\) transportation problem is :

Exam Year(s)

MH SET - 2018, SET Exam - 2018,

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.

Please log in or register to report this question.

6.

Consider the transportation problem

Min. \(z = \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}x_{ij}\)

Subject to :
\(\sum_{j=1}^{n} x_{ij} = a_{i}, i = 1, 2, ....., m,\)
\(\sum_{i=1}^{m} x_{ij} = b_{j}, j = 1, 2, ....., n\) and \(x_{ij} \ge 0\)

The existence of a feasible solution of the transportation problem is possible :

(I) if \(\sum_{i=1}^{m} a_{i} = \sum_{j=1}^{n} b_{j}\)
(II) if and only if \(\sum_{i=1}^{m} a_{i} = \sum_{j=1}^{n} b_{j}\)

Then which of the following is true ?

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

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.

Please log in or register to report this question.

7.

Consider the following transportation problem :

Destinations
SourcesD1D2D3D4
S1641514
S2892716
S343625
610154

The initial transportation cost by Vogel's method is :

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

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.

Please log in or register to report this question.

8.

A dairy firm has three plants \(P_{1}, P_{2}, P_{3}\) located in a state. They daily milk production at each plant (in thousand liters) is \(P_{1} \to 6\), \(P_{2} \to 1\), \(P_{3} \to 10\). Each day, the firm must fulfil the needs of its four distribution centers \(D_{1}, D_{2}, D_{3}, D_{4}\). The minimum requirement at each center (in thousand liters) is \(D_{1} \to 7\), \(D_{2} \to 5\), \(D_{3} \to 3\), \(D_{4} \to 2\). Cost in hundred of rupees of shipping one thousand liters from each plant to each distribution center is given below :

PlantD1D2D3D4
P123117
P21061
P358159

Then the initial basic feasible by North-West Corner method is :

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

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.

Please log in or register to report this question.

9.

Consider the following transportation problem :

Warehouse
FactoryW1W2W3W4
F112346
F243208
F3022110
4686

A solution to the problem is given below :

6
26
46

Which of the following is true about the solution ?

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

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.

Please log in or register to report this question.

10.

The number of basic variables in an \((m \times n)\) transportation table are :

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

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.

Please log in or register to report this question.

Loading…

Other Subjects

Tags: Transportation Problems Questions and Answers || Transportation Problems MCQ Questions and Answers || Transportation Problems GK Questions and Answers || Transportation Problems GK MCQ Questions || Transportation Problems Multiple Choice Questions and Answers || Transportation Problems GK || GK on Transportation Problems || Operations Research Questions and Answers || Operations Research MCQ Questions and Answers || Operations Research GK Questions and Answers || GK on Operations Research