Simplex method in prime how to use the constrains maximise s.t. constraints.
11-16-2023, 10:58 PM
Post: #61
 ftneek Member Posts: 94 Joined: Oct 2022
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
11-16-2023, 11:37 PM
Post: #62
 Gil Senior Member Posts: 630 Joined: Oct 2019
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(\\Gli*Sol i): with :0\\<=\\Gli\\<=: 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]
11-16-2023, 11:47 PM (This post was last modified: 11-16-2023 11:51 PM by ftneek.)
Post: #63
 ftneek Member Posts: 94 Joined: Oct 2022
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
11-16-2023, 11:48 PM
Post: #64
 Gil Senior Member Posts: 630 Joined: Oct 2019
RE: Simplex method in prime how to use the constrains maximise s.t. constraints.
Great!
11-17-2023, 12:19 AM
Post: #65
 Gil Senior Member Posts: 630 Joined: Oct 2019
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 ] } }
11-17-2023, 12:25 AM (This post was last modified: 11-17-2023 12:33 AM by Gil.)
Post: #66
 Gil Senior Member Posts: 630 Joined: Oct 2019
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(\\Gli*Sol i): with :0\\<=\\Gli\\<=: 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(\\Gli*Sol i): with :0\\<=\\Gli\\<=: 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 ] } :+\\Gm12[\\>=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 :\\Gm12[\\>=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 ] } :+\\Gm12[\\>=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 :\\Gm12[\\>=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.
11-17-2023, 06:29 AM (This post was last modified: 11-17-2023 06:47 AM by ftneek.)
Post: #67
 ftneek Member Posts: 94 Joined: Oct 2022
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
11-17-2023, 10:35 AM
Post: #68
 Gil Senior Member Posts: 630 Joined: Oct 2019
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.

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
11-17-2023, 10:47 AM
Post: #69
 Gil Senior Member Posts: 630 Joined: Oct 2019
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.
11-17-2023, 04:21 PM
Post: #70
 ftneek Member Posts: 94 Joined: Oct 2022
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
11-17-2023, 04:29 PM
Post: #71
 ftneek Member Posts: 94 Joined: Oct 2022
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
11-17-2023, 07:48 PM (This post was last modified: 11-17-2023 08:38 PM by Gil.)
Post: #72
 Gil Senior Member Posts: 630 Joined: Oct 2019
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.
11-17-2023, 10:45 PM
Post: #73
 ftneek Member Posts: 94 Joined: Oct 2022
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
11-17-2023, 11:09 PM
Post: #74
 Gil Senior Member Posts: 630 Joined: Oct 2019
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.
11-18-2023, 01:31 AM
Post: #75
 Albert Chan Senior Member Posts: 2,686 Joined: Jul 2018
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

 « Next Oldest | Next Newest »