linear_programming.simplex

Python implementation of the simplex algorithm for solving linear programs in tabular form with - >=, <=, and = constraints and - each variable x1, x2, …>= 0.

See https://gist.github.com/imengus/f9619a568f7da5bc74eaf20169a24d98 for how to convert linear programs to simplex tableaus, and the steps taken in the simplex algorithm.

Resources: https://en.wikipedia.org/wiki/Simplex_algorithm https://tinyurl.com/simplex4beginners

Classes

Tableau

Operate on simplex tableaus

Module Contents

class linear_programming.simplex.Tableau(tableau: numpy.ndarray, n_vars: int, n_artificial_vars: int)

Operate on simplex tableaus

>>> Tableau(np.array([[-1,-1,0,0,1],[1,3,1,0,4],[3,1,0,1,4]]), 2, 2)
Traceback (most recent call last):
...
TypeError: Tableau must have type float64

>>> Tableau(np.array([[-1,-1,0,0,-1],[1,3,1,0,4],[3,1,0,1,4.]]), 2, 2)
Traceback (most recent call last):
...
ValueError: RHS must be > 0

>>> Tableau(np.array([[-1,-1,0,0,1],[1,3,1,0,4],[3,1,0,1,4.]]), -2, 2)
Traceback (most recent call last):
...
ValueError: number of (artificial) variables must be a natural number

change_stage() → numpy.ndarray

Exits first phase of the two-stage method by deleting artificial rows and columns, or completes the algorithm if exiting the standard case.

>>> Tableau(np.array([
... [3, 3, -1, -1, 0, 0, 4],
... [2, 1, 0, 0, 0, 0, 0.],
... [1, 2, -1, 0, 1, 0, 2],
... [2, 1, 0, -1, 0, 1, 2]
... ]), 2, 2).change_stage().tolist()
... 
[[2.0, 1.0, 0.0, 0.0, 0.0],
[1.0, 2.0, -1.0, 0.0, 2.0],
[2.0, 1.0, 0.0, -1.0, 2.0]]

find_pivot() → tuple[Any, Any]

Finds the pivot row and column. >>> tuple(int(x) for x in Tableau(np.array([[-2,1,0,0,0], [3,1,1,0,6], … [1,2,0,1,7.]]), 2, 0).find_pivot()) (1, 0)

generate_col_titles() → list[str]

Generate column titles for tableau of specific dimensions

>>> Tableau(np.array([[-1,-1,0,0,1],[1,3,1,0,4],[3,1,0,1,4.]]),
... 2, 0).generate_col_titles()
['x1', 'x2', 's1', 's2', 'RHS']

>>> Tableau(np.array([[-1,-1,0,0,1],[1,3,1,0,4],[3,1,0,1,4.]]),
... 2, 2).generate_col_titles()
['x1', 'x2', 'RHS']

interpret_tableau() → dict[str, float]

Given the final tableau, add the corresponding values of the basic decision variables to the output_dict >>> {key: float(value) for key, value in Tableau(np.array([ … [0,0,0.875,0.375,5], … [0,1,0.375,-0.125,1], … [1,0,-0.125,0.375,1] … ]),2, 0).interpret_tableau().items()} {‘P’: 5.0, ‘x1’: 1.0, ‘x2’: 1.0}

pivot(row_idx: int, col_idx: int) → numpy.ndarray

Pivots on value on the intersection of pivot row and column.

>>> Tableau(np.array([[-2,-3,0,0,0],[1,3,1,0,4],[3,1,0,1,4.]]),
... 2, 2).pivot(1, 0).tolist()
... 
[[0.0, 3.0, 2.0, 0.0, 8.0],
[1.0, 3.0, 1.0, 0.0, 4.0],
[0.0, -8.0, -3.0, 1.0, -8.0]]

run_simplex() → dict[Any, Any]

Operate on tableau until objective function cannot be improved further.

# Standard linear program: Max: x1 + x2 ST: x1 + 3x2 <= 4

3x1 + x2 <= 4

>>> {key: float(value) for key, value in Tableau(np.array([[-1,-1,0,0,0],
... [1,3,1,0,4],[3,1,0,1,4.]]), 2, 0).run_simplex().items()}
{'P': 2.0, 'x1': 1.0, 'x2': 1.0}

# Standard linear program with 3 variables: Max: 3x1 + x2 + 3x3 ST: 2x1 + x2 + x3 ≤ 2

x1 + 2x2 + 3x3 ≤ 5

2x1 + 2x2 + x3 ≤ 6

>>> {key: float(value) for key, value in Tableau(np.array([
... [-3,-1,-3,0,0,0,0],
... [2,1,1,1,0,0,2],
... [1,2,3,0,1,0,5],
... [2,2,1,0,0,1,6.]
... ]),3,0).run_simplex().items()} 
{'P': 5.4, 'x1': 0.199..., 'x3': 1.6}

# Optimal tableau input: >>> {key: float(value) for key, value in Tableau(np.array([ … [0, 0, 0.25, 0.25, 2], … [0, 1, 0.375, -0.125, 1], … [1, 0, -0.125, 0.375, 1] … ]), 2, 0).run_simplex().items()} {‘P’: 2.0, ‘x1’: 1.0, ‘x2’: 1.0}

# Non-standard: >= constraints Max: 2x1 + 3x2 + x3 ST: x1 + x2 + x3 <= 40

2x1 + x2 - x3 >= 10

• x2 + x3 >= 10

>>> {key: float(value) for key, value in Tableau(np.array([
... [2, 0, 0, 0, -1, -1, 0, 0, 20],
... [-2, -3, -1, 0, 0, 0, 0, 0, 0],
... [1, 1, 1, 1, 0, 0, 0, 0, 40],
... [2, 1, -1, 0, -1, 0, 1, 0, 10],
... [0, -1, 1, 0, 0, -1, 0, 1, 10.]
... ]), 3, 2).run_simplex().items()}
{'P': 70.0, 'x1': 10.0, 'x2': 10.0, 'x3': 20.0}

# Non standard: minimisation and equalities Min: x1 + x2 ST: 2x1 + x2 = 12

6x1 + 5x2 = 40

>>> {key: float(value) for key, value in Tableau(np.array([
... [8, 6, 0, 0, 52],
... [1, 1, 0, 0, 0],
... [2, 1, 1, 0, 12],
... [6, 5, 0, 1, 40.],
... ]), 2, 2).run_simplex().items()}
{'P': 7.0, 'x1': 5.0, 'x2': 2.0}

# Pivot on slack variables Max: 8x1 + 6x2 ST: x1 + 3x2 <= 33

4x1 + 2x2 <= 48 2x1 + 4x2 <= 48

x1 + x2 >= 10

x1 >= 2

>>> {key: float(value) for key, value in Tableau(np.array([
... [2, 1, 0, 0, 0, -1, -1, 0, 0, 12.0],
... [-8, -6, 0, 0, 0, 0, 0, 0, 0, 0.0],
... [1, 3, 1, 0, 0, 0, 0, 0, 0, 33.0],
... [4, 2, 0, 1, 0, 0, 0, 0, 0, 60.0],
... [2, 4, 0, 0, 1, 0, 0, 0, 0, 48.0],
... [1, 1, 0, 0, 0, -1, 0, 1, 0, 10.0],
... [1, 0, 0, 0, 0, 0, -1, 0, 1, 2.0]
... ]), 2, 2).run_simplex().items()} 
{'P': 132.0, 'x1': 12.000... 'x2': 5.999...}

col_idx = None

col_titles

maxiter = 100

n_slack

n_stages

objectives = ['max']

row_idx = None

stop_iter = False

tableau