Homework 4, due Mar 2
(really: because this is simple)
Experiment with
the one-phase primal-dual method version of
Vanderbei's simplex pivot tool.
This is very clearly explained in the text in Chapter 7.
The second row (all -1's) and the second column (all 1's) ARE CONSIDERED
to be MULTIPLIED BY MU. Notice the allowable range on mu shown at the bottom
of left. To make a valid pivot, the lower bound on mu must be reduced.
Note that the terms involving mu in the top left entry in the dictionary
(the objective value) are not shown, as they are not needed to make pivot
choices and are eventually set to zero.
Use the default values for rows, cols and seed,
but change the number of problems to 5 instead of 10.
Have the program submit your score to the grader (yangxi@cims.nyu.edu)
as usual. You may exit and restart at any time.
You may want to experiment by setting the number of problems to
1 or 2 first. If you have trouble, send me email or phone me any time.
What is the significance of the highlighted yellow box in this tool?
Answer this in an email to the grader.
What happens in this algorithm if (a) the primal is infeasible,
(b) the dual is infeasible, or (c) both are infeasible? Answer with an
email to the grader.
It may help to experiment with
this version of the pivot tool which allows you to set your own data.
This way you can enter the data for the example on p.106-108, by setting
Rows to 3, Cols to 2 and using the Reset button in the tool, and then you
can work through the example, following the book.
As noted in class, there is a typo on p.107: in the last
last line (x5) of the first dictionary, there should be a -x1.
Sorry that the last class was not very well prepared. The next lecture will
be much better: we will show using matrix notation that the primal and
dual dictionaries are negative transposes of each other, and this will
give us a clean, short proof the strong duality theorem. I was not able
to find this in any book, but it turns out there is a nice way to do it.
The next homework (now posted) will ask you to modify the
Matlab program simplx.m to implement some of these simplex variants.
Remember to subscribe to the class mailing list, by sending email to
majordomo@cs.nyu.edu with the message body "subscribe g22_2730_001_sp98@cs.nyu.edu"