SIMPLEX ------- Simplex algorithm Made by Anders Forsberg in Mars 2000 Program version 1.00 SIMPLEX is a linear programming problem solver. It solves the following type of problems (using the "well known" algorithm Simplex): max/min cx Ax=b b>=0 x>=0 The condition of solving the problem is that you have a allowed starting base. Finding a allowed starting base can be difficult but can be solved by inserting more x variables and solving the new problem. This is called "Simplex phase 1", please check any book about "Combinatorial Optimization" to find out how this is done. The program can solve problems from "Simplex phase 1" but you have to enter them manually. If you supply the program with a allowed starting base you will get a optimal solution (if there is one) and the corresponding x values. If the solution is unbound the program will provide you with the direction that the problem is unbound in. Please observe that, if you supply a non valid starting base the solution will usually NOT be optimal or valid! ------------------------------------------------------------------------ Quick start: 1. Download program (to any folder). 2. Type "simplex()" 3. On the appearing dialogue box, enter (please watch out for unintentional use of "Alpha-lock"): 3.1 A is the conditions matrix 3.2 b is the right hand side row-matrix of the equation 3.3 c is the goal function row-matrix 3.4 bix is a row-matrix containing the index for a valid starting base 3.5 Choose if the problem is a max or min problem 4. Press "enter" and watch the solution appearing in the ProgramIO window. "z*" is the solution and direction (if applicable) is the direction which the problem is unbound (the solving is very slow for large matrixes). ------------------------------------------------------------------------ Interesting variables: x contains the x values z contains goal function value i,j latest base/nonbase index that were exchanged dir contains unbound direction (if applicable) There are some more variables used to store the entries made in the dialogue box. ------------------------------------------------------------------------ Notes about the program: It is made on my TI89 with OP-version 2.03 with English language. It has not been tested on a TI92 and not on any of the Language Localization platforms. I think it will work on the older OP but I have not tested that either. I do not intend to develop it further but fell free to use it as you like (I or Texas Instruments shall not be liable for any indirect, incidental or consequential damages, lost of profits, loss of use or data, or interruption of business from use of the program). In the zip file (For unzipping: "WinZip" http://www.winzip.com ) there are two programs for testing. Execute (in the same directory as "simplex") "normal()" or "unbound()" before "simplex()" the get the fields in the dialogue box filled out with an example. I made this program for a course in Combinatorial Optimization i took at Linkoping University. It is a translation from a Matlab code I and a friend) made in the lab course. Please read some book about Simplex to find out how the algorithm works (you can also find som information on http://www.isye.gatech.edu/~spyros/LP/LP.html ). Anders Forsberg 12 Mars 2000