import numpy as np
import math

class Simplex:
    def __init__(self, source):
        self.m, self.n = source.shape
        self.table = np.zeros((self.m, self.n + self.m - 1))
        self.basis = []

        for i in range(self.m):
            self.table[i, :self.n] = source[i, :]
            if (self.n + i) < self.table.shape[1]:
                self.table[i, self.n + i] = 1
                self.basis.append(self.n + i)

        self.n = self.table.shape[1]

    def calculate(self, result):
        while not self.is_optimal():
            main_col = self.find_main_col()
            main_row = self.find_main_row(main_col)
            self.basis[main_row] = main_col

            self.table[main_row, :] /= self.table[main_row, main_col]

            for i in range(self.m):
                if i == main_row:
                    continue
                self.table[i, :] -= self.table[i, main_col] * self.table[main_row, :]

        for i in range(len(result)):
            k = self.basis.index(i + 1) if i + 1 in self.basis else None
            result[i] = self.table[k, 0] if k is not None else 0

        return self.table

    def is_optimal(self):
        return all(self.table[self.m - 1, 1:] >= 0)

    def find_main_col(self):
        return np.argmin(self.table[self.m - 1, 1:]) + 1

    def find_main_row(self, main_col):
        positive_ratios = [i for i in range(self.m - 1) if self.table[i, main_col] > 0]
        main_row = positive_ratios[0] if positive_ratios else None

        for i in positive_ratios[1:]:
            if (self.table[i, 0] / self.table[i, main_col]) < (self.table[main_row, 0] / self.table[main_row, main_col]):
                main_row = i

        return main_row

if __name__ == "__main__":
    table = np.array([[45, 5, 3],
                      [-8, -1, 0],
                      [-10, 0, -1],
                      [0, -40, -36]])

    result = np.zeros(2)
    simplex_solver = Simplex(table)
    table_result = simplex_solver.calculate(result)

    if simplex_solver.is_optimal():
        np.set_printoptions(precision=2, suppress=True)
        print("Решенная симплекс-таблица:")
        print(table_result)

        print("\nРешение:")
        print(f"X[1] = {result[0]}")
        print(f"X[2] = {math.ceil(result[1])}")
        print(f"F(x1, x2) = {-table[-1][-2] * result[0] + -table[-1][-1] * math.ceil(result[1])}")
    else:
        print("Задача не имеет оптимального решения.")