6 Sensitivity Analysis and Parametric Programming

The data of a real LP are estimates: prices change, capacities are uncertain, new products are proposed. A solution is of little use unless we also know how it depends on the data. Sensitivity analysis answers, from the final basis alone and without re-solving, questions such as: over what range of a resource does the present plan stay optimal, and what is an extra unit worth; how far can a price move before the plan should change; is a new product worth making. Parametric programming follows the solution as a parameter varies over its whole range. Both rest on one observation: a basis \(B\) is optimal exactly when it is primal feasible, \(B^{-1}b \geq 0\), and dual feasible, all reduced costs of the right sign; \(b\) enters only the first condition and \(c\) only the second.

Throughout, the running example is Example 2.3.1 (maximise \(10x_1 + 15x_2\) with resources \(b = (26, 56, 5)\)), with optimal basis \(\{s_3, x_1, x_2\}\), \(x_B = (3, 8, 10)\), \(Z = 230\), and shadow prices \(y = (\frac 53, \frac {10}3, 0)\), and \[ B^{-1} = \begin {pmatrix} 1 & -\frac 12 & 1 \\ \frac 23 & -\frac 16 & 0 \\ -\frac 13 & \frac 13 & 0 \end {pmatrix} \] from the final tableau of Example 3.2.1 (rows for \(s_3\), \(x_1\), \(x_2\)).

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.