Homework 3, due Feb 24
(really: because of the holiday Monday, I expect
this homework to be done on time):
Exercises 2.13 and 2.14 on p.24 of the text.
Exercises 3.5 and 3.6 on p.40 of the text.
Exercises 4.4 and 4.5 on p.48 of the text.
Experiment with 3 more versions of Vanderbei's simplex pivot tool,
as follows. These refer to chapters 2, 3 and 4 in the text
respectively, which you should of course read carefully.
Phase I/Phase II: Artificial Variable x0
The objective has two rows now: the first one is for
Phase II and the second
one is the artificial variable objective in the auxiliary problem for
Phase I. You must click on
the appropriate row of the artificial variable column x0 to make the
first pivot, generating a feasible dictionary for the auxiliary problem,
eliminating all the purple colors in the left column and generating yellow
colors in the second row, highlighting the possible entering variables
for the auxiliary problem. If the original problem is infeasible, you
should be able to reduce x0 to zero and make the yellow colors all disappear,
and then continue with Phase II as usual.
Using the Lexicographic Rule to handle Degeneracy
Here e1,e2,e3,e4 are the epsilons explained in Chapter 3. In order
to figure out which variables leave the basis, you need to remember that
the epsilons are part of the current basic variable values and that
e1 >> e2 >> e3 >> e4.
The Klee-Minty example showing the Simplex Method can take Exponential time
Here b1,b2,b3,b4 are again components of the objective
function (text p.44), but this time they are really part of the problem
and not perturbations to it. As in the previous case, in order to figure
out the leaving variables, you need to remember the ordering; this time
b1 << b2 << b3 << b4.
The coefficients used are powers of 10 in the book
and powers of 2 in the tool.
In all cases,
use the default values for rows, cols and seed (which initializes the
random number generator), but change the number of problems to 5 instead of 10
(there is only 1 in the Klee-Minty case).
First experiment with the tools, listing your own email address so the
automatic grading program sends you the results and you can make sure
the system is working properly. Remember that nothing will get sent unless
you press Submit, and you cannot do that until you have completed all the
problems. 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.
When everything is working properly, arrange for the scores to be sent to
the grader (yangxi@cims.nyu.edu). However, if, as some students have
reported, you cannot get the program to send the grades to you or the
grader, don't worry about it. We'll take care of it later.
Added 2/18/98:
Important: it turns out that you cannot use Pine to read the email which is
sent by the grading program. You must use Mail or Elm to read it.
Sorry about the confusion!
For question 3.5 on p.40, assume that the initial dictionary is not degenerate.
Please 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"