Solving linear programming problems using simplex method

simplex.py

from fractions import Fraction

def to_frac(item):
    if isinstance(item, (int, float)) and not isinstance(item, bool):
        return Fraction(item)
    elif isinstance(item, tuple):
        (num, denom) = item
        return Fraction(num, denom)
    else:
        raise TypeError("Invalid type for fraction")

# Basic variables (left, column)
basic = ['x4', 'x5', 'x6', 'z']
# Nonbasic variables (top, row)
nonbasic = ['x1', 'x2', 'x3']

coeff = [
    [2, 3, 1],
    [4, 1, 2],
    [3, 4, 2],
    [-5,-4,-3]
]
coeff = list(map(lambda row: list(map(to_frac, row)), coeff))

rhs = [5, 11, 8, 0]
rhs = list(map(to_frac, rhs))

while True:
    objective_row = coeff[-1]
    pivot = None
    for pivot_col_value in sorted(objective_row):
        if pivot_col_value >= 0: # Only choose negative values
            break

        pivot_col_index = objective_row.index(pivot_col_value)
        pivot_row_index = None

        min_ratio = 99999.0

        for i, coeff_row in enumerate(coeff[:-1]):
            coeff_row_value = coeff_row[pivot_col_index]
            if coeff_row_value <= 0: # Only choose positive values
                continue
            ratio = rhs[i] / coeff_row_value
            if ratio < min_ratio:
                min_ratio = ratio
                pivot_row_index = i
        
        if pivot_row_index is not None:
            pivot = (pivot_row_index, pivot_col_index)
            break

    (pivot_row, pivot_col) = pivot
    pivot_value = coeff[pivot_row][pivot_col]

    print("Pivot: ({}, {})".format(pivot_row + 1, pivot_col + 1))

    # Interchange variables
    (basic[pivot_row], nonbasic[pivot_col]) = (nonbasic[pivot_col], basic[pivot_row])

    # Update other items, ignore pivot row and column
    for i, coeff_row in enumerate(coeff):
        if i == pivot_row:
            continue
        for j, value in enumerate(coeff_row):
            if j == pivot_col:
                continue
            coeff[i][j] = coeff[i][j] - (coeff[i][pivot_col] * coeff[pivot_row][j] / pivot_value)
    for i, value in enumerate(rhs):
        if i == pivot_row:
            continue
        rhs[i] = rhs[i] - (rhs[pivot_row] * coeff[i][pivot_col] / pivot_value)

    # Update pivot
    coeff[pivot_row][pivot_col] = 1 / pivot_value

    # Update pivot row
    for i, value in enumerate(coeff[pivot_row]):
        if i != pivot_col:
            coeff[pivot_row][i] = coeff[pivot_row][i] / pivot_value
    rhs[pivot_row] = rhs[pivot_row] / pivot_value

    # Update pivot column
    for i, coeff_row in enumerate(coeff):
        if i != pivot_row:
            coeff[i][pivot_col] = -(coeff[i][pivot_col] / pivot_value)

    # Print out
    print("  ", end="")
    print(" ".join(nonbasic))
    for i, row in enumerate(coeff):
        print(basic[i], end = " ")
        for j, value in enumerate(row):
            if value.denominator == 1:
                print(value.numerator, end = " ")
            else:
                print("{}/{}".format(value.numerator, value.denominator), end=" ")
        print(rhs[i])

    if min(coeff[-1]) > 0:
        print("Solution found!")
        break