Simplex Algorithm
11-21-2023, 08:36 AM (This post was last modified: 11-21-2023 08:38 AM by ftneek.)
Post: #38
 ftneek Member Posts: 83 Joined: Oct 2022
RE: Simplex Algorithm
(11-20-2023 06:12 PM)Albert Chan Wrote:
(11-19-2023 04:58 PM)Albert Chan Wrote:  I am not convinced that -1 slack variable will cause problem.

I am now convniced that it will not cause problem, even if scaled.
.
.
.
I am reverting back to the fast method, without (again) canonicalize all pivots.
And, no need to fill artrow, even in simplex_core(), it handles this internally

simplex(m, [art=0]) ≡ simplex_core(m, pivots, variables, art, 0)

I uploaded a new file with the infinite solution correction you mentioned. But I wasn't able to include this portion of code in simplex_core yet.

Code:
IF art THEN /* add artrow */  a:=append(a,artrow((c:=len(a[1])),art));  a[0]-=sum(a[POS(bv,J)],J,c-art,c-1); END;

I added a new test 4. It is an example of input that is currently allowed by simplex_core, but the command didn't work when I tried your version, because the -1's are not being pivoted on. This what I mean by limiting the number of ways you can input a system and arrive at the same solution.

Current simplex_core
> simplex_core([[2,4,-1,0,0,22],[3,2,0,-1,0,20],[4,5,0,0,-1,40],[6,5,0,0,0,0]],{3,4,5},5,0,0)
[320/7,[20/7,40/7,46/7,0,0],[[0,0,1,6/7,-8/7,46/7],[1,0,0,-5/7,2/7,20/7],[0,1,0,4/7,-3/7,40/7],[0,0,0,10/7,3/7,-320/7]],{3,1,2}]

> simplex_core([[2,4,-1,0,0,22],[3,2,0,-1,0,20],[4,5,0,0,-1,40],[6,5,0,0,0,0]],{3,4,5},5,0,0)
[0,[0,0,0,0,0],[[2,4,-1,0,0,22],[3,2,0,-1,0,20],[4,5,0,0,-1,40],[6,5,0,0,0,0]],{3,4,5}]

Also, appending an artificial row should not happen inside simplex_core, at least the current way you propose. Reminder, simplex_core is able to continue iteration on a tableau from any stage. For sensitivity analysis, we may consider what happens to the solution if we add a constraint. But just adding a row/bv to the original matrix and applying simplex algorithm again can be expensive for large systems. Instead, we insert the row into the final tableau and continue computation from there. This an example of where your current implementation is wrong, if you are going to set up the artificial row, it should be offset by ign.

- neek
 « 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)