The Museum of HP Calculators

Linear Programming: the Simplex method for the HP-41

This program is supplied without representation or warranty of any kind. Jean-Marc Baillard and The Museum of HP Calculators therefore assume no responsibility and shall have no liability, consequential or otherwise, of any kind arising from the use of this program material or any part thereof.

Introduction

The purpose is to find m non-negative real numbers:   x₁ , ..... , x_m
satisfying:
                          b_i ³ a_i;1x₁+ ....... + a_i;m x_m            i = 1 , .... , n                                ( n inequations )                   all the b_i , b_i' and b_i"
                          b_i'= a_i';1x₁+ ....... +a_i';m x_m            i' = 1 , ..... , n'                              ( n' equations )                    must be non-negative*
                          b_i"£ a_i";1x₁+ ....... +a_i";m x_m          i" = 1 , ..... , n"                             (n" inequations )

and such that F = c₁x₁+ ....... + c_mx_m is maximized. ( to find the minimum of F, seek the maximum of -F )

* if some b_i are negative, multiply the corresponding lines by -1.

Data registers:

         - R01 thru R(p+1)(m+n"+p+1) are used for the simplex array. ( p = n + n' + n" )
         - The coefficients of the system must be stored column by column from R01 to Rm(p+1)   ( store 0 in Rp+1 )
         - When the program stops, R00 = F maximum
                                                    R01 = x₁ , .... , Rmm = x_m
                                                    Rm+1 ...etc... = The slack and/or artificial variables.

Flags: F01 and F02. If at least one of these flags is set when the program stops, there is no solution ( or no bounded solution ).

Subroutine: none.

A short analysis of the program:

-Lines 01 thru 123 store the other coefficients of the simplex matrix.
If there are only inequations of the first type ( ³ ) it's quite easy: the right half is the unit matrix.
But if there are equations and/or inequations of the second type ( £ ) it's much more complex:
all the last row has to be changed because of the artificial variables.
-The idea is to weight these variables by a coefficient -W where W is such a large positive number
that for a maximum, all the artificial variables will eventually turn out to be zero.
On a calculator, we have to make a choice. In this program: W = 100 ( lines 41-42 and line 103 ).

-Lines 124 thru 214 are the heart of the simplex method itself.
-Lines 215 thru 287 move the results to registers R00 to Rmm ...
and verify 1- if a solution is found
2- if all the artificial variables are really 0 ( lines 274 to 282 )
Otherwise F01 and/or F02 are set.

Warning:

- Because of the choice W = 100 , all the c_j must be significantly smaller than 100.
As an example if F = 2400 x + 1200 y it would be better to find the maximum of 2.4 x + 1.2 y and to multiply the result by 1000.

-This recommendation doesn't apply if there are only inequations of the first type ( ³ ) i-e if n' = n" = 0.

-This program finds only 1 solution ( even if there are several solutions ).

N.B:

- Status registers M N O and a are used.
- Therefore, "SIMPLEX" must not be called as more than a first level subroutine.
- lines 137 and 214 are synthetic three-byte GTOs.
- If you don't have an HP-41CX, replace line 23 by these 6 lines:

   0
   LBL 14
   STO IND Y
   ISG Y
   GTO 14
   RDN                        ( another possibility is to execute CLRG before storing the coefficients of the matrix )

The Program:

001  LBL "SIMPLEX"

002  STO 00
003  RDN
004  STO O
005  +
006  X<>Y
007  STO N
008  +
009  1
010  ST+ 00
011  +
012  STO M
013  +
014  RCL O
015  +
016   E3
017  /
018  RCL 00
019  +
020  RCL M
021  *
022  ISG X
023  CLRGX
024  FRC
025  RCL M
026   E5
027  /
028  +
029  RCL 00
030  RCL M
031  ST+ Y
032  *
033  +
034  STO Y
035   E-5
036  +
037  RCL O
038  X=0?
039  GTO 00
040  -
041  2
042  10^X
043  1
044  LBL 01
045  ST- IND Z
046  X<>Y
047  ST- IND T
048  ISG Z
049  X<>Y
050  ISG T
051  GTO 01
052  LBL 00
053  RCL 00
054  .1
055  %
056  +
057  RCL M
058  STO Z
059  DSE X
060  +
061  *
062  DSE X
063  RCL M
064  1
065  +
066   E5
067  /
068  +
069  SIGN
070  LBL 02
071  STO IND L
072  DSE L
073  GTO 02
074  RCL M
075  RCL 00
076  DSE X
077  ST+ Y
078  RCL N
079  +
080   E3
081  /
082  +
083  STO a
084  RCL N
085  RCL M
086  DSE X
087  X=Y?
088  GTO 00
089   E-3
090  STO Z
091  *
092  RCL 00
093  X<> N
094  +
095  ISG X
096  ST+ Y
097  0
098  LBL 03
099  RCL IND Y
100  +
101  ISG Y
102  GTO 03
103   E2
104  *
105  ST+ IND Y
106  RDN
107  +
108  0
109  DSE N
110  GTO 03
111  LBL 00
112  RCL 00
113  RCL O
114  +
115  DSE X
116  RCL M
117  ST+ Y
118  ST* Y
119   E2
120  /
121  +
122   E3
123  /
124  ISG X
125  STO 00
126  CF 01
127  CF 02
128  LBL 04
129  RCL 00
130  STO O
131  LBL 05
132  ISG O
133  GTO 05
134  RCL 00
135  ISG X
136  STO M
137  GTO 10
138  LBL 05
139  RCL IND O
140  X<=0?
141  GTO 05
142  RCL O
143  1
144  -
145  STO M
146  RCL 00
147  LAST X
148  -
149  INT
150  STO N
151  CLST
152   E99
153  LBL 06
154  RCL IND M
155  X<=0?
156  GTO 06
157  RCL IND N
158  X<>Y
159  /
160  X>Y?
161  GTO 06
162  RCL M
163  STO Z
164  LBL 06
165  CLX
166  SIGN
167  ST- M
168  RDN
169  DSE N
170  GTO 06
171  X<>Y
172  ENTER^
173  X=0?
174  GTO 05
175  RCL M
176  INT
177  -
178  STO O
179  RCL IND Y
180  LBL 07
181  ST/ IND Y
182  ISG Y
183  GTO 07
184  RCL 00
185  INT
186  STO N
187  LBL 08
188  RCL 00
189  FRC
190  RCL N
191  +
192  RCL O
193  X=Y?
194  GTO 00
195  RCL M
196  RCL Z
197  +
198  RDN
199  RCL IND T
200  SIGN
201  LBL 09
202  CLX
203  RCL IND Y
204  LAST X
205  *
206  ST- IND Z
207  ISG Y
208  CLX
209  ISG Z
210  GTO 09
211  LBL 00
212  DSE N
213  GTO 08
214  GTO 04
215  LBL 10
216  RCL IND M
217  X<0?
218  GTO 00
219  X>0?
220  SF 01
221  RCL M
222  INT
223  LAST X
224  DSE Y
225  DSE X
226  CLX
227  INT
228   E3
229  /
230  +
231  1
232  STO O
233  LBL 11
234  RCL IND Y
235  1
236  X#Y?
237  GTO 11
238  ST- O
239  R^
240  STO N
241  RDN
242  LBL 11
243  RDN
244  ABS
245  -
246  DSE Y
247  GTO 11
248  RCL O
249  X=0?
250  X#Y?
251  GTO 00
252  RCL N
253  RCL 00
254  INT
255  MOD
256  RCL IND X
257  GTO 10
258  LBL 00
259  CLX
260  LBL 10
261  STO IND M
262  ISG M
263  GTO 10
264  RCL 00
265  0
266  LBL 12
267  RCL IND Y
268  STO IND Y
269  CLX
270  SIGN
271  +
272  ISG Y
273  GTO 12
274  CLX
275  LBL 13
276  X#0?
277  RCL IND a
278  X#0?
279  SF 02
280  PI
281  DSE a
282  GTO 13
283  RCL 00
284  CHS
285  STO 00
286  CLA
287  END

( 441 bytes / SIZE = 1+(p+1)(m+n"+p+1 ) with p = n+n'+n"

STACK                                INPUTS OUTPUTS

       T    n = the number of inequations of the 1st kind ( ³ )          /

       Z    n' = the number of equations ( = )          /

       Y    n" = the number of inequations of the 2nd kind ( £ )          /

       X    m = the number of unknowns     max (F)

       L                                     /           /

Example:

Find 4 non-negative numbers x, y, z and t satisfying:

             56 ³ x + 2y + 3z +4t
             41 ³ 5x + y - 3z - t
             61 ³ 4x + 7y +2z - 3t
             25 = 2x + 3y - z + 2t                          ( always write the "³" inequations first, then the "=" equations , and finally the "£" inequations )
               7 £   x + y + z + t
             17 £ 2x - y + z + 3t

such that F = 2x + 4y +3z + 5t is maximized.

1- SIZE 092 ( or greater )

2- We store these 35 numbers in registers R01 thru R35 like this:

            56   1   2   3   4                  R01 R08 R15 R22 R29
            41   5   1 -3 -1                 R02 R09 R16 R23 R30
            61   4   7   2 -3                 R03 R10 R17 R24 R31
            25   2   3 -1   2      in        R04 R11 R18 R25 R32           respectively.   ( we must store 0 at the place of F that is in R07 here )
             7    1   1   1   1                 R05 R12 R19   R26 R33
            17   2 -1   1   3                 R06 R13 R20   R27 R34
              0   2   4   3   5                 R07 R17 R21   R28 R35

3- There are 3 inequations of the first type, 1 equation , 2 inequations of the second type and 4 unknowns, therefore:

            3 ENTER^
            1 ENTER^
            2 ENTER^
            4 XEQ SIMPLEX and ( 3mn49s later ) we obtain 76 in the X-register and in R00 ( F01 and F02 are cleared )

            RCL 01 gives 2
            RCL 02   "      7
            RCL 03   "      8
            RCL 04   "      4       thus the maximum of F is 76 and it is achieved for x = 2, y = 7, z = 8, t = 4.

We can also verify that:

            R05 = 0 ; R06 = 52 ; R07 = 0    ( the n slack variables of the three first inequations )
            R08 = R09 = R10 = 0               ( the n'+n" artificial variables which are always 0 when a solution exists )
            R11 = 14 ; R12 = 0                  ( the n" slack variables of the two last inequations )

Reference: "Numerical analysis" by Francis Scheid McGraw-Hill ISBN: 07-055197-9

Go back to the HP-41 software library
Go back to the general software library
Go back to the main exhibit hall

STACK	INPUTS	OUTPUTS
T	n = the number of inequations of the 1st kind ( ³ )	/
Z	n' = the number of equations ( = )	/
Y	n" = the number of inequations of the 2nd kind ( £ )	/
X	m = the number of unknowns	max (F)
L	/	/