simplex.py

# -*- coding: utf-8 -*-
"""simplex.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/1IYvLmZIRB2hwYxjNogDshBdXOsVriGuP
"""

import math
import numpy as np
from fractions import Fraction

def to_tableau(z, A, b):
    tableau = [eq + [x] for eq, x in zip(A, b)]
    z = z + [0]
    tableau += [z]
    return tableau

def print_table(tableau):
    n_var = len(tableau[0])
    var = [f"x{i + 1}" for i in range(n_var - 1)]
    for j in var:
        print(j, end='\t')
    print("c", end='\n\n')

    for k in tableau:
        for eq in k:
            print(Fraction(str(eq)).limit_denominator(100), end='\t')
        print('\n')

def is_optimal(tableau):
    z = tableau[-1]
    return not any(i > 0 for i in z[:-1])

def find_pivot_element(tableau):
    z = tableau[-1]
    ipc = next(i for i, x in enumerate(z[:-1]) if x > 0)
    ratio = []
    for eq in tableau[:-1]:
        el = eq[ipc]
        ratio.append(math.inf if el <= 0 else eq[-1] / el)
    ipr = ratio.index(min(ratio))
    return ipr, ipc

def pivot_step(tableau, pivot_position):
    new_tableau = [[] for i in tableau]
    ipr, ipc = pivot_position
    pivot_element = tableau[ipr][ipc]
    new_tableau[ipr] = [el / pivot_element for el in tableau[ipr]]
    for eq_i, eq in enumerate(tableau):
        if eq_i != ipr:
            new_tableau[eq_i] = [
                tableau[eq_i][i] - new_tableau[ipr][i] * tableau[eq_i][ipc]
                for i in range(len(new_tableau[ipr]))
            ]
    return new_tableau

def simplex(z, A, b):
    tableau = to_tableau(z, A, b)
    print("Initial Tableau\n")
    print_table(tableau)
    it = 1
    while not is_optimal(tableau):
        pivot_position = find_pivot_element(tableau)
        tableau = pivot_step(tableau, pivot_position)
        print(f"\nIteration: {it}\n")
        print_table(tableau)
        it += 1
    return tableau
def is_basic(column):
    return sum(column) == 1 and len([c for c in column if c == 0]) == len(column) - 1

def get_solution(tableau):
    columns = np.array(tableau).T
    solutions = []
    for column in columns[:-1]:
        solution = 0
        if is_basic(column):
            one_index = column.tolist().index(1)
            solution = columns[-1][one_index]
        solutions.append(solution)
    return solutions

def show_solutions(tableau):
    solutions = get_solution(tableau)
    var = [f"x{i + 1}" for i in range(len(tableau) - 1)]
    for s, v in zip(solutions, var):
        print(f"{v}: {Fraction(str(s)).limit_denominator(100)}")
    print(f"Value of z at optimality: {abs(Fraction(str(tableau[-1][-1])).limit_denominator(100))}")

def main():
    num_vars = int(input("Enter the number of variables: "))
    num_constraints = int(input("Enter the number of constraints: "))

    z = list(map(int, input("Enter the coefficients of the objective function: ").split()))

    A = []
    print("Enter the coefficients of the constraints:")
    for _ in range(num_constraints):
        constraint = list(map(int, input().split()))
        A.append(constraint)

    b = list(map(int, input("Enter the amounts of resources: ").split()))

    show_solutions(simplex(z, A, b))

if __name__ == "__main__":
    main()