import numpy as np

def simplex_method(c, A, b):
    m, n = A.shape
    c = np.concatenate([c, np.zeros(m)])  # Дополнение коэффициентов целевой функции нулями
    A = np.column_stack([A, np.eye(m)])   # Дополнение матрицы A единичной матрицей
    basis = np.arange(n, n + m)           # Индексы базисных переменных

    while True:
        # Шаг 1: Проверка на оптимальность

        # Рассчитываем приведенные затраты (reduced_costs), вычитая из коэффициентов целевой функции (c)
        # линейную комбинацию базисных переменных и соответствующих им строк матрицы A.
        # Приведенные затраты - оценки изменения целевой функции при изменении значений переменных.
        reduced_costs = c - np.dot(c[basis], A)

        # Если все приведенные затраты неотрицательны (все переменные в базисе удовлетворяют условиям оптимальности),
        # то достигнуто оптимальное решение, и цикл прерывается.
        if all(reduced_costs >= 0):
            break

        # Шаг 2: Выбор входящей переменной
        # определяем индекс переменной, которую мы добавим в базис (войдет в решение) на следующей итерации. 
        # выбираем переменную с наименьшим уменьшенным коэффициентом в функции цели.
        entering_var = np.argmin(reduced_costs)

        # Шаг 3: Проверка на неограниченность
        # Проверяем, если все элементы столбца матрицы A, соответствующего входящей переменной,
        # меньше или равны нулю. Если это условие выполняется, то проблема неограничена.
        if all(A[:, entering_var] <= 0):
            raise Exception("Проблема неограничена")

        # Шаг 4: Выбор выходящей переменной
        # Рассчитываем отношения значений правых частей к соответствующим коэффициентам входящей переменной в матрице A.
        # Если коэффициент входящей переменной положителен, оставляем отношение, иначе присваиваем бесконечность.
        ratios = np.divide(b, A[:, entering_var], out=np.full_like(b, np.inf, dtype=float), where=A[:, entering_var] > 0)

        # Находим индекс минимального отношения, который определяет выходящую переменную.
        leaving_var = np.argmin(ratios)

        # Шаг 5: Обновление базиса
        # Обновляем базис, заменяя выходящую переменную на входящую переменную.
        basis[leaving_var] = entering_var


        # Шаг 6: Обновление симплекс-таблицы
        pivot = A[leaving_var, entering_var]   # Выбор опорного элемента (пересечение строки и столбца)
        A[leaving_var, :] /= pivot             # Деление строки с опорным элементом на опорный элемент
        b[leaving_var] /= pivot                # Деление правой части на опорный элемент
        for i in range(m):
            if i != leaving_var:
                factor = A[i, entering_var]              # Выбор элемента в столбце входящей переменной
                A[i, :] -= factor * A[leaving_var, :]    # Обновление строки матрицы
                b[i] -= factor * b[leaving_var]          # Обновление правой части

        c -= reduced_costs[entering_var] * A[leaving_var, :]  # Обновление коэффициентов целевой функции

    # Извлечение решения из симплекс-таблицы
    solution = np.zeros(n)
    for i in range(m):
        if basis[i] < n:
            solution[basis[i]] = b[i]  # Извлечение значений базисных переменных из симплекс-таблицы


    return solution

# Пример использования:
c = np.array([-3, -2])                   # Коэффициенты целевой функции для минимизации
A = np.array([[1, 2], [2, 1], [1, -1]])  # Коэффициенты ограничений-неравенств
b = np.array([4, 7, 1])                  # Значения правых частей ограничений

result = simplex_method(c, A, b)
print("Оптимальное решение:", result)