Question $1$

$(16$ points$)$ Provide explanations for your answers below. An answer that may seem correct with

an incorrect or missing explanation will receive zero credit.

a$.(3$ points$)$ A problem with an unbounded feasible region cannot have an optimal solution. True

or false? Explain your answer or provide a counter$-$example.

b$.(3$ points$)$ In each iteration of the simplex method, the value of the objective function strictly

improves. True or false? Explain your answer or provide a counter$-$example.

c$.(6$ points$)$ Suppose we are solving an LP with $2$ variables $(x_1,x_2)$ and the resulting feasi$-$

ble region is shown below. In the current iteration of the simplex method $x_1=4,x_2=0.$ Next,

suppose that $x_2$ enters the basis. Which variable would leave the basis? $($slack variables of the

constraints $1$ through $4$ are $x_3,x_4,x_5,$ and $x_6,$ respectively$).$

d$.(4$ points$)$ An LP problem might have exactly two alternative optimal solutions. True or

false? Explain your answer or provide a counter$-$example.