Analyzing Linear Programming Problem (LPP) Statements

Let's carefully examine each statement regarding Linear Programming Problems (LPPs) to determine which one is correct.

Evaluating LPP Statement 1: Unbounded Solutions

The first statement says: "A solution is unbounded in an LPP if all the feasible solutions of the problem fall within the boundary created by its constraints".

This statement is incorrect. An unbounded solution occurs when the objective function of the LPP can be increased or decreased infinitely without violating any constraints. This happens when the feasible region is unbounded, meaning it extends infinitely in some direction, allowing the objective function value to become arbitrarily large (for maximization) or arbitrarily small (for minimization).

If all feasible solutions fall within a bounded area, the problem has a bounded feasible region, and an optimal solution will exist (unless the feasible region is empty). Unbounded solutions are characterized by the feasible region extending indefinitely in a direction that improves the objective function.

Evaluating LPP Statement 2: Dual of Dual Problem

The second statement claims: "If A is a primal problem and B is its dual, then dual of B is not A".

This statement is incorrect. A fundamental property of duality in Linear Programming is that the dual of the dual of a primal problem is the original primal problem itself. If A is the primal LPP and B is its dual LPP, then the dual of B is always A. This relationship is symmetric.

Evaluating LPP Statement 3: Standard Form Constraints

The third statement suggests: "The constraints of an LPP in standard form is always expressed in less than and equal to form".

This statement is generally incorrect depending on the specific definition of "standard form" used. While some definitions of standard form for a maximization problem require all constraints (other than non-negativity) to be of the $\leq$ type, the most common definition used in the context of the Simplex method requires all constraints to be equalities ($\leq$) and all variables to be non-negative ($\geq 0$). Inequalities ($\leq$ or $\geq$) are converted to equalities by introducing slack or surplus variables. For example, $ax_1 + bx_2 \leq c$ becomes $ax_1 + bx_2 + s = c$ with $s \geq 0$. Therefore, constraints in standard form are typically equality constraints, not always less than and equal to form.

Evaluating LPP Statement 4: Multiple Optimum Solutions

The fourth statement posits: "If an LPP has two optimum solutions, then it has also infinite number of optimum solutions".

This statement is correct. If an LPP has two distinct optimal solutions, let's call them $\mathbf{x}_1^*$ and $\mathbf{x}_2^*$, where $\mathbf{x}_1^* \neq \mathbf{x}_2^*$. Since the feasible region of an LPP is a convex set, any point on the line segment connecting $\mathbf{x}_1^*$ and $\mathbf{x}_2^*$ is also a feasible solution. A point on this line segment can be represented as a convex combination: $$\mathbf{x}(\lambda) = \lambda \mathbf{x}_1^* + (1 - \lambda) \mathbf{x}_2^*, \quad \text{for } 0 \leq \lambda \leq 1$$ If $\mathbf{x}_1^*$ and $\mathbf{x}_2^*$ are optimal solutions with the same optimal objective value $Z^*$, the objective function is linear. For any $\lambda$ between 0 and 1, the objective value at $\mathbf{x}(\lambda)$ is: $$Z(\lambda) = c^T \mathbf{x}(\lambda) = c^T (\lambda \mathbf{x}_1^* + (1 - \lambda) \mathbf{x}_2^*) = \lambda (c^T \mathbf{x}_1^*) + (1 - \lambda) (c^T \mathbf{x}_2^*)$$ Since $c^T \mathbf{x}_1^* = Z^*$ and $c^T \mathbf{x}_2^* = Z^*$, we have: $$Z(\lambda) = \lambda Z^* + (1 - \lambda) Z^* = (\lambda + 1 - \lambda) Z^* = Z^*$$ So, every point on the line segment between $\mathbf{x}_1^*$ and $\mathbf{x}_2^*$ is also an optimal solution and is feasible. Since there are infinitely many values for $\lambda$ between 0 and 1, there are infinitely many such points, thus implying an infinite number of optimal solutions.

Conclusion on LPP Statements

Based on the analysis of each statement, the correct statement regarding a Linear Programming Problem (LPP) is that if an LPP has two optimum solutions, it then has an infinite number of optimum solutions.

Revision Table: Key LPP Concepts

Additional Information on LPP Properties

Understanding the properties of Linear Programming Problems is crucial for solving them and interpreting results. The feasible region of an LPP is always a convex polyhedron (it can be bounded or unbounded). The optimal solution(s), if they exist, will occur at one or more vertices of this feasible region. However, if multiple optimal solutions exist, they can form an entire edge or face of the polyhedron, leading to infinitely many optimal solutions between any two extreme optimal points.

The concept of duality is powerful in LPP. The optimal solution of the primal problem is related to the optimal solution of the dual problem. For example, according to the Duality Theorem, if the primal has a finite optimal solution, then the dual also has a finite optimal solution, and their optimal objective function values are equal.