3
$\begingroup$

Suppose I have a LP problem of the kind $\max f(x) = 2x_1 + c_2x_2$, subject to several restrictions. Suppose I know that the point $(a, b)$ is optimal. How much can $c_2$ change so that $(a, b)$ remains optimal?

Apparently I need that the gradient of the objective function remains within the angle of the restriction lines that meet to form the optimal vertex. But I don't know how to formulate that analytically.

1 Answers 1

3

Here's an example, and hopefully you can see how to adapt it to your problem. Suppose we are trying to solve the LP $\max \text{ } 2x_1 + c_2 x_2$ $\text{s.t. } x_1 + x_2 \leq 1$ $x_1 \leq 0.5$ $x_1, x_2 \geq 0$

The graph below gives the feasible region and, for $c_2 = 1$, the level curve (in yellow) of the objective function at the optimal solution $(0.5, 0.5)$.
enter image description here

Now, if you increase $c_2$, the level curve through $(0.5,0.5)$ will rotate counterclockwise. The point $(0.5,0.5)$ will remain optimal until the yellow line lies on top of the blue line: enter image description here

So $(0.5,0.5)$ will remain optimal as you increase $c_2$ until the level curve of the objective function is parallel to the constraint $x_1 + x_2 \leq 1$; i.e., until $c_2$ reaches $2$. You can also think of this in terms of slopes; the slope of the level curve of the objective function is $\frac{-2}{c_2}$. You can increase $c_2$ while keeping $(0.5, 0.5)$ optimal until the slope is the same as for the constraint $x_1 + x_2 \leq 1$; i.e., until the slope equals $-1$.

In the other direction, as you decrease $c_2$, the level curve through $(0.5,0.5)$ will rotate clockwise. And $(0.5,0.5)$ will remain optimal until the yellow line lies on top of the red line:

enter image description here

So $(0.5,0.5)$ will remain optimal as you decrease $c_2$ until the slope of level curve of the objective function is undefined. Making $\frac{-2}{c_2}$ undefined means decreasing $c_2$ to $0$.

Thus, for this problem, the range of values for which $c_2$ remains optimal is $0 \leq c_2 \leq 2$.