Problem $4($Shadow Prices$).$ Again suppose x$$ is an optimal solution to the max LP$,$ and y$$ is an optimal solution for the dual min LP$,$ so MAX $=$ c$$x$=$ b$$y$=$ MIN. Now suppose we modify b slightly, replacing b with b$\text{'}=$ b$+\backslash$Delta $,$ where $\backslash$Delta in $$m is a vector $($we think of $\backslash$Delta as a "small change" in b$).$ Let MAX' be the value of the modified max LP$.$ Likewise let MIN' be the value of the modified min LP$,$ again replacing b with b$\text{'}.$

$($a$)$ Argue that y$$ is still feasible for the modified min LP$,$ and MAX' $<=$ MAX $+\backslash$Delta $$y$.($Hint: use "weak duality", Lemma $29\mathrm{.}1.)$

$($b$)$ Argue MAX' $=$ MAX $+\backslash$Delta $$y$$ if$-$and$-$only$-$if y$$ is an optimal solution for the modified min LP$.($Remark: this often happens, if y$$ is a "vertex" of its feasible region, and $\backslash$Delta is small enough.$)$

$($c$)$ Consider the example on page $855(855-$max.lp$,$ x$=[2,6]$T$,855-$min.lp$,$ y$=[0,7/9,1/9]$T$,$ MAX$=$MIN$=8).$ Note b$=[8,10,2]$T$.$ Suppose we replace b with b$\text{'}=$ b$+\backslash$Delta $,$ where $\backslash$Delta $=[0,1,0]$T$.$ Show that MAX'$=$MAX $+\backslash$Delta $$y$.($You can do this by hand, or numerically using an LP solver.$)$