Simplex Algorithm
11-11-2023, 11:51 PM (This post was last modified: 11-12-2023 11:17 PM by Albert Chan.)
Post: #2
 Albert Chan Senior Member Posts: 2,637 Joined: Jul 2018
RE: Simplex Algorithm
Hi, ftneek

simplex_le code had a bug, using some HOME functions instead of CAS.
This sometimes turn exact numbers to approximate.

Also, I added "=" constraints, by adding "≥" on top of "≤" constraints.
(≤ constraint) + (≥ constraint) = (= constraint)

It is not efficient, but it is a 1 liner, worthy of adding in, for convenience.

Here is my latest update
Code:
simplex_le(a, dir) := BEGIN  LOCAL b := abs(dir);  IF b<len(a) THEN a := extend(-a[1 .. b],a) END  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;

Example: minimize Z = -2x - 3y - 4z
Constraints (3x+2y+z=10) AND (2x+5y+3z=15), x,y,z ≥ 0,

> m := [[3,2,1,10], [2,5,3,15], [-2,-3,-4,0]]
> simplex_le(m, -2)            /* '-' = minimize cost, top 2 are "=" constraints */

[-130/7, [15/7, 0, 25/7, 0, 0, 0, 0], ...]

We can't do ±0. For "≤" constraints only, dir = ±∞, (+ = max, - = min)

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

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

[9/2, [0,0,3/2,0,5/2], [[3/2,1,1,1/2,0,3/2],[-1/2,0,0,-1/2,1,5/2],[7/2,1,0,3/2,0,9/2]]]

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

[9/2, [0,0,3/2,0,5/2], [[3/2,1,1,1/2,0,3/2],[-1/2,0,0,-1/2,1,5/2],[7/2,1,0,3/2,0,9/2]]]
 « Next Oldest | Next Newest »

 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: 1 Guest(s)