Post Reply 
Simplex Algorithm
11-12-2023, 12:38 AM
Post: #4
RE: Simplex Algorithm
(11-11-2023 11:51 PM)Albert Chan Wrote:  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.
...
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], ...]

Some benchmarks.
On my old laptop, running HP Prime emulator (2018 10 16)

> time(simplex_le(m, -2))      → time = 0.0195 s

(11-11-2023 04:54 AM)ftneek Wrote:  > simplex2([[3,2,1,1,0,10],[2,5,3,0,1,15],[-2,-3,-4,0,0,0],[0,0,0,1,1,0]],{4,5},5,2,0)
[-130/7,[15/7,0,25/7,0,0],...]

I have no idea how this is setup, but it run faster , time = 0.0105 s
Use simplex wrapper is easier, but cost a bit more, time = 0.0125 s

> simplex([[3,2,1,1,0,10],[2,5,3,0,1,15],[-2,-3,-4,0,0,0],[0,0,0,1,1,0]])

(11-11-2023 01:43 AM)Albert Chan Wrote:  > m := [[3,2,1,10], [2,5,3,15], [-2,-3,-4,0]]
> m[1] /= m[1][1]
> m := pivot(m,1,1)
> m[2] /= m[2][2]
> m := pivot(m,2,2)

\(\left(\begin{array}{cccc}
1 & 0 & \frac{-1}{11} & \frac{20}{11} \\
0 & 1 & \frac{7}{11} & \frac{25}{11} \\
0 & 0 & \frac{-25}{11} & \frac{115}{11}
\end{array}\right) \)

> simplex_le(m, -∞)      /* "=" constraints are gone! */

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

Fastest is remove excess variables, turning it into slack variables.

Note that we scale pivot as 1 before clearing other cells.
This does not affect other constraints, not even cost functions.
In other words, row operations are safe.

Time (including pivot operations) = 0.0075 s
Production code need pivots selection, but should not cost much.
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: 2 Guest(s)