Simplex method in prime how to use the constrains maximise s.t. constraints.
|
11-06-2023, 12:53 AM
Post: #21
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
(11-05-2023 11:05 PM)Anthony The Koala Wrote: I appreciate please an elaboration of: (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. |
|||
11-06-2023, 03:16 AM
Post: #22
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
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 |
|||
11-06-2023, 04:34 AM
(This post was last modified: 11-06-2023 05:04 AM by ftneek.)
Post: #23
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
(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. - neek |
|||
11-06-2023, 06:53 AM
Post: #24
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
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 |
|||
11-06-2023, 08:15 AM
Post: #25
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
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). - neek |
|||
11-08-2023, 08:26 PM
Post: #26
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
(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 |
|||
11-08-2023, 11:06 PM
Post: #27
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
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 |
|||
11-09-2023, 12:15 AM
Post: #28
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
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 |
|||
11-09-2023, 12:44 AM
Post: #29
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
Dear Albert Chan,
I checked the Aops and cannot find the XCas. How to access the XCas in HP Prime? Thank you Anthony, Sydney |
|||
11-09-2023, 04:09 AM
Post: #30
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
(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. 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, 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. - neek |
|||
11-09-2023, 06:21 AM
Post: #31
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
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 |
|||
11-09-2023, 06:36 AM
Post: #32
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
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.
- neek |
|||
11-09-2023, 09:09 AM
Post: #33
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints. | |||
11-09-2023, 12:09 PM
Post: #34
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
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:
|
|||
11-09-2023, 08:02 PM
Post: #35
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
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) - neek |
|||
11-09-2023, 08:17 PM
(This post was last modified: 11-09-2023 08:32 PM by HPCarnace.)
Post: #36
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
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" |
|||
11-09-2023, 10:11 PM
Post: #37
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
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 |
|||
11-10-2023, 04:05 PM
(This post was last modified: 11-10-2023 09:00 PM by Albert Chan.)
Post: #38
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
(11-09-2023 08:02 PM)ftneek Wrote: Example 2: Multiply each ">=" constraint row by -1 to convert to "<=". 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 */ > 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. |
|||
11-10-2023, 06:48 PM
(This post was last modified: 11-10-2023 07:52 PM by ftneek.)
Post: #39
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
(11-10-2023 04:05 PM)Albert Chan Wrote: I like the machine to take care of slack variables. Less typing, less errors. 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! - neek |
|||
11-10-2023, 08:01 PM
Post: #40
|
|||
|
|||
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
(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() |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)