1
$\begingroup$

Ok so we have the following linear problem:

$\max10x_1+10x_2+9x_3$

$s.t$

$2x_1+3x_2+4x_3\le24 $

$3x_1+4x_2+5x_3\le33 $

$x_1,x_2,x_3\ge0 $

By using simplex i can easily find that the optimal solution is $x_1=11, x_2=x_3=0.$ .My question is this. Suppose 33,24 are our resources for producing products. Ηow much can we increase or decrease 33 and keep our solution optimal??? The example is to make me understand this more easily, i am looking for a general way to examine how much we can change a constraint in a linear program while our solution stays optimal.

$\endgroup$
1
$\begingroup$

Here is a general approach.

Solve the original (a.k.a. baseline) problem, producing optimal solution $x^*$, with corresponding optimal objective value $V^*$

Now pick a single inequality ( $\le$ )constraint, with all terms involving the variables on the left-hand side.

If this inequality is satisfied with equality at $x*$, no decrease of the right-hand side value is possible without making $x^*$ infeasible, and therefore non-optimal (but see next paragraph). If it is not satisfied with equality at $x*$, the right-hand side value can be decreased without making $x^*$ non-optimal down to the value the left-hand side attains for $x^*$.

If this inequality is satisfied with equality at $x*$, you can find out down to what right-hand side value the optimal objective value, $V^*$, can be maintained (but with a different optimal x) by solving another Linear Programming problem. Specifically, the new problem is the same as the original problem, except that the objective function is changed to minimize $R$, the inequality constraint in question is changed to have right-side of$R$, and another constraint is added: original objective function $ = V^*$ (in your example, $10x_1 + 10x_2 + 9x_3 = V^*$). The optimal value of R returned by the program is the minimal value of right-hand side for the inequality constraint in your original problem such that the optimal objective value is unchanged.

The maximum right-hand side value for the specified inequality constraint for which the solution $x^*$ remains optimal can be handled in a similar manner. Note that if the right-hand side value is increased, $x^*$ can never become infeasible, so it's just a question of at what point a better solution becomes optimal. Therefore, solve a new problem, exactly as described in the previous problem, except that the added constraint is: original objective function $\ge V^* + \text{tol}$, where $\text{tol}$ is some minimum amount by which the optimal objective value must improve, and must be greater than solver constraint tolerance; so $\text{tol}$ of say, 1e-4. If this new problem is infeasible, then $x^*$ remains optimal (within objective value tolerance of $\text{tol}$) for the original problem, no matter how much the right-hand side value of the inequality constraint is increased.

In your particular example, solving the problems in the two preceding paragraphs shows that if the right-hand side value of 33 is decreased at all, the optimal objective value decreases, and if it is increased at all, the optimal objective value increases.

$\endgroup$
0
$\begingroup$

If we rewrite this example like this:
$2x_1+3x_2+4x_3≤a_1$
$3x_1+4x_2+5x_3≤a_2$
Then $x_1=\min([\frac{a_1}{2}], [\frac{a_2}{3}]), x_2,x_3=0$ will be optimal. So if you increase/decrease your $a_1$ or $a_2$ so that the minimum changes the optimal solution will shift. Note that sometimes there is more than one optimal solution.

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