11 Consider the following LP:

a Find all the basic feasible solutions for this LP.
b Show that when the simplex is used to solve this LP, every basic feasible solution must be examined before the optimal solution is found.
By generalizing this example, Klee and Minty (1972)
constructed (for n 2, 3, . . .) an LP with n decision variables and n constraints for which the simplex algorithm examines 2n 1 basic feasible solutions before the optimal solution is found. Thus, there exists an LP with 10 variables and 10 constraints for which the simplex requires 210 1
1,023 pivots to find the optimal solution. Fortunately, such “pathological” LPs rarely occur in practical applications.

max z=10x1 + x2 s.t. x1 VI 20x1 + x2 100 X1, X20