Post Reply 
HP50G SIMPLEX Version14b Max Min Pivot Algorithm, multiple/unbounded, unfeasible sol
11-27-2022, 09:45 PM (This post was last modified: 01-29-2023 02:49 PM by Gil.)
Post: #3
RE: HP49-50G LP for Simplex Max Min Pivot Algorithm
Most of the examples & explanations are included as a long string
at the very beginning of the main program —>GO at first menu page.

Examplification
to the unique input Argument (Matrix):

[[a11... a1n 'L' C1]
[ a21... a2n 'E' C2]
[]
[1 0 0 0 0 'L' 9]
[0 1 0 0 0 'L' -7]
[0 0 1 0 0 'G' 6]
[0 0 0 1 0 'F' 0]
[0 0 0 0 1 'E' 0]
[am1amn 'G' Cm]
[z1 zn 8 0]]

Explanation of the
letters in the Matrix, to be entered at column n+1:

'L' Less <=
'E' Equal >=
'F'   Free var xi, i.e. xi >=0 or xi <=0
'G'  Greater >=

Explanation for the
above Matrix:

[[a11... a1n 'L' 8]
1st row * <=8,
which means,
with minimum two coefficients of variable xi, xj ≠ 0,
that -infinity < above row * <= 8.

Note 0a
In other words, with no specifications, a Row * may be <=0 (unless only one variable xi is concerned, in which case xi is, by default, >=0, according to Simplex rules).

[a21... a2n 'E' C2]
2nd row = C2
[]

[10 0 0 0 'L' 9]
for Var x1 <= 9
but x1, however, assumed >= 0,
as all xi generally, according to Simplex convention/rules.

Note 0b
Remember: x1, and more or generally xi, by default always assumed >= 0in the Simplex algorithm.

Note 0c
For effective x1 (xi) <=9,
in which x1 (xi) may be <=0,
(-infinity <x1/xi<=9),
always write 2 rows:
[1 0 0 0 'F' 0]
[10 0 0 'L' 9], i.e.
specifying also that
x1 (xi) isFree,
but, of course,saying that it is <=9.

[0 10 0 0 'L' -7]
for var x2 <=-7

[0 0 1 0 0 'G' 6]
for var x3 >= 6

[0 0 0 10 'F' 0]
for Free var x4,
i.e. x4>=0 or x4<=0
when we don't know its sign.

[0 0 0 0 1 'E' 2]
for var x5 = 2

[am1... amn 'G' Cm]
Row m >=Cm

[ z1... zn 80]]
i.e. last row m+1
for Z=z1x1+... +znxn+8

Note 1a
Attention for possible, existing Constant C (8)in Z objective function:
if, say, we have three unknown Var x1 x2 x3
& Z=1x1+0x2+3x3+8,
the corresponding last Matrix m+1 row should be:
[1 0 3 8 0 ]
or [1 0 3 8 'Max']
or [1 0 3 8 'Min' ],
but never [1 0 3 08].

In other words, in the last Matrix row,
the possible, existing Constant C (8) of Z should always be placed in penultimate (second to last) bottom row cell (column c+1, and not last column c+2).

Note 1b
You don't need to specify the last cell name/content (0, 'Max', 'Min') : the program will do it afterwards for you when you execute it (according to your answer at first question relative to Max/Min). Its content has basically no real effect on the program results; but, if it is exactly equal to 'Min', the first question, when running —> GO program, will suppose a 0 answer corresponding to a Min choice; nevertheless, you can still decide to answer, to that first question, by 1 to choose a Max problem.

Note 1c
Contrarily to possible constant C (column n+1) of the Z-objective function (in last row), all the terms Ci coming after the signs >= (here 'G' ), <= (here 'L') or = (here 'E') are to be placed at last column n+2.

Note 2
- Order for the rows of
the Inequalities or Equalities is free.
- Only Z coefficients must always
be inlast Matrix row m+1.

Note 3
When Inequalities transformations were necessary in order to have the Matrix 'Simplex compatible', the automatically introduced Slack added variables will be duly indicated with xi=beta.i ± di under SLACK.beta variable (2ndmenu page).

Note 4a

With the default fraction mode (question 3 under main program —>GO), the non integer solution (SOL variable at first menu page) always appears under two forms : fractions (even if you have inequalities of the form 2.23x1 + 4.108x2 <= 99.114 or xi =7.019) and latter corresponding numerical values.

Note 4b
Note that no fractions is given if you chose the alternative fast mode option (question 3 above under main program —>GP: see also NB 8).

Note 4c
When final results of the form
4.0799999903 (six 9s) or
2.370000008 (six 0s) are found, the subroutine ROUND¦9&0 transforms them into, respectively, the more readable 4.08 & 2.37 results.
This was not given as an option, in order not to hassle the user with always the same recurring question.
Should you not be satisfied by the above rounding mode, edit the ROUND¦9&0 program (to be found at the very last page of the many program-variables).
As explained at the very beginning of that program, modify then the string relative to the number of nines you want (not the zeros to be changed, as they will be adjusted automatically for you by the program) in order to get a "nicer" result. Furthermore, as explained in ROUND¦9&0 program, no rounding at all is possible & achieved simply by changing the original string of 9s (always in ROUND¦9&0 program) with a string containing twice the infinity mathematical sign.

Note 5a
"Feasibility"
A checking of the found solution, to verify if the calculated xi values respect the inequalities/equalities of the initial system, is then registered under RESULT¦Ci.rows variable-program (at 2nd menu page), with the resulting values for each of the m rows relative to ak1x1+ak2x2+...
When the inequalities or equalities are not respected — which should be seldom the case since version 9d — with the found "solution", then a 'not' appear before the signs <= (here 'L') , >= (here 'G') or = (here 'E') in the corresponding row i Matrix of
RESULT¦Ci.rows variable-program; it means that the given result is "not feasible, i.e., it is not allowed, as it breaks condition row i.

If such a non feasible solution does appear despite the changes in the version 9d, the problematic rows will be also indicated, in form of a list, at the beginning of the Sol variable solution (to be found at first menu page).
(See also next Notes such as #6 for other special situations.)

Example
Suppose we have the following System:
[[ 2 3 'L' 4 ]
[ 5 3 'L' 10 ]
[ 6 4 'G' 50 ]
[ 0 1 'L' 0 ]
[ 1 -1 0 'Max' ]] and launch —>GO.

To the four questions, accept the suggested choice just pressing ENTER.

The given SOL variable (to be found at first menu page) shows the following content:
{ :Att\166 found 'Sol': VIOLATES.input :Inequal (Ci) at: { :row: 1 :row: 4 } Var\|>2\166Steps\|>5 Time\|>1\166s :Z-Max: -150 :x1: -55 :x2: 95 }

And RESULT¦Ci.rows Variable, as mentioned to be found at 2nd menu page, is:
:SolviolatesRowInCi:
[[ 175 'not\|>LE' 4 ]
[ 10 'LE' 10 ]
[ 50 'GE' 50 ]
[ 95 'not\|>LE' 0 ]]

Note 5b
Other example of an "unfeasible" problem
[[ 1 1 'L' 5 ]*
[ 0 1 'G' 8 ]**
[ 6 4 0 'Max' ]]

According to usual SIMPLEX convention (in this program), if nothing is said about xi (here x1 and x2), it is assumed to be >=0.
If x2 >= 8 according to **, then * cannot be <0 as said in *, unless breaking the above rule and accepting that x1 might be <= 0 (x1=-3).

Put
[[ 1 1 'L' 5]
[ 0 1 'G' 8 ]
[ 6 4 0 'Max' ]]
on the stack and launch —>GO.

You get then:
{ Var 2¦Steps 4 Time1¦s :

Z-Max: 14 :x1: -3 :x2: 8 :
Sign { x1 }
not allowed: UNFEASIBLE.problem }

Note 6
"Unbounded" case
It may also happen that the Simplex algorithm is stopped "too early": some Z coefficient of the Simplex table are indeed positive (to carry on the process as usual), but no negative value is found in the same, corresponding positive z column (to allow a further step).
That case, when it occurrs, means that there is no Min/Max solutions, that there is an infinity of feasible "solutions"; then this observation of "unbounded" problem will be duly included at the end of SOL variable (as for non feasible "solutions", see also Note 5 above).

Example
Suppose that you have to solve:

[[ 1 -1 1 'E' 0 ] *
[ 0 -1 4 'E' 1 ] **
[ -1 -4 -2 0 'Min' ]], 'E' meaning "equal to".

Run —>GO, choose 0 for the 1st question (we have to deal with a Min) then press 3 times ENTER.

The output will be the following:

{ :'Sol' is no Max!: \ooUnbound.Sol\->\ooMax Var\|>2\166Steps\|>4 Time\|>1\166s :

Z-Max: 52 :x1: 32 :x2: 20 :
as only positive Val: in.Col\1662\166final.STEPS }.

Now, let's look at final Simplex table.
To that, just press STEPS variable (at first menu page).
Edit it by pressing "down arrow".
Go to last line of that large content
by pressing RS+ "down arrow".

We have then:

[[ 1 'y3' '\Gb2' 'Con1' ]
[ 'x1' '-1/2' '3/2' 32 ]
[ 'x2' 0 1 20 ]
[ 'y4' '-5/2' '9/2' 0 ]
[ 'Z' '-1/2' ' 5/2' 52 ]]

We see that, among columns 1 & 2, we do have a positive number in last row Z for column 2: 5/2. Unfortunately, no way to proceed as no value in that column 2 is negative (we have +3/2,+1 and +9/2).

Other example

Enter then the following Matrix:
[[ 1 0 0 'F' 0 ]
[ 0 1 0 'F' 0 ]
[ 0 0 1 'F' 0 ]
[ 1 -1 1 'E' 0 ] *
[ 0 -1 4 'E' 1 ] **
[ -1 -4 -2 0 'Min' ]], ***
remembering that 'F' stands for Free (variable),
allowing x1, x2 and x3 to be negative.

Put the above Matrix on the stack
and launch —>GO.

To the four questions, accept the suggested choice just pressing ENTER.

The "solution" found is shown in the following form:
{ :'Sol' is no Min!: \ooUnbound.Sol\->\ooMin Var\|>3\166Steps\|>6 Time\|>2\166s :

Z-Min: 5 :x1: -1 :x2: -1 :x3: 0 :
as only positive Val: in.Col\1665\166final.STEPS },

noting here that \oo stands for the mathematical infinity symbol.

Let x2 be := 1003 in equation **.
It comes from ** that x3=251.
With those values in *, it comes that x1=752.
And finally, from *** and with above xi values, Z=-5266,
which is < than given Simplex solution Z = 5.

Now, let's look at final Simplex table.
To that, just press STEPS variable (at first menu page).
Edit it by pressing "down arrow".
Go to last line of that large content
by pressing RS+ "down arrow".

We get:
:Final Step:
[[ 3 'y07' '\Gb2' 'y10' '\Gb4' '\Gb5' 'x3b' 'Con1' ]
[ 'x1a' -1 1 -1 0 3 -3 0 ]
[ 'x1b' 0 1 0 0 0 0 1 ]
[ 'x2a' 0 0 -1 1 4 -4 0 ]
[ 'x2b' 0 0 0 1 0 0 1 ]
[ 'x3a' 0 0 0 0 1 0 0 ]
[ 'y08' -1 0 0 0 0 0 0 ]
[ 'y09' 0 0 -1 0 0 0 0 ]
[ 'Z' -1 0 -5 0 21 -21 -5 ]]

We see that, among columns 1,2,3,4,5 & 6, we do have a positive number in last row Z for column 5: 21. Unfortunately, no way to proceed as no value in that column 5 is negative (we have +3,+4 and +1).

Note 7
Inclusion of 2nd main solution, when possible

Suppose you have the following Matrix on the stack:
[[ 8 6 1 'L' 48 ]
[ 4 2 1.5 'L' 20 ]
[ 2 1.5 .5 'L' 8 ]
[ 0 1 0 'L' 5 ]
[ 60 35 20 0 'Max' ]]

Launch —> GO and press 4 times ENTER to the 4 program questions.

The answer SOL, at first menu page will appear as:

{ :\GlSol 1+(1-\Gl)Sol 2: \Gl\166GE\1840\183and\183\Gl\166LE\1841 :Main Sol 1,as Zrow=0: in.Col\1662\166final.STEPS Var\|>3\166Steps\|>2 Time\|>0\166s :Z-Max: 280 :x1: 2 :x2: 0 :x3: 8 :Main Sol 2,as Zrow=0: in.Col\1662\166addit.STEPS Var\|>3\166Steps\|>3 Time\|>1\166s :Z-Max: 280 :x1: 0 :x2: [ '8/5' 1.6 ] :x3: [ '56/5' 11.2 ] }

In fact, here two main solutions are calculated & given under SOL: SOL 1 & Sol 2.
The general solution (to be found under SOL at first menu page) is then:
lambda × SOL 1 + (1-lambda) × SOL 2,
with 0 <= lambda <= 1 (as mentioned here in a compact way).

Note 8
Other special case for infinite/multiple solution

Where Sol i (general)
= Sol by SIMPLEX + lambda0 × [lambda1, lambda2... lambdan]
= [x1, x2... xn] + lambda0 × [lambda1, lambda2... lambdan],
in which lambda0 is any number.

To illustrate the above, put the following Matrix in stack level 1:

[[ 1 0 0 '1/4' -8 -1 9 'E' 0 ]
[ 0 1 0 '1/2' -12 '-1/2' 3 'E' 7 ]
[ 0 0 1 0 0 1 0 'E' 1 ]
[ 0 0 0 '3/4' 20 '-1/6' 6 0 'Min' ]]

... and press —> GO

Then, pressing 4 times ENTER to answer the 4 questions, you should get:

{ Var\|>7\166Steps\|>11 Time\|>5\166s :

Z-Min: [ '-1/6' -.166666666667 ] :x1: 1 :x2: [ '15/2' 7.5 ] :x3: 0 :x4: 0 :x5: 0 :x6: 1 :x7: 0 :

(Above Sol) + \lambda.free *: [ 1 '19/11' 0 '-20/11' '3/44' 0 0 ] }

Note 9
As cycling does not appear very often, no counting loop has been made yet to check and break the process for that type of occurrence.

An example of cycling is given in directory called DATA, a directory to be found at last menu page (in DATA directory, enter then the directory labelled SPECIAL and choose the variable CYCLE).

Note 10a
If you chose the full stack option (default case at question 4 under main program —>GO), all the intermediate, important decision steps will be registered under STEPS variable (at first menu page, as mentioned).

For the above example, STEPS variable is:
{ :Part1\166added x7=\Gb7+: 1 :as in transf. '\<=': some.Ci :<0 Ci min: -1 :Step-0 (total: 3):
[[ 0 'x1a' 'x1b' 'x2a' 'x2b' 'x3a' 'x3b' '\Gb7' 'Con1' ]
[ 'y1' -1 1 1 -1 -1 1 1 1 ]
[ 'y2' 1 -1 -1 1 1 -1 1 1 ]
[ 'y3' 0 0 1 -1 -4 4 1 2 ]
[ 'y4' 0 0 -1 1 4 -4 1 0 ]
[ 'x7' 0 0 0 0 0 0 1 1 ]
[ 'Z' 0 0 0 0 0 0 -1 -1 ]] { "Ratios w/ C7" "(to elimin \Gb7)" :L1: 1 :L2: 1 :L3: 2 :L4: 0 :L5: 1 :Min: L4 }
[[ 1 'x1a' 'x1b' 'x2a' 'x2b' 'x3a' 'x3b' 'y4' 'Con1' ]
[ 'y1' -1 1 2 -2 -5 5 1 1 ]
[ 'y2' 1 -1 0 0 -3 3 1 1 ]
[ 'y3' 0 0 2 -2 -8 8 1 2 ]
[ 'x7' 0 0 1 -1 -4 4 1 1 ]
[ 'Z' 0 0 -1 1 4 -4 -1 -1 ]] { "Ratios w/ C4" :L1: '-1/2' :L3: -1 :L4: -1 :Max: L1 }
[[ 2 'x1a' 'x1b' 'x2a' 'y1' 'x3a' 'x3b' 'y4' 'Con1' ]
[ 'x2b' '-1/2' '1/2' 1 '-1/2' '-5/2' '5/2' '1/2' '1/2' ]
[ 'y2' 1 -1 0 0 -3 3 1 1 ]
[ 'y3' 1 -1 0 1 -3 3 0 1 ]
[ 'x7' '1/2' '-1/2' 0 '1/2' '-3/2' '3/2' '1/2' '1/2' ]
[ 'Z' '-1/2' '1/2' 0 '-1/2' '3/2' '-3/2' '-1/2' '-1/2' ]] { "Ratios w/ C2" :L2: -1 :L3: -1 :L4: '-1' :Max: L2 } :Final Step:
[[ 3 'x1a' 'y2' 'x2a' 'y1' 'x3a' 'x3b' 'y4' 'Con1' ]
[ 'x2b' 0 '-1/2' 1 '-1/2' '-4' 4 1 1 ]
[ 'x1b' 1 -1 0 0 -3 3 1 1 ]
[ 'y3' 0 1 0 1 0 0 -1 0 ]
[ 'x7' 0 '1/2' 0 '1/2' 0 0 0 0 ]
[ 'Z' 0 '-1/2' 0 '-1/2' 0 0 0 0 ]] \173\173\173\173\173\173\173\173\173\173\173\173\173\173\173\173\173\173\173\173​\173\173 :Part2\166with x1a=\Gb1a+: 0 :x1b=\Gb1b+: 1 :x2a=\Gb2a+: 0 :x2b=\Gb2b+: 1 :x3a=\Gb3a+: 0 :x3b=\Gb3b+: 0 :Step-0 (total: 3):
[[ 0 '\Gb1' '\Gb2' '\Gb3' '\Gb4' '\Gb5' '\Gb6' 'Con1' ]
[ 'x1a' 1 0 0 0 0 0 0 ]
[ 'x1b' 0 1 0 0 0 0 1 ]
[ 'x2a' 0 0 1 0 0 0 0 ]
[ 'x2b' 0 0 0 1 0 0 1 ]
[ 'x3a' 0 0 0 0 1 0 0 ]
[ 'x3b' 0 0 0 0 0 1 0 ]
[ 'y07' -1 1 1 -1 -1 1 0 ]
[ 'y08' 1 -1 -1 1 1 -1 0 ]
[ 'y09' 0 0 1 -1 -4 4 0 ]
[ 'y10' 0 0 -1 1 4 -4 0 ]
[ 'Z' 1 -1 4 -4 2 -2 -5 ]] { "Ratios w/ C1" "(to elimin \Gb1)" :L7: 0 :Max: L7 }
[[ 1 'y07' '\Gb2' '\Gb3' '\Gb4' '\Gb5' '\Gb6' 'Con1' ]
[ 'x1a' -1 1 1 -1 -1 1 0 ]
[ 'x1b' 0 1 0 0 0 0 1 ]
[ 'x2a' 0 0 1 0 0 0 0 ]
[ 'x2b' 0 0 0 1 0 0 1 ]
[ 'x3a' 0 0 0 0 1 0 0 ]
[ 'x3b' 0 0 0 0 0 1 0 ]
[ 'y08' -1 0 0 0 0 0 0 ]
[ 'y09' 0 0 1 -1 -4 4 0 ]
[ 'y10' 0 0 -1 1 4 -4 0 ]
[ 'Z' -1 0 5 -5 1 -1 -5 ]] { "Ratios w/ C3" "(to elimin \Gb3)" :L9: 0 :Max: L9 }
[[ 2 'y07' '\Gb2' 'y10' '\Gb4' '\Gb5' '\Gb6' 'Con1' ]
[ 'x1a' -1 1 -1 0 3 -3 0 ]
[ 'x1b' 0 1 0 0 0 0 1 ]
[ 'x2a' 0 0 -1 1 4 -4 0 ]
[ 'x2b' 0 0 0 1 0 0 1 ]
[ 'x3a' 0 0 0 0 1 0 0 ]
[ 'x3b' 0 0 0 0 0 1 0 ]
[ 'y08' -1 0 0 0 0 0 0 ]
[ 'y09' 0 0 -1 0 0 0 0 ]
[ 'Z' -1 0 -5 0 21 -21 -5 ]] { "Ratios w/ C6" "(to elimin \Gb6)" :L6: 0 :Min: L6 } :Final Step:
[[ 3 'y07' '\Gb2' 'y10' '\Gb4' '\Gb5' 'x3b' 'Con1' ]
[ 'x1a' -1 1 -1 0 3 -3 0 ]
[ 'x1b' 0 1 0 0 0 0 1 ]
[ 'x2a' 0 0 -1 1 4 -4 0 ]
[ 'x2b' 0 0 0 1 0 0 1 ]
[ 'x3a' 0 0 0 0 1 0 0 ]
[ 'y08' -1 0 0 0 0 0 0 ]
[ 'y09' 0 0 -1 0 0 0 0 ]
[ 'Z' -1 0 -5 0 21 -21 -5 ]] }

Note 10b
Note, however, that such default full stack option may cause interruption of the program for large Matrixes that require a lot of Memory storage capacity and may use a very large number of stacks levels.
Hence, to prevent premature program interruption in large Matrixes, the alternative option is to have just 4 stack-level (in last question 4 choice of the main program —>GO) : it may then help the program, without accumulating too many results in the different stacks levels & saving all the intermediate results, to fulfil nevertheless all the required steps and get the solution. By alternative 4 stacks levels, only initial and final steps are saved under STEPS variable (to be found at first menu page).

If 4 stacks levels were chosen, STEPS variable would look like:
{ :Part1\166added x7=\Gb7+: 1 :as in transf. '\<=': some.Ci :<0 Ci min: -1 :Step-0 (total: 3):
[[ 0 'x1a' 'x1b' 'x2a' 'x2b' 'x3a' 'x3b' '\Gb7' 'Con1' ]
[ 'y1' -1 1 1 -1 -1 1 1 1 ]
[ 'y2' 1 -1 -1 1 1 -1 1 1 ]
[ 'y3' 0 0 1 -1 -4 4 1 2 ]
[ 'y4' 0 0 -1 1 4 -4 1 0 ]
[ 'x7' 0 0 0 0 0 0 1 1 ]
[ 'Z' 0 0 0 0 0 0 -1 -1 ]] :Final Step:
[[ 3 'x1a' 'y2' 'x2a' 'y1' 'x3a' 'x3b' 'y4' 'Con1' ]
[ 'x2b' 0 '-1/2' 1 '-1/2' '-4' 4 1 1 ]
[ 'x1b' 1 -1 0 0 -3 3 1 1 ]
[ 'y3' 0 1 0 1 0 0 -1 0 ]
[ 'x7' 0 '1/2' 0 '1/2' 0 0 0 0 ]
[ 'Z' 0 '-1/2' 0 '-1/2' 0 0 0 0 ]] \173\173\173\173\173\173\173\173\173\173\173\173\173\173\173\173\173\173\173\173​\173\173 :Part2\166with x1a=\Gb1a+: 0 :x1b=\Gb1b+: 1 :x2a=\Gb2a+: 0 :x2b=\Gb2b+: 1 :x3a=\Gb3a+: 0 :x3b=\Gb3b+: 0 :Step-0 (total: 3):
[[ 0 '\Gb1' '\Gb2' '\Gb3' '\Gb4' '\Gb5' '\Gb6' 'Con1' ]
[ 'x1a' 1 0 0 0 0 0 0 ]
[ 'x1b' 0 1 0 0 0 0 1 ]
[ 'x2a' 0 0 1 0 0 0 0 ]
[ 'x2b' 0 0 0 1 0 0 1 ]
[ 'x3a' 0 0 0 0 1 0 0 ]
[ 'x3b' 0 0 0 0 0 1 0 ]
[ 'y07' -1 1 1 -1 -1 1 0 ]
[ 'y08' 1 -1 -1 1 1 -1 0 ]
[ 'y09' 0 0 1 -1 -4 4 0 ]
[ 'y10' 0 0 -1 1 4 -4 0 ]
[ 'Z' 1 -1 4 -4 2 -2 -5 ]] :Final Step:
[[ 3 'y07' '\Gb2' 'y10' '\Gb4' '\Gb5' 'x3b' 'Con1' ]
[ 'x1a' -1 1 -1 0 3 -3 0 ]
[ 'x1b' 0 1 0 0 0 0 1 ]
[ 'x2a' 0 0 -1 1 4 -4 0 ]
[ 'x2b' 0 0 0 1 0 0 1 ]
[ 'x3a' 0 0 0 0 1 0 0 ]
[ 'y08' -1 0 0 0 0 0 0 ]
[ 'y09' 0 0 -1 0 0 0 0 ]
[ 'Z' -1 0 -5 0 21 -21 -5 ]] }

Note 11a
To speed up process, sometimes quite a lot, in particular for large Matrixes, you may not be interested by exact, fractional results (default mode at question 4 mentioned further above), and prefer to chose the alternative option (fast/approximation mode, with no fractions, relative to mentioned question 4).

Note 11b
Note, however, that if you chose the option "All Gen/Mult Sol:check lin dep" at question 2, option that requires exact mode, you won't be able to access to question 4 relative to fast approximation mode.
For fast approximation calculation, you must select 0 at question 2, indicating that you selected the corresponding option "only SIMPLEX solution"; then only you will be prompted the question for fast mode in question 4.

Note 11c
Note also that, when choosing approximation mode (question 4/5 in OPTIONS prompted), you might get unexpected, special solutions.

Example
Go (press) DATA directory (last menu page).
Go then to (press) SPECIAL directory.
Choose last variable (last menu page) called SPEC.SPEC.
You should get
[[ 1 -1 0 0 1 0 0 'E' 3 ]
[ -3 2 9 2 0 -2 0 'E' 22 ]
[ 0 1 0 0 0 -1 0 'E' 2 ]
[ 4 3 5 0 1 0 -1 'E' 4 ]
[ -1 0 3 -1 0 0 0 0 'Max' ]]
Press then —>GO.

a) Press 5 times ENTER.
The full solution is then given by
{lambda × [ 0 2 2 0 5 0 17 ]
+ (1-lambda) [ 5 2 '11/3' 0 0 0 '121/3' ]
+ mu1 × [ 1 1 '1/3' 0 0 1 '26/3' ]
+ mu2 × [ 0 1 0 0 1 1 4 ]},
with 0<=lambda<=1
& mu i >= 0

b) Press now INPUT.last (at 1st menu page)
& launch (press) a 2nd time the main program —>GO.
Be careful and, to the questions/prompts that appear:
- answer 1 for 1st question (MAX option)
- answer 0 for 2nd question (no multiple solution)
- answer 1 for 3rd question here (automatic mode)
- answer 0 for 4th question here (no fractions —> approximation)
- answer 1 for 5th question (full stacks & details).
The full and unrecognisable solution is then given as:
[ 0 8.28947368439 2 0 11.2894736843 6.28947368439 42.1578947369 ].

c) In fact, the above solution b) is a special case of a).
Indeed:

Solution b) [ 0 8.28947368439 2 0 11.2894736843 6.28947368439 42.1578947369 ]
=?
solution a)
lambda × [ 0 2 2 0 5 0 17 ]
+ (1-lambda) × [ 5 2 '11/3' 0 0 0 '121/3' ]
+ mu1× [ 1 1 '1/3' 0 0 1 '26/3' ]
+ mu2 × [ 0 1 0 0 1 1 4 ]

Set lambda = 1, mu1 =0, mu2 =6.28947368439.
Then solution b) [/b]
[ 0 8.28947368439 2 0 11.2894736843 6.28947368439 42.1578947369 ]
=?
solution a)
1 × [ 0 2 2 0 5 0 17 ]
+ 6.28947368439 × [ 0 1 0 0 1 1 4 ]

Or [ 0 8.28947368439 2 0 11.2894736843 6.28947368439 42.1578947369 ]
=?
[ 0 2 2 0 5 0 17 ]
+ [ 0 6.28947368439 0 0 6.28947368439 6.28947368439 25.1578947376 ]

And we see that the expected (or unexpected!) equality is, to the rounding errors, indeed fully fulfilled.

Note 12

Question 3, under main program —>GO, enables you to choose your own column (within an allowed list of Simplex compatible columns, of course). It's called the step-by-step mode : besides the possibility of letting you chose your own colums, the program stops then at every important intermediate decision step.
Note, however, that it is not the default setting, for which the program makes itself all the appropriate "decisions", with no stop till the final solution.

Note 13a

For checking purposes, you can use subroutine Mkl—>N (last page of the many program-variables) to change the line and column of your test Matrix M according to Simplex Pivot Rules. But don't modify or delete that subroutine used in Simplex algorithm program.
Use: enter Matrix in stack level 3 (without labels in 1st row & in 1st column, or with them as the program will detect them and not consider them), the row# k of the pivot (not counting the first row of label names if such a line exists) in stack level 2 and column # l of the pivot
(not counting the first column of label names if such a column exists) in stack level 1.

Note 13b
If you have a Matrix to be 'pivoted' together with its labels, you can also use now '\->PIVOT\166&COL.ROW' subprogram (at last page of the many program-variables), counting here, however & contrarily to Mkl—>N subprogram, the label top line as the first row and the left label column as the first column.

Note 14
Initial Inequalities & Equalities System Matrix, including Z objective Max/Min function in last row, are saved always under INPUT.last (first appearing variable at page 1).
Note that the answer to the first question Max/Min will be integrated to last cell of the INPUT.last.

Note 15
Regarding your own System of Matrixes (including Z objective Max/Min function in last row): to keep the program directory clean of "new entries /Matrixes", preferably save them in DATA Directory at the very last page of the many program variables, directory including interesting Min/Max problems. Note that this DATA directory may be freely deleted (purged).

Note 16
Observe, finally, that the SOL variable informs you also about the number of recursive loops/steps ("SIMPLEX tables"), the number of variables involved and the elapsed time, in seconds, to get the solution.

Note 17
- When solutions are not a linear combination of the variables xi,
& if the given solution SOL (at first menu page)
is of the kind Sum (lambda i × solution i),
with 0<=lambda<=1 & sum (lambda i) = 1,
then it will present a minimum of two particular solutions : main solution 1
& main solution 2, but not always all the possible other solutions (such as lambda 3 × solution 3, lambda 4 × solution 4, etc.).
- For linear combination of the variables xi, when corresponding option is selected,
the given solution under S.LIN & d.LIN (both at 1st menu page) are always exhaustive.

Tests & bugs reporting, as well as commentaries, are welcome.

Gil
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: HP49-50G LP for Simplex Max Min Pivot Algorithm - Gil - 11-27-2022 09:45 PM



User(s) browsing this thread: 1 Guest(s)