1. Is the following tableau optimal

under the circumstances below?  If it is optimal, also state the value of the optimal objective function.

(a) The problem is a minimisation problem and the z-row of the tableau was initialised with the cost vector (ct ).

(b) The problem is a maximisation problem and the z-row of the tableau was initialised with the cost vector (ct ).

(c) The problem is a minimisation problem and the z-row of the tableau was initialised with the negative of the cost vector (-ct ).

(d) The problem is a maximisation problem and the z-row of the tableau was initialised with the negative of the cost vector (-ct ).

2.  Consider the linear program

max   5x + y

s.t.

x + y s 7

x - y s 3

x, y > 0

(a) Derive the dual linear program.

(b) Plot the feasible regions to both the primal and the dual problems.

(c) Solve the primal problem using the simplex method.  In each iteration, indicate on the graphs both the current primal basic feasible solution and its corresponding dual solution.

3. The simplex method is a typically efficient algorithm for solving linear programs.  However, there is no version of it that has been shown theoretically to solve any linear program in polynomial time. In fact, it is much worse. In 1972, Klee and Minty came up with an example in n dimensions that requires 2n  - 1 iterations if Dantzig’s rule1  is used to choose entering variables. These problems are of the form

n

max      10n −j xj

j=1

s.t.

2  10i −j xj 、+ xi  s 100i − 1 ,    i e {1, 2, . . . , n}

xj  > 0,    j e {1, 2, . . . , n}.

(a) Write the problem for n = 3.

(b) Solve the problem using Dantzig-rule.