Online Exercises

Simplex Method---Klee-Minty Problems


Below is a java applet that will present a Klee-Minty-type linear programming problem for you to solve. The Klee-Minty problem is to be solved using the Simplex Method with the largest-coefficient rule.

In this applet, b1, b2, b3, b4 are again components of the constant terms in each row (see the 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.

The particular Klee-Minty problem is determined by specifying the number of rows in the problem. Your instructor will tell you what value to use. In this exercise, the correct final score is 2^m-1, where m denotes the number of rows in the problem.

Be sure to enter your email address and your instructor's email address.

When you are ready to begin, press the Go Pivoting button and then, when the pivot window pops up, press the Start button.

Don't forget that incorrectly pressing the termination button, Optimal, counts as an extra pivot, so press this button only when you are confident that it is the correct thing to do.

Final note: if for any reason you wish to start over, you may press the Exit button to quit the exercise. At that point you can start afresh. Of course, at some time before this online assignment is due you must go to the end and submit a score.

Comment on Usage. If you press the Go Pivoting button twice, then you will get two windows that are initially identical. This is convenient since you can let one window lag behind the other by one iteration and thereby watch your pivots better.