6.2 Changes in the objective

A change in \(c\) leaves \(x_B = B^{-1}b\) feasible and alters only the reduced costs \(\bar c_j = c_j - c_B^{\mathsf T}B^{-1}A_j\) (for the maximisation, optimal while all \(\bar c_j \leq 0\)).

• If \(c_j\) belongs to a non-basic variable, only \(\bar c_j\) changes, and by the same amount: the basis stays optimal while \(c_j\) rises by less than \(-\bar c_j\). This is how much a product’s profit must improve before it is worth making.
• If \(c_k\) belongs to a basic variable, \(c_B\) changes, so every reduced cost changes, linearly in \(c_k\); the range is the interval on which all of them keep their sign. The solution \(x\) is unchanged on that range, and the value changes by \(x_k\) per unit change in \(c_k\).

For the running example the ranges are \(7.5 \leq c_1 \leq 30\) and \(5 \leq c_2 \leq 20\) (Software 6.5.1), the second agreeing with the graphical calculation of the problem at the end of the section on geometry. The analogue of Theorem 6.1.3 is that the optimal value is a convex piecewise linear function of \(c\), the maximum of \(c^{\mathsf T}v\) over the vertices \(v\) of the primal region.

Ranges hold for one coefficient at a time. For simultaneous changes the \(100\%\) rule (Bradley, Hax and Magnanti) gives a sufficient condition: if each change is expressed as a fraction of the allowed change in its direction, the basis remains optimal when the fractions add up to at most \(1\).

Questions on this section

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