Problem $1.$ Consider Problem $5\mathrm{.}2in$ Chvatal.

$(1)$ Write down the dual $LP.$

$(2)$ Solve the dual $LP$ using the simplex method and write down its optimal basic

feasible solution $y^{*}.$ Hint: $An$ optimal basis $is\{5,8\}.$

$(3)$ Read off the primal optimal solution $x^{*}$ from the optimal tableau $of$ the dual $LP.$

$(4)$ Check that $x^{*}is$ feasible for the primal problem and that strong duality holds. $\begin{array}{cc}5\mathrm{.}2& \text{M}\text{a}\text{x}\text{i}\text{m}\text{i}\text{z}\text{e}\\ -x_1-2x_2& ?\\ ?& \text{s}\text{u}\text{b}\text{j}\text{e}\text{c}\text{t}to\\ -3x_1+x_2& -1\\ ?& x_1-x_2\\ 1& ?\\ ?& ?\\ -2x_1+7x_2& 6\\ ?& 9x_1-4x_{2}r\\ 6& ?\\ ?& ?\\ -5x_1+2x_{2}r& -3\\ ?& ?\\ 7x_1-3x_{2}r& 6\\ ?& ?\\ x_1{x}_{2}r& 0.\end{array}rrrrrrrrrr$