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

[Albert Chan]

(11-09-2023 08:02 PM)ftneek Wrote:  Example 2: Multiply each ">=" constraint row by -1 to convert to "<=".
We now have 3 "<=" constraints, so we only need add a slack variable to each row.

> a:=[[-2,-4,1,0,0,-22],[-3,-2,0,1,0,-20],[-4,-5,0,0,1,-40],[6,5,0,0,0,0]]

> simplex(a)

Reading about simplex algorithm, I now get why simplex code minimized object function.
Matrix had a hidden column!

\(\left(\begin{array}{ccccccc}
-2 & -4 & 1 & 0 & 0 & 0 & -22 \\
-3 & -2 & 0 & 1 & 0 & 0 & -20 \\
-4 & -5 & 0 & 0 & 1 & 0 & -40 \\
6 & 5 & 0 & 0 & 0 & 1 & 0
\end{array}\right) \)

Since slack variables are non-negative, objective function is minimized.

I like machine to take care of slack variables. Less typing, less errors.
I added simplex_le(a) wrapper that add slack stuff.

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.

Code:

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

> simplex_le([-[2,4,22],-[3,2,20],-[4,5,40],[6,5,-1]])

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

simplex_reduce example from HP Prime Help screen (it always maximize)

> simplex_reduce([[3,2,2],[1,1,1]],[3,4],[1,2,3])

\(\frac{9}{2},[0,0,\frac{3}{2},0,\frac{5}{2}],\left(\begin{array}{cccccc}
\frac{3}{2} & 1 & 1 & \frac{1}{2} & 0 & \frac{3}{2} \\
\frac{-1}{2} & 0 & 0 & \frac{-1}{2} & 1 & \frac{5}{2} \\
\frac{7}{2} & 1 & 0 & \frac{3}{2} & 0 & \frac{9}{2}
\end{array}\right) \)

> simplex_le([[3,2,2,3],[1,1,1,4],[1,2,3,+1]])

\(\frac{9}{2},[0,0,\frac{3}{2},0,\frac{5}{2}],\left(\begin{array}{cccccc}
\frac{3}{2} & 1 & 1 & \frac{1}{2} & 0 & \frac{3}{2} \\
\frac{-1}{2} & 0 & 0 & \frac{-1}{2} & 1 & \frac{5}{2} \\
\frac{7}{2} & 1 & 0 & \frac{3}{2} & 0 & \frac{9}{2}
\end{array}\right) \)

We could make arguments match, but I found [a|b] input more convenient.
We can flip constraint inequality, from from ≤ to ≥, with a negate.