Duality

Duality in linear programming (LP) refers to a set of relationships between the primal LP problem and its associated dual problem. The primal problem involves maximizing or minimizing a linear objective function subject to linear constraints, while the dual problem involves minimizing or maximizing a linear function subject to linear constraints.

The dual problem is obtained by constructing a new LP problem based on the constraints and objective function of the primal problem. The variables in the dual problem correspond to the constraints in the primal problem, and vice versa. The objective function in the dual problem is a function of the dual variables, and it is derived from the objective function in the primal problem.

The duality theorem states that the optimal solution of the primal problem is equal to the optimal solution of the dual problem. This means that if one problem is solved, the optimal solution of the other problem can be determined without solving it directly. The duality theorem also implies that if the primal problem is a maximization problem, then the dual problem is a minimization problem, and vice versa.

The dual problem has several important properties, including:

Weak Duality: The optimal value of the dual problem is always less than or equal to the optimal value of the primal problem.

Strong Duality: If the primal problem has an optimal solution, then the dual problem also has an optimal solution, and the optimal values of both problems are equal.

Complementary Slackness: If a constraint in the primal problem is binding (i.e., holds with equality), then the corresponding dual variable is positive.

Similarly, if a constraint in the dual problem is binding, then the corresponding primal variable is positive.

Duality has many applications in LP, including sensitivity analysis, optimization of dual variables, and integer programming. It provides a powerful tool for understanding and solving LP problems, and it is a fundamental concept in optimization theory.