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 comimengusf9619a568f7da5bc74eaf20169a24d98 for how to convert linear programs to simplex tableaus and the steps taken in the simplex algorithm resources https en wikipedia orgwikisimplexalgorithm https tinyurl comsimplex4beginners operate on simplex tableaus tableaunp array1 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 tableaunp array1 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 tableaunp array1 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 max iteration number to prevent cycling check if rhs is negative number of decision variables x1 x2 x3 2 if there are or constraints nonstandard 1 otherwise std number of slack variables added to make inequalities into equalities objectives for each stage in two stage simplex first minimise then maximise index of current pivot row and column does objective row only contain nonnegative values generate column titles for tableau of specific dimensions tableaunp array1 1 0 0 1 1 3 1 0 4 3 1 0 1 4 2 0 generatecoltitles x1 x2 s1 s2 rhs tableaunp array1 1 0 0 1 1 3 1 0 4 3 1 0 1 4 2 2 generatecoltitles x1 x2 rhs decision slack finds the pivot row and column tableaunp array2 1 0 0 0 3 1 1 0 6 1 2 0 1 7 2 0 findpivot 1 0 find entries of highest magnitude in objective rows choice is only valid if below 0 for maximise and above for minimise pivot row is chosen as having the lowest quotient when elements of the pivot column divide the righthand side slice excluding the objective rows rhs elements of pivot column within slice array filled with nans if element in pivot column is greater than zero return quotient or nan otherwise arg of minimum quotient excluding the nan values nstages is added to compensate for earlier exclusion of objective columns pivots on value on the intersection of pivot row and column tableaunp array2 3 0 0 0 1 3 1 0 4 3 1 0 1 4 2 2 pivot1 0 tolist doctest normalizewhitespace 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 avoid changes to original tableau entry becomes 1 variable in pivot column becomes basic ie the only nonzero entry exits first phase of the twostage method by deleting artificial rows and columns or completes the algorithm if exiting the standard case tableaunp 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 changestage tolist doctest normalizewhitespace 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 objective of original objective row remains slice containing ids for artificial columns delete the artificial variable columns delete the objective row of the first stage operate on tableau until objective function cannot be improved further standard linear program max x1 x2 st x1 3x2 4 3x1 x2 4 tableaunp array1 1 0 0 0 1 3 1 0 4 3 1 0 1 4 2 0 runsimplex 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 tableaunp 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 runsimplex doctest ellipsis p 5 4 x1 0 199 x3 1 6 optimal tableau input tableaunp array 0 0 0 25 0 25 2 0 1 0 375 0 125 1 1 0 0 125 0 375 1 2 0 runsimplex p 2 0 x1 1 0 x2 1 0 nonstandard constraints max 2x1 3x2 x3 st x1 x2 x3 40 2x1 x2 x3 10 x2 x3 10 tableaunp 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 runsimplex 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 tableaunp array 8 6 0 0 52 1 1 0 0 0 2 1 1 0 12 6 5 0 1 40 2 2 runsimplex 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 tableaunp 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 runsimplex doctest ellipsis p 132 0 x1 12 000 x2 5 999 stop simplex algorithm from cycling completion of each stage removes an objective if both stages are complete then no objectives are left find the values of each variable at optimal solution if there are no more negative values in objective row delete artificial variable columns and rows update attributes given the final tableau add the corresponding values of the basic decision variables to the outputdict tableaunp array 0 0 0 875 0 375 5 0 1 0 375 0 125 1 1 0 0 125 0 375 1 2 0 interprettableau p 5 0 x1 1 0 x2 1 0 p rhs of final tableau gives indices of nonzero entries in the ith column first entry in the nonzero indices if there is only one nonzero value in column which is one 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 max iteration number to prevent cycling check if rhs is negative number of decision variables x1 x2 x3 2 if there are or constraints nonstandard 1 otherwise std number of slack variables added to make inequalities into equalities objectives for each stage in two stage simplex first minimise then maximise index of current pivot row and column does objective row only contain non negative values 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 decision slack finds the pivot row and column tableau np array 2 1 0 0 0 3 1 1 0 6 1 2 0 1 7 2 0 find_pivot 1 0 find entries of highest magnitude in objective rows choice is only valid if below 0 for maximise and above for minimise pivot row is chosen as having the lowest quotient when elements of the pivot column divide the right hand side slice excluding the objective rows rhs elements of pivot column within slice array filled with nans if element in pivot column is greater than zero return quotient or nan otherwise arg of minimum quotient excluding the nan values n_stages is added to compensate for earlier exclusion of objective columns 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 doctest normalize_whitespace 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 avoid changes to original tableau entry becomes 1 variable in pivot column becomes basic ie the only non zero entry 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 doctest normalize_whitespace 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 objective of original objective row remains slice containing ids for artificial columns delete the artificial variable columns delete the objective row of the first stage operate on tableau until objective function cannot be improved further standard linear program max x1 x2 st x1 3x2 4 3x1 x2 4 tableau np array 1 1 0 0 0 1 3 1 0 4 3 1 0 1 4 2 0 run_simplex 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 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 doctest ellipsis p 5 4 x1 0 199 x3 1 6 optimal tableau input 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 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 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 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 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 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 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 doctest ellipsis p 132 0 x1 12 000 x2 5 999 stop simplex algorithm from cycling completion of each stage removes an objective if both stages are complete then no objectives are left find the values of each variable at optimal solution if there are no more negative values in objective row delete artificial variable columns and rows update attributes given the final tableau add the corresponding values of the basic decision variables to the output_dict 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 p 5 0 x1 1 0 x2 1 0 p rhs of final tableau gives indices of nonzero entries in the ith column first entry in the nonzero indices if there is only one nonzero value in column which is one
from typing import Any

import numpy as np


class Tableau:
    

    
    maxiter = 100

    def __init__(
        self, tableau: np.ndarray, n_vars: int, n_artificial_vars: int
    ) -> None:
        if tableau.dtype != "float64":
            raise TypeError("Tableau must have type float64")

        
        if not (tableau[:, -1] >= 0).all():
            raise ValueError("RHS must be > 0")

        if n_vars < 2 or n_artificial_vars < 0:
            raise ValueError(
                "number of (artificial) variables must be a natural number"
            )

        self.tableau = tableau
        self.n_rows, n_cols = tableau.shape

        
        self.n_vars, self.n_artificial_vars = n_vars, n_artificial_vars

        
        self.n_stages = (self.n_artificial_vars > 0) + 1

        
        self.n_slack = n_cols - self.n_vars - self.n_artificial_vars - 1

        
        self.objectives = ["max"]

        
        if self.n_artificial_vars:
            self.objectives.append("min")

        self.col_titles = self.generate_col_titles()

        
        self.row_idx = None
        self.col_idx = None

        
        self.stop_iter = False

    def generate_col_titles(self) -> list[str]:
        
        args = (self.n_vars, self.n_slack)

        
        string_starts = ["x", "s"]
        titles = []
        for i in range(2):
            for j in range(args[i]):
                titles.append(string_starts[i] + str(j + 1))
        titles.append("RHS")
        return titles

    def find_pivot(self) -> tuple[Any, Any]:
        
        objective = self.objectives[-1]

        
        sign = (objective == "min") - (objective == "max")
        col_idx = np.argmax(sign * self.tableau[0, :-1])

        
        if sign * self.tableau[0, col_idx] <= 0:
            self.stop_iter = True
            return 0, 0

        
        

        
        s = slice(self.n_stages, self.n_rows)

        
        dividend = self.tableau[s, -1]

        
        divisor = self.tableau[s, col_idx]

        
        nans = np.full(self.n_rows - self.n_stages, np.nan)

        
        
        quotients = np.divide(dividend, divisor, out=nans, where=divisor > 0)

        
        
        row_idx = np.nanargmin(quotients) + self.n_stages
        return row_idx, col_idx

    def pivot(self, row_idx: int, col_idx: int) -> np.ndarray:
        
        
        piv_row = self.tableau[row_idx].copy()

        piv_val = piv_row[col_idx]

        
        piv_row *= 1 / piv_val

        
        for idx, coeff in enumerate(self.tableau[:, col_idx]):
            self.tableau[idx] += -coeff * piv_row
        self.tableau[row_idx] = piv_row
        return self.tableau

    def change_stage(self) -> np.ndarray:
        
        
        self.objectives.pop()

        if not self.objectives:
            return self.tableau

        
        s = slice(-self.n_artificial_vars - 1, -1)

        
        self.tableau = np.delete(self.tableau, s, axis=1)

        
        self.tableau = np.delete(self.tableau, 0, axis=0)

        self.n_stages = 1
        self.n_rows -= 1
        self.n_artificial_vars = 0
        self.stop_iter = False
        return self.tableau

    def run_simplex(self) -> dict[Any, Any]:
        
        
        for _ in range(Tableau.maxiter):
            
            
            if not self.objectives:
                
                return self.interpret_tableau()

            row_idx, col_idx = self.find_pivot()

            
            if self.stop_iter:
                
                self.tableau = self.change_stage()
            else:
                self.tableau = self.pivot(row_idx, col_idx)
        return {}

    def interpret_tableau(self) -> dict[str, float]:
        
        
        output_dict = {"P": abs(self.tableau[0, -1])}

        for i in range(self.n_vars):
            
            nonzero = np.nonzero(self.tableau[:, i])
            n_nonzero = len(nonzero[0])

            
            nonzero_rowidx = nonzero[0][0]
            nonzero_val = self.tableau[nonzero_rowidx, i]

            
            if n_nonzero == 1 and nonzero_val == 1:
                rhs_val = self.tableau[nonzero_rowidx, -1]
                output_dict[self.col_titles[i]] = rhs_val
        return output_dict


if __name__ == "__main__":
    import doctest

    doctest.testmod()