simplex_le now have maximize default (d=∞), matched simplex_reduce.
simplex_le(a) ≡ simplex_le(a, ∞)
Code:
simplex_le(a) :=
BEGIN
LOCAL b, p, v,(p:=[]),(d:=inf);
IF dim(dim(a))<2 THEN a,d:=a END
IF abs(d)<len(a) THEN a,p:=remove_eq_c(a,d) END
b := dim(a);
a := transpose(extend(a, identity(b[1])));
a[0] := a[b[2]];
a := transpose(delrows(a, b[2] .. b[2]+len(p)));
v := sum(b)-2 - len(p); /* variables */
p := extend(p,range(b[2],v+1)); /* pivots */
IF d>0 THEN a[0] := -a[0] END /* maximize */
a := simplex2(a,p,v,0,0);
IF d>0 THEN a[1] := -a[1] END /* undo flip */
return a;
END;
remove_eq_c(a, n) :=
BEGIN
LOCAL j,k, c := len(a[1]);
LOCAL p := makelist(n:=abs(n)); /* max pivots */
FOR j FROM n DOWNTO 1 DO
p[j] := k := pivot_index(suppress(a[j],c));
IF k==0 and a[j][c] THEN error(a) END
a := k ? pivot((a[j]:=a[j]/a[j][k]),j,k) : delrows(a,j);
END
return a, remove(0,p);
END;
pivot_index(a) :=
BEGIN
LOCAL b := contains((a:=abs(a)),1);
IF b THEN RETURN b END
IF (b:=max(a)) THEN b := contains(a,b) END
RETURN b;
END;
(11-14-2023 11:48 AM)Albert Chan Wrote: 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
> simplex_le([[2,3,4,6],[4,2,5,5],[22,20,40,0]])
\([\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) ]\)