Homework 5, due Mar 9

MISTAKE CORRECTED: I had c > 0 earlier where it should be c < 0 (see below).

Modify the Matlab program simplx.m as follows

  • First modify it slightly so that it implements the form of the primal simplex method on p.96 (ask me for a copy if you don't have the book). The only difference is that instead of computing xB and y (which is really yN) directly, it updates them from their previous values. EXPLAIN IN THE COMMENTS WHY THE TWO ALGORITHMS SHOULD BE IDENTICAL IN EXACT ARITHMETIC. I was confused about this in class last night. It has nothing to do with the Sherman-Morrison-Woodbury formula. It follows directly from the primal and dual dictionaries. The way I wrote the program originally, the new xB and the new yN are computed at the top of the loop using the NEW dictionary, that is the NEW B. The way it is done on p.96, the new xB and the new yN are computed at the bottom of the loop from the OLD dictionary, that is using the old B, assuming the old xB and yN are known and making use of the dictionary formula for the new xB and the new yN as a function of the entering variable.

  • Experiment with the two versions of the code, on problems for which b > 0 (but not c < 0) so you have an initial primal feasible point. Do you they give exactly the same results? If they are very different, there is undoubtedly a bug. Compare the final iterates by subtracting them from each other. I would expect the difference to be around unit roundoff (about 10^(-16)). Is this still true as you run bigger random problems? Type "help rand" to find out how to generate random matrices.

  • Modify the Matlab code further to implement the dual simplex method, and run it on random problems with c < 0 (but not b > 0), so you have a dual feasible initial point.

  • Modify the code further to implement the primal-dual simplex method. Test it on problems with
    --- b > 0 (compare it to the primal simplex method: are the iterates the same?)
    --- c < 0 (compare it to the dual simplex method: are the iterates the same?)
    --- neither b > 0 nor c < 0
    Test the program carefully, on the example in Chapter 7, and on one of the examples generated by the primal-dual version of the Pivot Tool, and on a significantly bigger example.

    Hand in program listings as well as output obtained using "diary" to justify the correctness of your programs. You can get nice output with proper use of "fprintf".

  • Prove that the basis matrix B is always nonsingular (in exact arithmetic) if you start with B set to the identity matrix (or any other nonsingular matrix).

  • Following the symmetric definition of the primal and dual dictionaries, show AT LEAST ONE of the 3 parts in the Exercise at the bottom of p.7 of my hand written notes.