(Comp.sys.hp48)
Item: 929 by george@unixg.ubc.ca [George chow]
Subj: Here's my implementation of the Simplex Method
Keyw: simplex method, linear programming
Date: Wed Apr 15 1992

The following directory contains a set of routines for the Primal Simplex
Algorithm with full tableau. The routines allow one to manually step through
the method by choosing each pivot or to have the automatic procedure execute
the entire method for you. (I haven't tried mixing the two...)

For the dual problem

  P = max { c^T x : A x <= b, x >= 0 }
  D = min { y^T b : y^T A >= c^T, y >= 0 }

this implementation requires an initial tableau with the following layout:

          +---+---------+---------+
          |   |         |         |
          |   |         |         |
          | b |    A    |    I    |
          |   |         |         |
          |   |         |         |
          +---+---------+---------+
          | 0 |  -c^T   |    0    |
          +---+---------+---------+

After each step, a copy of the tableau can be returned to be stack. The
returned tableau has layout:

          +---+---------+---------+
          |   |         |         |
          | ^ |         |         |
          | b |    U    |    B    |
          |   |         |         |
          |   |         |         |
          +---+---------+---------+
          | a |    n    |    y    |
          +---+---------+---------+

For instance, the problem:

  max { 3 x1 + 2 x2 } subject to
  
    x1 + 2 x2 <= 3
  2 x1 -   x2 <= 2
   -x1 + 2 x2  = 1
    x1        >= 0
           x2 >= 0

has initial tableau:

       x1 x2  e1 e2 e3
 [[ 3   1  2   1  0  0 ]
  [ 2   2 -1   0  1  0 ]
  [ 1  -1  2   0  0  1 ]
  [ 0  -3 -2   0  0  0 ]]

where e3 is artificial.

The algorithm is split into 3 phases:
  Phase 0: drive all artificial variables out of the basis
  Phase 1: eliminate all negative components of b.
  Phase 2: eliminate all unwanted negative components of n and y.
  
Here is a description of each routine:

INIT: This must be run before any of the other routines will work correctly.
      INIT precomputes all of the dimensions and indices needed by the other
      routine. It takes as argument from the stack the initial tableau and the
      index of the artificial variable block. One must keep all the artificial
      variables to the extreme right hand side. The index that is provided is
      the beginning of the artificial variable sections. In the above example,
      we would have an index of 3.  [Note: User Flag 1 controls whether or not
      a copy of the tableau is left on the stack, I think.  -jkh-]
      
FIND.P0.COLUMN: takes a row index from the stack and returns the index of the
                first non-zero element of that row or 0 if none. This is used
                for picking the pivotal column in Phase 0.

\GB.STATE: returns the index of the first negative component of b or 0 if
           none.

FIND.TARGET.COLUMN: takes a row index from the stack and returns the index of
                    the first negative element of that row or 0 if none. This
                    is used for picking the pivotal column in Phase 1 and 2.

GEN.RATIO: generates the list of ratios b[i]/A[i][j] for the argument row i.
           These ratios are used with MIN.CRITERION to pick the pivotal row.
             
MIN.CRITERION: returns the index of the element in the argument list with the
               small value.

PRIMAL.STEP: takes as argument a row and a column index. Performs the required
             row operation on the tableau.
             
DOIT: This starts the automatic Simplex method. This will step thru all three
      phases of the Simplex method and return the final tableau.
  
      
Full Example:
  1. Download the SIMPLEX directory to your hp48sx
  2. CRDIR a new directory inside SIMPLEX called TEST
  3. Change into the directory TEST
  4. Key in the above matrix and store as INIT.TABLEAU
  5. Put INIT.TABLEAU's contents and a 3 on the stack
  6. Set user-flag 1 (1 SF) and press [CST]
  7. Execute INIT
  8. You should get a copy of INIT.TABLEAU on the stack
  9. Since we have an artificial variable, we need to do Phase 0:
 10. Do: 
        3 2 STEP
     You should get back:
        1: [[4 0 4 1 0 1]
            [4 0 3 0 1 2]
              [-1 1 -2 0 0 -1]
              [-3 0 -8 0 0 -3]]
     You have just pivoted with row 3 and column 2 (which is a -1)
     Since we only have one artifical variable, we're done in Phase 0 and can
     proceed to Phase 1.
 11. We want to use the -2 in row 3 as our pivot. Do:
        3 3 STEP
     You should get back:
        1: [[2 2 0 1 0 -1]
            [2.5 1.5 0 0 1 .5]
              [.5 -.5 1 0 0 .5]
              [1 -4 0 0 0 1]]
                                   ^
 12. We now have all elements of b positive so Phase 1 is done. We proceed to
     Phase 2. We take the second 2 in row 1 as our pivot. Do:
        1 2 STEP
     You should get back:
        1: [[1 1 0 .5 0 -.5]
            [1 0 0 -.75 1 1.25]
              [1 0 1 .25 0 .25]
              [5 0 0 2 0 -1]]
              
                         ^
 13. Since we now have b positive and all needed elements of n and y positive,
     we're done. Our optimal program is:
         x = [1 1]
           y = [2 0 -1]
           n = [0 0]
           e = [0 1 0]
     with optimal value 5.
     
 14. Using the automatic routine gives us the same result. Do:
         1  SF  INIT.TABLEAU  3  INIT  DOIT
     You should get three tableaux, the final of which gives you the same
     optimal program.
  

Notes: 
  1. There are no smarts in DOIT. Conceivably, it can get trapped in a cycle
     very easily. I wrote this as an aid for my homework, not to solve `real'
     optimization problems.
  2. This implementation isn't very fast. A typical homework problem with a
     5x7 tableau takes about 70-90 seconds for DOIT to process.
  3. Generating the initial tableau is a hassle but I haven't found a fast way
     for the machine to do it.  Where possible, start typing into your HP
     ASAP.  ;)
  4. If you have any comments/bug-reports/problems, please email me.
  5. I'm working on the implicit method.