Duality Theory, Complementary Slackness & Post-Optimality Sensitivity Analysis

Every Linear Programming Problem, which we designate as the **Primal Problem (P)**, is intrinsically paired with a companion linear optimization problem constructed from the exact same data arrays $(\mathbf{A}, \mathbf{b}, \mathbf{c})$, termed the **Dual Problem (D)**. Originating in John von Neumann's 1947 notes linking linear programming to zero-sum matrix games and formalized by David Gale, Harold Kuhn, and Albert Tucker (1951), Duality Theory reveals that optimizing a primal system in $\mathbb{R}^n$ subject to $m$ constraints is mathematically equivalent to optimizing a dual system in $\mathbb{R}^m$ subject to $n$ constraints. ### Symmetric Primal-Dual Pairings Consider the **Symmetric Canonical Primal Problem (P)** in $n$ non-negative decision variables $\mathbf{x} = (x_1, \dots, x_n)^T \in \mathbb{R}_+^n$ and $m$ resource inequalities defined by $\mathbf{A} = [a_{ij}] \in \mathbb{R}^{m \times n}$, $\mathbf{b} \in \mathbb{R}^m$, and $\mathbf{c} \in \mathbb{R}^n$: $$\text{(P)} \quad \text{Maximize } Z = \mathbf{c}^T \mathbf{x} = \sum_{j=1}^n c_j x_j \quad \text{subject to} \quad \mathbf{A}\mathbf{x} \le \mathbf{b} \;\; \left(\sum_{j=1}^n a_{ij} x_j \le b_i, \; i=1,\dots,m\right), \quad \mathbf{x} \ge \mathbf{0}$$ Associated with each of the $m$ primal constraints $i \in \{1, \dots, m\}$, we introduce a scalar **dual variable** $y_i$ to form the dual column vector $\mathbf{y} = (y_1, y_2, \dots, y_m)^T \in \mathbb{R}^m$. The **Symmetric Dual Problem (D)** reverses the sense of optimization from maximization to minimization, interchanges the roles of the right-hand-side capacity vector $\mathbf{b}$ and the objective coefficient vector $\mathbf{c}$, and transposes the technological matrix $\mathbf{A}$ to $\mathbf{A}^T \in \mathbb{R}^{n \times m}$: $$\text{(D)} \quad \text{Minimize } W = \mathbf{b}^T \mathbf{y} = \sum_{i=1}^m b_i y_i \quad \text{subject to} \quad \mathbf{A}^T \mathbf{y} \ge \mathbf{c} \;\; \left(\sum_{i=1}^m a_{ij} y_i \ge c_j, \; j=1,\dots,n\right), \quad \mathbf{y} \ge \mathbf{0}$$ ### Asymmetric Formulations and the General Primal-Dual Correspondence Table What if the Primal Problem contains a mixture of $\le$ inequalities, $\ge$ inequalities, and strict equalities ($=$), alongside non-negative, non-positive, and unrestricted variables? By converting any general Primal LP into symmetric canonical form (replacing $\mathbf{a}_i^T\mathbf{x} \ge b_i$ by $-\mathbf{a}_i^T\mathbf{x} \le -b_i$, replacing $\mathbf{a}_i^T\mathbf{x} = b_i$ by the pair $\mathbf{a}_i^T\mathbf{x} \le b_i$ and $-\mathbf{a}_i^T\mathbf{x} \le -b_i$ with dual variables $y_i^+, y_i^- \ge 0$ so $y_i = y_i^+ - y_i^- \in \mathbb{R}$ is unrestricted, and splitting unrestricted primal variables $x_j = x_j^+ - x_j^-$), we obtain an exact one-to-one structural correspondence between the $m$ primal constraints and $m$ dual variables, and between the $n$ primal variables and $n$ dual constraints: #### Theorem 3.1 (Involutory Property: The Dual of the Dual is the Primal): For any Linear Programming Problem (P), constructing the dual of its dual problem (D) recovers the exact original Primal Problem (P). #### Proof: Write the symmetric Dual (D) as a maximization problem by negating its objective and constraints: $\max (-W) = (-\mathbf{b})^T \mathbf{y}$ subject to $(-\mathbf{A}^T)\mathbf{y} \le -\mathbf{c}, \mathbf{y} \ge \mathbf{0}$. Applying the canonical dual transformation to this maximization problem yields a minimization problem in vector $\mathbf{x} \ge \mathbf{0}$: $\min (-\mathbf{c})^T \mathbf{x}$ subject to $(-\mathbf{A}^T)^T \mathbf{x} \ge -\mathbf{b}, \mathbf{x} \ge \mathbf{0}$. Negating the objective back to maximization and multiplying the constraints by $-1$ produces $\max Z = \mathbf{c}^T\mathbf{x}$ subject to $\mathbf{A}\mathbf{x} \le \mathbf{b}, \mathbf{x} \ge \mathbf{0}$, which is identically (P).

Duality Theory is far more than a formal algebraic transposition; as discovered by Leonid Kantorovich (1939) and Tjalling Koopmans (1951), the Dual Linear Program embodies the decentralized price mechanism of competitive economic equilibrium and statistical resource valuation.

Suppose the Primal Problem $\max Z = \sum_{j=1}^n c_j x_j$ subject to $\sum_{j=1}^n a_{ij} x_j \le b_i$ ($i=1,\dots,m$), $x_j \ge 0$, models a manufacturing enterprise or statistical research institute that uses $m$ scarce resources (each available in total quantity $b_i$ units) to produce $n$ distinct outputs (in quantities $x_j$, each generating net revenue $c_j$ dollars per unit and consuming $a_{ij}$ units of resource $i$ per unit of output $j$). Dimensional analysis immediately illuminates the meaning of the dual variables $y_i$:

• Because $b_i$ is measured in [units of resource i] and the dual objective $W = \sum_{i=1}^m b_i y_i$ is measured in [dollars], each dual variable $y_i$ must have physical dimensions of [dollars per unit of resource i].

Thus, $y_i$ represents the imputed unit valuation (or accounting price / shadow price) assigned internally to one unit of scarce resource $i$. Now consider an outside entrepreneur or resource broker who offers to rent or purchase the entire endowment $(b_1, \dots, b_m)$ of the enterprise's resources at unit prices $\mathbf{y} = (y_1, \dots, y_m)^T \ge \mathbf{0}$:

1. The Dual Constraint ($\sum_{i=1}^m a_{ij} y_i \ge c_j$): To produce one unit of activity $j$, the enterprise consumes bundle $(a_{1j}, a_{2j}, \dots, a_{mj})$ of the $m$ resources. At unit resource prices $y_i$, the total imputed opportunity cost of the resources tied up in producing one unit of activity $j$ is $\sum_{i=1}^m a_{ij} y_i$. For the enterprise to be willing to cede its resources rather than operate activity $j$ internally, the imputed value of the resources required to make one unit of product $j$ must be at least as large as the direct profit $c_j$ that product $j$ would generate! If $\sum_{i=1}^m a_{ij} y_i < c_j$, an arbitrage profit opportunity exists: purchasing the required resources at prices $y_i$ and running activity $j$ yields a strictly positive net economic rent $c_j - \sum_{i=1}^m a_{ij} y_i > 0$.

2. The Dual Objective ($\min W = \sum_{i=1}^m b_i y_i$): Subject to offering competitive resource valuations that leave zero excess arbitrage profit across all $n$ production activities ($\mathbf{A}^T\mathbf{y} \ge \mathbf{c}$), the buyer seeks to minimize the total expenditure $W = \sum_{i=1}^m b_i y_i$ paid for the resource bundle $\mathbf{b}$.

At the joint primal-dual optimum $(\mathbf{x}^*, \mathbf{y}^*)$, Strong Duality ($\mathbf{c}^T\mathbf{x}^* = \mathbf{b}^T\mathbf{y}^*$) states that the maximum total profit achievable by physical production equals the minimum total imputed value of the scarce resources! Moreover, if the optimal primal basis $\mathbf{B}$ is non-degenerate, the optimal dual vector $\mathbf{y}^* = (\mathbf{B}^{-1})^T \mathbf{c}_B$ equals the exact marginal partial derivative (shadow price) of the optimal objective value function $Z^*(\mathbf{b}) = \mathbf{c}_B^T \mathbf{B}^{-1}\mathbf{b}$ with respect to each resource availability $b_i$:

That is, $y_i^*$ quantifies the exact rate at which maximum achievable profit $Z^*$ increases per additional unit of resource $i$ made available (within the feasibility range of the current optimal basis $\mathbf{B}$).

We now establish the rigorous mathematical theorems governing the relationship between the Primal Problem (P): $\max Z = \mathbf{c}^T\mathbf{x}$ subject to $\mathbf{A}\mathbf{x} \le \mathbf{b}, \mathbf{x} \ge \mathbf{0}$, and the Dual Problem (D): $\min W = \mathbf{b}^T\mathbf{y}$ subject to $\mathbf{A}^T\mathbf{y} \ge \mathbf{c}, \mathbf{y} \ge \mathbf{0}$. ### Lemma 3.1 (The Weak Duality Theorem): Let $\mathbf{x} \in \mathbb{R}_+^n$ be any feasible solution of the Primal Problem (P) ($\mathbf{A}\mathbf{x} \le \mathbf{b}, \mathbf{x} \ge \mathbf{0}$), and let $\mathbf{y} \in \mathbb{R}_+^m$ be any feasible solution of the Dual Problem (D) ($\mathbf{A}^T\mathbf{y} \ge \mathbf{c}, \mathbf{y} \ge \mathbf{0}$). Then the primal objective value never exceeds the dual objective value: $$Z(\mathbf{x}) = \mathbf{c}^T \mathbf{x} \le \mathbf{b}^T \mathbf{y} = W(\mathbf{y})$$ #### Proof: Because $\mathbf{y}$ is dual feasible ($\mathbf{A}^T\mathbf{y} \ge \mathbf{c}$, or $\mathbf{c}^T \le \mathbf{y}^T\mathbf{A}$) and $\mathbf{x} \ge \mathbf{0}$ is non-negative, taking the inner product with $\mathbf{x}$ preserves the direction of inequality: $$\mathbf{c}^T \mathbf{x} \le (\mathbf{y}^T \mathbf{A}) \mathbf{x} = \mathbf{y}^T (\mathbf{A}\mathbf{x})$$ Similarly, because $\mathbf{x}$ is primal feasible ($\mathbf{A}\mathbf{x} \le \mathbf{b}$) and $\mathbf{y} \ge \mathbf{0}$ is non-negative, taking the inner product with $\mathbf{y}^T$ preserves the inequality: $$\mathbf{y}^T (\mathbf{A}\mathbf{x}) \le \mathbf{y}^T \mathbf{b} = \mathbf{b}^T \mathbf{y}$$ Chaining these two inequalities together yields $\mathbf{c}^T\mathbf{x} \le \mathbf{y}^T\mathbf{A}\mathbf{x} \le \mathbf{b}^T\mathbf{y}$, completing the proof. The non-negative difference $W(\mathbf{y}) - Z(\mathbf{x}) = \mathbf{b}^T\mathbf{y} - \mathbf{c}^T\mathbf{x} \ge 0$ is called the **duality gap** at the feasible pair $(\mathbf{x}, \mathbf{y})$. #### Immediate Corollaries of Weak Duality: 1. **Sufficient Certificate of Optimality**: If $\mathbf{x}^*$ is primal feasible, $\mathbf{y}^*$ is dual feasible, and their objectives coincide ($\mathbf{c}^T\mathbf{x}^* = \mathbf{b}^T\mathbf{y}^*$), then $\mathbf{x}^*$ is globally optimal for (P) and $\mathbf{y}^*$ is globally optimal for (D), because for every primal feasible $\mathbf{x}$ and dual feasible $\mathbf{y}$, $\mathbf{c}^T\mathbf{x} \le \mathbf{b}^T\mathbf{y}^* = \mathbf{c}^T\mathbf{x}^* \le \mathbf{b}^T\mathbf{y}$. 2. **Primal Unboundedness Implies Dual Infeasibility**: If (P) is unbounded above ($\sup \mathbf{c}^T\mathbf{x} = +\infty$), then (D) must be strictly infeasible ($\mathcal{F}_D = \emptyset$), since any dual feasible vector $\mathbf{y}$ would provide a finite upper bound $\mathbf{b}^T\mathbf{y} < \infty$ on $\mathbf{c}^T\mathbf{x}$. 3. **Dual Unboundedness Implies Primal Infeasibility**: Symmetrically, if (D) is unbounded below ($\inf \mathbf{b}^T\mathbf{y} = -\infty$), then (P) must be strictly infeasible ($\mathcal{F}_P = \emptyset$). (Note: It is possible for **both** (P) and (D) to be simultaneously infeasible!) ### Farkas' Lemma and the Strong Duality Theorem The bridge from Weak Duality to zero duality gap at optimality is anchored by **Farkas' Lemma** (Gyula Farkas, 1902), a foundational theorem of the alternative deduced from separating hyperplanes: for any matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$ and vector $\mathbf{b} \in \mathbb{R}^m$, **exactly one** of the following two linear systems possesses a solution: - **System I**: $\mathbf{A}\mathbf{x} = \mathbf{b}$ and $\mathbf{x} \ge \mathbf{0}$ (meaning $\mathbf{b}$ lies inside the finitely generated convex cone $\text{cone}(\mathbf{a}_1, \dots, \mathbf{a}_n)$). - **System II**: $\mathbf{A}^T\mathbf{y} \le \mathbf{0}$ and $\mathbf{b}^T\mathbf{y} > 0$ (meaning there exists a hyperplane with normal $\mathbf{y}$ separating $\mathbf{b}$ from $\text{cone}(\mathbf{a}_1, \dots, \mathbf{a}_n)$). ### Theorem 3.2 (The Strong Duality Theorem of Linear Programming): If either the Primal Problem (P) or the Dual Problem (D) possesses a finite optimal solution, then **so does the other**, and their optimal objective values are **strictly equal** (zero duality gap): $$Z^* = \max_{\mathbf{x} \in \mathcal{F}_P} \mathbf{c}^T \mathbf{x} = \min_{\mathbf{y} \in \mathcal{F}_D} \mathbf{b}^T \mathbf{y} = W^*$$ Moreover, if $\mathbf{B}$ is an optimal basis matrix for the standard-form Primal Problem ($\max \mathbf{c}^T\mathbf{x} + \mathbf{0}^T\mathbf{s}$ subject to $\mathbf{A}\mathbf{x} + \mathbf{I}_m\mathbf{s} = \mathbf{b}, \mathbf{x},\mathbf{s} \ge \mathbf{0}$), then the **Simplex multiplier vector** $\mathbf{y}^* = (\mathbf{B}^{-1})^T \mathbf{c}_B$ is an **optimal Basic Feasible Solution of the Dual Problem (D)**! #### Constructive Simplex Proof of Strong Duality: Suppose (P) has a finite optimal solution. Adding slack variables $\mathbf{s} \ge \mathbf{0}$ with cost $\mathbf{c}_s = \mathbf{0}$, the Simplex Algorithm (with Bland's anti-cycling rule) terminates at an optimal basis $\mathbf{B}$ with primal BFS $\mathbf{x}_B^* = \mathbf{B}^{-1}\mathbf{b} \ge \mathbf{0}$ and optimal objective $Z^* = \mathbf{c}_B^T \mathbf{B}^{-1}\mathbf{b}$. At termination, the Simplex optimality condition holds across all $n$ structural columns $\mathbf{a}_j$ of $\mathbf{A}$ and all $m$ slack columns $\mathbf{e}_i$ of $\mathbf{I}_m$. Define $\mathbf{y}^* = (\mathbf{B}^{-1})^T \mathbf{c}_B$, so $(\mathbf{y}^*)^T = \mathbf{c}_B^T \mathbf{B}^{-1}$. 1. For the $n$ structural columns $j = 1, \dots, n$, the optimal net evaluation satisfies: $$z_j - c_j = \mathbf{c}_B^T \mathbf{B}^{-1} \mathbf{a}_j - c_j = (\mathbf{y}^*)^T \mathbf{a}_j - c_j \ge 0 \implies \mathbf{A}^T \mathbf{y}^* \ge \mathbf{c}$$ 2. For the $m$ slack columns $s_i$ with unit column $\mathbf{e}_i$ and cost $c_{s_i} = 0$, the optimal net evaluation satisfies: $$z_{s_i} - 0 = \mathbf{c}_B^T \mathbf{B}^{-1} \mathbf{e}_i - 0 = (\mathbf{y}^*)^T \mathbf{e}_i = y_i^* \ge 0 \implies \mathbf{y}^* \ge \mathbf{0}$$ Thus $\mathbf{y}^* = (\mathbf{B}^{-1})^T \mathbf{c}_B$ satisfies both $\mathbf{A}^T\mathbf{y}^* \ge \mathbf{c}$ and $\mathbf{y}^* \ge \mathbf{0}$, proving that **$\mathbf{y}^*$ is Dual Feasible**! Notice further that $y_i^* = z_{s_i} - c_{s_i}$, meaning **the optimal dual variables $y_1^*, \dots, y_m^*$ appear directly in the final Simplex $z_j - c_j$ row under the $m$ slack columns**! Finally, evaluating the dual objective at $\mathbf{y}^*$ gives: $$W(\mathbf{y}^*) = \mathbf{b}^T \mathbf{y}^* = (\mathbf{y}^*)^T \mathbf{b} = \mathbf{c}_B^T \mathbf{B}^{-1} \mathbf{b} = \mathbf{c}_B^T \mathbf{x}_B^* = Z^*$$ By Corollary 1 of Weak Duality, equality $W(\mathbf{y}^*) = Z^*$ proves that $\mathbf{y}^*$ is globally optimal for (D) and $Z^* = W^*$.

The algebraic chain of inequalities in the proof of the Weak Duality Lemma ($\mathbf{c}^T\mathbf{x} \le \mathbf{y}^T\mathbf{A}\mathbf{x} \le \mathbf{b}^T\mathbf{y}$) yields a powerful necessary and sufficient condition linking the positive variables of one problem to the binding constraints of the other, known as the Complementary Slackness Theorem.

Let $\mathbf{x} \in \mathbb{R}_+{}^n$ be primal feasible for (P) with primal slack vector $\mathbf{s} = \mathbf{b} - \mathbf{A}\mathbf{x} \ge \mathbf{0}$ ($s_i = b_i - \sum_{j=1}^n a_{ij}x_j \ge 0$ for $i=1,\dots,m$), and let $\mathbf{y} \in \mathbb{R}_+{}^m$ be dual feasible for (D) with dual surplus vector $\mathbf{e} = \mathbf{A}^T\mathbf{y} - \mathbf{c} \ge \mathbf{0}$ ($e_j = \sum_{i=1}^m a_{ij}y_i - c_j \ge 0$ for $j=1,\dots,n$). Expressing the duality gap $W(\mathbf{y}) - Z(\mathbf{x})$ in terms of $\mathbf{s}$ and $\mathbf{e}$, we substitute $\mathbf{b} = \mathbf{A}\mathbf{x} + \mathbf{s}$ and $\mathbf{c} = \mathbf{A}^T\mathbf{y} - \mathbf{e}$:

Writing out the two inner products componentwise:

Theorem 3.3 (The Complementary Slackness Theorem):

Let $\mathbf{x}$ be feasible for the Primal Problem (P) and $\mathbf{y}$ be feasible for the Dual Problem (D). Then $\mathbf{x}$ and $\mathbf{y}$ are simultaneously optimal for (P) and (D), respectively, if and only if they satisfy the Complementary Slackness Conditions:

Equivalently, in logical implication form at any primal-dual optimal pair $(\mathbf{x}^*, \mathbf{y}^*)$:

• If a primal constraint is non-binding (has positive slack $s_i^* > 0$), its corresponding dual shadow price must equal zero ($y_i^* = 0$). Economically, a resource that is in excess supply (leftover idle capacity at the optimum) is a free good with zero marginal shadow value!
• If a dual shadow price is strictly positive ($y_i^* > 0$), its corresponding primal resource constraint must be tightly binding ($s_i^* = 0$, i.e., $\sum_{j=1}^n a_{ij}x_j^* = b_i$).
• If a primal activity is operated at a strictly positive level ($x_j^* > 0$), its corresponding dual constraint must hold with exact equality ($e_j^* = 0$, i.e., $\sum_{i=1}^m a_{ij}y_i^* = c_j$). Economically, any product actually manufactured at the optimum must break even exactly against the imputed opportunity cost of the resources it consumes.
• If a dual constraint has positive surplus ($e_j^* > 0$, so imputed resource cost $\sum_{i=1}^m a_{ij}y_i^* > c_j$ exceeds unit revenue), that primal activity must be shut down completely ($x_j^* = 0$).

Proof:

By Strong Duality, feasible vectors $\mathbf{x}$ and $\mathbf{y}$ are optimal if and only if the duality gap vanishes: $W(\mathbf{y}) - Z(\mathbf{x}) = \sum_{i=1}^m s_i y_i + \sum_{j=1}^n e_j x_j = 0$. Because $s_i \ge 0, y_i \ge 0$ for all $i$ and $e_j \ge 0, x_j \ge 0$ for all $j$, every single product term $s_i y_i \ge 0$ and $e_j x_j \ge 0$ is non-negative. A sum of non-negative real numbers equals zero if and only if every individual term equals zero, namely $s_i y_i = 0$ for all $i=1,\dots,m$ and $e_j x_j = 0$ for all $j=1,\dots,n$. (Furthermore, the Goldman–Tucker Strict Complementary Slackness Theorem proves that whenever (P) and (D) are feasible, there exists at least one optimal pair $(\mathbf{x}^*, \mathbf{y}^*)$ that is strictly complementary, satisfying $s_i^* + y_i^* > 0$ for all $i$ and $e_j^* + x_j^* > 0$ for all $j$.)

In the standard (Primal) Simplex Algorithm of Unit 2, computation begins at a primal feasible basic solution ($\bar{\mathbf{b}} = \mathbf{B}^{-1}\mathbf{b} \ge \mathbf{0}$) that is dual infeasible ($z_j - c_j < 0$ for some $j \in N$), and pivots iteratively to achieve dual feasibility ($z_j - c_j \ge 0$) while preserving primal feasibility ($\bar{\mathbf{b}} \ge \mathbf{0}$) at every step.

Frequently, however—especially in post-optimality sensitivity analysis when a right-hand-side capacity $b_i$ is reduced, when a new cutting-plane inequality is appended in Gomory's integer programming algorithm (Unit 6), or in minimization models with $\ge$ constraints ($\sum a_{ij}x_j \ge b_i \iff \sum (-a_{ij})x_j + s_i = -b_i < 0$) and positive costs $c_j \ge 0$—we possess a basis $\mathbf{B}$ that is already Dual Feasible (satisfying the Simplex optimality condition $z_j - c_j \ge 0$ for all $j \in N$ in maximization, or $z_j - c_j \le 0$ in minimization), but Primal Infeasible because one or more basic variables are strictly negative ($\bar{b}_i < 0$ for some $i \in \{1, \dots, m\}$). Rather than introducing artificial variables and starting over with a costly Two-Phase or Big-M procedure, Carlton E. Lemke (1954) invented the Dual Simplex Algorithm, which performs pivots that preserve dual feasibility ($z_j - c_j \ge 0$) while systematically eliminating negative right-hand sides ($\bar{b}_i < 0$) until primal feasibility ($\bar{\mathbf{b}} \ge \mathbf{0}$) is attained!

Algorithmic Mechanics of the Dual Simplex Method (Maximization Form)

Assume the current Simplex tableau is dual feasible ($z_j - c_j \ge 0$ for all $j \in \{1, \dots, n\}$), and we wish to achieve primal feasibility ($\bar{b}_i \ge 0$ for all $i = 1, \dots, m$):

1. Primal Optimality Check: If $\bar{b}_i \ge 0$ for all $i = 1, \dots, m$, stop! Because the tableau is simultaneously primal feasible ($\bar{\mathbf{b}} \ge \mathbf{0}$) and dual feasible ($z_j - c_j \ge 0$), the current BFS is globally optimal.

2. Leaving Variable Selection (Most Negative RHS Rule): If at least one basic variable is negative, select the leaving basic variable $x_{B(r)}$ in row $r$ corresponding to the most negative right-hand-side constant:

3. Primal Infeasibility Certificate Check: Inspect the coefficients $y_{rj}$ across row $r$ for all non-basic variables $j \in N$. Because the $r$-th basic equation reads:

if $y_{rj} \ge 0$ for all $j \in N$, then for any non-negative vector $\mathbf{x} \ge \mathbf{0}$, the left-hand side $\sum_{j \in N} y_{rj}x_j + x_{B(r)} \ge 0$ is non-negative while the right-hand side $\bar{b}_r < 0$ is strictly negative! This is an impossible contradiction (equivalent to the Dual objective being unbounded above), proving that the Primal LP is strictly infeasible ($\mathcal{F}_P = \emptyset$).

4. Entering Variable Selection (Dual Minimum Ratio Test): To make the new basic variable in row $r$ positive ($\bar{b}_r^{\text{new}} = \bar{b}_r / y_{rk} > 0$ since $\bar{b}_r < 0$), the pivot element $y_{rk}$ must be strictly negative ($y_{rk} < 0$). Furthermore, after pivoting on $y_{rk} < 0$, the updated net evaluation row entries become:

To preserve dual feasibility $(z_j - c_j)^{\text{new}} \ge 0$ across all columns $j \in N$ with $y_{rj} < 0$, we must choose the entering variable $x_k$ via the Dual Minimum Ratio Test:

5. Gauss–Jordan Pivot: Pivot on $y_{rk} < 0$ to bring $x_k$ into the basis and expel $x_{B(r)}$. Note that in a maximization problem, each Dual Simplex pivot decreases (tightens) the super-optimal upper bound $Z_0$ monotonically down toward $Z^*$: $Z_{\text{new}} = Z_0 - \frac{\bar{b}_r}{y_{rk}}(z_k - c_k) \le Z_0$.

Once an optimal Basic Feasible Solution $\mathbf{x}_B^* = \mathbf{B}^{-1}\mathbf{b} \ge \mathbf{0}$ with optimal basis $\mathbf{B}$, optimal dual shadow prices $\mathbf{y}^* = (\mathbf{B}^{-1})^T\mathbf{c}_B$, and optimal objective $Z^* = \mathbf{c}_B^T \mathbf{B}^{-1}\mathbf{b}$ has been computed, Post-Optimality Sensitivity Analysis investigates how perturbations in the model's exogenous data $(\mathbf{b}, \mathbf{c}, \mathbf{A})$ affect the optimal basis and solution—without resolving the Linear Program from scratch! Everything hinges on the Fundamental Matrix Invariance Principle: every entry in the final Simplex tableau is a deterministic function of the optimal basis inverse $\mathbf{B}^{-1}$:

Perturbations in the Right-Hand-Side Resource Vector ($\mathbf{b} \to \mathbf{b} + \Delta \mathbf{b}$)

Suppose the resource capacity vector $\mathbf{b}$ is perturbed to $\hat{\mathbf{b}} = \mathbf{b} + \Delta \mathbf{b}$ (or a single resource $b_r$ is perturbed to $b_r + \Delta b_r$, so $\Delta \mathbf{b} = \Delta b_r \mathbf{e}_r$). Inspect the fundamental tableau formulas above:

• Dual Feasibility is Completely Unaffected: Because $\mathbf{b}$ does not appear anywhere in $z_j - c_j = \mathbf{c}_B^T \mathbf{B}^{-1}\mathbf{a}_j - c_j$, changing $\mathbf{b}$ leaves the entire net evaluation row $z_j - c_j \ge 0$ and the dual shadow prices $\mathbf{y}^* = (\mathbf{B}^{-1})^T\mathbf{c}_B$ completely unchanged!
• Primal Feasibility Condition (Stability Range of the Optimal Basis $\mathbf{B}$): The current optimal basis $\mathbf{B}$ remains optimal if and only if the perturbed basic variables remain non-negative:

Specifically, if a single resource $b_r$ is perturbed by $\Delta b_r$, let $\boldsymbol{\beta}_{*r} = (\beta_{1r}, \beta_{2r}, \dots, \beta_{mr})^T$ denote the $r$-th column of $\mathbf{B}^{-1}$ (which is located directly under the $r$-th initial slack/artificial variable in the final Simplex tableau!). Then the $m$ perturbed basic variables are:

Solving these $m$ linear inequalities for $\Delta b_r$ yields the exact Feasibility (Allowable) Range for $\Delta b_r$ within which the current basis $\mathbf{B}$ and shadow prices $\mathbf{y}^*$ remain invariant:

Within this allowable interval $[\Delta b_r^{\min}, \Delta b_r^{\max}]$, the optimal objective value is a strictly linear function of $\Delta b_r$ with slope equal to the $r$-th shadow price $y_r^*$:

If $\Delta b_r$ exceeds this interval, one or more $\hat{x}_{B(i)}$ become negative while $z_j - c_j \ge 0$ remains satisfied; a single iteration of Lemke's Dual Simplex Algorithm (Section 3.5) immediately transitions to the new optimal basis, where the slope $\frac{\partial Z^*}{\partial b_r}$ steps down, making the global value function $Z^*(b_r)$ a piecewise-linear concave function of $b_r$!

Post-Optimality Sensitivity Analysis II: Objective Coefficients, New Activities, and New Constraints

Continuing from the Fundamental Matrix Invariance Principle, we now analyze how perturbations in the objective coefficients $\mathbf{c}$, the introduction of a new structural activity $x_{n+1}$, or the addition of a new constraint row affect the optimal solution.

1. Perturbation in a Non-Basic Objective Coefficient ($c_k \to c_k + \Delta c_k, \; k \in N$)

Suppose $x_k$ ($k \in N$) is currently a non-basic variable ($x_k^* = 0$) at the optimum, so its current activity level is zero because its unit profit $c_k$ is less than or equal to its imputed resource cost $z_k = (\mathbf{y}^*)^T \mathbf{a}_k$ ($z_k - c_k \ge 0$). Because $k \notin B$, $c_k$ does not appear in $\mathbf{c}_B$. Therefore, changing $c_k$ to $c_k + \Delta c_k$ leaves $\mathbf{x}_B^* = \mathbf{B}^{-1}\mathbf{b}$, $\mathbf{y}^* = (\mathbf{B}^{-1})^T\mathbf{c}_B$, $Z^*$, and every other column's $z_j - c_j$ ($j \ne k$) completely unchanged! Only the single net evaluation entry for column $k$ changes:

Thus, for any non-basic variable $x_k$ ($k \in N$), the optimal solution remains completely invariant for all $\Delta c_k \in (-\infty, \, z_k - c_k]$. Only if $c_k$ increases by more than its reduced cost $z_k - c_k$ does $x_k$ become profitable to enter the basis via a standard Primal Simplex pivot.

2. Perturbation in a Basic Objective Coefficient ($c_{B(r)} \to c_{B(r)} + \Delta c_{B(r)}, \; B(r) \in B$)

Suppose $x_{B(r)}$ is the $r$-th basic variable ($B(r) \in B$). Perturbing $c_{B(r)}$ by $\Delta c_{B(r)}$ changes the basic cost vector to $\hat{\mathbf{c}}_B = \mathbf{c}_B + \Delta c_{B(r)} \mathbf{e}_r$.

• Primal Feasibility is Unaffected: $\mathbf{x}_B^* = \mathbf{B}^{-1}\mathbf{b} \ge \mathbf{0}$ does not depend on $\mathbf{c}$, so the vertex coordinates remain $\bar{\mathbf{b}}$.
• Dual Feasibility Condition (Optimality Range for $\Delta c_{B(r)}$): For every basic variable $j \in B$, $\hat{z}_j - \hat{c}_j = 0$ remains zero. However, for every non-basic variable $j \in N$, the imputed cost changes by $\Delta c_{B(r)} y_{rj}$, where $y_{rj}$ is the entry in row $r$ and column $j$ of the final Simplex tableau:

Solving this system of inequalities over all non-basic columns $j \in N$ yields the exact Optimality Range for $\Delta c_{B(r)}$:

Within this range, the optimal decision vector $\mathbf{x}^*$ is completely unchanged, while the optimal objective value shifts linearly as $\hat{Z}^* = Z^* + \bar{b}_r \Delta c_{B(r)}$.

3. Addition of a New Structural Activity ($x_{n+1}$) and Addition of a New Constraint

• Pricing a New Activity Column: Suppose management proposes a new product $x_{n+1} \ge 0$ with unit profit $c_{n+1}$ and resource consumption column $\mathbf{a}_{n+1} \in \mathbb{R}^m$. Using the existing optimal shadow prices $\mathbf{y}^* = (\mathbf{B}^{-1})^T\mathbf{c}_B$, we immediately compute its reduced cost:

If $z_{n+1} - c_{n+1} \ge 0$, the new activity's imputed resource cost exceeds or equals its revenue, so $x_{n+1}^* = 0$ and the current optimum is unchanged! If $z_{n+1} - c_{n+1} < 0$, we compute its updated tableau column $\mathbf{y}_{n+1} = \mathbf{B}^{-1}\mathbf{a}_{n+1}$ and pivot $x_{n+1}$ into the basis via the Primal Simplex Method.

• Appending a New Constraint: Suppose a new regulatory or technological constraint $\mathbf{a}_{m+1}^T \mathbf{x} \le b_{m+1}$ is added. First, substitute the current optimal vector $\mathbf{x}^*$ directly into the new constraint: if $\mathbf{a}_{m+1}^T \mathbf{x}^* \le b_{m+1}$, the current optimal solution already satisfies the new constraint with slack $s_{m+1}^* = b_{m+1} - \mathbf{a}_{m+1}^T \mathbf{x}^* \ge 0$ and remains globally optimal! If $\mathbf{a}_{m+1}^T \mathbf{x}^* > b_{m+1}$, we append the row $\mathbf{a}_{m+1}^T \mathbf{x} + s_{m+1} = b_{m+1}$ with basic variable $s_{m+1}$ to the final tableau, eliminate the basic variables $\mathbf{x}_B$ from row $m+1$ using the existing tableau rows (which leaves $\bar{b}_{m+1} = b_{m+1} - \mathbf{a}_{m+1}^T \mathbf{x}^* < 0$ while maintaining $z_j - c_j \ge 0$), and apply Lemke's Dual Simplex Method to restore primal feasibility!

Parametric Linear Programming, the 100% Simultaneous Perturbation Rule, and Degenerate Shadow Prices

Single-parameter sensitivity intervals characterize how far an individual resource $b_r$ or individual profit coefficient $c_j$ can move while holding all other parameters fixed ceteris paribus. In realistic statistical and econometric environments, however, multiple resource capacities $\mathbf{b} + \Delta\mathbf{b}$ or multiple objective coefficients $\mathbf{c} + \Delta\mathbf{c}$ fluctuate simultaneously due to macroeconomic trends, seasonal shifts, or correlated estimation errors.

Bradley, Hax, and Magnanti's 100% Rule for Simultaneous Perturbations

Suppose several right-hand-side capacities $b_1, \dots, b_m$ are perturbed simultaneously by increments $\Delta b_1, \dots, \Delta b_m$, where each individual increment $\Delta b_i \ne 0$ has a known maximum allowable increase $\Delta b_i^+ > 0$ and maximum allowable decrease $\Delta b_i^- > 0$ (so its single-parameter feasibility interval is $[b_i - \Delta b_i^-, \, b_i + \Delta b_i^+]$). Define the fractional excursion $r_i \ge 0$ of resource $i$ toward its single-parameter stability boundary by:

The 100% Rule for Simultaneous RHS Perturbations states that if the sum of the percentage excursions across all perturbed resources does not exceed $100\%$:

then the current optimal basis $\mathbf{B}$ and its dual shadow price vector $\mathbf{y}^*$ are guaranteed to remain valid and optimal! The proof follows directly from convexity of the non-negative orthant in basis space: the unperturbed vector $\Delta \mathbf{b} = \mathbf{0}$ and the $m$ single-axis boundary vectors $\Delta b_i^+ \mathbf{e}_i$ (or $-\Delta b_i^- \mathbf{e}_i$) all satisfy $\bar{\mathbf{b}} + \mathbf{B}^{-1}\Delta\mathbf{b} \ge \mathbf{0}$; whenever $\sum_{i=1}^m r_i \le 1$, the simultaneous perturbation vector $\Delta\mathbf{b} = \sum_{i=1}^m r_i (\pm \Delta b_i^\pm \mathbf{e}_i) + \left(1 - \sum_{i=1}^m r_i\right)\mathbf{0}$ is a convex combination of feasible perturbation vectors, so $\bar{\mathbf{b}} + \mathbf{B}^{-1}\Delta\mathbf{b} \ge \mathbf{0}$ holds automatically! An identical 100% Rule for Simultaneous Objective Perturbations guarantees that the current optimal solution $\mathbf{x}^*$ remains optimal whenever the fractional excursions of simultaneously perturbed cost coefficients $\Delta c_j$ sum to at most $100\%$. Note carefully that the 100% Rule is a sufficient condition, not a necessary condition: if $\sum r_i > 1$, the basis may still remain optimal if oppositely signed matrix entries $\beta_{ki}\Delta b_i$ cancel each other out, which can always be checked exactly via $\bar{\mathbf{b}} + \mathbf{B}^{-1}\Delta\mathbf{b} \ge \mathbf{0}$.

Parametric Linear Programming along a Continuous Ray

When parameters vary continuously along a prescribed directional ray $\mathbf{b}(\theta) = \mathbf{b} + \theta \mathbf{d}$ or $\mathbf{c}(\theta) = \mathbf{c} + \theta \mathbf{f}$ as a scalar trade-off parameter $\theta \ge 0$ increases from $0$ to $+\infty$ (as in Markowitz mean-variance-linearized efficient frontier tracing or statistical regularization path tracking), Parametric Linear Programming traces the entire piecewise-linear family of optimal bases $\{\mathbf{B}_1, \mathbf{B}_2, \dots, \mathbf{B}_K\}$ across consecutive critical breakpoints $0 = \theta_0 < \theta_1 < \theta_2 < \dots < \theta_K$. Within each interval $\theta \in [\theta_{k-1}, \theta_k]$, the basis $\mathbf{B}_k$ remains constant; at the upper breakpoint $\theta_k$, a basic variable $\bar{b}_r(\theta) = \bar{b}_r + \theta (\mathbf{B}_k^{-1}\mathbf{d})_r$ hits zero (for RHS parameterization) or a reduced cost $z_j(\theta) - c_j(\theta)$ hits zero (for objective parameterization), triggering a single Dual Simplex or Primal Simplex pivot to the adjacent basis $\mathbf{B}_{k+1}$.

Two-Sided Directional Shadow Prices under Primal Degeneracy

Finally, a subtle theoretical distinction arises when the optimal primal BFS $\mathbf{x}^*$ is degenerate ($\bar{b}_i = 0$ for some basic variable). At a degenerate primal vertex, multiple distinct optimal bases $\mathbf{B}^{(1)}, \dots, \mathbf{B}^{(L)}$ represent the same geometric corner $\mathbf{x}^*$, corresponding to alternative optimal solutions $\mathbf{y}^{(1)}, \dots, \mathbf{y}^{(L)}$ in the Dual Problem! Consequently, the optimal value function $Z^*(b_r)$ exhibits a kink (non-differentiability) at the current capacity $b_r$: the right-hand marginal shadow price (for increasing $b_r$, $\Delta b_r > 0$) equals the minimum of $y_r$ over the dual optimal face, $\frac{\partial Z^*}{\partial b_r^+} = \min_{\mathbf{y}^* \in \mathcal{F}_D^*} y_r^*$, whereas the left-hand marginal shadow price (for decreasing $b_r$, $\Delta b_r < 0$) equals the maximum of $y_r$ over the dual optimal face, $\frac{\partial Z^*}{\partial b_r^-} = \max_{\mathbf{y}^* \in \mathcal{F}_D^*} y_r^*$.

Statistical Application: Duality in Quantile Regression and Support Vector Classifiers

In modern mathematical statistics, Linear Programming Duality provides the theoretical bridge between primal residual minimization and dual score-function processes. Consider Roger Koenker and Gilbert Bassett's (1978) Quantile Regression estimator for the $\tau$-th conditional quantile ($\tau \in (0, 1)$) of a response vector $\mathbf{y} \in \mathbb{R}^N$ given design matrix $\mathbf{X} \in \mathbb{R}^{N \times p}$, which minimizes the asymmetric tilted absolute loss $\sum_{i=1}^N \rho_\tau(y_i - \mathbf{x}_i^T \boldsymbol{\beta})$. Splitting each residual into positive and negative parts $y_i - \mathbf{x}_i^T\boldsymbol{\beta} = u_i - v_i$ ($u_i, v_i \ge 0$), the Primal Quantile Regression Linear Program is:

By the asymmetric primal-dual rules of Section 3.1, the $N$ equality constraints correspond to an unrestricted dual vector $\mathbf{d} \in \mathbb{R}^N$, the free variable vector $\boldsymbol{\beta} \in \mathbb{R}^p$ yields $p$ strict dual equality constraints $\mathbf{X}^T\mathbf{d} = \mathbf{0}$, and the non-negative deviation vectors $\mathbf{u}, \mathbf{v} \ge \mathbf{0}$ impose box bounds $-(1-\tau)\mathbf{1}_N \le \mathbf{d} \le \tau \mathbf{1}_N$. Reparameterizing via $\mathbf{a} = \mathbf{d} + (1-\tau)\mathbf{1}_N \in [0, 1]^N$ transforms the Dual of Quantile Regression into the compact bounded-variable maximization problem:

By Complementary Slackness, observations lying strictly above the fitted $\tau$-quantile hyperplane ($u_i^* > 0$) have dual rank score $a_i^* = 1$; observations lying strictly below the hyperplane ($v_i^* > 0$) have dual rank score $a_i^* = 0$; and the $p$ interpolated basic observations lying directly on the hyperplane ($u_i^* = v_i^* = 0$) take fractional dual weights $a_i^* \in (0, 1)$, forming the exact generalization of Hájek's regression rank-score statistics used for distribution-free hypothesis testing in linear models!