Simplex method in prime how to use the constrains maximise s.t. constraints.

[Albert Chan]

(11-05-2023 11:05 PM)Anthony The Koala Wrote:  I appreciate please an elaboration of:
(i) it needs to satisy all constraints, and
(ii) most of them not vertices. What are these vertices

(i) Of course solution need to satisfy all constraints (it is given!)

Intersection of 2 constraints only implied these 2 are satisfied.
The point may satisfied other constraints, but it is not guaranteed.

(ii) HPCarnace post #5 have a nice picture.
https://www.hpmuseum.org/forum/attachment.php?aid=12759

Purple regions are feasible solution, satisfied all constraints.
When I say vertices, I am referring to the vertices of this purple polygon.

To minimize cost, solution must be on the edge of feasible region.
If cost function slope is different than constraints, solution is on one of the vertices.

There are line intersecting points outside purple region, those are not vertices.
Getting those points are just a waste of time, even if cost is lower.

[Anthony The Koala]

Dear Albert Chan,
Thank you for the reply.

In essence your reply is to:
1. Look visually at the constraints to see if constraints are in feeasble region. As demonstrated by HP Carnace picture.
2. Look at the lines which are on the feasible region. Apply the maths earlier to work out the x, y of constraint pounts on the feasible region.
3. Of those points x,y on the feasible region use them to work out the cost.
4. The cost you want to minimuse is the solution.

Principled question please.
What to do for higher order more than 2, say 3 or more variables to minimise cost or maxmise profit? How to visualize the feasible region?

Thank you again
Anthony, Sydney

[ftneek]

(11-06-2023 03:16 AM)Anthony The Koala Wrote:  What to do for higher order more than 2, say 3 or more variables to minimise cost or maxmise profit? How to visualize the feasible region?

Graphical solutions can only really be obtained for problems with 3 or less variables. For 3 variables we would have a 3 dimensional feasible region. Refer to this link for an example with 3 variables and the graphed feasible region. With k variables we have a k-dimensional feasible region, and as far as I know there is no easy way to visualize something with k dimensions.

For linear programs with 3 or more variables, the simplex algorithm (or one of its variations) is often used to find a minimum or maximum.

[Anthony The Koala]

Dear ftneek,
Thank you for the reply.

So I can conclude that to find the feasible planes and the verticies in a multivariable simplex problem, there must be a way to detect whether the simultaneous points are vertices within a feasible region or planes?

Thank you
Anthony, Sydney

[ftneek]

Generally the system of equations must be converted into standard form and the coefficients extracted into a matrix, and then a series of pivots and row reductions are performed. There are different styles of standard form depending on the source.

I recommend searching online for "simplex method examples" for videos and examples to get a better idea of how it works or referring to a linear programming textbook for more details.

This text uses minimization for standard form, it's discussed in section 3.1. Section 3.5 shows examples of the simplex method in tableau/matrix form.
An Introduction to Linear Programming and Game Theory 3rd Edition, Paul R. Thie and Gerard E. Keough (ISBN: 978-0470232866).

[Albert Chan]

(11-03-2023 03:34 PM)jte Wrote:  The HP Prime doesn't currently have a built-in app for handling constrained optimization.

I just discovered XCas can! Perhaps it can add this to HP Prime Cas as well.

solver.cc Wrote:// COBYLA will try to make all the values of the constraints positive.

OP example, with guess in the feasible region.

XCas> fMin(6x+5y, [x, y, 2x+4y-22, 3x+2y-20, 4x+5y-40], [x,y], [99,99])

[2.85714285714, 5.71428571429]

XCas> [6,5] * ans()

45.7142857143

[Anthony The Koala]

Dear Albert Chan,

I typed the the following on my HP Prime in cas mode

Quote:fMin(6x+5y, [x y 2x+4y-22 3x+2y-20 4x+5y-40], [x y], [99 99])

I used the [ ] by pressing Shift 5 hence no need for commas between elements enclosed between the brackets.

When I pressed Enter, there was no output.

Questions please:
1. No output no result
2. What was the choice of [99 99] based on.

Thank you
Anthony, Sydney

[Albert Chan]

Hi, Anthony The Koala

Although HP Prime Cas also has fMin, simplex method is not implemented (yet)
From help screen, it only have the form fMin(Expr, [Var]).

XCas fMin allow more options: fMin(expr, constraints, vars, init, epsilon, max_iterations)

About [x,y] guess = [99, 99], it is just some number in the feasible region.

XCas Manual Wrote:Although the initial point is required to be feasible, the algorithm will sometimes succeed
even with a poor choice of initial point. Note that the initial value of a variable must not be zero.

[Anthony The Koala]

Dear Albert Chan,
I checked the Aops and cannot find the XCas.

How to access the XCas in HP Prime?

Thank you
Anthony, Sydney

[ftneek]

(11-08-2023 08:26 PM)Albert Chan Wrote:  I just discovered XCas can! Perhaps it can add this to HP Prime Cas as well.

OP example, with guess in the feasible region.

XCas> fMin(6x+5y, [x, y, 2x+4y-22, 3x+2y-20, 4x+5y-40], [x,y], [99,99])

[2.85714285714, 5.71428571429]

XCas> [6,5] * ans()

45.7142857143

I hope the prime is able to add lpsolve() from Xcas. The optional arguments make it useful for other kinds of problems such as maximization or (mixed) integer programming.

XCas > lpsolve(6x+5y,[2x+4y>=22,3x+2y>=20,4x+5y>=40],
assume=lp_nonnegative)

[320/7,[x=20/7,y=40/7]]

~[45.7142857143, [x=2.85714285714,y=5.71428571429]]

https://www-fourier.univ-grenoble-alpes....tml#sec674

(11-09-2023 12:44 AM)Anthony The Koala Wrote:  Dear Albert Chan,
I checked the Aops and cannot find the XCas.

How to access the XCas in HP Prime?

Thank you
Anthony, Sydney

HP Prime is missing some commands from Xcas. The commands that are available are mostly listed in the toolbox catalog and help files. To access all commands from Xcas you should download it or access the web version. https://www-fourier.ujf-grenoble.fr/~par...casen.html. Copy and paste the Xcas commands to try them for yourself.

   

[Anthony The Koala]

Dear ftneek,

When I inputted in the HP Prime in CAS mode:
lpsolve(6x+5y,[2x+4y>=22,3x+2y>=20,4x+5y>=40],assume=lp_nonnegative)

I get "Error bad argument value"

Is there something I am doing wrong?

Thank you

Anthony, Sydney

[ftneek]

lpsove() is one of the Xcas commands that are not available on the HP Prime. So it will not work on the HP Prime. To use the command you should try it in the link I attached in my previous comment. The version of cas on the Prime is based on Xcas, but they are not completley identical.

[Anthony The Koala]

I tried using simplex_reduce
m =
2 4
3 2
4 5

P = [5 9]

c = [22 20 40?]

Using simplex_reduce(m, c, p)

I did not get the result as per expected

   

To ftneek
I went to the site at Grenoble
The result was instant.

But using the CAS simplex_reduce did not get the result.

Thank you
Anthony, Sydney

[parisse]

simplex_reduce will solve a maximization problem with inequality constraints like 2x+4y<=22, not >=.
From the doc:
Reduction by simplex algorithm to find max(c.x) under A.x<=b and x>=0, b>=0. Returns the maximum, the augmented solution x and the reduced matrix.
It's unclear for me if it's possible to rewrite the initial problem and call simplex_reduce. Changing the sign of c would replace a max by a min, but you can't change sign of x (since x>=0), and if you negate Ax>=b, b would become <=0 instead of >=0

The COBYLA solver (in solve.cc in giac) could be added to the Prime codebase, we would probably have to display the license in the Terminal:

Code:


/*
 * Copyright (c) 1992, Michael J. D. Powell (M.J.D.Powell@damtp.cam.ac.uk)
 * Copyright (c) 2004, Jean-Sebastien Roy (js@jeannot.org)
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

But lpsolve can not, it is released under GPL3 license.

[ftneek]

Sad to hear prime can't recieve lpsolve.

Anthony, you may find this program I wrote to be useful. It can be loaded onto the HP Prime using the Connectivity Kit. But currently it requires you to extract the coefficients into a matrix yourself. When I get around to it I would like to add support for symbolic input, so that you are not required to put it in standard form yourself. I make no guarantee that it is bug free, and there are probably optimizations I can make, but in my experience it works as long as you input the system correctly. On my virtual calculator it seems to always return a solution instantly, but on the physical calculator larger problems may take a few seconds. If it takes more than a few seconds, you may be stuck in an infinite loop and should hit Shift On to stop the program and recheck everything was typed correctly.

Here are 2 example ways to use it for your original problem, but other combinations can produce the same result as well.

Convert the system into standard form:
Example 1: 3 ">=" constraints, so we must subtract a slack variable and add an artificial variable to each row. Because we add artificial variables, we add an extra row to the bottom as shown below. the matrix becomes:

> a:=[[2,4,-1,0,0,1,0,0,22],[3,2,0,-1,0,0,1,0,20],[4,5,0,0,-1,0,0,1,40],[6,5,0,0,0,0,0,0,0],[0,0,0,0,0,1,1,1,0]]

> simplex(a)

[320/7,[20/7,40/7,46/7,0,0],[[0,0,1,6/7,-8/7,46/7],[1,0,0,-5/7,2/7,20/7],[0,1,0,4/7,-3/7,40/7],[0,0,0,10/7,3/7,-320/7]]]

The system has only 2 variables so x1,x2 are the first 2 items from the second item in the list. Thus the min is 320/7 at x1=20/7 and x2=40/7

Example 2: Multiply each ">=" constraint row by -1 to convert to "<=". We now have 3 "<=" constraints, so we only need add a slack variable to each row.

> a:=[[-2,-4,1,0,0,-22],[-3,-2,0,1,0,-20],[-4,-5,0,0,1,-40],[6,5,0,0,0,0]]

> simplex(a)

[320/7,[20/7,40/7,46/7,0,0],[[0,0,1,6/7,-8/7,46/7],[1,0,0,-5/7,2/7,20/7],[0,1,0,4/7,-3/7,40/7],[0,0,0,10/7,3/7,-320/7]]]
Same min.

  simplex.hpprgm (Size: 11.89 KB / Downloads: 10)

[HPCarnace]

Hi Anthony.
You can use the program HpPrime TORA like this video (its your example):
Using HP Prime TORA
(sorry for the sound and my English)

Additionally, you can also use the command in HOME:

Quote: funcHPTORA({{"example", 0, 1, 2, 3, 4, 0}, {[[6,5]]}, {{[[2,4]] , 2 , 22}, {[[3,2]], 2, 20}, {[[4,5]], 2, 40}}},3)

But, this is if you have HP Prime TORA installed.
The command has two arguments:
funcHPTORA(Exercise,Method)
Exercise: List with three lists: The first list contains: {ProblemName, IsMaximize?, IsMinimize?, NoVariables, NoConstraints, NoDecimals, ShowFraction?}. The second list contains the objective function as an array. The third list contains the three constraints in list form, where each restriction is of the form: {Array, Sign, Resource}, the sign is 1 for <=, 2 for >= and 3 for =.
Method: 1(all constraints <=), 2(M-method), 3(two-phase method), 4(dual simplex).

The result displays a list with the following elements:

Quote:{"example",6," (optimum)",45.7142857142,"X2","X1","s1",5.71428571429,2.85714285714,6.57142857144}

The first element is the name of the exercise, the second is the number of iterations, the third element shows whether a solution has been found (optimum), no solution was found (not feasible) or when there are multiple solutions. The fourth element is the maximum or minimum value (45.7142857142). The elements that follow are the names of the variables and then the values in the optimal table: X1=2.85714285714, X2=5.71428571429, s1 is "surplus variable" with value 6.57142857144.
I know it's a bit difficult to read the arguments of funcHPTORA, but I was thinking of using that function in new versions of the program for "Integer Linear Programming"

[Anthony The Koala]

Dear ftneek and hp carnace.,

Thank you for the links.

To ftneek
I have downloaded the hppgram file.

To hp carnace,
Thank you for the video link.

I went to hpcalc.org and searched terms "simplex" and "tora" and went directly to your page at
https://www.hpcalc.org/authors/1902

For both answers, I will lean both methods. This will be not only a learning experien e in itself BUT additionally I will be learning how to transfer files between my pc and hp prime.

Gracias, merci, thank you
Anthony, Sydney

[Albert Chan]

(11-09-2023 08:02 PM)ftneek Wrote:  Example 2: Multiply each ">=" constraint row by -1 to convert to "<=".
We now have 3 "<=" constraints, so we only need add a slack variable to each row.

> a:=[[-2,-4,1,0,0,-22],[-3,-2,0,1,0,-20],[-4,-5,0,0,1,-40],[6,5,0,0,0,0]]

> simplex(a)

Reading about simplex algorithm, I now get why simplex code minimized object function.
Matrix had a hidden column!

\(\left(\begin{array}{ccccccc}
-2 & -4 & 1 & 0 & 0 & 0 & -22 \\
-3 & -2 & 0 & 1 & 0 & 0 & -20 \\
-4 & -5 & 0 & 0 & 1 & 0 & -40 \\
6 & 5 & 0 & 0 & 0 & 1 & 0
\end{array}\right) \)

Since slack variables are non-negative, objective function is minimized.

I like machine to take care of slack variables. Less typing, less errors.
I added simplex_le(a) wrapper that add slack stuff.

max(c) = -min(-c), but I don't want to think about this either.
On the cost function, it does maximze if last element is positive.

Code:

simplex_le(a) := /* no need to fill slack variables */
BEGIN
 LOCAL b := col(a,0);
 a := concat(delcol(a,len(a[0])),identity(length(a)))
 a := replace(a,{1,length(a[0])},transpose(b));
 a[0][0] := 0;
 IF b[0]>0 THEN a[0] := -a[0] END /* maximize */
 a := simplex(a);
 IF b[0]>0 THEN a[1] := -a[1] END /* undo flip */
 return a;
END;

> simplex_le([-[2,4,22],-[3,2,20],-[4,5,40],[6,5,-1]])

\([\frac{320}{7},[\frac{20}{7},\frac{40}{7},\frac{46}{7},0,0],\left(\begin{array}{cccccc}
0 & 0 & 1 & \frac{6}{7} & \frac{-8}{7} & \frac{46}{7} \\
1 & 0 & 0 & \frac{-5}{7} & \frac{2}{7} & \frac{20}{7} \\
0 & 1 & 0 & \frac{4}{7} & \frac{-3}{7} & \frac{40}{7} \\
0 & 0 & 0 & \frac{10}{7} & \frac{3}{7} & \frac{-320}{7}
\end{array}\right) ]\)

simplex_reduce example from HP Prime Help screen (it always maximize)

> simplex_reduce([[3,2,2],[1,1,1]],[3,4],[1,2,3])

\(\frac{9}{2},[0,0,\frac{3}{2},0,\frac{5}{2}],\left(\begin{array}{cccccc}
\frac{3}{2} & 1 & 1 & \frac{1}{2} & 0 & \frac{3}{2} \\
\frac{-1}{2} & 0 & 0 & \frac{-1}{2} & 1 & \frac{5}{2} \\
\frac{7}{2} & 1 & 0 & \frac{3}{2} & 0 & \frac{9}{2}
\end{array}\right) \)

> simplex_le([[3,2,2,3],[1,1,1,4],[1,2,3,+1]])

\(\frac{9}{2},[0,0,\frac{3}{2},0,\frac{5}{2}],\left(\begin{array}{cccccc}
\frac{3}{2} & 1 & 1 & \frac{1}{2} & 0 & \frac{3}{2} \\
\frac{-1}{2} & 0 & 0 & \frac{-1}{2} & 1 & \frac{5}{2} \\
\frac{7}{2} & 1 & 0 & \frac{3}{2} & 0 & \frac{9}{2}
\end{array}\right) \)

We could make arguments match, but I found [a|b] input more convenient.
We can flip constraint inequality, from from ≤ to ≥, with a negate.

[ftneek]

(11-10-2023 04:05 PM)Albert Chan Wrote:  I like the machine to take care of slack variables. Less typing, less errors.
Rename simplex as simplex1, I added simplex(a) wrapper that add slack stuff.
.
.
.
> simplex([-[2,4,22],-[3,2,20],-[4,5,40],[6,5,-1]])

I have to admit the negative/positive argument in the c row for min/max is a nice idea.

I agree it would be nice if slack/artificial variables aren't required to be entered by the user. My only concern with this is approach is now all constraints are assumed to be "<=". If an "=" constraint is present, an artificial variable should be added instead of a slack variable. Therefore like simplex_reduce(), this wrapper method would be limited to solving systems in the form A.x<=b (but with no restriction on b), where as my simplex program can be used for mixed constraints as long as appropriate variables are added. And eventually I would like get around to handling mixed constraints without the user needing to add any additional variables.

For this reason I think the name of the wrapper should change to simplex_red() to indicate some similarities with simplex_reduce(), or simplex_le() to indicate that it is only for use with "less than or equal to (<=)" constraints. Then it is more clear (to me) that it could be used as a substitute/replacement for simplex_reduce(). Thank you for the examples!

[Albert Chan]

(11-10-2023 06:48 PM)ftneek Wrote:  ... I think the name of the wrapper should change to simplex_red() to indicate some similarities with simplex_reduce(), or simplex_le() to indicate that it is only for use with "less than or equal to (<=)" constraints.

I like less than or equal to reminder, and updated my wrapper name as simplex_le()