Problem $1(25$ points$).$ Solve the following $LPs$ using the two$-$phase simplex method.

$mamize,6x_1+x_2,$

subject $to-x_1+3x_2,6$

$,x_1-3x_2,=6$

$,x_1+x_2,1$

$,x_1,x_2,0$

Part I $(10$ points$)$: formulate the auxiliary $(phase-I)LP.(introduce$ the slack and auxiliary variables for

each $of$ the constraints$)$

Part $II(5$ points$)$: determine the initial basic and non$-$basic variables for the phase$-$I $LP.$

Part III $(5$ points$)$: solve the phase$-$I $LP$ using simplex method.

Part $IV(5$ points$)$: starting from the optimal basic and non$-$basic variables for phase$-$I $LP,$ remove the

auxiliary variables, and use the rest basic and non$-$basic variables $to$ start simplex for the original $LP.$