---

import numpy as np
from scipy.optimize import linprog

def solve_game(A):
    """
    Решение матричной игры для игрока A через ЛП.
    Возвращает:
        p_opt : оптимальная смешанная стратегия A (list)
        V     : цена игры
        success: True, если решение найдено
    """
    A = np.array(A, dtype=float)
    m, n = A.shape  # m стратегий A, n стратегий B

    # 1. Проверка седловой точки
    row_min = A.min(axis=1)          # минимум по строкам
    col_max = A.max(axis=0)          # максимум по столбцам
    alpha = row_min.max()            # нижняя цена игры
    beta = col_max.min()             # верхняя цена игры
    print(f"Нижняя цена игры: {alpha}")
    print(f"Верхняя цена игры: {beta}")

    if np.isclose(alpha, beta):
        # Есть чистая стратегия
        i = np.argmax(row_min)       # индекс строки с максиминным выигрышем
        p_opt = np.zeros(m)
        p_opt[i] = 1.0
        V = alpha
        print("Найдена седловая точка (чистая стратегия).")
        return p_opt.tolist(), V, True

    # 2. Смешанное расширение – сводим к ЛП
    # Гарантируем положительную цену игры V'>0, добавив ко всем элементам сдвиг shift
    shift = max(0, -A.min()) + 1.0
    A_pos = A + shift
    print(f"Сдвиг для положительности V: {shift}")

    # Целевая функция: минимизировать sum(xi), xi>=0
    c = np.ones(m)

    # Ограничения: A_pos.T @ x >= 1  (в linprog записывается как -A_pos.T @ x <= -1)
    A_ub = -A_pos.T
    b_ub = -np.ones(n)

    # Границы: x >= 0
    bounds = [(0, None)] * m

    # Решаем ЛП
    res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')
    if not res.success:
        print("Ошибка решения ЛП:", res.message)
        return None, None, False

    x_opt = res.x
    V_shifted = 1.0 / x_opt.sum()   # 1 / (сумма xi) = V' (цена игры сдвинутой матрицы)
    p_opt = x_opt * V_shifted       # вероятности p_i = x_i * V'
    V = V_shifted - shift           # истинная цена игры

    return p_opt.tolist(), V, True


# =====================================================
# Пример: платёжная матрица из задачи (компания A)
# Восстановлена по таблице как 3x4 (строки: модели A1,A2,A3; столбцы: стратегии B1..B4)
A = [
    [4, 4, 9, 7, 7, 5],   # A1
    [3, 8, 4, 7, 6, 7],   # A2
    [1, 3, 1, 4, 7, 6],   # A3
    [1, 3, 5, 8, 5, 7]    # A4
]
p, V, ok = solve_game(A)

if ok:
    print("\nРезультат:")
    print("Оптимальная смешанная стратегия компании A (доли выпуска моделей):")
    for i, prob in enumerate(p, start=1):
        print(f"  Модель A{i}: {prob:.4f} ({prob*100:.1f}%)")
    print(f"Цена игры (гарантированная прибыль компании A): {V:.4f}")
    # Проверка: ожидаемый выигрыш для каждой стратегии B
    expected = np.array(p) @ A
    print("Ожидаемые выигрыши против каждой стратегии B:", expected.round(4))
else:
    print("Не удалось найти решение.")