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. 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) 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]] > 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. |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)