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

11162023, 10:58 PM
Post: #61




RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
Thank you for pointing that out, I will investigate. There is a part in my code to detect infinite solutions, but it may need a modification. I'll let you know when I figure it out.
 neek 

11162023, 11:37 PM
Post: #62




RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
Try also [/i]the following system
[[ 1 2 'L' 5 ] [ 1 1 'L' 4 ] [ 2 4 0 'Max' ]]. "{ :S = \\GS(\\Gli*Sol i): with :0\\<=\\Gli\\<=: 1 :\\GS\\Gl: 1 : Main Sol 1,as Zrow=0: in.Col\\1661\\166final.STEPS Var\\>2\\166Steps\\>2 Time\\>0\\166s : ZMax: 10 :x1: 3 :x2: 1 : Main Sol 2,as Zrow=0: inCol\\1661\\166addit.STEPS Var\\>2\\166Steps\\>3 Time\\>0\\166s : ZMax: 10 :x1: 0 :x2: [ '5/2' 2.5 ] : Or not? SIMPLEX Sol i: [ 3 1 ] }" } Two basic solutions above. Sol = lambda×(sol1) + (1lambda) × sol2. [i] 

11162023, 11:47 PM
(This post was last modified: 11162023 11:51 PM by ftneek.)
Post: #63




RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
This one detected infinite solutions.
> simplex2([[1,2,1,0,5],[1,1,0,1,4],[2,4,0,0,0]],{3,4},4,0,0) [10,[3*t+3,(3*t+2)/2,0,3*t/2],[[1/2,1,1/2,0,5/2],[1/2,0,1/2,1,3/2],[0,0,2,0,10]]] Meaning infinite solutions for 0≤t≤1. Also the algorithm assumes minimization. So for max=min=10  neek 

11162023, 11:48 PM
Post: #64




RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
Great!


11172023, 12:19 AM
Post: #65




RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
Another case, with no max
. [[ 2 3 'L' 4 ] [ 5 3 'G' 100 ] [ 1 1 0 'Max' ]] { :'Sol' is no Max!: Unbound.SolMax Var2¦Steps4 Time1¦s : ZMax: 52 :x1: 32 :x2: 20 : as only positive Val: in.Col¦2¦final.STEPS : Or not? SIMPLEX Sol i: [ 32 20 ] } } 

11172023, 12:25 AM
(This post was last modified: 11172023 12:33 AM by Gil.)
Post: #66




RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
And try this tricky case:
{ [[ 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' ]] E for equal "{ :S = \\GS(\\Gli*Sol i): with :0\\<=\\Gli\\<=: 1 :\\GS\\Gl: 1 : Main Sol 1,as Zrow=0: in.Col\\1661\\166final.STEPS Var\\>7\\166Steps\\>15 Time\\>8\\166s : ZMax: 6 :x1: 0 :x2: 2 :x3: 2 :x4: 0 :x5: 5 :x6: 0 :x7: 17 : Main Sol 2,as Zrow=0: inCol\\{ [[ 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' ]] "{ :S = \\GS(\\Gli*Sol i): with :0\\<=\\Gli\\<=: 1 :\\GS\\Gl: 1 : Main Sol 1,as Zrow=0: in.Col\\1661\\166final.STEPS Var\\>7\\166Steps\\>15 Time\\>8\\166s : ZMax: 6 :x1: 0 :x2: 2 :x3: 2 :x4: 0 :x5: 5 :x6: 0 :x7: 17 : Main Sol 2,as Zrow=0: inCol\\1661\\166addit.STEPS Var\\>7\\166Steps\\>16 Time\\>10\\166s : ZMax: 6 :x1: 5 :x2: 2 :x3: [ '11/3' 3.66666666667 ] :x4: 0 :x5: 0 :x6: 0 :x7: [ '121/3' 40.3333333333 ] : Or not? SIMPLEX Sol i: { [ 5 2 '11/3' 0 0 0 '121/3' ] [ 0 2 2 0 5 0 17 ] } :+\\Gm12[\\>=0]*d, d: { [ 1 1 '1/3' 0 0 1 '26/3' ] [ 0 1 0 0 1 1 4 ] } : \\>Mixed Solution: 0\\<=\\Gl\\<=1 \\Gl(Sol 1) + (1\\Gl) * (not? SIMPLEX Sol 2): Plus :\\Gm12[\\>=0]*d, d: { [ 1 1 '1/3' 0 0 1 '26/3' ] [ 0 1 0 0 1 1 4 ] } }" }.STEPS Var\\>7\\166Steps\\>16 Time\\>10\\166s : ZMax: 6 :x1: 5 :x2: 2 :x3: [ '11/3' 3.66666666667 ] :x4: 0 :x5: 0 :x6: 0 :x7: [ '121/3' 40.3333333333 ] : Or not? SIMPLEX Sol i: { [ 5 2 '11/3' 0 0 0 '121/3' ] [ 0 2 2 0 5 0 17 ] } :+\\Gm12[\\>=0]*d, d: { [ 1 1 '1/3' 0 0 1 '26/3' ] [ 0 1 0 0 1 1 4 ] } : \\>Mixed Solution: 0\\<=\\Gl\\<=1 \\Gl(Sol 1) + (1\\Gl) * (not? SIMPLEX Sol 2): Plus :\\Gm12[\\>=0]*d, d: { [ 1 1 '1/3' 0 0 1 '26/3' ] [ 0 1 0 0 1 1 4 ] } }" } Here, 2 main solutions L(sol1) + (1L)sol2+ mu1× [ 1 1 '1/3' 0 0 1 '26/3' ] +mu2 ×[ 0 1 0 0 1 1 4 ], with mu1& mu2 free It was for me quite a nightmare to solve these cases. 

11172023, 06:29 AM
(This post was last modified: 11172023 06:47 AM by ftneek.)
Post: #67




RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
(11162023 10:50 PM)Gil Wrote: Yes, but there are an infinity of solutions Can you share the final basic variables for the alternate solution? For example for the first solution the final basic variables are {x3,x1}. There is a 0 is c row index 2, x2 is not a basic variable, so I think there might be infinite solutions. Using same pivoting rule as before usually returns infinite solution. But there is a 1 in the column, how did you determine pivot selection? My idea was: multiply row by 1 > negative b entry > apply dual simplex > arrived back at original solution... (11172023 12:19 AM)Gil Wrote: Another case, with no maxsolved > simplex2([[2,3,1,0,4],[5,3,0,1,100],[1,1,0,0,0]],{3,4},4,0,0) (11172023 12:25 AM)Gil Wrote: And try this tricky case:solved > simplex2([[1,1,0,0,1,0,0,1,0,0,0,3],[3,2,9,2,0,2,0,0,1,0,0,22],[0,1,0,0,0,1,0,0,0,1,0,2],[4,3,5,0,1,0,1,0,0,0,1,4],[1,0,3,1,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,1,0]],{8,9,10,11},11,4,0)  neek 

11172023, 10:35 AM
Post: #68




RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
There is no alternate solution, but just the one you found, ie solution1.
But to your vector solution1, you could create a more general solution always including your initial solution : general solution = solution1 (always to be included) + mu*[vector d], with mu a free real. Your solution1 is equivalent to general solutions +mu=0 * [vector d]. Note further that ZMax/Min(x) = always 0 for x = mu× (vector d), but not including solution 1. Finding d is not (the normal) part of simplex algorithm. As said, nice to get, as in my program HP50G EMU48 posted in that forum, the following general solution: [ '2/3' 0 '4/3' 0 0 ] :+µ[>0]*d, with d : [ 1 1 0 0 0 ]. Try for instance with µ=10 x1: 2/3+10×1 x2: 0+ 10×1 x3: 4/3+10×0 x4: 0+10×0 x5: 0+10×0 

11172023, 10:47 AM
Post: #69




RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
As for last problem
[[ 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' ]] E for equal There should have 2 distinct solutions : Solution 1 ZMax: 6 :x1: 0 :x2: 2 :x3: 2 :x4: 0 :x5: 5 :x6: 0 :x7: 17 : Solution 2 ZMax: 6 :x1: 5 :x2: 2 :x3: [ '11/3' 3.66666666667 ] :x4: 0 :x5: 0 :x6: 0 :x7: [ '121/3' 40.3333333333 ] : So that solution Simplex L×(solution1) + (1L)×solution2 But again, here we have a special, so that the full solution should be : {L×(solution1) + (1L)×solution + mu1× [ 1 1 '1/3' 0 0 1 '26/3' ] + mu2 ×[ 0 1 0 0 1 1 4 ]}, with mu1& mu2 free. 

11172023, 04:21 PM
Post: #70




RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
You have confused me. In your previous comment you said there is an infinity of solutions. But in the comment you just made you say there is no alternate solution. Which is it? If there is no alternate solution there should only be one unique solution. If there is only one solution, I don't know how you want to make the answer "more general". Can you leave a link with an example explaining the information you think is missing?
 neek 

11172023, 04:29 PM
Post: #71




RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
(11172023 10:47 AM)Gil Wrote: As for last problem 2 solutions means infinite solutions along the edge between the two vertices of the feasible region. If you want to recover either you can substitute for t=0 and t=1.  neek 

11172023, 07:48 PM
(This post was last modified: 11172023 08:38 PM by Gil.)
Post: #72




RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
Yes,
<{infinite solutions with t in [1 0], as you calculated by simplex} + {(again an infinity of other solutions with any number) × specific vector d1} + {{again an infinity of other solutions with any number} × specific vector d2}> with values of vectors d1 and d2 as indicated (not found by "normal" Simplex procefure). Complete solution (composed of 4 terms, of which 2 found by “normal" simplex procedure): {t ×[x1: 0 :x2: 2 :x3: 2 :x4: 0 :x5: 5 :x6: 0 :x7: 17] + (1t) × [x1: 5 :x2: 2 :x3: [ '11/3' 3.66666666667 ] :x4: 0 :x5: 0 :x6: 0 :x7: [ '121/3' 40.3333333333 ]] + mu1× [ 1 1 '1/3' 0 0 1 '26/3' ] + mu2 ×[ 0 1 0 0 1 1 4 ]}, with t in [0 1] and with mu1& mu2 free. 

11172023, 10:45 PM
Post: #73




RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
I understand that for that problem you are saying there are 4 terms to the 'complete' solution. But I still don't understand where the last 2 terms are coming from, what they represent, or how they contribute to the solution.
But then for the previous mentioned problem, you are saying that there is only 1 solution found by simplex and 1 additional mu term in the complete solution, correct? Like I said I would need to read some kind of reference to really understand what you're talking about. Please leave some kind of source so I can try to understand for myself, otherwise I have no idea how to produce what you're asking for.  neek 

11172023, 11:09 PM
Post: #74




RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
See my examples in
https://www.hpmuseum.org/forum/archive/i...19215.html For a source and explanations, see https://ieeexplore.ieee.org/stamp/stamp....er=6075407 from which last example was taken. 

11182023, 01:31 AM
Post: #75




RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
(11172023 10:45 PM)ftneek Wrote: I understand that for that problem you are saying there are 4 terms to the 'complete' solution. But I still don't understand where the last 2 terms are coming from, what they represent, or how they contribute to the solution. Simplex algorithm solve A * S ≤ B General solution solve A * X = 0 Complete solution: A * (S+X) ≤ B 

« Next Oldest  Next Newest »

User(s) browsing this thread: