Homework 2, due Feb 10:

  • Experiment with Vanderbei's Simplex Pivot Tool . Use this link (not the one from the text book home page), with the default values for rows (m), cols (ntilde), seed (which defines the random number generator), and the number of problems (10). Include the grader's email address (yangxi@cims.nyu.edu) so he is informed of your scores. You may exit and restart at any time.

  • Verify that my Matlab code simplx.m (see course home page) generates the same answers as the Simplex Pivot Tool, provided you use the same strategy to choose the entering and leaving variables in both cases. In particular, verify that the dictionary is the same at every step (make sure the definitions of y and BinvN do not have semicolons so their output is not suppressed). You need to press any key to continue after the message about which variables enter and leave the basis. If the dictionaries differ from those generated by the Simplex Pivot Tool, probably you are doing something wrong: come and see me. You do not need to test all the problems; just run enough to convince yourself and provide evidence that this is the case (a few pages of output, not too much). To get output from a Matlab session, type help diary . Before calling the script simplx , you need to define the quantities Atilde, b, ctilde and maxit . To find out how to set up a matrix in Matlab, type help paren . For more information on Matlab, see the course home page.

  • Modify the Matlab code so that it keeps track of what variables are in the basis: at present, it computes the optimal value of the LP but does not keep track of which of the original variables (regular or slack) are in the basis and which are not. Hint: start by setting two vectors nonbasics = 1 : m (the vector [1 2 3....m]) and basics = ntilde + 1: ntilde + m , and change these appropriately at each iteration, making sure that the ordering corresponds to the ordering in the columns of B and N . Check that the updated values agree with those generated by the Simplex Pivot Tool, remembering that w_j is the same as x_(ntilde + j) . Turn in a program listing highlighting the change you made together with evidence that it works correctly.

    The harder problem of changing the code to use the simple updating explained in Chapter 1 instead of the overkill of the "backslash" opertor to compute B^(-1) N and B^(-1) b is postponed till after the next class.