Understanding Transportation Problems and Basic Feasible Solutions

A transportation problem is a special type of linear programming problem that deals with determining the most cost-effective way to transport goods from a set of sources to a set of destinations. We have 'm' sources (like factories) and 'n' destinations (like warehouses).

A solution to a transportation problem involves determining the quantity of goods to be shipped from each source to each destination. A feasible solution is one where the total quantity shipped from each source equals its supply capacity, and the total quantity received at each destination equals its demand requirement.

A basic feasible solution (BFS) is a feasible solution with a specific number of positive allocations (amounts being shipped). These positive allocations correspond to the basic variables in the linear programming formulation of the problem.

Degeneracy in Transportation Problems

A basic feasible solution in a transportation problem can be either degenerate or non-degenerate.

• Degenerate BFS: A basic feasible solution is called degenerate if the number of positive allocations is less than the required number of basic variables, which is typically \(m + n - 1\). This can happen when a basic variable has a value of zero. Degeneracy can cause issues when using methods like the stepping-stone method or MODI method to find the optimal solution, as it might not be possible to trace a unique closed loop.
• Non-degenerate BFS: A basic feasible solution is called non-degenerate if it contains exactly the required number of positive allocations.

Condition for a Non-Degenerate Basic Feasible Solution

For an \(m \times n\) transportation problem, a basic feasible solution is considered non-degenerate if and only if:

1. It contains exactly \(m + n - 1\) positive allocations (basic variables).
2. These \(m + n - 1\) positive allocations are in independent positions.

The condition of being in "independent positions" means that it's not possible to form a closed loop (or cycle) by connecting the cells with positive allocations using only horizontal and vertical lines. A closed loop involves moving from a cell with an allocation horizontally or vertically to another cell with an allocation, and eventually returning to the starting cell without moving diagonally.

If the allocations form a closed loop, it indicates linear dependence among the corresponding basic variables, which is not a characteristic of a true basic solution where the basic variables should be linearly independent.

Analyzing the Options

Let's look at the given options based on our understanding of a non-degenerate BFS:

Based on the definition, a non-degenerate basic feasible solution must have exactly \(m + n - 1\) positive allocations that are in independent positions. Option 2 correctly states both these requirements.

Conclusion on Non-Degenerate BFS

A basic feasible solution of an \(m \times n\) transportation problem is non-degenerate if it satisfies the conditions of having exactly \(m + n - 1\) positive allocations and these allocations are in independent positions, meaning they do not form a closed loop.

Revision Table: Transportation Problem BFS

Additional Information: Solving Transportation Problems

Finding the optimal solution to a transportation problem typically involves two phases:

1. Finding an Initial Basic Feasible Solution: Methods like the North-West Corner Rule, Least Cost Method, or Vogel's Approximation Method (VAM) are used to find a starting BFS. VAM usually provides a better initial solution closer to the optimum.
2. Improving the Solution to Optimality: Once an initial BFS is found, methods like the Stepping-Stone Method or the Modified Distribution (MODI) Method are used to check if the current solution is optimal and, if not, to find an improved solution by moving units into currently unallocated cells (non-basic variables) that can reduce the total cost. This process is repeated until no further cost reduction is possible. Degeneracy can sometimes complicate the application of these methods, requiring special handling like introducing a very small positive value (\(\epsilon\)) to make zero-value basic variables appear positive temporarily.