1

enter image description here

Question: What change in the RHS vector $b=(8,4)^T$ would increase on the optimal value of the objective function?

Attempt:

Suppose we change the first component of $b$, say now we have $b' = (k,4)$, the basis matrix $B = [ (1,-1)^T; (0,1)^T] $ and we see that $$ B^{-1} b' = (k, 4+k)^T $$

now this values correspond to objective coefficients of the dual, thus in this cases the dual is a multiple of $k$ and since $k \geq 0 $( for which otherwise we lose feasibility, then the increase in the optimal is a multiple of $k$.

Now, if we were to increase the second component, say now our new $b$ is $b' = (8,k)^T$, then we have

$$ B^{-1} b' = (8, 8+k)^T $$

So in this case the dual objective is of the form $8y_1 + 8y_2+ky_2$ which evidently gives a lesser value than before.

IS this correct?

Community
  • 1
Mikey Spivak
  • 871
  • The part "now this values correspond to objective coefficients of the dual" is wrong: you computed the change in $x$. Multiply with $c_B$ to compute the change in objective value. – LinAlg Nov 26 '18 at 20:24
  • Isnt it dual objective $z = b_1 y_1 + b_2 y_2 $ where $b_1,b_2$ are the new values? – Mikey Spivak Nov 26 '18 at 20:30
  • That is indeed the dual objective (with $b_1=k$, $b_2=4$), but the dual objective requires $y$ which you have not computed yet. – LinAlg Nov 26 '18 at 21:20

0 Answers0