Homework 5, due Mar 9 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
MISTAKE CORRECTED: I had c > 0 earlier where it should be c < 0 (see below).
Modify the Matlab program simplx.m as follows
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.