Simplex Algorithm
11-14-2023, 09:23 AM
Post: #17
 Albert Chan Senior Member Posts: 2,637 Joined: Jul 2018
RE: Simplex Algorithm
(11-14-2023 06:24 AM)ftneek Wrote:
(11-14-2023 02:25 AM)Albert Chan Wrote:  You can do this with simplex_le too, but not much typing is saved.
Constraints already are "=", artificial variables need to start with -1, thus result negated.

> simplex_le([[1,2,0,1,-1,0,0,20],[2,1,1,0,0,-1,0,10],[-1,4,-2,3,0,0,-1,40],[1,4,3,2,0,0,0,0]],-3)

[35,[5,0,0,15,0,0,0],[[0,3/2,-1/2,1,-1/4,0,-1/4,15],[0,0,0,0,-3/2,1,1/2,0],[1,1/2,1/2,0,-3/4,0,1/4,5],[0,1/2,7/2,0,5/4,0,1/4,-35]]]

Inside numbers not quite match, because simplex_le use pivots order {5,6,1}. But that shouldn't matter.

Does that input still save computing time? That is closer, potentially promising. Order of pivots does not matter. But the coefficients of the objective function/z row should match simplex2, including in sign, else the dual solution will not be correct. To me it seems those columns need to be multiplied by -1, except for the entries where the b coefficient is 0...

Constraint (a*x ≤ b) is setup as matrix [a|b], with a 1 column b
To turn "≤" into "=", we do a*x + (slack var) = b + (artificial var)

But we can't setup this way, thus a*x + (slack var) + (artficial var) = b

(artificial var) = [5/4,0,1/4]
(artificial var) = [5/4,0,1/4]      // answer do match simplex2

Purpose of wrapper function is not to save computing time, but to save typing time.
But yes, to match result of standard form, you might as well just use simplex2.

Again, simplex_le() is just a wrapper for simplex2().
I have nothing against the standard form, except for typing it all in.

simplex_le can do dual problem, with identity matrix squeeze inside.
Video 1st dual probelm (time = 6 .. 17 minutes)

> simplex_le([[2,4,40],[1,1,12],[5,1,40],[20,30,0]],+∞)

$$[320,[4,8,0,0,12],\left(\begin{array}{cccccc} 0 & 1 & \frac{1}{2} & -1 & 0 & 8 \\ 1 & 0 & \frac{-1}{2} & 2 & 0 & 4 \\ 0 & 0 & 2 & -9 & 1 & 12 \\ 0 & 0 & 5 & 10 & 0 & 320 \end{array}\right) ]$$

Note that P column is always [0,0 .. 0,1] thus not needed to carry along.
 « 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)