Skip to content
Snippets Groups Projects
Select Git revision
  • master default protected
1 result
Compare History
Brandon Rodriguez's avatar
Update __init__ importing to be more library friendly
Brandon Rodriguez authored 
Uses same logic as "graph library" __init__ files
52640b4b
Name Last commit Last update
documents
resources
tests
.editorconfig
.gitignore
__init__.py
main.py
readme.md
run_unit_tests.sh
readme.md

Python - Linear Programming Simplex Algorithm

Description

Python implementation of a "Simplex" for Linear Programming problems. Algorithm is acquired from pages (869, 871, 887) in "Algorithms Third Edition by Thomas H Cormen" book.

Changes to Algorithm

The Pivot algorithm (pg 869) seemed to have an error on line 8. Essentially, it was saying to loop through "all columns that are a Basic Variable", but then on the next line, using this values as a "row_index". This was causing of "index out of range" errors.

So instead, I changed that to properly loop through all rows in the matrix.

Python Environment

This project is tested using Python3.7. Written using PyCharm. Tested with Pycharm 2017.2.3 and 2019.2 versions.

Creating a New Env

Most installations of Python3 will allow you to simply run python3.7 -m venv ./.venv to create a new Python3.7 environment called ".venv" at the current directory folder.

Once created, load this environment with source .venv/bin/activate on Linux or . .venv/Scripts/activate on Windows.

Third Party Libraries

  • If any additional libraries have been used, then they will be found in requrements.txt at the project root.
  • To install, load your local Python Environment and run pip install -r requirements.txt when at the project root.

Running the Program

Run the program via python ./main.py while at the project root.

Expected Output

Main has two possible outputs.

First output is reading in and solving a file, determined by user input. Should work with both relative paths from the project root, or absolute paths. On both read in and solve, all three output formats should be displayed for the matrix.

Second output is has 2 examples of reading in from JSON files, then 1 example of reading in and solving. For each read in, the problem should be displayed to console in "Tableau" (aka matrix) form. After the one is solved, then it should print the solution in all three formats.

Example JSON Files

Some example JSON files are located at <project_root>/resources/json_files.

Running Tests

To run all unittests for this project, open a terminal and run the run_unit_tests.sh bash script.

For more information about testing, see the documents/testing.md file.

References

See the documents/c_references.md and documents/python_references files.