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

[ftneek]

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.

[Gil]

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]

[ftneek]

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

[Gil]

Great!

[Gil]

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 ] } }

[Gil]

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.

[ftneek]

(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)

[Gil]

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

[Gil]

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.

[ftneek]

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?

[ftneek]

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

[Gil]

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.

[ftneek]

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.

[Gil]

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.

[Albert Chan]

(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