Post Reply 
Simplex method in prime how to use the constrains maximise s.t. constraints.
11-16-2023, 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
Find all posts by this user
Quote this message in a reply
11-16-2023, 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 :

Z-Max: 10 :x1: 3 :x2: 1 :
Main Sol 2,as Zrow=0: inCol\\1661\\166addit.STEPS Var\\|>2\\166Steps\\|>3 Time\\|>0\\166s :

Z-Max: 10 :x1: 0 :x2: [ '5/2' 2.5 ] :
Or not? SIMPLEX Sol i: [ 3 1 ] }" }

Two basic solutions above.
Sol = lambda×(sol1) + (1-lambda) × sol2.

[i]
Find all posts by this user
Quote this message in a reply
11-16-2023, 11:47 PM (This post was last modified: 11-16-2023 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
Find all posts by this user
Quote this message in a reply
11-16-2023, 11:48 PM
Post: #64
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
Great!
Find all posts by this user
Quote this message in a reply
11-17-2023, 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.SolŸMax Var†2¦Steps†4 Time†1¦s :

Z-Max: 52 :x1: 32 :x2: 20 :
as only positive Val: in.Col¦2¦final.STEPS :
Or not? SIMPLEX Sol i: [ 32 20 ] } }
Find all posts by this user
Quote this message in a reply
11-17-2023, 12:25 AM (This post was last modified: 11-17-2023 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 :

Z-Max: 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 :

Z-Max: 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 :

Z-Max: 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 :

Z-Max: 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) + (1-L)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.
Find all posts by this user
Quote this message in a reply
11-17-2023, 06:29 AM (This post was last modified: 11-17-2023 06:47 AM by ftneek.)
Post: #67
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
(11-16-2023 10:50 PM)Gil Wrote:  Yes, but there are an infinity of solutions
in that special case.

My program on my HP50G EMU48 finds 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

And the minimum value remains at 14/3.

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...

(11-17-2023 12:19 AM)Gil Wrote:  Another case, with no max
solved
> simplex2([[2,-3,1,0,4],[5,-3,0,-1,100],[-1,-1,0,0,0]],{3,4},4,0,0)

(11-17-2023 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
Find all posts by this user
Quote this message in a reply
11-17-2023, 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 Z-Max/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
Find all posts by this user
Quote this message in a reply
11-17-2023, 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
Z-Max: 6 :x1: 0 :x2: 2 :x3: 2 :x4: 0 :x5: 5 :x6: 0 :x7: 17 :

Solution 2
Z-Max: 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) + (1-L)×solution2

But again, here we have a special, so that the full solution should be :

{L×(solution1) + (1-L)×solution +
mu1× [ 1 1 '1/3' 0 0 1 '26/3' ] +
mu2 ×[ 0 1 0 0 1 1 4 ]}, with mu1& mu2 free.
Find all posts by this user
Quote this message in a reply
11-17-2023, 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
Find all posts by this user
Quote this message in a reply
11-17-2023, 04:29 PM
Post: #71
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
(11-17-2023 10:47 AM)Gil Wrote:  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 :


So that solution Simplex
L×(solution1) + (1-L)×solution2

But again, here we have a special, so that the full solution should be :

{L×(solution1) + (1-L)×solution +
mu1× [ 1 1 '1/3' 0 0 1 '26/3' ] +
mu2 ×[ 0 1 0 0 1 1 4 ]}, with mu1& mu2 free.

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
Find all posts by this user
Quote this message in a reply
11-17-2023, 07:48 PM (This post was last modified: 11-17-2023 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]

+ (1-t) × [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.
Find all posts by this user
Quote this message in a reply
11-17-2023, 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
Find all posts by this user
Quote this message in a reply
11-17-2023, 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.
Find all posts by this user
Quote this message in a reply
11-18-2023, 01:31 AM
Post: #75
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
(11-17-2023 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



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




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