$[5$ points$]$ Solve the following linear program. You can use a solver. Explain your answers to parts

$($b$),($c$)$ and $($d$)$ using sensitivity analysis.

Maximize $u=2000x_1+3000x_2+5000x_3+4000x_4$

Subject to:

$100x_1+100x_2+100x_3+100x_{4}4000$

$10x_1+10x_2+20x_3+20x_{4}600$

$20x_1+20x_2+30x_3+20x_{4}900$

$20x_1+10x_2+30x_3+30x_{4}700$

$x_1,x_2,x_3,x_{4}0$

a$.$ What is the optimal solution?

b$.$ For what range in variations in $c_3=5000$ from the optimization function does

the current basis remain optimal?

c$.$ If the first constraint $b_1=4000$ changes, for what range of supply will the basis

remain optimal?

d$.$ If the supply is within the range given by part $($b$),$ what will the profit be$?$

$[15$ pts$]$ True or False. Explain why or provide a counter$-$example.

a$.$ In the simplex algorithm, a variable that has just left the basis cannot reenter in the

very next iteration.

b$.$ In the simplex algorithm, a variable that has just entered the basis cannot leave in the

very next iteration.

c$.$ If we have a constraint in standard maximum form, and we multiply both the right$-$

hand side of each constraint by $k$ and multiply the constants in the objective function

by $k,$ the optimal solution is also multiplied by $k.$

d$.$ It is possible to construct a linear program in which every feasible point is optimal

e$.$ A degenerate LP always has multiple solutions that provide the same optimal value