---

import numpy as np

def hungarian_correct(cost_matrix):
    n = cost_matrix.shape[0]
    C = cost_matrix.astype(float).copy()

    for i in range(n):
        min_row = np.min(C[i, :])
        C[i, :] -= min_row

    for j in range(n):
        min_col = np.min(C[:, j])
        C[:, j] -= min_col

    def max_zero_matching(matrix):
        row_cover = np.zeros(n, dtype=bool)
        col_cover = np.zeros(n, dtype=bool)
        assign = np.full(n, -1)

        for i in range(n):
            for j in range(n):
                if matrix[i, j] == 0 and not col_cover[j]:
                    assign[i] = j
                    col_cover[j] = True
                    break
        return assign

    while True:

        assign = max_zero_matching(C)

        row_mark = np.zeros(n, dtype=bool)
        col_mark = np.zeros(n, dtype=bool)

        for i in range(n):
            if assign[i] == -1:
                row_mark[i] = True

        changed = True
        while changed:
            changed = False

            for i in range(n):
                if row_mark[i]:
                    for j in range(n):
                        if C[i, j] == 0 and not col_mark[j]:
                            col_mark[j] = True
                            changed = True
            for i in range(n):
                if not row_mark[i] and assign[i] != -1 and col_mark[assign[i]]:
                    row_mark[i] = True
                    changed = True

        covered_rows = ~row_mark
        covered_cols = col_mark
        num_lines = np.sum(covered_rows) + np.sum(covered_cols)

        if num_lines == n:
            break

        unc_rows = np.where(~covered_rows)[0]
        unc_cols = np.where(~covered_cols)[0]
        min_val = np.min(C[np.ix_(unc_rows, unc_cols)])

        for i in range(n):
            for j in range(n):
                if ~covered_rows[i] and ~covered_cols[j]:
                    C[i, j] -= min_val
                elif covered_rows[i] and covered_cols[j]:
                    C[i, j] += min_val


    def find_perfect_matching(matrix):
        used_col = np.zeros(n, dtype=bool)
        assignment = np.full(n, -1)

        def dfs(row):
            if row == n:
                return True
            for col in range(n):
                if matrix[row, col] == 0 and not used_col[col]:
                    used_col[col] = True
                    if dfs(row + 1):
                        assignment[row] = col
                        return True
                    used_col[col] = False
            return False

        if dfs(0):
            return assignment
        else:
            for i in range(n):
                for j in range(n):
                    if matrix[i, j] == 0 and not used_col[j]:
                        assignment[i] = j
                        used_col[j] = True
                        break
            return assignment

    final_assign = find_perfect_matching(C)

    total = cost_matrix[np.arange(n), final_assign].sum()
    X = np.zeros_like(cost_matrix, dtype=int)
    X[np.arange(n), final_assign] = 1

    return final_assign, total, X

cost = np.array([
    [1, 3, 7, 8, 3, 1],
    [8, 1, 1, 7, 5, 4],
    [5, 1, 2, 1, 1, 9],
    [9, 4, 1, 3, 2, 8],
    [2, 5, 4, 3, 9, 5],
    [7, 2, 10, 1, 5, 1]
])

assign, f_val, X = hungarian_correct(cost)

print("\nМатрица назначений X:")
print(X)

print(f"\nf(x) = {f_val}")



def show_table(plan, sup, dem, title="Таблица", rrows=None, rcols=None):
    if rrows is None:
        rrows = len(sup)
    if rcols is None:
        rcols = len(dem)

    print(f"\n{title}")
    print("┌───────" + "┬──────────" * len(dem) + "┬─────────┐")
    print("│       ", end="")
    for j in range(len(dem)):
        print(f"│   B{j+1:<2}    ", end="")
    print("│ Запасы  │")
    print("├───────" + "┼──────────" * len(dem) + "┼─────────┤")

    for i in range(len(sup)):
        print(f"│  A{i+1:<2}  ", end="")
        for j in range(len(dem)):
            if plan[i][j] > 0:
                print(f"│  {plan[i][j]:<6}  ", end="")
            else:
                print(f"│     ·    ", end="")
        print(f"│  {sup[i]:<6} │")
        if i < len(sup) - 1:
            print("├───────" + "┼──────────" * len(dem) + "┼─────────┤")

    print("├───────" + "┼──────────" * len(dem) + "┼─────────┤")
    print("│ Спрос ", end="")
    for j in range(len(dem)):
        print(f"│  {dem[j]:<6}  ", end="")
    print("│         │")
    print("└───────" + "┴──────────" * len(dem) + "┴─────────┘")


def real_cost(plan, cst, rrows, rcols):
    total = 0
    for i in range(rrows):
        for j in range(rcols):
            total += plan[i][j] * cst[i][j]
    return total


def balance(sup, dem, cst):
    total_sup = sum(sup)
    total_dem = sum(dem)

    print(f"Сумма запасов: {total_sup}")
    print(f"Сумма спроса: {total_dem}")

    if total_sup == total_dem:
        return sup, dem, cst
    elif total_sup < total_dem:
        fake = total_dem - total_sup
        sup.append(fake)
        cst.append([0] * len(dem))
        print(f"Добавлен фиктивный поставщик с запасом {fake}")
        return sup, dem, cst
    else:
        fake = total_sup - total_dem
        dem.append(fake)
        for row in cst:
            row.append(9)
        print(f"Добавлен фиктивный потребитель со спросом {fake} (стоимость 9)")
        return sup, dem, cst


def northwest(sup, dem, cst):
    m, n = len(sup), len(dem)
    s, d = sup[:], dem[:]
    plan = [[0] * n for _ in range(m)]
    base = []

    i = j = 0
    while i < m and j < n:
        amount = min(s[i], d[j])
        plan[i][j] = amount
        if amount > 0:
            base.append((i, j))
        s[i] -= amount
        d[j] -= amount
        if s[i] == 0:
            i += 1
        if d[j] == 0:
            j += 1

    return plan, base


def mincost(sup, dem, cst):
    m, n = len(sup), len(dem)
    s, d = sup[:], dem[:]
    plan = [[0] * n for _ in range(m)]
    base = []

    cells = [(cst[i][j], i, j) for i in range(m) for j in range(n)]
    cells.sort()

    for c, i, j in cells:
        if s[i] > 0 and d[j] > 0:
            amount = min(s[i], d[j])
            if amount > 0:
                plan[i][j] = amount
                base.append((i, j))
                s[i] -= amount
                d[j] -= amount

    return plan, base


def potentials(plan, cst, base, m, n):
    u = [None] * m
    v = [None] * n
    u[0] = 0

    changed = True
    while changed:
        changed = False
        for i, j in base:
            if u[i] is not None and v[j] is None:
                v[j] = cst[i][j] - u[i]
                changed = True
            elif u[i] is None and v[j] is not None:
                u[i] = cst[i][j] - v[j]
                changed = True
    return u, v


def main():
    real_sup = [240, 100, 240, 100, 240]
    real_dem = [90, 180, 350, 185, 80]
    real_cst = [
        [7, 6, 4, 3, 9],
        [3, 8, 5, 4, 7],
        [2, 3, 7, 2, 3],
        [4, 5, 2, 3, 5],
        [5, 7, 3, 9, 2]
    ]


    sup, dem, cst = balance(
        real_sup[:], real_dem[:],
        [row[:] for row in real_cst]
    )

    rrows = len(real_sup)
    rcols = len(real_dem)

    plan_nw, base_nw = northwest(sup[:], dem[:], cst)
    cost_nw = real_cost(plan_nw, cst, rrows, rcols)

    plan_mc, base_mc = mincost(sup[:], dem[:], cst)
    cost_mc = real_cost(plan_mc, cst, rrows, rcols)
    print(f"\nСтоимость опорного плана (северо-западный угол): {cost_nw}")
    print(f"Стоимость опорного плана (минимальная стоимость): {cost_mc}")

    if cost_nw <= cost_mc:
        best_plan, best_base = plan_nw, base_nw
    else:
        best_plan, best_base = plan_mc, base_mc

    m, n = len(sup), len(dem)
    u, v = potentials(best_plan, cst, best_base, m, n)

    print("\nПотенциалы:")
    print("u =", [f"{ui:.2f}" if ui is not None else "None" for ui in u])
    print("v =", [f"{vj:.2f}" if vj is not None else "None" for vj in v])

    print("\nОценки свободных клеток:")
    for i in range(m):
        for j in range(n):
            if (i, j) in best_base:
                continue
            if u[i] is not None and v[j] is not None:
                delta = cst[i][j] - u[i] - v[j]
                if delta < -1e-10:
                    print(f"Δ({i+1},{j+1}) = {delta:6.2f} *")
                else:
                    print(f"Δ({i+1},{j+1}) = {delta:6.2f}")

    show_table(best_plan, sup, dem, "ЛУЧШИЙ ОПОРНЫЙ ПЛАН", rrows, rcols)
    print(best_plan)

if __name__ == "__main__":




import numpy as np

def simplex_general(c, A, b, signs, sense='min', M=1e5):
    """
    Универсальный симплекс-метод с искусственным базисом.
    c     : коэффициенты целевой функции
    A     : матрица ограничений
    b     : правые части (любого знака)
    signs : знаки ограничений ('<=', '>=', '=')
    sense : 'min' или 'max'
    M     : большой коэффициент штрафа
    """
    n_orig = len(c)
    c = np.array(c, dtype=float)

    # 1. Приведение правых частей к неотрицательным
    m = len(signs)
    A_mod = []
    b_mod = []
    signs_mod = []
    for i in range(m):
        if b[i] < 0:
            A_mod.append([-a for a in A[i]])
            b_mod.append(-b[i])
            # меняем знак неравенства
            if signs[i] == '<=':
                signs_mod.append('>=')
            elif signs[i] == '>=':
                signs_mod.append('<=')
            else:  # '='
                signs_mod.append('=')
        else:
            A_mod.append(A[i][:])
            b_mod.append(b[i])
            signs_mod.append(signs[i])

    A_mod = np.array(A_mod, dtype=float)
    b_mod = np.array(b_mod, dtype=float)

    # 2. Подсчёт дополнительных переменных
    n_le = sum(1 for s in signs_mod if s == '<=')
    n_ge = sum(1 for s in signs_mod if s == '>=')
    n_eq = sum(1 for s in signs_mod if s == '=')

    total_vars = n_orig + n_le + 2 * n_ge + n_eq
    A_ext = np.zeros((m, total_vars), dtype=float)
    b_vec = b_mod.copy()

    basis = []
    art_vars = []

    slack_idx = n_orig
    surplus_idx = n_orig + n_le
    art_ge_idx = n_orig + n_le + n_ge
    art_eq_idx = n_orig + n_le + n_ge + n_ge

    row = 0
    for i, sign in enumerate(signs_mod):
        A_ext[row, :n_orig] = A_mod[i]
        if sign == '<=':
            A_ext[row, slack_idx] = 1.0
            basis.append(slack_idx)
            slack_idx += 1
            row += 1
        elif sign == '>=':
            A_ext[row, surplus_idx] = -1.0
            A_ext[row, art_ge_idx] = 1.0
            basis.append(art_ge_idx)
            art_vars.append(art_ge_idx)
            surplus_idx += 1
            art_ge_idx += 1
            row += 1
        elif sign == '=':
            A_ext[row, art_eq_idx] = 1.0
            basis.append(art_eq_idx)
            art_vars.append(art_eq_idx)
            art_eq_idx += 1
            row += 1

    # 3. Целевая функция и штрафы
    c_ext = np.zeros(total_vars, dtype=float)
    c_ext[:n_orig] = c
    # Для искусственных переменных: +M при min, -M при max
    for a in art_vars:
        c_ext[a] = M if sense == 'min' else -M

    basis = np.array(basis, dtype=int)
    Cb = c_ext[basis]
    A0 = b_vec.copy()
    eps = 1e-10

    # 4. Симплекс-итерации
    while True:
        z = Cb @ A_ext
        deltas = c_ext - z

        if sense == 'max':
            # проверка оптимальности: все Δj <= 0
            if np.all(deltas <= eps):
                break
            # ввод: максимальная положительная Δj
            ent_col = np.argmax(deltas)
            if deltas[ent_col] <= eps:
                break
        else:  # минимизация
            # проверка оптимальности: все Δj >= -eps (т.е. неотрицательные)
            if np.all(deltas >= -eps):
                break
            # ввод: минимальная отрицательная Δj (наибольшая по модулю)
            ent_col = np.argmin(deltas)
            if deltas[ent_col] >= -eps:
                break

        col = A_ext[:, ent_col]
        ratios = np.full(m, np.inf)
        for i in range(m):
            if col[i] > eps:
                ratios[i] = A0[i] / col[i]

        row = np.argmin(ratios)
        if ratios[row] == np.inf:
            raise ValueError("Целевая функция не ограничена.")

        # Обновление базиса
        basis[row] = ent_col
        Cb[row] = c_ext[ent_col]
        pivot = A_ext[row, ent_col]
        A0[row] /= pivot
        A_ext[row, :] /= pivot

        for i in range(m):
            if i != row:
                factor = A_ext[i, ent_col]
                if abs(factor) > eps:
                    A0[i] -= factor * A0[row]
                    A_ext[i, :] -= factor * A_ext[row, :]

    # 5. Извлечение решения
    x_opt = np.zeros(n_orig, dtype=float)
    for i, var_id in enumerate(basis):
        if var_id < n_orig:
            x_opt[var_id] = A0[i]

    f_opt = Cb @ A0
    return x_opt, f_opt


# ================= ВАША ЗАДАЧА (исходные данные) =================
if __name__ == "__main__":
    c = [175, 107]
    A = [
        [-30, 9],
        [-30, -45],
        [-60, -36]
    ]
    b = [-1887, -4425, -4692]
    signs = ['>=', '>=', '<=']

    x_opt, f_opt = simplex_general(c, A, b, signs, sense='max')
    print("Оптимальное решение:")
    for i, val in enumerate(x_opt):
        print(f"  x{i+1} = {val:.6f}")
    print(f"Минимальное значение функции: {f_opt:.6f}")