Post Reply 
Simplex Algorithm
11-16-2023, 11:42 AM
Post: #21
RE: Simplex Algorithm
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) ]\)
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
Simplex Algorithm - ftneek - 11-11-2023, 11:21 PM
RE: Simplex Algorithm - Albert Chan - 11-11-2023, 11:51 PM
RE: Simplex Algorithm - Albert Chan - 11-12-2023, 12:38 AM
RE: Simplex Algorithm - Albert Chan - 11-12-2023, 05:11 PM
RE: Simplex Algorithm - ftneek - 11-12-2023, 05:40 PM
RE: Simplex Algorithm - Albert Chan - 11-13-2023, 02:48 PM
RE: Simplex Algorithm - ftneek - 11-12-2023, 12:00 AM
RE: Simplex Algorithm - ftneek - 11-12-2023, 01:44 AM
RE: Simplex Algorithm - Albert Chan - 11-12-2023, 11:04 PM
RE: Simplex Algorithm - ftneek - 11-13-2023, 01:51 AM
RE: Simplex Algorithm - Albert Chan - 11-12-2023, 08:46 PM
RE: Simplex Algorithm - ftneek - 11-12-2023, 10:09 PM
RE: Simplex Algorithm - ftneek - 11-13-2023, 05:34 PM
RE: Simplex Algorithm - Albert Chan - 11-13-2023, 10:46 PM
RE: Simplex Algorithm - Albert Chan - 11-14-2023, 02:25 AM
RE: Simplex Algorithm - ftneek - 11-14-2023, 06:24 AM
RE: Simplex Algorithm - Albert Chan - 11-14-2023, 09:23 AM
RE: Simplex Algorithm - ftneek - 11-14-2023, 10:39 AM
RE: Simplex Algorithm - Albert Chan - 11-15-2023, 04:36 PM
RE: Simplex Algorithm - ftneek - 11-15-2023, 05:58 PM
RE: Simplex Algorithm - Albert Chan - 11-16-2023 11:42 AM
RE: Simplex Algorithm - Albert Chan - 11-16-2023, 07:15 PM
RE: Simplex Algorithm - ftneek - 11-17-2023, 07:47 AM
RE: Simplex Algorithm - Albert Chan - 11-17-2023, 11:04 AM
RE: Simplex Algorithm - ftneek - 11-18-2023, 01:27 AM
RE: Simplex Algorithm - ftneek - 11-18-2023, 10:31 PM
RE: Simplex Algorithm - Albert Chan - 11-19-2023, 12:57 AM
RE: Simplex Algorithm - ftneek - 11-19-2023, 07:05 AM
RE: Simplex Algorithm - Albert Chan - 11-19-2023, 04:58 PM
RE: Simplex Algorithm - Albert Chan - 11-20-2023, 06:12 PM
RE: Simplex Algorithm - ftneek - 11-21-2023, 08:36 AM
RE: Simplex Algorithm - Albert Chan - 11-21-2023, 02:05 PM
RE: Simplex Algorithm - ftneek - 11-19-2023, 08:02 PM
RE: Simplex Algorithm - ftneek - 11-20-2023, 12:18 AM
RE: Simplex Algorithm - Albert Chan - 11-20-2023, 02:14 AM
RE: Simplex Algorithm - ftneek - 11-20-2023, 09:02 AM
RE: Simplex Algorithm - Albert Chan - 11-20-2023, 11:42 AM
RE: Simplex Algorithm - Albert Chan - 11-20-2023, 03:34 PM
RE: Simplex Algorithm - ftneek - 11-20-2023, 07:52 PM
RE: Simplex Algorithm - Albert Chan - 11-21-2023, 05:58 PM
RE: Simplex Algorithm - Albert Chan - 11-21-2023, 11:20 PM
RE: Simplex Algorithm - Albert Chan - 11-22-2023, 06:44 PM
RE: Simplex Algorithm - Albert Chan - 11-22-2023, 10:10 PM
RE: Simplex Algorithm - Albert Chan - 12-24-2023, 03:46 PM
RE: Simplex Algorithm - ftneek - 12-24-2023, 07:32 PM
RE: Simplex Algorithm - Albert Chan - 12-24-2023, 08:05 PM
RE: Simplex Algorithm - ftneek - 11-23-2023, 01:23 AM
RE: Simplex Algorithm - Albert Chan - 11-23-2023, 06:35 AM
RE: Simplex Algorithm - ftneek - 12-22-2023, 07:38 AM
RE: Simplex Algorithm - Albert Chan - 12-22-2023, 04:07 PM
RE: Simplex Algorithm - ftneek - 12-22-2023, 07:28 PM
RE: Simplex Algorithm - Albert Chan - 12-23-2023, 04:44 AM
RE: Simplex Algorithm - ftneek - 12-23-2023, 07:46 AM
RE: Simplex Algorithm - Albert Chan - 12-23-2023, 10:23 AM
RE: Simplex Algorithm - ftneek - 12-23-2023, 09:30 PM
RE: Simplex Algorithm - ftneek - 01-07-2024, 02:40 AM



User(s) browsing this thread: 4 Guest(s)