Let's say we have the following optimization problem :
Max cx
Subject to $Ax=b$ with $x\geq0$
How can we find the interval of the values for the coefficient $c_{j}$ of the objective where the optimal solution stays always the same ?
Do I have to think of the slope ? I don't get it.
Normally if we imagine the graph, we can say that if we have a line that passes by a point, if we change the slope, the optimal value would stay the same as long as we are between the lines on the consrtaints.
I would appreciate any answer/ guide.
$\endgroup$ 71 Answer
$\begingroup$You can solve problems like these with the revised simplex method. The solution $x = B^{-1}b$ remains optimal as long as the dual variables are negative: $c_N - c_B B^{-1} N \leq 0$. If you fill in $B$ and $N$ you obtain the condition on $c_j$.
$\endgroup$ 1
