z x RHS

$1$ cBB$1$A $$ c cBB$1$

b

$0$ B$1$A B$1$

b

Assume that current basis is optimal.

$($a$)$ Tuna knows that cBB$1$

b is the objective function value. He says that if we change a non$-$basic

c $($for example, we change c$4$ and x$4$ is non$-$basic$),$ since we only have cB in that multiplication,

the optimal value cannot change. Explain why this may not be true by showing the cases

where he would be right or wrong.

$($b$)$ Now he argues that changing cB will change the objective function value since it is calculated

by cBB$1$

b$,$ however, the optimal solution will not change since it is calculated by only B$1$

b$.$

Again explain the cases where he would be correct and would not be correct and hope that

he gets it$.$

$($c$)$ Suppose that x$1$ is a non$-$basic variable. Someone changes both the coefficient column it

corresponds $($a$1)$ and its objective coefficient $($c$1).$ Thankfully, after these changes, he knows

that he should be checking the row$-0$ values. However, just when he started calculating

cBB$1$A $$ c$,$ you stop him and remind him that there are $150344$ columns $($and only $3$ rows,

such an interesting problem$)$ and he cannot do it in a reasonable time. He immediately gives

up$.$ You say that there is a much more efficient way of doing this and now you explain:

$($d$)$ Tuna is now very excited because you have taught him a very valuable trick! Now he will try

to do the same by changing a$2$ and c$2,$ however, you see that x$2$ is a basic variable. Give him

the bad news...