Post Reply 
Simplex Algorithm
11-11-2023, 11:51 PM (This post was last modified: 11-12-2023 11:17 PM by Albert Chan.)
Post: #2
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]]]
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: 1 Guest(s)