Simplex Algorithm

[Albert Chan]

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) ]\)