Симплекс-метод

Симплекс-метод гениально прост: иди по рёбрам многогранника от угла к углу, всегда в сторону роста цели, пока расти некуда.

Симплекс-метод — алгоритм решения LP, переходящий между смежными вершинами многогранника по улучшающим рёбрам до достижения оптимальной вершины.

Идея за минуту

Раз оптимум в вершине, а вершин слишком много для перебора, симплекс действует как умный альпинист: стартует в какой-то вершине и идёт по ребру к соседней вершине, если та даёт больше цели. Повторяет, пока из текущей вершины нет улучшающего ребра — это и есть оптимум. На практике симплекс обходит лишь несколько вершин из астрономического их числа.

Стандартная форма и slack-переменные

Неравенства $Ax\le b$ превращают в равенства, добавляя дополнительные (slack) переменные $s\ge0$: ограничение $4x_1+2x_2\le 40$ становится $4x_1+2x_2+s_1=40$. Slack показывает неиспользованный ресурс. После этого задача — система линейных уравнений, и вершины соответствуют выбору, какие переменные «базисные» (ненулевые), а какие нули.

Симплекс-таблица: правила хода

Выбор входящей переменной (pivot column): та, что сильнее всего увеличивает цель (самый «выгодный» отрицательный коэффициент в строке цели для задачи на максимум).
Выбор выходящей переменной (pivot row): правило минимального отношения $b_i/a_{ij}$ — определяет, какое ограничение «упрётся» первым.
Pivot (исключение Гаусса): пересчитываем таблицу, меняя базис, — это шаг к соседней вершине.

Реализация на нашей задаче

Решим симплексом ту же задачу о цехе: $\max 30x_1+20x_2$ при $4x_1+2x_2\le40$, $2x_1+3x_2\le42$, $x\ge0$. Реализуем табличный симплекс на чистом Python.

def simplex(c, A, b):
    m, n = len(A), len(c)
    # таблица: столбцы = n переменных + m slack + RHS; нижняя строка = -c (цель)
    T = [row[:] + [1 if j == i else 0 for j in range(m)] + [b[i]]
         for i, row in enumerate(A)]
    T.append([-ci for ci in c] + [0] * m + [0])
    width = n + m + 1
    while True:
        # входящий столбец: самый отрицательный коэффициент в строке цели
        last = T[-1]
        col = min(range(width - 1), key=lambda j: last[j])
        if last[col] >= -1e-9:
            break                    # все неотрицательны -> оптимум
        # выходящая строка: минимальное отношение RHS / элемент
        ratios = []
        for i in range(m):
            a = T[i][col]
            ratios.append(T[i][-1] / a if a > 1e-9 else float('inf'))
        row = min(range(m), key=lambda i: ratios[i])
        # pivot
        piv = T[row][col]
        T[row] = [v / piv for v in T[row]]
        for i in range(m + 1):
            if i != row and abs(T[i][col]) > 1e-12:
                factor = T[i][col]
                T[i] = [T[i][j] - factor * T[row][j] for j in range(width)]
    return T[-1][-1]                  # значение цели в правом нижнем углу

c = [30, 20]
A = [[4, 2], [2, 3]]
b = [40, 42]
print("Оптимальная прибыль:", round(simplex(c, A, b), 2))

Вывод:

Оптимальная прибыль: 355.0

Симплекс самостоятельно дошёл до прибыли $355$ — той же, что мы нашли перебором вершин, но без перечисления всех углов: он сделал лишь пару pivot-шагов, переходя по рёбрам.

Как работает под капотом

Каждый pivot — это шаг от одной базисной вершины к смежной с гарантированным (нестрогим) ростом цели. Поскольку цель монотонно не убывает, а вершин конечно, метод завершается (защита от зацикливания на вырожденных задачах — правило Бленда). В худшем теоретическом случае симплекс может обойти экспоненциально много вершин (примеры Кли–Минти), но на реальных задачах он почти всегда невероятно быстр — это одна из самых успешных эвристик в истории вычислений. Гарантированно полиномиальные альтернативы — методы внутренней точки.

Частые ошибки

Неверное правило отношения. Брать минимум $b_i/a_{ij}$ только по положительным $a_{ij}$; иначе нарушится допустимость.
Зацикливание на вырождении. При равных отношениях нужно правило Бленда, иначе метод может застрять.
Забыть про неограниченность. Если в улучшающем столбце нет положительных элементов — цель неограничена сверху.

Итоги

Симплекс идёт по рёбрам от вершины к вершине, увеличивая цель, пока есть улучшающее ребро.
Slack-переменные превращают неравенства в равенства; ходы — это pivot (Гаусс) в симплекс-таблице.
На практике очень быстр, хотя в худшем случае экспоненциален; альтернатива — внутренняя точка.