Aspects of OR - Linear Programming (Part 3)

In Part 1 we formulated linear programs and in Part 2 we solved them with the simplex method. In this final part of the LP mini-series, we turn to one of the most elegant concepts in optimization: duality. Every linear program has a companion problem — its dual — and the relationship between the two reveals deep structural insights. Duality is not just a theoretical curiosity; it has direct practical applications in sensitivity analysis, pricing, and algorithm design.

The dual problem

Consider a primal LP in standard form:

$\text{(P)} \quad \min \; c^T x \quad \text{subject to} \quad Ax \geq b, \quad x \geq 0.$

The dual of this LP is:

$\text{(D)} \quad \max \; b^T y \quad \text{subject to} \quad A^T y \leq c, \quad y \geq 0.$

Here $y \in \mathbb{R}^m$ is the vector of dual variables — one for each primal constraint. The construction is systematic: every primal constraint gives rise to a dual variable, and every primal variable gives rise to a dual constraint. The primal objective coefficients become the dual right-hand side, and vice versa.

The following table summarizes the correspondence:

An important property: the dual of the dual is the primal. So duality is a symmetric relationship.

Weak duality

The first key result is weak duality: for any primal feasible $x$ and any dual feasible $y$,

$b^T y \leq c^T x.$

This says that every dual feasible solution provides a lower bound on the primal optimal value, and every primal feasible solution provides an upper bound on the dual optimal value. The proof is a short chain of inequalities:

$b^T y \leq (Ax)^T y = x^T A^T y \leq x^T c = c^T x,$

where the first inequality uses primal feasibility ($Ax \geq b$, $y \geq 0$) and the second uses dual feasibility ($A^T y \leq c$, $x \geq 0$).

Weak duality has an immediate corollary: if we find a primal feasible $x^*$ and a dual feasible $y^*$ with $c^T x^* = b^T y^*$, then both must be optimal for their respective problems — no other feasible solution can do better.

Strong duality

Strong duality goes further: if the primal has an optimal solution, then the dual also has an optimal solution, and their objective values are equal:

$c^T x^* = b^T y^*.$

This is one of the central theorems of linear programming. The proof typically follows from the simplex method: the final simplex tableau provides both a primal optimal solution and a dual optimal solution (the dual values can be read from the objective row entries corresponding to the slack variables).

Strong duality can fail only when the primal or dual is infeasible or unbounded:

Complementary slackness

Complementary slackness provides a precise characterization of when a pair $(x^*, y^*)$ is simultaneously optimal for the primal and dual. The conditions are:

$y_i^* \cdot (a_i^T x^* - b_i) = 0 \quad \text{for all } i = 1, \ldots, m,$ $x_j^* \cdot (c_j - A_j^T y^*) = 0 \quad \text{for all } j = 1, \ldots, n.$

In words:

• If a dual variable $y_i^* > 0$, then the corresponding primal constraint must be binding ($a_i^T x^* = b_i$).
• If a primal variable $x_j^* > 0$, then the corresponding dual constraint must be binding ($A_j^T y^* = c_j$).

Complementary slackness is extremely useful for verifying optimality and for understanding the structure of optimal solutions. It also connects directly to the economic interpretation of dual variables.

Shadow prices and economic interpretation

The dual variables have a natural economic interpretation: $y_i^*$ represents the shadow price (or marginal value) of the $i$-th resource. It answers the question: "By how much would the optimal objective improve if we had one additional unit of resource $i$?"

Formally, if we perturb the right-hand side from $b$ to $b + \Delta b$ (with a small enough perturbation that the current basis remains optimal), the change in the optimal objective value is:

$\Delta z^* = (y^*)^T \Delta b.$

This is the essence of sensitivity analysis — understanding how the optimal solution changes when the problem data changes.

Example: Production planning revisited

Recall the furniture workshop from Part 1:

$\max \; 70 x_1 + 50 x_2 \quad \text{s.t.} \quad 4x_1 + 2x_2 \leq 240, \quad 2x_1 + 3x_2 \leq 180, \quad x_1, x_2 \geq 0.$

The dual of this problem (after converting max to min) is:

$\min \; 240 y_1 + 180 y_2 \quad \text{s.t.} \quad 4y_1 + 2y_2 \geq 70, \quad 2y_1 + 3y_2 \geq 50, \quad y_1, y_2 \geq 0.$

In Part 2, we found the optimal simplex tableau:

The dual optimal values can be read from the objective row under the slack variables: $y_1^* = 13.75$ and $y_2^* = 7.5$. These are the shadow prices.

Interpretation:

• One extra hour of carpentry (increasing 240 to 241) would increase the maximum profit by approximately €13.75.
• One extra hour of finishing (increasing 180 to 181) would increase the maximum profit by approximately €7.50.

This tells the workshop manager that carpentry capacity is more valuable than finishing capacity. If they could invest in expanding one department, carpentry offers a better return.

We can verify strong duality: the dual objective is $240 \cdot 13.75 + 180 \cdot 7.5 = 3300 + 1350 = 4650$, which matches the primal optimal value.

Sensitivity analysis in practice

Beyond shadow prices, sensitivity analysis addresses several practical questions:

Range of optimality (objective coefficients)

How much can we change an objective coefficient $c_j$ before the current optimal basis changes? For a basic variable, this range can be computed from the simplex tableau. As long as all reduced costs remain non-negative (for minimization) or non-positive (for maximization), the current basis stays optimal (though the optimal values of the variables will change).

Range of feasibility (right-hand side)

How much can we change a right-hand side value $b_i$ before the current basis becomes infeasible? The current BFS remains feasible as long as $B^{-1}(b + \Delta b) \geq 0$, where $B$ is the basis matrix. This gives an interval for each $b_i$.

Gurobi makes this easy

Modern solvers provide sensitivity analysis output directly:

import gurobipy as gp
from gurobipy import GRB

model = gp.Model('production_planning')

x1 = model.addVar(name='tables', lb=0)
x2 = model.addVar(name='chairs', lb=0)

model.setObjective(70 * x1 + 50 * x2, GRB.MAXIMIZE)

carpentry = model.addConstr(4 * x1 + 2 * x2 <= 240, 'carpentry')
finishing = model.addConstr(2 * x1 + 3 * x2 <= 180, 'finishing')

model.optimize()

# Shadow prices (dual values)
print(f'Shadow price carpentry: €{carpentry.Pi:.2f}')
print(f'Shadow price finishing: €{finishing.Pi:.2f}')

# Right-hand side sensitivity ranges
print(f'\nCarpentry RHS range: [{carpentry.SARHSLow:.1f}, {carpentry.SARHSUp:.1f}]')
print(f'Finishing RHS range: [{finishing.SARHSLow:.1f}, {finishing.SARHSUp:.1f}]')

# Objective coefficient sensitivity ranges
print(f'\nTables obj range: [{x1.SAObjLow:.2f}, {x1.SAObjUp:.2f}]')
print(f'Chairs obj range: [{x2.SAObjLow:.2f}, {x2.SAObjUp:.2f}]')

The output tells us for example that the shadow price of €13.75 for carpentry is valid as long as carpentry capacity stays within a certain range — beyond that, the basis changes and the shadow price may differ.

Reduced costs

The simplex method also provides reduced costs for non-basic variables. The reduced cost $\bar{c}_j$ of a non-basic variable $x_j$ tells us by how much the objective would improve per unit increase of $x_j$. At optimality, all reduced costs are non-negative (for minimization), meaning no non-basic variable can improve the objective.

For basic variables, the reduced cost is always zero. For non-basic variables, the reduced cost indicates how much cheaper variable $x_j$ would need to become before it would be worthwhile to include it in the solution. In Gurobi, reduced costs are accessible via x.RC.

Duality beyond LP

The primal-dual relationship is not limited to linear programming. It extends in various forms to:

• Integer programming: LP relaxation duality provides bounds used in branch-and-bound.
• Network optimization: dual variables correspond to node potentials (shortest paths, min-cost flow).
• Lagrangian relaxation: a generalization of LP duality for hard combinatorial problems.
• Game theory: LP duality is closely tied to minimax theorems and zero-sum games.

These connections make duality one of the most important ideas in all of optimization.

Summary of the LP mini-series

Across the three parts, we covered:

1. Part 1 — LP definition, standard form, geometric intuition, production planning and blending examples.
2. Part 2 — The simplex method: slack variables, tableaux, pivoting, degeneracy, Bland's rule, complexity.
3. Part 3 — Duality, strong duality, complementary slackness, shadow prices, sensitivity analysis.

Linear programming is the foundation for much of Operations Research. In upcoming mini-series, we will build on these ideas to tackle integer programming, where decision variables are required to take integer values — a constraint that makes problems much harder but also much more practically relevant.