From: rmarimon@leland.Stanford.EDU (Ricardo Jose Marimon)
Subject: Solving Linear Programs with SIMPLEX
Organization: DSG, Stanford University, CA 94305, USA
Date: Fri, 13 Nov 92 22:30:17 GMT

Here is a program that I hope you would all enjoy...

The program is used to solve the simplex.  I find it very fast, it can solve
a 8 variables by 5 constraints problem in less than 15 seconds performing 5
iterations on the tableau.

The problem this program is intended to solve is of the form,

        min    c.x
        st     A.x =  b    (* b must be greater than zero *)
                 x >= 0

The way the problem is entered is as a matrix of the following form,

             [ c | 0 | 0 ]
             [---+---+---]
             [ A | I | b ]

Where I is the matrix formed by adding the slack and excess variables.
And is NOT necessarily the identity matrix.

For examples to solve the following problem

           max x1 + 2 x2 + x3
           st
               x1 + x2      <= 3
               x1 - x2 + x3 <= 3
                    x2 + x3 <= 3
               x1 + x2 + x3 >= 3
                    x2      <= 2
               x1, x2, x3 >=0

We convert it to the standard form

           min - x1 - 2 x2 - x3
           st
               x1 + x2      + x4                     = 3
               x1 - x2 + x3      + x5                = 3
                    x2 + x3           + x6           = 3
               x1 + x2 + x3                - x7      = 3
                    x2                          + x8 = 2
               x1, x2, x3 >= 0

And write it as a matrix to enter it in the program.

          [[ -1 -2 -1 0 0 0  0 0 0 ]
           [  1  1  0 1 0 0  0 0 3 ]
           [  1 -1  1 0 1 0  0 0 3 ]
           [  0  1  1 0 0 1  0 0 3 ]
           [  1  1  1 0 0 0 -1 0 3 ]
           [  0  1  0 0 0 0  0 1 2 ]]

This is matrix is provided as an examples and it is stored in the
directory containing the program under the name "P" (weird name hu?).

To solve the problem right away, just enter the matrix, press the
[INIT] key which initializes some of the variables used by the program
and then press the [SOLVE] key which iterates and gives the solution
in three parts as follows,

           3:  :X: [ 2 .999999999998 2 0 0 0 2 1 ]
           2:  :\Gl: [ -1 0 -1 0 0 ]
           1:  :Z: -6

Where x is the actual point that minimizes the problem, the \Gl (lambda)
is the solution to the dual problem or shadow prices of each of the
constraints, and Z is the objective function value at the point found to
be the minimum.

This is the end of the quick start procedure to solve linear programs (LP)
with my program.  Now lets go to some details...

The solution of an LP can be classified into,

     unfeasible, when there is no point satisfying the set of constraints
     unbounded, when the set of constraints can not restrict the decrease
                of the objective function (c.x)
     feasible & bounded, when there is a solution to the set of constraints
                         which minimizes the objective function value.

The problem can handle all three cases, giving the solution when it is
feasible and bounded, providing a ray (which is a vector through which
you can infinitely decrease the objective function while remaining in
the feasible region) when the solution is unbounded, or flagging that
there is no feasible solution.

To achieve the different solutions, the program goes through the two
phase simplex method automatically (you don't have to include artificial
variables).  Phase 1 is used to derive a starting basic feasible solution 
by introducing a set of artificial variables whith the objective of
minimizing its sum; when this is achieved, the set of artificial
variables is removed and Phase 2 starts with the original objective
function.  (refer to any LP book for more details into the 2 phase
simplex method)  One important thing to notice, is that the columns
corresponding to the artificial variables, although not taken into
account on phase 2, are not removed from the problem because it is
sometimes usefull to have these columns at the end of the problem in
order to perform sensitivity analysis.

The basic algorithm that I used to solve the problem is a pseudo
revised simplex method, where all that is maintained is the inverse of
the base, the set of basic and non basic variables, and the rest of
the data provided at the initialization process.  I think this is
the most effective procedure in terms of time because it requires less
computations...

Now it will give a brief explanation of what the programs in the
directory do.  This first set of programs are the ones intended to
be used directly to solve the problem,

  [INIT]  Initializes the set of variables that are needed by the
          program.
  [TABL]  Provided the current tableau.
  [SOLU]  Extracts the solution from the current tableau.
  [SRAY]  Extracts a ray from an unbounded LP.
  [TRACE] Performs one iteration at a time, it is equivalent to solve,
          but you can take a look at the partial tableaus that are
          generated by the procedure.
  [SOLVE] Gives the answer to the LP if it exists.

This second set of programs should not be used directly unless you
REALLY know what you're doing.  There are some system-RPL programs
that can crash your system...

  [ITER]  Given which variables enter and which variable goes out,
          this program performs the necessary iterations.  Becarefull
          because the number that this programs expects are the
          indices into the BVAR and NVAR variables corresponding to
          the basic and non-basic variables.
  [INVAR] Calculates which variable enters tha base.  It returns 0
          if it is an optimum.
  [OUTVAR] Given which variable enters the base, it gives which
           variable must exit the base.  It returns 0 if the solution
           is unbounded.
  [PH1]   Performs all the calculations necesary to start phase 1.
  [PH2]   Same but for phase 2.
  [MCHOP] Given a matrix and the contents of the 'ZERO' variable
          if an element of the matrix is less than 'ZERO' in absolute
          value it changes it to 0.
  [MVIN]  Calculates the min element such that it is strictly less
          than zero.  It returns the index into the array corresponding
          to the element.  It returns 0 if no negative elements are
          found.
  [MVOUT] It performs the ratio test among two vectors.
          2: v2
          1: v1
          Returns i s.t. min over all i [ v1[i]/v2[i] for v2[i]>0 ]
          Returns 0 if all v2[i] are less or equal to 0.
  [MJOC]  Given two matrices it joins them in the standard form
          2: [ A ]
          1: [ B ]   It returns [ A | B ]
  [MSBC]  It takes the columns of a column as specified by a list
          with the numbers of the columns.
          2: [ A ]
          1: { 3 2 2 1}  It returns [ A3 A2 A2 A1 ] where Ai represents
          the ith column of A.
  [MELM]  This program is used to calculate the matrix that when
          multiplied by the inverse of the base, it gives the new
          inverse.
          2: [1 2 4]
          1: 1        It returns [[ 1 0 0]
                                  [-2 1 0]
                                  [-4 0 1]
          Multyplying by this matrix is equivalent to performing
          row reduction in row 1 (as specified by element in level 1)
          given that the column involved is specified by the element
          in level 2.
  [MBASE] It quickly calculates wether there is a base in the system
          and if there is, which one it is.  It returns a list such that
          its elements correspond to the elements of the original matrix
          that corresponds to the the columns of the identity.
  [MSPL]  It just separates the original problem form,

             [ c | 0 | 0 ]
             [---+---+---]
             [ A | I | b ]

          Into the matrices [ A | I ], [ b ], and [ c ].
  [CLR14] Clears the top 14 rows of the display.

Here are the variables used by the above procedures.  Do not play with 
these variables during a run of the problem because you might get 
incorrect answers.

  [ZERO]  Threshold after which numbers are considered to be zero.
          This in important because due to numeric problems, results
          tend to show some rounding errors.
  [BINV]  This is the inverse of the base.
  [ACST]  Actual cost function being used, it changes from phase 1
          to phase 2.
  [NVAR]  Non basic variables.
  [BVAR]  Basic variables, in the order in which they are in the 
          inverse of the base.
  [COST]  The original objective function coefficients of the problem.
          The matrix [ c ]
  [DATA]  The matrix [ A | I ]
  [RSRC]  The matrix [ b ]
  [ARTI]  Number of artificial variables included.
  [COLS]  Number of variables in the problem, excluding artificials.
  [ROWS]  Number of constraints in the problem.

The custom menu provides a quick access to all of these variables.

I hope that most of the question will be answered by the above brief
description, but you can always contact me, and if I have time I will
get back yo you fairly soon.

    Ricardo Marimon
    28-D Escondido Village
    Stanford CA 94305

    Email: rmarimon@leland.stanford.edu

Most of the bugs have already been worked out, but as Murphy says, there
is always one more bug...  Please send any bug reports to my email
address...


Of course, I am not responsible for any damages that this program might
cause to your calculator, your job, yout studies, or your life...  :-)
But again, I haven't had any troubles for months.


And here is the program.   Store it is in ASC format, and it is a
directory.


----- Cut Here -----
%%HP: T(3)A(R)F(.);
"69A20FF7CAB20000001005108E92097300339202000060000900000000000000
0000190000000000000029000000000000001900000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000010000000000000001000000000000000000000000000
0000100000000000000000000000000000000000000000000000000000000000
0000000000000000000030000000000000001000000000000000190000000000
0000100000000000000000000000000000001000000000000000000000000000
0000000000000000000000000000000000003000000000000000000000000000
0000100000000000000010000000000000000000000000000000000000000000
0000100000000000000000000000000000000000000000000000300000000000
0000100000000000000010000000000000001000000000000000000000000000
0000000000000000000000000000000000001900000000000000000000000000
0000300000000000000000000000000000001000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
000010000000000000002048300303435453047A2084E20402667162784E2040
2696E66784E2040E667162784E20404616471684E20402737273684E20401636
374784E204036F63747B2130D70004027F677374033920000000000000005012
0004036F6C637403392000000000000000801200040162747964033920000000
0000000000120004046164716408E9209E200339202000050000900000000000
0000000100000000000000010000000000000000000000000000000100000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000010000000000000001900000000000000100000000
0000000000000000000000010000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000100000000
0000000100000000000000000000000000000000000000000000000100000000
0000000000000000000000000000000000000000000000000000000100000000
0000000100000000000000010000000000000000000000000000000000000000
0000000000000000000000019000000000000000000000000000000100000000
0000000000000000000000010000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000100000000
000000000AF2004027372736408E920960003392020000500001000000000000
0000003000000000000000300000000000000030000000000000003000000000
00000020A70004036F63747408E9209900033920200001000080000000000000
0000019000000000000002900000000000000190000000000000000000000000
0000000000000000000000000000000000000000000000000000000AA0004026
6716274047A209C2A23F2A2743A2ED2A2C53A2B2130F20004016363747408E92
0990003392020000100008000000000000000000190000000000000029000000
0000000019000000000000000000000000000000000000000000000000000000
00000000000000000000000000AA00040E66716274047A20803A2D13A2233A2B
213052000402696E667408E9209A100339202000050000500009997666666666
6609994333333333330999333333333333978900000000000590000000000000
0009993333333333339999433333333333099976666666666607890000000000
0590000000000000000999766666666666099943333333333309997666666666
6600000000000000019000000000000000099933333333333309994333333333
3399993333333333330789000000000005000000000000000009993333333333
3399994333333333330999333333333333978900000000000590000000000000
010AB1005034C425134350D9D20FEF30B7040FD621B21307200040A55425F440
3392019900000000000501200040D43505C440D9D202BA81D9F811192040000D
9D20881308A7532FA30CB916D9D201192010500A3836B2130CA1307A22632230
7A22657B30CB916D9D201192010500A3836B213003D43D0040073E5954500D47
0E04166B316EC370122708B5533223043370649266B316E0E30CA1302CE30FED
30CAF069B1364B2A2244302C230EC37059230EF11609736F665343370B9F06E0
4167E3166B3162CE30FED306B316F6E307F370122708B553322306B3165A3704
42307E316E0E309FF30CA1302CE30FED30CAF069B1364B2A2244302C230EC370
59230EF11609736F665343370B9F06E04167E3166B3162CE306B316FED307F37
0122706B31680836122707F370122708B55332230433706B3165A370442307E3
16E0E306B316E0E30CA1302CE30FED30CAF069B1364B2A2244302C230EC37059
230EF11609736F665343370B9F0679470B2130B21301920050D42414355450D9
D202BA812BF811192040000D9D20881308A753A2170D9D201192010500A3836B
213003D4330040073E5954500D4704B2A27E316073E595450322306B316BD370
FEF30CAF0612270322307E316BD3702C2306B316CBD3033F068B55388130FC7A
28DA16D9D209C2A21C8A28DA16D9D20BBF066AC308DA1612270D9D20FEF30F00
46B2130E9016B2130D9D20BBF0653526E9016F0046B2130B21304423043370B9
F06592304D2268DA16D9D205923012270FBD81CAF0600CD132230B2130442304
33704423079470B2130B21308A10040D454C4D440D9D20D8A81D9F8111920140
00D9D20AEC813223088130265309BC269B1364B2A2244309FF3032230EF116BD
3702C230C1216CBD30FED3033F069C2A232230F665343370B9F0659230C1216C
AF06A32168B553E9016A3216BD370122708B553100262C23028216CBD3033F06
BBF069A21612270E4D308DA16D9D20E5216EF9A2029A2B2130FAAA232230F665
3592304337032230AF01627F06B2130B21307410040D435243440D9D20D8A81D
9F811192054000D9D20FA45084E36D9D201192030200A3836B2130D7ED588130
D2E3052330881308A753A2170D9D201192010500A3836B2130BBF065B0369B13
64B2A2244302C230BD3701227032230B601696126A2170D9D201192020200A38
36B2130AEC81662262C2302821638D3057B30CB916D9D201192030200A3836B2
130B601628216BD3702C23028216CBD3033F068B5534C016100262C23028216C
BD3033F062001632230F665310026433704CB2662726433704C016E7F06B2130
B2130C910040D4A4F43440D9D20D8A81D9F811192044000D9D20881308A7532F
A30CB916D9D201192010500A3836B2130C12168A7532FA30CB916D9D20119201
0500A3836B21309FF309FF3003D43B2040073E5954500D47083416C6416E4D30
CB916D9D201192010500A3836B213032230C6416BD3706B316E0416C27368813
0CAF060E5167F370122708B553CAF0643370322307E316C5416C273688130CAF
060F5167F370122708B553CAF0643370322304337085230C6416C5416E0416CB
D30CA1302CE30FED30CAF069B1364B2A2244302C2309FF307F37059230EF1160
9736F665343370B9F0679470B2130B21308D10050D465F4554550D9D20D8A81D
9F811192044000D9D2032230274A2FEF30100268813026530EF11626530BE026
A2170D9D201192010500A3836B2130BD370122708B55388130997A28DA16D9D2
059230122708B55359230EF9A288130E5216178A28DA16D9D204C01610026852
3012270CAF06B21304423032230B2130442304337085230B9F06FBD81B2130B2
130C110040D46594E440D9D202BA81D9F811192040000D9D208813026530274A
2119200000010026BD370122708B553881304B2A2178A28DA16D9D2088130A32
16178A28DA16D9D2010026852301227059230B213044230B2130442304337062
726FBD81B2130B2130AC00050D43484F40550D9D202BA81D9F811192040000D9
D2044B7384E2040A55425F4322308813026530FED309FF307F370122708B5530
09A2EF116178A2CB916D9D204B2A212270F6653B213043370B9F06B2130B2130
9A0003005842330D9D20E163284E2040E6671627B7FC147A20B21309C2A2E0CF
1301323CE2292CF184E204036F6C637D5CE1AFE22D9D20DBBF18DBF1B21305BF
2276BA15DF22C42323CE2278BF18B9C184E2040E66716278B9C1DBBF190DA184
E204016274796279E1AFE22D9D204563284E2040E667162797632DCC024B2A24
563284E20401627479697632DCC0284E204036F637474563284E204016363747
97632DCC02B21305BF228DBF15DF2293632B2130361003005841330D9D20E163
24B2A24563284E20401627479697632DCC0247A20B213084E204026671627330
3278BF14B2A24BAC178BF1D5032D9D20E0CF192CF176BA1E0CF1E0CF184E2040
36F6C6374563284E204016274796976324F80276BA1704D1B2130496328DBF13
CE2284E204016274796AFE22D9D204563284E20402667162797632DCC0284E20
4027F67737CD2D1DBBF184E2040D435243484E204046164716DBBF184E2040D4
A4F4344563284E20404616471697632DCC029C2A284E204036F6C63784E20401
627479676BA1ED2A2387C14B2A2681D184E204036F6C6379C2A276BA184E2040
36F6C63784E20401627479676BA10A132D6E201096D6E2010969C2A2704D1C42
32B21305BF22D9D208DBF18DBF184E204036F63747B21305DF224563284E2040
1636374797632DCC0293632B2130F620060F4554565142560D9D20E163284E20
40E6671627DBBF16C7D19C2A2387C184E204046164716DBBF184E2040D435243
484E20402696E667DBBF1EEDA184E2050D43484F40584E20402696E66784E204
027372736EEDA184E2050D43484F40584E2050D465F4554593632B21309D0005
094E465142550D9D20E163284E20401636374784E20402667162784E2040D435
243484E20402696E667EEDA184E20404616471684E2040E667162784E2040D43
52434EEDA184E20401636374784E2040E667162784E2040D435243490DA1599A
184E2050D43484F40584E2040D46594E493632B2130CE000409445542540D9D2
0E16321C432D6E202096E6D6E2030F65747E163284E20402696E66784E204046
1647164563284E2040E667162797632D6E202096E66C7D19C2A2387C184E2040
D4352434EEDA1D6E2030F6574784E2040D454C4D44563284E20402696E667976
32357024563284E2040E667162797632D6E202096E66C7D14563284E20402667
162797632D6E2030F657476C7D14563284E2040E667162797632D6E202096E6E
0CF1704D14563284E20402667162797632D6E2030F65747E0CF1704D1EF53293
632B2130891005035F4C4655450D9D20E1632916C11C432D6E205066C6167637
E16323392010000000000000105D2C13C03284E205034C4251343C2A20B10009
4475627164796F6E6A3029C2A2485A184E205094E46514253CE2278BF14B2A2D
9AE1AFE22D9D2078BF184E2060F455456514253CE2278BF14B2A2D9AE1AFE22D
9D201C432D6E202096E6D6E2030F65747E1632C2A20B100094475627164796F6
E6A3024563284E2040E667162797632D6E202096E66C7D1B0BC176BA1C2A20B0
00002D80276BA14563284E20402667162797632D6E2030F657476C7D1B0BC176
BA19C2A2485A1D6E202096E6D6E2030F6574784E204094455425EF532B21305B
F22D9D208DBF18DBF1C2A205200055E626F657E6460235F6C6574796F6E69C2A
2485A19C2A24A5A1339201000000000000010472C1B21305DF22B21305BF22D9
D208DBF13CE2284E204016274796AFE22D9D20C2A20B200094E696479616C696
A7564602058616375602239C2A2485A184E20300584233CE2284E20401627479
6AFE22D9D20C2A20F20000527F626C656D60296370255E6665616379626C6569
C2A2485A1B21305DF22B21305BF22D9D20C2A201200035F6C6574796F6E60264
F657E6469C2A2485A184E204035F4C4559C2A24A5A1339201000000000000010
472C1B21305DF22B21305DF22DE032339201000000000000010313C19B632D6E
205066C6167637F76C1EF53293632B21305140050452514345450D9D20E16328
4E205034C4251343C2A20B100094475627164796F6E6A3029C2A2485A184E205
094E46514253CE2278BF14B2A2D9AE1AFE22D9D2078BF184E2060F4554565142
53CE2278BF14B2A2D9AE1AFE22D9D201C432D6E202096E6D6E2030F65747E163
2C2A20B100094475627164796F6E6A3024563284E2040E667162797632D6E202
096E66C7D1B0BC176BA1C2A20B000002D80276BA14563284E204026671627976
32D6E2030F657476C7D1B0BC176BA19C2A2485A1D6E202096E6D6E2030F65747
84E204094455425EF532B21305BF22D9D208DBF18DBF1C2A205200055E626F65
7E6460235F6C6574796F6E69C2A2485A184E204035251495B21305DF22B21305
BF22D9D208DBF13CE2284E204016274796AFE22D9D2084E20300584233CE2284
E204016274796AFE22D9D20C2A20F20000527F626C656D60296370255E666561
6379626C6569C2A2485A1B21305BF22D9D20C2A20B200094E696479616C696A7
564602058616375602239C2A2485A1B21305DF22B21305BF22D9D20C2A201200
035F6C6574796F6E60264F657E6469C2A2485A184E204035F4C455B21305DF22
B21305DF229C2A24A5A193632B213077300403525149540D9D20E163284E2040
2696E66784E204046164716EEDA184E2040E667162784E205094E46514256C7D
19C2A2387C184E2040D4352434599A184E204036F6C63784E20401627479676B
A19C2A2387C14B2A2681D19C2A284E2040266716278B9C10A132D6E20109692C
F1D6E2010966C7D14563284E20402667162797632D6E2010966C7D1DBBF1704D
1C4232DBBF18DBF193632B2130731004035F4C45540D9D20E163284E20402696
E66784E204027372736EEDA184E204036F6C63784E20401627479676BA19C2A2
387C14B2A2681D19C2A284E2040266716278B9C10A132D6E20109692CF1D6E20
10966C7D14563284E20402667162797632D6E2010966C7D1DBBF1704D1C4232C
2A207000085EB522DBBF184E20401636374784E20402667162784E2040D43524
3478BF184E20402696E667EEDA147A2084E204027F67737B2130FD0D1C2A2070
00069EB522DBBF1E0CF1EEDA1B7FC18DBF1C2A2070000A5EB52293632B2130F9
10040451424C440D9D20E163284E2040461647168B9C1B7FC18DBF11C432D6E2
01027D6E201036E163247A209C2A2D6E201036B21304B2A2681D184E20401636
374784E20402667162784E2040D435243484E20402696E667EEDA19C2A2D6E20
10360A132D6E20109678BF184E204046164716D6E2010969C2A2387C184E2040
D4352434EEDA1B7FC18DBF13CE22D6E20109684E204036F6C63784E204016274
79676BA1CFCE1AFE22D9D2084E204016363747D6E2010966C7D1B21305BF224B
2A25DF2290DA1E0CF1D6E201096E0CF1704D1DBBF1C423284E204027372736EE
DA1599A184E2040D4A4F434599A1293D184E20402696E66784E204046164716E
EDA184E20402696E66784E204027372736EEDA184E2040D4A4F434293D184E20
40D4A4F434293D184E2050D43484F405EF53293632B2130C62004094E4944540
D9D20E163278BF18B9C1B7FC18DBF11C432D6E201046D6E2010D6D6E2010E6E1
63284E205034C4251343C2A20310003596D607C656879C2A2485A1D6E2010D69
C2A290DA14563284E204027F6773797632DCC02D6E2010E69C2A290DA1456328
4E204036F6C63797632DCC02D6E20104684E2040D43505C44563284E20404616
471697632DCC024563284E20402737273697632DCC024563284E204036F63747
97632DCC0284E20404616471684E2050D4241435544563284E20402667162797
632DCC0284E20300584133CE2284E204016274796AFE22C2A20B200094E69647
9616C696A7564602058616375602135BF22C2A20D100064F657E646021602241
637565DF229C2A2485A147A20B21309C2A284E204036F6C6370A132D6E201096
3CE2284E204026671627D6E2010964BAC1F88E1AFE22D9D20D6E20109676BA1B
21305DF22C42324563284E2040E667162797632DCC0284E20404616471684E20
402667162784E2040D43524344563284E20402696E66797632DCC029C2A24A5A
1EF53293632B213023FE"
----- Down To Here ------
Newsgroups: comp.sys.hp48