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.

Bugs. This applet works fine when accessed via Netscape3 on most UNIX workstations and it works fine with either Netscape4 or InternetExplorer4 on WindowsNT. Most other browser/platform combinations do not work correctly. The problem seems to be due to bugs in the browser's JAVA interpreter as implemented on the given platform. If you have trouble getting the applet to behave as described above, try finding a different browser/platform combination.