changes on RHS of a constraint in LP

324 Views Asked by At

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?