Question

The solution to a transportation problem with \( m \)-rows (supplies) and \( n \)-columns (destinations) is feasible if number of positive allocations are

• A. \( m + n \)
• B. \( m \times n \)
• C. \( m + n - 1 \)
• D. \( m + n + 1 \)

Hint:

In a transportation problem, a basic feasible solution has \( m + n - 1 \) positive allocations, corresponding to the number of independent constraints (supply and demand equations minus one redundancy).

Answer 1

The Correct Option is C

Step 1: Understand the transportation problem.
A transportation problem is a type of linear programming problem where the goal is to minimize the cost of transporting goods from \( m \) sources (supplies) to \( n \) destinations (demands). The problem is represented as a table with \( m \) rows and \( n \) columns, where each cell represents the amount transported from a source to a destination (an allocation). Step 2: Define a feasible solution in a transportation problem.
A feasible solution must satisfy:
The supply constraints: The total amount shipped from each source must equal its supply.
The demand constraints: The total amount received at each destination must equal its demand.
Non-negativity: All allocations must be non-negative.
For the solution to be feasible and non-degenerate, the allocations must form a basic feasible solution.
Step 3: Determine the number of positive allocations for a basic feasible solution.
In a transportation problem with \( m \) sources and \( n \) destinations, there are:
\( m \) supply constraints,
\( n \) demand constraints.
However, these constraints are not all independent: The sum of supplies equals the sum of demands (a balanced transportation problem), so one constraint is redundant.
The total number of independent constraints is \( m + n - 1 \). In linear programming, a basic feasible solution has the number of positive variables (allocations) equal to the number of independent constraints.
Therefore, a basic feasible solution to a transportation problem has exactly \( m + n - 1 \) positive allocations (non-zero entries in the transportation table).
If the number of positive allocations is less than \( m + n - 1 \), the solution is degenerate. If it is more, the solution is not a basic feasible solution.
Step 4: Evaluate the options.
(1) \( m + n \): Incorrect, as this overestimates the number of independent constraints by 1 (it does not account for the redundancy). Incorrect.
(2) \( m \times n \): Incorrect, as this is the total number of cells in the table, not the number of positive allocations needed for a basic feasible solution. Incorrect.
(3) \( m + n - 1 \): Correct, as this matches the number of independent constraints, which determines the number of positive allocations in a basic feasible solution. Correct.
(4) \( m + n + 1 \): Incorrect, as this exceeds the number of independent constraints. Incorrect.
Step 5: Select the correct answer.
The solution to a transportation problem is a basic feasible solution if the number of positive allocations is \( m + n - 1 \), matching option (3).