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

[Albert Chan]

(11-10-2023 06:48 PM)ftneek Wrote:  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.

(≤ constraint) + (≥ constraint) ≡ (= constraint) ?

Example taken from https://en.wikipedia.org/wiki/Simplex_algorithm

Minimize Z = -2x - 3y - 4z

Constraints:
3x + 2y + z = 10
2x + 5y + 3z = 15
x, y, z >= 0

> m := [[3,2,1,10], [2,5,3,15], [-2,-3,-4,-1]
> m := extend(−m[1..2], m)
> simplex_le(m)

\([\frac{-130}{7},[\frac{15}{7},0,\frac{25}{7},0,0,0,0],\left(\begin{array}{cccccccc}
1 & \frac{1}{7} & 0 & \frac{3}{-7} & 0 & 0 & \frac{1}{-7} & \frac{15}{7} \\
0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\
0 & \frac{11}{7} & 1 & \frac{2}{7} & 0 & 0 & \frac{3}{7} & \frac{25}{7} \\
0 & \frac{25}{7} & 0 & \frac{2}{7} & 0 & 0 & \frac{10}{7} & \frac{130}{7}
\end{array}\right) \)

Matched wikipedia answer ... or, am I just lucky?

[ftneek]

Yes, I suppose it is equivalent. But the textbook I'm learning from uses artificial variables for equality. Here is the difference.

Originally we had n "=" constraints. Using artificial variables, we only need add n columns and 1 row.

> simplex([[3,2,1,1,0,10],[2,5,3,0,1,15],[-2,-3,-4,0,0,0],[0,0,0,1,1,0]])
>dim(Ans(3))
[3 6], only keeping track of 18 elements once the artificial row is deleted.

Of course, the artificial columns could be deleted once w (sum of artificial variables) is determined to be 0, meaning calculations from that point on would be on a matrix of dimension [3 4], bringing down to 12 elements. This is under the assumption no artificial variables are currently basic variables. If there is one, it probably needs to be replaced with non-artificial variable before the column can be deleted. But I have left the artificial columns in since solutions to the "primal system" can give solutions to the "dual system".

Using the <= + >= method, we now have 2n <= constraints, and must therefore add 2n columns for slack variables.

(11-10-2023 08:26 PM)Albert Chan Wrote:  > m := [[3,2,1,10], [2,5,3,15], [-2,-3,-4,-1]
> m := extend(−matrix(row(m,1 .. 2)), m)
> simplex_le(m)

> dim(Ans(3))
[5 8]
We must keep track of 40 elements. The size of the matrix is larger, meaning more memory and calculations are required, and none of the columns should be deleted. Although I admit I am not as familiar with this method, so maybe you could delete some rows/columns at some point.

In short, I believe the artificial variable method should be more efficient.

[Albert Chan]

(11-10-2023 04:05 PM)Albert Chan Wrote:  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.

There may be situations that c has non-zero offset.
We could solve for c without offset, then add it later, but I don't want to worry about it.

To make room, cost direction (max or min) moved outside the matrix, as 2nd argument.

Code:

simplex_le(a, dir) :=
BEGIN
 LOCAL b := col(a,0);
 a := concat(delcol(a,len(a[0])),identity(len(a)))
 a := replace(a,{1,len(a[0])},transpose(b));
 IF dir>0 THEN a[0] := -a[0] END /* maximize */
 a := simplex(a);
 IF dir>0 THEN a[1] := -a[1] END /* undo flip */
 return a;
END;

Quote:Minimize Z = -2x - 3y - 4z

Constraints:
3x + 2y + z = 10
2x + 5y + 3z = 15
x, y, z >= 0

With 2 equations and 3 unknown, we can knock down 2 variables.

> xyz := solve(3x+2y+z=10 AND 2x+5y+3z=15 ,[x,y,z])[0]

[1/11*z+20/11, -7/11*z+25/11, z]

> simplify([-2,-3,-4] * xyz)

(-25*z - 115)/11

Z is minimized if z is maximized. From y, max(z) = (25/11) / (7/11) = 25/7
min(Z) = (-25*(25/7) - 115)/11 = -130/7

Lets solve min(Z) with simplex_le(), noted that Z has an offset.
Constraint x≥0 --> 20/11 ≥ -1/11*z
Constraint y≥0 --> 25/11 ≥ 7/11*z

Note that [a|b] matrix, we evaluate a*x - b
Same for cost function, Z = (-25*z - 115)/11 input as [-25,115]/11

> simplex_le([[-1,20], [7,25], [-25,115]/11], −∞)

[−18.5714285714, [25/7, 165/7, 0], ...]

We get the same thing if we do row operations, without affecting cost function.

> m := [[3,2,1,10], [2,5,3,15], [-2,-3,-4,0]]
> m[1] /= m[1][1]
> m := pivot(m,1,1)
> m[2] /= m[2][2]
> m := pivot(m,2,2)

\(\left(\begin{array}{cccc}
1 & 0 & \frac{-1}{11} & \frac{20}{11} \\
0 & 1 & \frac{7}{11} & \frac{25}{11} \\
0 & 0 & \frac{-25}{11} & \frac{115}{11}
\end{array}\right) \)

[ftneek]

(11-11-2023 01:43 AM)Albert Chan Wrote:  There may be situations that c has non-zero offset.

Yes, the offset actually goes in the last position of the objective function row. So where your +/- argument was for min/max. I'm glad you noticed and made a fix, I forgot to mention it.

Example 3.1.1 from the mentioned textbook:

Xcas > lpsolve(-3x1+2x2+x3-x4+x5+87,[4x1-x2+x4-x5+x6=6,-7x1+8x2+x3-x7=7,x1+x2+4x4-4x5=12],assume=lp_nonnegative)
->1441/17

> simplex2([[4,-1,0,1,-1,1,0,1,0,0,6],[-7,8,1,0,0,0,-1,0,1,0,7],[1,1,0,4,-4,0,0,0,0,1,12],[-3,2,1,-1,1,0,0,0,0,0,-87],[0,0,0,0,0,0,0,1,1,1,0]],{8,9,10},10,3,0)
>Ans(1)
1441/17

Note I think there is a bug with my wrapper simplex() method, sometimes the artificial variable counter is not updated. So far the bad effect is for some systems with artificial variables. But also note that simplex2() works as intended with the correct arguments. I need to determine a correct (and hopefully efficient) way to identify artificial variables without false positives, as that would have a bad effect for systems without artificial variables. But with symbolic input or a list of constraint symbols, this task should be much easier.

If you want to help me debug/think of a better way to detect artificial variables... The simplex wrapper assumes the matrix is in standard form. The search should probably start from the right, since slack/artificial variables are generally added to the end of the matrix. A slack variable is chosen for the I-th basic variable if a column has a single 1 in position of the I-th row. An artificial variable should be identified if there are 2 1's in the column: in the position of the current row number, and the last position of the column. But be cautious, it is possible for the coefficients of the objective function to be 1 (and there is a 1 in position of current row, and there is no artificial row). We should stop looking in a row if a basic variable was identified for it. When looking for next bv, we need not check columns of previously identified bv. We should stop looking for basic variables if size(b0) equals the number of constraints. We should only call simplex2() if we have enough basic variables when the search is complete.

I think this is worth finding the correct way to do because the size of the matrix grows much larger when using the <= + >= method. But I have 3 major assignments due this weekend , so it will be a little while before I can really find a fix, especially since simplex2() works fine.

As for "knocking down" the variables, I'm not sure I understand what you did at the moment. It seems the min value may be the same, but it doesn't seem to have the same solution when applying simplex regularly.

(11-11-2023 01:43 AM)Albert Chan Wrote:  > simplex_le([[-1,20], [7,25], [-25,115]/11], −∞)
[−18.5714285714, [25/7, 165/7, 0], ...]

> simplex2([[3,2,1,1,0,10],[2,5,3,0,1,15],[-2,-3,-4,0,0,0],[0,0,0,1,1,0]],{4,5},5,2,0)
[-130/7,[15/7,0,25/7,0,0],...]
This problem should have one solution at x1=15/7,x2=0,x3=25/7.

I just want to mention one last thing for now. Artificial variables are not always required to solve a problem, but they give a starting point for the simplex method. If you randomly choose a set of starting basic variables, there's a chance it will not result in a feasible solution (does not satisfy some constraint). Thus we use slack and artificial variables as a starting point.

[ftneek]

(11-11-2023 04:54 AM)ftneek Wrote:  Xcas > lpsolve(-3x1+2x2+x3-x4+x5+87,[4x1-x2+x4-x5+x6=6,-7x1+8x2+x3-x7=7,x1+x2+4x4-4x5=12],assume=lp_nonnegative)

> simplex2([[4,-1,0,1,-1,1,0,1,0,0,6],[-7,8,1,0,0,0,-1,0,1,0,7],[1,1,0,4,-4,0,0,0,0,1,12],[-3,2,1,-1,1,0,0,0,0,0,-87],[0,0,0,0,0,0,0,1,1,1,0]],{8,9,10},10,3,0)

Also if you're wondering where the -87 comes from, it is because standard form says the constant goes on the right.

-3x1+2x2+x3-x4+x5+87=z
thus
-3x1+2x2+x3-x4+x5=z-87
and the z column is omitted.

[Albert Chan]

(11-11-2023 04:54 AM)ftneek Wrote:  Yes, the offset actually goes in the last position of the objective function row. So where your +/- argument was for min/max. I'm glad you noticed and made a fix, I forgot to mention it.

Bonus: I now have room to implement "=" constraints.
With |dir| > number of constraints, say ±∞, it assumed all constraints are "≤".
Otherwise, top |dir| constraints assumed "=" constraints. (not implemented yet)

The naive way is just to add "≥" constraints, but could be very inefficient.
(still worth considering though, since we don't expect too many "=" constraints)

Here is another way, but I don't know how to setup artificial variables.

Quote:> simplex([[3,2,1,1,0,10],[2,5,3,0,1,15],[-2,-3,-4,0,0,0],[0,0,0,1,1,0]])

There is no reason to assume constraints have positive coefficients.
Instead of (3x+2y+z ≤ 10), we do (-3x-2y-z ≤ -10), it does not work.

> simplex([[-3,-2,-1,1,0,-10],[2,5,3,0,1,15],[-2,-3,-4,0,0,0],[0,0,0,1,1,0]])

["No Solution: empty feasible region (w ≠ 0)",[], ...]

Third way is to remove all "=" constraints, and "simplex" sub-matrix.

(11-11-2023 01:43 AM)Albert Chan Wrote:  > m := [[3,2,1,10], [2,5,3,15], [-2,-3,-4,0]]
> m[1] /= m[1][1]
> m := pivot(m,1,1)
> m[2] /= m[2][2]
> m := pivot(m,2,2)

\(\left(\begin{array}{cccc}
1 & 0 & \frac{-1}{11} & \frac{20}{11} \\
0 & 1 & \frac{7}{11} & \frac{25}{11} \\
0 & 0 & \frac{-25}{11} & \frac{115}{11}
\end{array}\right) \)

> m2 := transpose(col(m,3 .. 0))
> simplex_le(transpose(m2, -∞)

\([-18.5714285714,[0,0,0],\left(\begin{array}{cccc}
0 & 1.0 & 0.142857142857 & 2.14285714286 \\
1.0 & 0.0 & 1.57142857143 & 3.57142857143 \\
0 & 0 & 3.57142857143 & 18.5714285714
\end{array}\right) ]\)

There is simplex() bug (or, HP Prime bug?) returning all zeroes for variables.
To bypass the bug, I scale away denominator, solved for min(cost) * 11

> simplex_le(m2*11, -∞)

\(\displaystyle[
\frac{-1430}{7},[\frac{25}{7},\frac{165}{7},0],\left(\begin{array}{cccc}
0 & 1 & \frac{1}{7} & \frac{165}{7} \\
1 & 0 & \frac{1}{7} & \frac{25}{7} \\
0 & 0 & \frac{25}{7} & \frac{1430}{7}
\end{array}\right)] \)

min(cost) occurs at z = 25/7. Back substitution for other variables.

> rref( m[0]:=[0,0,1,25/7] )

\(\left(\begin{array}{cccc}
1 & 0 & 0 & \frac{15}{7} \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & \frac{25}{7}
\end{array}\right) \)

[Albert Chan]

(11-11-2023 12:39 PM)Albert Chan Wrote:  > m2 := transpose(col(m,3 .. 0))
> simplex_le(transpose(m2, -∞)

\([-18.5714285714,[0,0,0],\left(\begin{array}{cccc}
0 & 1.0 & 0.142857142857 & 2.14285714286 \\
1.0 & 0.0 & 1.57142857143 & 3.57142857143 \\
0 & 0 & 3.57142857143 & 18.5714285714
\end{array}\right) ]\)

There is simplex() bug (or, HP Prime bug?) returning all zeroes for variables.

I mistakenly use DELCOL instead of delcols, CONCAT instead of extend ...
Still, even with float, getting all 0's for variables are weird.

Now, we get the right output:

\(\displaystyle [
\frac{-130}{7},[\frac{25}{7},\frac{15}{7},0],\left(\begin{array}{cccc}
0 & 1 & \frac{1}{7} & \frac{15}{7} \\
1 & 0 & \frac{11}{7} & \frac{25}{7} \\
0 & 0 & \frac{25}{7} & \frac{130}{7}
\end{array}\right)]\)

Latest update:

Code:

simplex_le(a, dir) :=
BEGIN
 LOCAL b := dim(a);
 a := transpose(extend(
    [col(a,1 .. b(2)-1)],
    [col(identity(b(1)),1 .. b(1)-1)],
    [col(a,b(2))]
 ));
 IF dir>0 THEN a[0] := -a[0] END /* maximize */
 a := simplex(a);
 IF dir>0 THEN a[1] := -a[1] END /* undo flip */
 return a;
END;

[ftneek]

(11-11-2023 12:39 PM)Albert Chan Wrote:  There is simplex() bug (or, HP Prime bug?) returning all zeroes for variables.
To bypass the bug, I scale away denominator, solved for min(cost) * 11

If there is a floating point number in the matrix, you should run exact() on it first before calling simplex(). You can try sol() on the exact() matrix to see if that’s where the issue is, v is just the number of variables/solutions to read. If you tried exact inputs and still get 0’s, my suggestion is to use the debug() command and try to see what commands result in a decimal appearing.

[ftneek]

(11-11-2023 12:39 PM)Albert Chan Wrote:  There is no reason to assume constraints have positive coefficients.
Instead of (3x+2y+z ≤ 10), we do (-3x-2y-z ≤ -10), it does not work.

> simplex([[-3,-2,-1,1,0,-10],[2,5,3,0,1,15],[-2,-3,-4,0,0,0],[0,0,0,1,1,0]])

["No Solution: empty feasible region (w ≠ 0)",[], ...]

If you multiply the constraint by -1, you should flip the inequality. Thus you should use (-3x-2y-z >= -10)

[Albert Chan]

(11-11-2023 04:35 PM)ftneek Wrote:  

(11-11-2023 12:39 PM)Albert Chan Wrote:  There is no reason to assume constraints have positive coefficients.
Instead of (3x+2y+z ≤ 10), we do (-3x-2y-z ≤ -10), it does not work.

> simplex([[-3,-2,-1,1,0,-10],[2,5,3,0,1,15],[-2,-3,-4,0,0,0],[0,0,0,1,1,0]])

["No Solution: empty feasible region (w ≠ 0)",[], ...]

If you multiply the constraint by -1, you should flip the inequality. Thus you should use (-3x-2y-z >= -10)

I was trying to simulate (3x+2y+z ≥ 10), and how to use artificial variables to turn it to "="

Reminder: true constraints are (3x+2y+z=10), (2x+5y+3z=15)

[ftneek]

To convert "=" to standard form, we should add an artificial variable.
Ex: (3x+2y+z = 10) becomes (3x+2y+z +r1 = 10)

To convert ">=" to standard form, we should subtract a slack (to make ">=" become "=") and add an artificial variable (because we now have "=", and the slack is negative).
Ex:(3x+2y+z ≥ 10) becomes (3x+2y+z -s1+r1≥ 10)
Alternatively, multiply by -1 changes ">=" to "<=" constraint: (-3x-2y-z <= -10)

To convert "<=" to standard form, we add a slack variable (to force "="). Since the slack variable is positive, we don't add an artificial variable.
Ex: (-3x-2y-z <= -10) becomes (-3x-2y-z+s1=-10)

If we added artificial variables, we should add a row to the bottom. [0 ... 0 1 ... 1 0] where there are 1's in the position of the artificial columns. By convention we usually order the matrix so that variables are listed first, then slack variables, then artificial variables.

Ex: constraints are
(5x+y-z = 5) becomes (5x+y-z +0s1+r1+0r2= 5) (0s1, 0r2 shown for clarity below)
(3x+2y+z ≥ 10) becomes (3x+2y+z -s1+0r1+r2= 10)
Then the matrix looks like
[[5,1,-1,0,1,0,5],[3,2,1,-1,0,1,10],[c row...],[0,0,0,0,1,1,0]]
We have 2 constraints so we need 2 initial basic variable, in this case we use artificial variables {5,6} (for variables/columns x5,x6).
We could either call simplex2(matrix,{5,6},6,2,0) or simplex2(matrix,{5,6},3,2,0). The only difference should be in number of variable solutions read in the end, we have 3 true variables so we should put at least 3.
The 2 because this "example" has 2 artificial variables, and the 0 because this is an "initial tableau", so we should not ignore any artificial columns.

[Albert Chan]

(11-11-2023 12:39 PM)Albert Chan Wrote:  Third way is to remove all "=" constraints, and "simplex" sub-matrix.

(11-11-2023 01:43 AM)Albert Chan Wrote:  > m := [[3,2,1,10], [2,5,3,15], [-2,-3,-4,0]]
> m[1] /= m[1][1]
> m := pivot(m,1,1)
> m[2] /= m[2][2]
> m := pivot(m,2,2)

\(\left(\begin{array}{cccc}
1 & 0 & \frac{-1}{11} & \frac{20}{11} \\
0 & 1 & \frac{7}{11} & \frac{25}{11} \\
0 & 0 & \frac{-25}{11} & \frac{115}{11}
\end{array}\right) \)

We can solve it all, directly!
Think of (x, y) as the slack variables, both "=" constraints turned "≤"

> simplex_le(m, -∞)

\(\displaystyle
[\frac{-130}{7},[\frac{15}{7},0,\frac{25}{7},\frac{15}{7},0],\left(\begin{array}{cccccc}
1 & \frac{1}{7} & 0 & 1 & \frac{1}{7} & \frac{15}{7} \\
0 & \frac{11}{7} & 1 & 0 & \frac{11}{7} & \frac{25}{7} \\
0 & \frac{25}{7} & 0 & 0 & \frac{25}{7} & \frac{130}{7}
\end{array}\right) ]\)

[ftneek]

(11-11-2023 06:59 PM)Albert Chan Wrote:  

(11-11-2023 12:39 PM)Albert Chan Wrote:  Third way is to remove all "=" constraints, and "simplex" sub-matrix.

We can solve it all, directly!
Think of (x, y) as the slack variables, both "=" constraints turned "≤"

> simplex_le(m, -∞)

\(\displaystyle
[\frac{-130}{7},[\frac{15}{7},0,\frac{25}{7},\frac{15}{7},0],... ]\)

Nice. I'm curious if there are any computation savings from this, or is it essentially pre computing some things before calling simplex? It seems fine for the Primal system. But if you consider the Dual system, the 15/7 may or may not lead you to an incorrect solution.

(11-11-2023 04:54 AM)ftneek Wrote:  > simplex2([[3,2,1,1,0,10],[2,5,3,0,1,15],[-2,-3,-4,0,0,0],[0,0,0,1,1,0]],{4,5},5,2,0)
[-130/7,[15/7,0,25/7,0,0],...]
This problem should have one solution at x1=15/7,x2=0,x3=25/7.

For anyone interested, I made a thread in the software forum to discuss the simplex program. Thanks to Albert, there is already a small patch that allows for numeric input.

[Albert Chan]

(11-09-2023 12:09 PM)parisse Wrote:  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

I just learn we can solve dual problem for answer.
Cost is also a constraint, here for the minimum.

2x + 4y >= 22
3x + 2y >= 20
4x + 5y >= 40
6x + 5y >= cost

Transpose above, we have dual problem.

2 z1 + 3 z2 + 4 z3 <= 6
4 z1 + 2 z2 + 5 z3 <= 5
22 z1 + 20 z2 + 40 z3 <= cost

> simplex_reduce([[2,3,4],[4,2,5]], [6,5], [22,20,40])

\(\frac{320}{7},[0,\frac{10}{7},\frac{3}{7},0,0],\left(\begin{array}{cccccc}
\frac{-6}{7} & 1 & 0 & \frac{5}{7} & \frac{-4}{7} & \frac{10}{7} \\
\frac{8}{7} & 0 & 1 & \frac{-2}{7} & \frac{3}{7} & \frac{3}{7} \\
\frac{46}{7} & 0 & 0 & \frac{20}{7} & \frac{40}{7} & \frac{320}{7}
\end{array}\right) \)

Last row for original problem solution: x = 20/7, y = 40/7, min(cost) = 320/7

But, it would be better if simplex_reduce accept negative b's.

[parisse]

Thanks for the pointer.
Please correct me if I'm wrong:
If b is not positive and c is negative, then I should rewrite Ax<=b as -Ax>=B where B=-b is all positive, rewrite max(c*x) to min(C*x) with C=-c, then solve the dual problem with transpose(-A), B'=C=-c, C'=B=-b ?
In other words, translate the call simplex_reduce(A,b,c) to simplex_reduce(tran(-A),-c,-b)?
Probably with a warning in the terminal about solving the dual problem...

[Albert Chan]

(11-15-2023 07:23 AM)parisse Wrote:  ... translate the call simplex_reduce(A,b,c) to simplex_reduce(tran(-A),-c,-b)?

Quote:2x + 4y >= 22
3x + 2y >= 20
4x + 5y >= 40
6x + 5y >= cost

Not quite. Cost is considered as constraint too. Transpose whole matrix for dual setup.

\(\left(\begin{array}{ccc}
2 & 4 & 22 \\
3 & 2 & 20 \\
4 & 5 & 40 \\
6 & 5 & cost
\end{array}\right)
\quad → \quad
\left(\begin{array}{cccc}
2 & 3 & 4 & 6 \\
4 & 2 & 5 & 5 \\
22 & 20 & 40 & cost
\end{array}\right)
\)

Dual setup, '≥' turned '≤', i.e it search for max(cost), same as simplex_reduce()

Note that original cost coefficients goes to column b
If some of them are negative, we would still get problem of column b < 0

[parisse]

Then it's probably better not to modify anything. Maybe the documentation should point to the existence of dual problem.

[Gil]

How long does it take to solve
This simplex system?

[ 0 0 1 0 'F' 0 ]
[ 0 0 0 1 'F' 0 ]
[ 4 4 3 7 'L' 90 ]
[ 6 3 5 4 'L' 120 ]
[ 5 2 3 3 'L' 60 ]
[ 0 1 0 0 'L' 15 ]
[ 1 0 0 0 'L' 10 ]
[ 6 5 1 2 'L' 100 ]
[ 75 65 80 75 0 'Max' ]]

L=less or equal
F=Free variable, here x3 and x4
G=Greater or equal

And for that one?
[[ 4 4 3 7 'L' 90 ]
[ 6 3 5 4 'L' 120 ]
[ 5 2 3 3 'L' 60 ]
[ 0 1 0 0 'L' 15 ]
[ 1 0 0 0 'L' 10 ]
[ 6 5 1 2 'L' 100 ]
[ 75 65 80 75 0 'Max' ]]

And the following special system

{
[[ 1 -1 1 -1 0 'E' 2 ]
[ 2 -2 -1 0 1 'E' 0 ]
[ 1 -1 3 0 0 0 'Min' ]]
{ Var†5¦Steps†10 Time†4¦s :

{ "[[ 1 -1 1 -1 0 'E' 2 ]
[ 2 -2 -1 0 1 'E' 0 ]
[ 1 -1 3 0 0 0 'Min' ]]" "{ Var\\|>5\\166Steps\\|>10 Time\\|>4\\166s :


Z-Min
: [ '14/3' 4.66666666667 ] :x1: [ '2/3' .666666666667 ] :x2: 0 :x3: [ '4/3' 1.33333333333 ] :x4: 0 :x5: 0 :
Or not? SIMPLEX 
Sol 
i: [ '2/3' 0 '4/3' 0 0 ] :
+\\Gm

[
\\>=0
]
*
d
, 
d
: [ 1 1 0 0 0 ] :
\\->Mixed 
Solution
:
 
0\\<=
\\Gl
\\<=1

\\Gl
(
Sol 1
) 
+
 (
1-\\Gl
) *
(not? SIMPLEX 
Sol 2
): Plus :
\\Gm

[
\\>=0
]
*
d
, 
d
: [ 1 1 0 0 0 ] }"

And
{
[[ 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 ] } }" }

[ftneek]

(11-16-2023 08:49 PM)Gil Wrote:  How long does it take to solve
This simplex system?
.
.
.
And the following special system

{
[[ 1 -1 1 -1 0 'E' 2 ]
[ 2 -2 -1 0 1 'E' 0 ]
[ 1 -1 3 0 0 0 'Min' ]]
{ Var†5¦Steps†10 Time†4¦s :

{ "[[ 1 -1 1 -1 0 'E' 2 ]
[ 2 -2 -1 0 1 'E' 0 ]
[ 1 -1 3 0 0 0 'Min' ]]" "{ Var\\|>5\\166Steps\\|>10 Time\\|>4\\166s :

I tested your 3rd system using my simplex program, on my virtual calculator it was solved instantly. Problem 3 has solution 14/3 at x1=2/3,x2=0,x3=4/3,x4=0,x5=0. If you want to time how long it takes for you, you can try the commands yourself. You can time it by wrapping the command with time(). Also some of your text seems to have corrupted, there are floating boxes everywhere.

problem 3:
> simplex2([[1,-1,1,-1,0,1,0,2],[2,-2,-1,0,1,0,1,0],[1,-1,3,0,0,0,0,0],[0,0,0,0,0,1,1,0]],{6,7},7,2,0)

[Gil]

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.