Simplex V 1.05 -------------- Simplex is an LP solver program for the HP49. It is written as a single SysRPL object for speed and ease of use. It can do exact arithmetic to avoid round off errors. License ------- Simplex: SysRPL linear programming solver for the HP49 calculator. Copyright (C) 2001-2003 Peter Österlund. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; see the file COPYING. If not, write to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. Description ----------- This program solves the LP problem min c*x st A*x = b x >= 0 There are no special requirements on c, A and b, in particular, b may have negative elements. If the problem has inequality constraints, slack variables must be added manually. The input to the program is a single matrix in the form: [[ A | b ] [---+---] [ c | 0 ]] The result will either be an error message (infeasible or unbounded problem) or a vector containing the optimum variable values and the optimal value of the objective function: [ x | z ] Features -------- * This program can do exact arithmetic if the input matrix is exact. For this reason, the program can not easily be made to work on an HP48. * This program honors system flag -100 (step-by-step mode). If this flag is set, the program stops after each step in the algorithm. See below for an explanation of the algorithm and for the meaning of the extra elements in the intermediate matrices. Examples -------- Suppose you want to solve the following problem: min -7 * x1 - 2 * x2 -1 * x1 + 2 * x2 <= 4 5 * x1 + 1 * x2 <= 20 -2 * x1 + -2 * x2 <= -7 After adding slack variables, the required input matrix becomes [[-1 2 1 0 0 4] [ 5 1 0 1 0 20] [-2 -2 0 0 1 -7] [-7 -2 0 0 0 0]] Putting this matrix on the stack and running the program gives the following result: [36/11 40/11 0 0 75/11 -332/11] which means that the optimal value is -332/11 and this value is attained for x1=36/11 and x2=40/11. Algorithmic details ------------------- The program uses the standard simplex algorithm. All required data is kept in the matrix all the time, and the algorithm works by performing row operations (RCI and RCIJ) on the matrix. The steps in the algorithm are as follows: * Make b>=0 by multiplying needed rows with -1. * Add artificial variables. * Optimize the artificial objective function to find a feasible solution. * If no feasible solution was found, abort with error message. * Remove the artificial variables. * Optimize the original objective function. * If the solution is unbounded, abort with error message. * Create solution vector. During the computations, an extra row is added at the bottom of the matrix. This row keeps track of the current basis variables and also keeps track of the current state of the algorithm. There are four possible states: 0 before artificial variables have been added 1 when solving for a feasible solution 2 after the artificial variables have been removed 3 When the current solution is dual feasible but not primal feasible The program starts in state 0 and proceeds to state 1 and 2 if all goes well. State 3 is never entered automatically by the program, but it can be used manually when the dual simplex algorithm is preferred. If the program aborts because of an infeasible or unbounded problem, the matrix will be left on the stack in the state it had when the error was detected. Compiling --------- The source code was compiled on a RedHat Linux 7.1 machine. I used the HpTools compiler/assembler, version 3.06. Version 2.x will not work because the source uses features unique to the HP49. The HpTools package is available from www.hpcalc.org. The 'm4' macro preprocessor is also required. It is used to make it easier to call subroutines in SysRPL programs. The provided Makefile should work in unix-like environments, provided that the SASM_INCLUDE environment variable has been set to point to the directory where the file with supported entry points is located. (This file must be called "SupRomEntr_49.a" unless you change the source code.) Author ------ If you have any suggestions or bug reports, don't hesitate to let me know. -- Peter Osterlund - petero2@telia.com http://w1.894.telia.com/~u89404340