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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.