Understanding Duality in Linear Programming Problems (LPP)

Duality is a fundamental concept in linear programming. Every Linear Programming Problem (LPP), called the primal problem, is associated with another LPP called its dual problem. The primal and dual problems are closely related, and understanding this relationship provides significant insights into the structure and solution of LPPs.

Analyzing Statements on LPP Duality Properties

Let's examine each statement provided regarding the relationship between a primal LPP and its dual problem.

Statement (a): Simplex Table and Dual Solution

The statement says: "The final simplex table giving optimal solution of the primal also contains optimal solution of its dual in itself."

This statement is correct. A significant advantage of using the simplex method to solve a primal LPP is that the optimal solution for the dual problem can be directly obtained from the final optimal simplex tableau of the primal. Specifically, the values of the dual variables are often found in the entries of the objective function row (the Z or Cj-Zj row) under the columns of the slack, surplus, or artificial variables associated with the primal constraints. These values represent the 'shadow prices' of the resources or constraints.

For a maximization primal problem with $\le$ constraints and non-negative variables, the dual is a minimization problem. The optimal dual variable values are the coefficients in the Z-row corresponding to the slack variables in the final simplex table.

Thus, statement (a) accurately describes a property of the simplex method and duality.

Statement (b): Finite Optimal Solutions

The statement says: "If either the primal or the dual problem has a finite optimal solution, then the other problem also has a finite optimal solution."

This statement is correct and is a key part of the Strong Duality Theorem in linear programming. The theorem states that if both the primal and the dual problems have feasible solutions, then both problems have finite optimal solutions, and the optimal values of their objective functions are equal. That is, if $Z^*$ is the optimal objective value for the primal and $W^*$ is for the dual, then $Z^* = W^*$. Conversely, if one problem has a finite optimal solution, it implies that the other problem must also have a finite optimal solution with the same objective value.

This theorem establishes a strong link between the existence of finite optimal solutions for the primal and dual problems.

Therefore, statement (b) is true.

Statement (c): Unbounded and Infeasible Solutions

The statement says: "If either problem has an unbounded optimum solution, then the other problem has no feasible solution at all"

This statement is also correct. This property is derived from the relationship between primal and dual feasibility and optimality.

• If the primal problem has an unbounded objective function (e.g., maximization tending towards infinity), it means there are feasible solutions for the primal, but no upper bound exists for the objective value. In this scenario, the dual problem is guaranteed to have no feasible solution (it is infeasible). There are no values for the dual variables that can satisfy all dual constraints.
• Conversely, if the dual problem has an unbounded objective function (e.g., minimization tending towards negative infinity, depending on formulation), then the primal problem is guaranteed to have no feasible solution (it is infeasible).

It is important to note that it is possible for both the primal and the dual problem to be infeasible. However, the case described in statement (c) is also a valid duality relationship.

Thus, statement (c) is true.

Conclusion on Duality Statements

Based on the analysis:

• Statement (a) is correct, as the optimal dual solution can be found in the final primal simplex tableau.
• Statement (b) is correct, reflecting the strong duality theorem regarding finite optimal solutions.
• Statement (c) is correct, describing the relationship between one problem being unbounded and the other being infeasible.

All three statements (a), (b), and (c) accurately describe important properties of duality in Linear Programming Problems.

Revision Table: Key Duality Concepts

Additional Information on LPP Duality

Duality theory is a powerful tool in linear programming for several reasons:

• Alternative Perspective: It offers a different way to look at the same problem. Solving the dual can sometimes be computationally easier than solving the primal, especially if the dual has fewer constraints (which happens if the primal has many variables but few constraints).
• Economic Interpretation: In many practical applications, especially resource allocation problems, the dual variables have significant economic meaning. They represent the marginal value or 'shadow price' of the resources (constraints). The optimal value of a dual variable indicates how much the primal objective function would improve if the corresponding resource constraint were relaxed by one unit.
• Optimality Conditions: The Karush-Kuhn-Tucker (KKT) conditions, when applied to LPPs, essentially express the complementary slackness conditions between the primal and dual variables. These conditions state that at optimality, if a primal variable is positive, its corresponding dual constraint must be binding (satisfied as an equality), and if a dual variable is positive, its corresponding primal constraint must be binding.
• Sensitivity Analysis: Duality is crucial for performing sensitivity analysis, which examines how changes in the problem parameters (like objective coefficients or constraint right-hand sides) affect the optimal solution.

Understanding duality deepens the comprehension of LPP structure and provides valuable insights for analysis and decision-making.