Simplex Algorithm
11-11-2023, 11:21 PM (This post was last modified: 01-07-2024 02:41 AM by ftneek.)
Post: #1
 ftneek Member Posts: 83 Joined: Oct 2022
Simplex Algorithm
Attached is an implementation of the simplex algorithm as developed in
An Introduction to Linear Programming and Game Theory 3rd Edition, Paul R. Thie and Gerard E. Keough (ISBN: 978-0470232866).

Thanks to Albert Chan for his contributions. I have also included their simplex_le() method.

I originally posted it in this thread, but there's been a few changes since then.

2023/11/17: some speed improvements. simplex2 was renamed to simplex_core(), shown examples will still work if you just change the name.
2023/11/18: added simplex_int() for integer programming problems. simplex_core() returns a list of basic variables as 4th item when there is a solution. Updated and added some integer tests. See post 26 for an example.
2023/11/19: speed improvements, new simplex() wrapper. See post 27 for example inputs.
2023/11/19: fixed exact-> floating point bug for integer problems, more tests
2023/11/21: fixed bug in infinite solution code, new test
2023/12/21:
• new files for simplex, tests, and Game Theory
• improved simplex() command can handle maximization problems, integer restrictions, binary restrictions, or unrestricted variables. No need to manually input slack/artificial variables or negate the objective function row.
• adds solveGame() to solve 2-person zero-sum games
• minor bug fixes, changes to documentation, returns x as a column
• simplex_core() and simplex_int() accept linear programs in canonical form; simplex_core2() and simplex_int2() accept programs in standard form (simplex2 was renamed to simplex_core2)
2023/12/22: new files for simplex and tests, bug fix
2023/12/23:
• new files for simplex and tests
• simplex_core returns ∅ for infeasible model with no solution/empty feasible region
• simplex_core and simplex_int accept an additional parameter
• incorporates changes to simplex_le
2024/01/06:
• new simplex, tests, and hashin files
• switches to Bland's pivoting rule when a repeated basis is detected to prevent cycling
• infeasible models return "∅" instead of ∅

Attached File(s)