Consider the 2-variable LP instance in Figure 7.9 and equation (7.29).

(a) State the instance in the (LP) standard form format above, fixing a = 1>4.

(b) Construct the basic solution corresponding to x112 in the figure.

(c) Show that movement to figure solution x122 can be understood as the simplex direction introducing the slack variable on constraint x1 … 1 and that it is both feasible and improving in your forulation of (a).

(d) Show how similar simplex moves lead to figure points x132 then x142.

(e) Explain how this suggests that simplex can take exponentially many iterations to compute an optimum for simple instances like (7.29).

(f) How can this exponential behavior on specific instances be reconsiled with the generally excellent performance of the simplex algorithm on most LPs?