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

[Anthony The Koala]

I found a reference to the Simplex method. But it does not specify how to specify maximise subject to constraints then plotting.

Reference: "HP prime guide finite mathematics" ISBN 9780195573035, page 61.

Minimise: C = 6x + 5y
Subject to:
x >= 0, y >= 0
2x + 4y >= 22
3x + 2y >= 20
4x + 5y >= 40

I tried using the Advanced Graphics app.
When I entered x>= 0 into the editor, I got a syntax error.

Is there a way of entering the equations into the Advanced Graphics editor then to plot using Plot and see the various graphs of the equation when pressing Plot?

Thank you
Anthony, Sydney

[Joe Horn]

Try using upper case X and Y as the softkeys suggest.

[Anthony The Koala]

Dear Joe,
Thank you for the reply.
I changed to upper case.
Attached are the screenshots of the Advanced Graphics interface and plot

My question is how to solve for X and Y.

Thank you
Anthony,Sudney

[dg1969]

I don't understand very well your problem... But pearhaps using the "AND" keyword is what you need ?
2*X+3*Y>2 AND etc... On a single line Vi.

Or unchek all your first lines and add on a new one
V1 AND V2 AND V3...

[HPCarnace]

I have not read the book, but, I had made a program called 'TORA' to solve these linear programming problems, including the graphical method. My program is based on the "Advanced Graphics" application so after exiting the program the equations appear in the Symbolic View and as dg1969 suggests it is better with "AND" (the feasible region is shown more clearly)

I don't know if the book "HP prime guide finite mathematics" explains this: https://www.phpsimplex.com/en/graphical_...illustrate %20more%20than%203D.
What you are asking is step 5 and 6

[Albert Chan]

(11-01-2023 02:42 AM)Anthony The Koala Wrote:  Minimise: C = 6x + 5y
Subject to:
x >= 0, y >= 0
2x + 4y >= 22
3x + 2y >= 20
4x + 5y >= 40

L0: C = 6x + 5y  --> slope = -1.2
L1: 2x + 4y = 22 --> slope = -0.5
L2: 3x + 2y = 20 --> slope = -1.5
L3: 4x + 5y = 40 --> slope = -0.8

Constraints slope are different than L0 slope, solution must be one of the vertices.
Graphically, we start with 0 = 6x + 5y, and "raise" it (increase C) until it hit a vertex.

Sort the slopes, smallest to biggest, we have {L2, L0, L3, L1}
Based on slope alone, vertex is intersection of L2 and L3

2*L2 - L3 --> 2x - y = 0 --> y = 2x
L2: 3x + 2y = 7x = 20    --> x = 20/7
L1: 2x + 4y = 10x = 200/7 ≈ 28.57 ≥ 22      ✔ (20/7, 40/7) is a true vertex

min(C) = 6x + 5y = 16x = 320/7 ≈ 45.71

[Anthony The Koala]

Dear all, thank you for replies.

Here is what I tried:

HP Carnace macro to solve a simplex. Could you please share the link to the TORA macro.


To DG1969, I created the entry in the afvanced menue
V1 6x + 5y
Subject to:
V2 x >= 0,
V3 y >= 0
V4 2x + 4y >= 22
V5 3x + 2y >= 20
V6 4x + 5y >= 40

I made another line
V7. V4 AND V5 AND V7

Pressed plot
Result: "Error Invalid Object"
Is there or are there additional steps?

To Albert Chan,
* I mentally made a note of the slopes
* there were three equations for two unknowns I ranked the magnitude of the slopes
* used the Linear Solver app and entered the two equations to obtain the soln to X and Y
*,X = 2.85714, Y = 5.7143
* then in the home screen subtituted the formula X*6 + 5*Y = 45.713

Thank you all
Anthony, Sydney

[HPCarnace]

This is the program TORA for HP Prime: https://www.hpcalc.org/details/9494
In this forum: HP Prime TORA

[Albert Chan]

(11-01-2023 07:32 PM)HPCarnace Wrote:  ... as dg1969 suggests it is better with "AND" (the feasible region is shown more clearly)

Still, with overlapping regions, it is very hard to spot the solution.
Even *after* we have the solution, confirming with plots may be tough.
This is especially true if slopes are close, which made polygon look like circle.

It may be better to plot something else ...

C = 6x + 5y --> y = (C-6x)/5
Elminate y from constraints, and solve for C

L1: 2x + 4y ≥ 22      → C ≥ 3.5x + 27.5
L2: 3x + 2y ≥ 20      → C ≥ -1.5x + 50
L3: 4x + 5y ≥ 40      → C ≥ 2x + 40

For vertices, inequality changed to equal sign. With x≥0, we have:
L1: C ≥ 27.5
L2: C ≤ 50
L3: C ≥ 40               → 40 ≤ C ≤ 50

If we plot below (V1,V2,V3), min(C) is the "lowest" intersection.
If a ball fall from the sky, min(C) is where it landed.

gnuplot> V1(x) = 3.5*x + 27.5
gnuplot> V2(x) = -1.5*x + 50
gnuplot> V3(x) = 2*x + 40
gnuplot> set terminal dumb
gnuplot> plot [0:5] [40:50] V1(x), V2(x), V3(x)

Code:

  50 ###-----------+-------------+-------------+-------------+------------$$
     +  #####      +             +             +             +V1(x) ****** +
     |       #####                                            V2(x)$###### |
     |            #####                                       V3(x) $$$$$$ |
  48 ++                #####                               $$$$           ++
     |                      #####                      $$$$                |
     |                           #####              $$$                    |
     |                                #####    $$$$$                       |
  46 ++                                   ######                          ++
     |                                  $$$$   #####                       |
     |                               $$$$           #####                 **
  44 ++                          $$$$                    #####         ***++
     |                       $$$$$                            #####  ***   |
     |                    $$$                                      ***##   |
     |                $$$$                                       ***   #####
  42 ++           $$$$                                         **         ++
     |         $$$$                                          **            |
     |     $$$$                                            **              |
     + $$$$        +             +             +         **  +             +
  40 $$------------+-------------+-------------+-------**----+------------++
     0             1             2             3             4             5

Even with crude ASCII plot, we get min(C) ≈ 46, from V2, V3 intersection.

[jte]

If plotting within the Advanced Graphing app, the V1, V2, ... each need two arguments when referenced in definitions.

I'm attaching some screenshots. I've also added SIN(1.5(6X+3Y))<0 so that one can get an idea as to how 6X+3Y is behaving. (From the plot, looking to where the waves of SIN(1.5(6X+3Y)) break, one can see where extrema of 6X+3Y lie along the boundary of the intersection of halfplanes.)

   

   

   

   

[jte]

By going back and forth between the Plot view and Symbolic view of the Advanced Graphing app, and checking / unchecking various definitions, I could see which two defined the corner the waves were breaking on. So I added boundary definitions for those two (by swapping >= for =), returned to the Plot view, long-held near the intersection so that I could choose one of the two boundary definitions involved, and then switched the trace mode to "Intersections with..." the other boundary definition, and ... the plot cursor jumped to the corner.

   

Going back to Home and evaluating 6X+5Y gives 45.7142857142, which seems to agree with Albert's result.

[Anthony The Koala]

Dear all,
Thank you for the replies.

This is my attempts.

To HP Carnace, I downloaded the zip on the simplex macro. To do in transferring the program to my HP Prime.

To Albert Chan,
I could not follow in re-arranging the eqn to maximisr and make y y the subject then substituting it for the constraints. I don't think my HP Prime has access to the gnuplot program.

Will converting the first equation in respect to y make it easier to solve the problem?

To jte,
I followed the procedure and here are the screenshots of the Advanced Graphics interface and the graph.

       

Furthermore I could not get the optimum solution of X = 2.85714, Y = 5.7143
* then the profit of X*6 + 5*Y = 45.713 as I did in my previous reply.

Thank you
Anthony, Sydney

[Albert Chan]

(11-03-2023 09:42 AM)Anthony The Koala Wrote:  Will converting the first equation in respect to y make it easier to solve the problem?

Eliminate x to make C as a function of y follow same steps.

Minimize C = 6x + 5y      → x = (C-5y)/6
Substitute above x to constraints, solve for C

L1: 2x + 4y ≥ 22      → C ≥ -7y + 66
L2: 3x + 2y ≥ 20      → C ≥ y + 40
L3: 4x + 5y ≥ 40      → C ≥ -2.5y + 60

For vertices, inequality changed to equal sign. With y≥0, we have:
L1: C ≤ 66
L2: C ≥ 40
L3: C ≤ 60               → 40 ≤ C ≤ 60

y ≤ max((66-min(C))/7, (60-min(C))/2.5) = max(26/7, 8) = 8

Quote:I don't think my HP Prime has access to the gnuplot program.

No need to use gnuplot, any plotting program will work.
I choose gnuplot simply because setting xrange, yrange is simple.

XCas is another good choice, its cfg menu can set-up plot box ranges.
XCas> plotfunc(max(-7y+66, y+40, -2.5y+60), y=0..8)

HP Prime Advanced Graphing App, we need to map (y,C) --> (X,Y)
(this is the reason my previous post do (x,C), to reduce confusion)

V1: Y>=MAX(-7*X+66, X+40, -2.5*X+60)

Is there a simple way to zoom-in, with X = [0,8], Y = [40,60] ?

Zoom-Box option does not allow directly entering corner coordinates.
It only allow point and click for corners, but does not show coordinates.
We don't even know where the corners are without zoom-out, many times.

The only fast way I can think of is to map (y,C) --> (X,Y+50)

V1: Y+50>=MAX(-7*X+66, X+40, -2.5*X+60)

min(C) = min(Y) + 50 = -4.28571428571 + 50 = 45.7142857143

[Albert Chan]

(11-03-2023 02:55 AM)jte Wrote:  I've also added SIN(1.5(6X+3Y))<0 so that one can get an idea as to how 6X+3Y is behaving.

Typo: C = 6*X+5*Y, 3Y should be 5Y

Assuming 1.5 really meant roughly pi/2, above implied RAD mode.
Since users may have different mode setting, this made SIN not portable.

Instead, we may use portable equivalent: ((6*X+5*Y) MOD 4)>2
Intent is also clearer, square wave with period of 4

(11-03-2023 09:42 AM)Anthony The Koala Wrote:  To jte ... I could not get the optimum solution of X = 2.85714, Y = 5.7143

Your plot is missing the crucial square wave function, described above.
With the parallel ruler, we can locate vertex with min(C)

BTW, we could get min(C) without getting vertex (X,Y)
Follow the ruler, interpolate for Y intercept, then multiply by 5

C = 6x + 5y = 6*0 + 5*(y intercept) ≈ 5*9.1 = 45.5

[jte]

(11-03-2023 09:42 AM)Anthony The Koala Wrote:  ⋮
To jte,
I followed the procedure and here are the screenshots of the Advanced Graphics interface and the graph.



Furthermore I could not get the optimum solution of X = 2.85714, Y = 5.7143
* then the profit of X*6 + 5*Y = 45.713 as I did in my previous reply.
⋮

I could certainly have been more detailed in my earlier message... Plotting 5Y+6X=C in the Advanced Graphing app will plot a line for a particular value of C (to see the value, one could evaluate C in the home screen before going to the plot view).

The HP Prime doesn't currently have a built-in app for handling constrained optimization.

My plotting of SIN(1.5(6X+5Y))<0 was to show how 6X+5Y lay relative to the region of interest. If one plotted SIN(π*(6*X+5*Y))=0, for example, the plot would include 6*X+5*Y=K for each integer value of K; 6*X+5*Y would be increasing / decreasing perpendicularly to these contour lines.

Here is a plot with the contour lines:

   

From this sort of plot, I could visually see where 6*X+5*Y=K was first hitting the region of interest (as K increases from negative infinity). I could then toggle (check / uncheck) the various region constraints in the symbolic view to see which two where involved with the vertex of interest. I then added two equations that would define the boundaries (of each constraint). A screenshot of my symbolic view at this point is as follows:

   

And here is a plot view (I've adjusted the colours a bit, so that the lines are a bit easier to see, so that the region is not quite so heavy):

   

I added the two equations as the Advanced Graphing app does allow one to lock the plotting cursor to the intersection of two curves (via Trace / PoI / Intersections with...) — the two curves, in this case, being the two lines that together define the vertex of interest.

[jte]

(11-03-2023 03:30 PM)Albert Chan Wrote:  

(11-03-2023 02:55 AM)jte Wrote:  I've also added SIN(1.5(6X+3Y))<0 so that one can get an idea as to how 6X+3Y is behaving.

Typo: C = 6*X+5*Y, 3Y should be 5Y
⋮

Whoops... Yes, I agree.

(11-03-2023 03:30 PM)Albert Chan Wrote:  ⋮
Assuming 1.5 really meant roughly pi/2, above implied RAD mode.
Since users may have different mode setting, this made SIN not portable.
⋮

Yes, although I actually first tried a scaling factor of 1, thought that a bit coarse, changed to 2, thought that a bit too fine, changed to 1.5. (I wasn't aiming for pi/2, just for a nice plot.)

(11-03-2023 03:30 PM)Albert Chan Wrote:  ⋮
Instead, we may use portable equivalent: ((6*X+5*Y) MOD 4)>2
Intent is also clearer, square wave with period of 4
⋮

Yes; I'm just used to comparing SIN(K * ...) to zero.

(Albert: we seemed to have been typing our earlier replies in in parallel, which is why I'm replying to yours now...)

[Albert Chan]

(11-01-2023 10:15 PM)Albert Chan Wrote:  Sort the slopes, smallest to biggest, we have {L2, L0, L3, L1}
Based on slope alone, vertex is intersection of L2 and L3

Based on slope alone might be wrong, thus true vertex confirmation required
If vertex is not real (not satisfy all contraints), we need to search others.

(11-02-2023 09:20 PM)Albert Chan Wrote:  C = 6x + 5y --> y = (C-6x)/5
Elminate y from constraints, and solve for C
L1: 2x + 4y ≥ 22      → C ≥ 3.5x + 27.5
L2: 3x + 2y ≥ 20      → C ≥ -1.5x + 50
L3: 4x + 5y ≥ 40      → C ≥ 2x + 40

Example, if we adjust L1 RHS from 22 to 30, we get:
L1: 2x + 4y ≥ 30      → C ≥ 3.5x + 37.5
L2: 3x + 2y ≥ 20      → C ≥ -1.5x + 50
L3: 4x + 5y ≥ 40      → C ≥ 2x + 40

For vertices, inequality changed to equal sign.
L1: C(x=0) = 37.5
L2: C(x=0) = 50
L3: C(x=0) = 40

L2 has highest C(x=0), and the only constraint with negative dC/dx --> vertex lies on L2

Intersections:
L2 and L1: x = (50-37.5) / (1.5+3.5) = 2.5
L2 and L3: x = (50-40) / (1.5+2) = 20/7 ≈ 2.85714

x>2.5, L2 is out of the picture --> min(C) = -1.5*2.5 + 50 = 46.25

It we plot this, only 1 vertex appeared. L3 constraint not involved at all!

Cas> plotfunc([3.5*x+37.5, -1.5*x+50, 2*x+40], x = 0 .. (50-37.5)/3.5)

Cas plotfunc(...) only show curve shape (HP Prime emulator, 2018 10 16)
For details, paste plotfunc(...) to Geometry App, Symbolic View, then [Plot]

[Anthony The Koala]

Dear all,
This is a learning experience.

To jte thank you for alerting me to "The HP Prime doesn't currently have a built-in app for handling constrained optimization"

To Albert Chan,
Since the HP Prime does not do constrained optimisation, I work out the minimum cost by the following.using the info:
Cost 6x + 5y
(1) 2x + 4y = 22
(2) 3x + 2y = 20
(3) 4x + 5y = 40
x >= 0, y >= 0
Work out the corner points for (1), (2 ) and (3) and when x = 0, y = 0
When x = 0. f(1)(0,y) = 22/4.ie (0,22/4), Cost = 22
f(2)(0,y) = 10 ie (0,10), Cost = 20
f(3)(0,y) = 8 ie (0, 8), Cost = 40
y = 0 f(1)(x,0) = 11 ie (11,0), Cost = 66
f(2) (x,0)= 6.6666, Cost = 40
f(3)(x,0) = 10, Cost = 60
Using the HP Prime to solve for x and y for all pairwise solving of f1, f2, f3 using
col(RREF([[2 4 22],[3 2 20]]),3) = (9/2, 13/4) , Cost = 173/4 = 43.25
col(RREF([[2 4 22],[4 5 40]]),3) = (25/3, 4/3), Cost = 170/3 = 57.667
col(RREF([[3 2 43.2520],[5 5 40]]),3) = (20/7,40/7) , Cost = 320/7 = 45.71

Since x and y require +ve amounts, therefore the min cost 43.25 when x= 9/2 and y=13/4.

I stand to be corrected on this.

Thank you
Anthony, Sydney

[Albert Chan]

(11-05-2023 02:47 PM)Anthony The Koala Wrote:  Using the HP Prime to solve for x and y for all pairwise solving of f1, f2, f3 using
col(RREF([[2 4 22],[3 2 20]]),3) = (9/2, 13/4) , Cost = 173/4 = 43.25
col(RREF([[2 4 22],[4 5 40]]),3) = (25/3, 4/3), Cost = 170/3 = 57.667
col(RREF([[3 2 43.2520],[5 5 40]]),3) = (20/7,40/7) , Cost = 320/7 = 45.71

Since x and y require +ve amounts, therefore the min cost 43.25 when x= 9/2 and y=13/4.

Wrong. min(Cost) is not enough, it need to satisfy *all* constraints.

L3: 4x + 5y >= 40

Point (9/2, 13/4), LHS = 34.25, failed constraint.

Brute force way is going to generate \(\binom{n}{2}\) intersections, most of them not vertices.

[Anthony The Koala]

Dear Albert Chan,
Thank you for the reply.

Quote:Wrong. min(Cost) is not enough, it need to satisfy *all* constraints.

L3: 4x + 5y >= 40

Point (9/2, 13/4), LHS = 34.25, failed constraint.

Brute force way is going to generate (n2)
intersections, most of them not vertices.

I appreciate please an elaboration of:
(i) it needs to satisy all constraints, and
(ii) most of them not vertices. What are these vertices

Thank you,
Anthony, Sydney