import numpy as np


class Simplex:
    def __init__(self, source):
        # Получение размеров матрицы source в переменные
        # m (количество строк) и n (количество столбцов).
        m, n = source.shape
        self.table = np.zeros((m, n + m - 1))
        # Будет содержать индексы базисных переменных.
        self.basis = []


        # Заполнение матрицы table значениями из матрицы source до столбца n.
        # Остальные элементы инициализируются нулями.
        for i in range(m):
            for j in range(self.table.shape[1]):
                if j < n:
                    self.table[i, j] = source[i, j]
                else:
                    self.table[i, j] = 0
            # Добавление единицы в ячейку подходящей строки и столбца для создания единичной матрицы.
            # Запись индекса этой переменной в список базисных переменных.
            if (n + i) < self.table.shape[1]:
                self.table[i, n + i] = 1
                self.basis.append(n + i)
        # Сохранение значений m и n в атрибуты объекта.
        self.m = m
        self.n = self.table.shape[1]

    # Метод calculate, который выполняет итерации симплекс-метода до достижения оптимального решения
    # или обнаружения отсутствия решения.
    def calculate(self, result):
        # Цикл, выполняющийся до тех пор, пока не будет достигнут критерий окончания
        # (проверяется методом is_it_end()).
        while not self.is_it_end():
            main_col = self.find_main_col()
            main_row = self.find_main_row(main_col)

            # Обновление списка базисных переменных.
            self.basis[main_row] = main_col

            # Инициализация новой матрицы нулями той же размерности, что и self.table.
            new_table = np.zeros((self.m, self.n))

            # Заполнение строки main_row новой матрицы значениями,
            # полученными делением соответствующих элементов из исходной матрицы.
            for j in range(self.n):
                new_table[main_row, j] = self.table[main_row, j] / self.table[main_row, main_col]

            # Заполнение остальных строк новой матрицы путем вычитания соответствующих элементов исходной матрицы.
            for i in range(self.m):
                if i == main_row:
                    continue

                for j in range(self.n):
                    new_table[i, j] = self.table[i, j] - self.table[i, main_col] * new_table[main_row, j]

            # Обновление исходной матрицы.
            self.table = new_table

        # Заполнение массива result значениями переменных в соответствии с текущим базисом.
        for i in range(len(result)):
            k = self.basis.index(i + 1) if i + 1 in self.basis else -1
            result[i] = self.table[k, 0] if k != -1 else 0
        # Возвращение итоговой матрицы после завершения симплекс-метода.
        return self.table

    # Метод проверяет, выполнено ли условие завершения симплекс-метода.
    def is_it_end(self):
        # sВозвращает True, если все элементы последней строки матрицы больше
        # или равны нулю (условие оптимальности).
        return np.all(self.table[self.m - 1, 1:] >= 0)

    # Метод нахождения ведущего столбца методом find_main_col().
    def find_main_col(self):
        main_col = 1

        for j in range(2, self.n):
            if self.table[self.m - 1, j] < self.table[self.m - 1, main_col]:
                main_col = j

        return main_col

    # Метод для нахождения ведущий строки. Возвращает индекс найденной ведущей строки.
    def find_main_row(self, main_col):
        # Переменная  для отслеживания индекса ведущей строки
        main_row = 0

        for i in range(self.m - 1):
            if self.table[i, main_col] > 0:
                main_row = i
                break

        # Поиск строки с минимальным отношением элемента в столбце 0 к элементу в заданном столбце
        # Отношение используется для выбора оптимальной строки для ведущей.
        for i in range(main_row + 1, self.m - 1):
            if self.table[i, main_col] > 0 and (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