Every Linear Programming Problem (called the Primal) has an associated companion problem called the Dual. The dual is also an LPP, derived from the same data but with the roles of constraints and variables interchanged. Solving either problem automatically yields information about the solution of the other.
Primal:
\[ \begin{aligned} \text{Max}\;Z &= \mathbf{c}^{T}\mathbf{x}, \\ A\mathbf{x} &\le \mathbf{b}, \quad \mathbf{x} \ge \mathbf{0}. \end{aligned} \]Dual:
\[ \begin{aligned} \text{Min}\;W &= \mathbf{b}^{T}\mathbf{y}, \\ A^{T}\mathbf{y} &\ge \mathbf{c}, \quad \mathbf{y} \ge \mathbf{0}. \end{aligned} \]Each constraint of the primal corresponds to a variable of the dual, and vice-versa. The RHS vector \(\mathbf{b}\) of the primal becomes the objective coefficient of the dual; the objective coefficients \(\mathbf{c}\) of the primal become the dual's RHS.
For an LPP that is not in pure canonical form, apply the following correspondences:
| Primal (Max Z) | Dual (Min W) |
|---|---|
| Number of variables (\(n\)) | Number of constraints (\(n\)) |
| Number of constraints (\(m\)) | Number of variables (\(m\)) |
| Objective coefficients \(c_j\) | RHS of dual constraints |
| RHS \(b_i\) | Objective coefficients of dual |
| Coefficient matrix \(A\) | \(A^{T}\) (transpose) |
| Maximisation | Minimisation |
| \(i\)-th constraint: \(\le\) | \(i\)-th dual variable \(y_i \ge 0\) |
| \(i\)-th constraint: \(\ge\) | \(y_i \le 0\) |
| \(i\)-th constraint: = | \(y_i\) unrestricted in sign |
| Variable \(x_j \ge 0\) | \(j\)-th dual constraint: \(\ge\) |
| Variable \(x_j \le 0\) | \(j\)-th dual constraint: \(\le\) |
| Variable \(x_j\) unrestricted | \(j\)-th dual constraint: = |
Mnemonic: "Max ↔ Min, ≤ ↔ ≥, ≥ ↔ ≤, = ↔ unrestricted, ≥ 0 ↔ ≥, unrestricted ↔ =". Always assume the primal is in maximisation canonical form with \(\le\) constraints when applying the table directly; convert any deviation before reading the rules.
Primal: Max \(Z = 3 x_1 + 5 x_2 + 4 x_3\) subject to
Dual (3 constraints in primal ⇒ 3 dual variables \(y_1, y_2, y_3\); 3 primal variables ⇒ 3 dual constraints):
Primal: Max \(Z = 5 x_1 + 6 x_2\) subject to
Dual:
For any feasible primal solution \(\mathbf{x}\) and any feasible dual solution \(\mathbf{y}\):
\[ \mathbf{c}^{T}\mathbf{x} \;\le\; \mathbf{b}^{T}\mathbf{y} \]i.e., a feasible primal objective never exceeds a feasible dual objective.
If either the primal or the dual has an optimal solution, then both have optimal solutions and
\[ Z^{*} \;=\; W^{*}. \]i.e., the optimal objective values are equal.
At optimality:
Formally:
\[ (b_i - \mathbf{a}_i^{T}\mathbf{x})\,y_i = 0,\qquad (A^{T}\mathbf{y} - \mathbf{c})_j \, x_j = 0. \]The dual of the dual is the primal.
| Primal | Dual |
|---|---|
| Optimal solution | Optimal solution (same Z*) |
| Unbounded | Infeasible |
| Infeasible | Unbounded OR Infeasible |
If the primal models a profit-maximisation problem (with resources \(b_i\) and per-unit profit \(c_j\)), then the optimal dual variable \(y_i^{*}\) is the shadow price of resource \(i\) — the rate at which the optimal profit would increase per additional unit of that resource, holding everything else fixed.
In the diet problem, dual variables represent marginal cost of meeting one more unit of each nutrient requirement.
If the primal has many constraints but few variables, the dual will have many variables but few constraints — which can be easier to solve by hand. Solve the dual; recover the primal solution from the optimal dual's tableau (or by complementary slackness).
Primal: Max \(Z = 4 x_1 + 5 x_2\) s.t. \(2 x_1 + x_2 \le 8,\; x_1 + 2 x_2 \le 10,\; x_1, x_2 \ge 0\).
Dual: Min \(W = 8 y_1 + 10 y_2\) s.t. \(2 y_1 + y_2 \ge 4,\; y_1 + 2 y_2 \ge 5,\; y_1, y_2 \ge 0\).
Solve the dual via Big-M (Unit 4): optimal \(y_1^{*} = 1, y_2^{*} = 2, W^{*} = 28\).
By strong duality, \(Z^{*} = 28\). Use complementary slackness to recover \(x^{*}\):
The dual simplex method is used when the starting tableau is:
The algorithm iteratively restores primal feasibility while maintaining dual optimality — the exact opposite of the regular simplex.
If at some iteration no negative coefficient appears in the leaving row, the LPP is infeasible.
Min \(Z = 3 x_1 + 2 x_2 + x_3\) subject to
Convert to canonical form for the dual simplex. Multiply each ≥ by −1 to get ≤ with negative RHS:
Convert Min to Max: \(Z' = -3 x_1 - 2 x_2 - x_3\) (so \(c_j - z_j\) is dual-feasible since all are ≤ 0 in initial tableau).
| cB | Basis | xB | x₁ (−3) | x₂ (−2) | x₃ (−1) | s₁ (0) | s₂ (0) |
|---|---|---|---|---|---|---|---|
| 0 | s₁ | −3 | −3 | −1 | −1 | 1 | 0 |
| 0 | s₂ | −6 | 3 | −3 | −1 | 0 | 1 |
| cj−Zj | −3 | −2 | −1 | 0 | 0 | ||
All \(c_j - z_j \le 0\) ⇒ dual feasible. But b's are negative ⇒ primal infeasible. Use dual simplex.
After pivoting and another iteration, the optimal solution is \(x_1 = 0,\; x_2 = 1.5,\; x_3 = 1.5,\; Z = 4.5\) (both constraints binding: \(x_2 + x_3 = 3\) and \(3x_2 + x_3 = 6\)).
| Aspect | Primal Simplex | Dual Simplex |
|---|---|---|
| Starting condition | Primal feasible (b ≥ 0), dual may be infeasible | Dual feasible (cⱼ − zⱼ ≤ 0 for Max), primal may be infeasible |
| Direction of moves | Improves objective each iteration; feasibility preserved | Restores feasibility; optimality preserved |
| Termination — optimal | All cⱼ − zⱼ ≤ 0 | All bᵢ ≥ 0 |
| Termination — infeasible | Artificial positive at end | No negative entry in pivot row |
| Termination — unbounded | All non-positive entries in entering column | n/a |