$2($a$)$ Consider the following LP:

max$6x_1-3x_2$

subject $to2x_1+3x_{2}3$

$6x_1+2x_{2}4$

with $x_1,x_{2}0.$

$($i$)$ Reformulate the LP into a Standard Form $($SF$)$ LP$.$

$($ii$)$ Write a Simplex Tableau for your SF LP$.$

$($iii$)$ Explain why the tableau is not in Canonical Form $($CF$).$

$($iv$)$ The Dual Simplex method $($DSM$)$ is needed to pivot to CF$.$

A$.$ Which row & column should you pivot on$?$ Explain your choice.

B$.$ Use the DSM to pivot to CF $$ explain each row operation clearly.

$($v$)$ Explain why the tableau is not in Optimal Form $($OF$).$

$($vi$)$ The Simplex method $($SM$)$ is needed to pivot to OF$.$

A$.$ Which row & column should you pivot on$?$ Explain your choice.

B$.$ Use the SM to pivot to $OF-$ explain each row operation clearly.

$($vii$)$ Explain why the tableau is now in OF$.$

$($viii$)$ What are the the optimal values of $x_1,x_2$ and the objective function $z$ for the

original max problem?

$($Q$.2$ is continued on the next page.$)($b$)$ As part of the process of formulating an LP in SF$,$ "free variables" must be expressed

in terms of non$-$negative variables.

$($i$)$ Starting with a LP that is otherwise in $SF,$ explain carefully how free variables

can be eliminated using the expression $x=y-$ we where $e$ is a constant vector

of ones, $x$ is a vector of free variables, $y$ is a non$-$negative vector and $w$ is a

non$-$negative scalar variable.

$($ii$)$ Consider your starting tableau in part $($a$)($ii$)$ of this Question with the non$-$

negativity conditions dropped. Explain why an extra column must be added to

the starting tableau. Write the extra column of the tableau.