Симплекс: ходить по вершинам, а не перебирать их

Если ты понимаешь, что такое базис и почему шаг симплекса - это переход по ребру многогранника, и знаешь, что худший случай экспоненциален, листай до «Теперь сам».

Как думаешь, зачем вообще алгоритм

Перебор вершин для двух переменных выглядел честной работой: десяток пересечений, проверил допустимость, выбрал лучшее. Прикинь теперь задачу планирования смен: 200 переменных и 500 ограничений. Сколько вершин надо перебрать?

Число сочетаний из 500 по 200 - это единица с сотней с лишним нулей. Столько вершин не переберёт никто и никогда. Значит нужен способ приходить в нужную вершину, не осматривая остальные, - и именно это делает симплекс.

На что это похоже

Подъём в гору в тумане. Ты стоишь на склоне и видишь только тропинки от своего места. Выбираешь ту, что ведёт вверх, идёшь по ней до развилки, там снова смотришь. Когда все тропинки ведут вниз - ты на вершине. Для выпуклой горы (а многогранник выпуклый) такой подъём гарантированно приводит на САМУЮ высокую точку, и в этом вся сила: локальный максимум здесь совпадает с глобальным.

Механизм: базис и шаг

Сначала неравенства превращают в равенства, добавляя дополнительные переменные - остатки ресурсов:

2x + 3y <= 12        →      2x + 3y + s₁ = 12,   s₁ >= 0
4x +  y <= 10        →      4x +  y + s₂ = 10,   s₂ >= 0

Теперь переменных больше, чем уравнений. Базисное решение: выбираем m переменных (базис), остальные приравниваем нулю и решаем систему. Каждому допустимому базисному решению соответствует вершина многогранника.

шаг симплекса:
    1. выбрать ВХОДЯЩУЮ переменную - ту, чей рост увеличивает цель
       (если такой нет - текущая вершина оптимальна, стоп)
    2. выбрать ВЫХОДЯЩУЮ переменную - ту, которая первой упрётся в ноль
       при росте входящей (правило отношений)
       (если ни одна не упирается - цель не ограничена, стоп)
    3. поменять их местами в базисе и пересчитать

Геометрически шаг - это переход по ребру многогранника в соседнюю вершину. Цель при этом не убывает.

вырожденность - в вершине сходится больше ограничений, чем нужно;
                тогда шаг может не сдвинуть точку вовсе, а лишь сменить базис
зацикливание  - последовательность базисов повторяется; лечится правилом Блэнда
                (при выборе всегда брать переменную с наименьшим номером)

Правило

Симплекс-метод ходит по вершинам многогранника, а не перебирает их. Вершине соответствует базис - набор переменных, которым разрешено быть ненулевыми; шаг меняет одну переменную в базисе и переводит точку в соседнюю вершину, не ухудшая цель. Нет входящей переменной - оптимум найден; нет выходящей - цель не ограничена. Худший случай экспоненциален (куб Кли-Минти заставляет метод обойти все 2ⁿ вершин), на практике же число шагов обычно порядка числа ограничений. Полиномиальные гарантии дают эллипсоидный метод (Хачиян, 1979) и методы внутренней точки (Кармаркар, 1984); последние применяют для по-настоящему больших задач.

Разбор: два шага на задаче про цех

Задача из прошлого урока: максимизировать 5x + 4y при 2x + 3y <= 12, 4x + y <= 10.

старт: базис {s₁, s₂}, то есть x = y = 0        вершина (0, 0), цель 0

шаг 1. входящая: x (его коэффициент в цели 5 - самый большой рост)
       правило отношений: s₁ упрётся при x = 12/2 = 6
                          s₂ упрётся при x = 10/4 = 2.5  ← меньше, выходит s₂
       новый базис {s₁, x}                      вершина (2.5, 0), цель 12.5
       «пересчитать» значит выразить новую базисную переменную через небазисные
       и подставить это выражение в остальные строки и в цель - после чего цель
       выглядит как 12.5 + 2.75y − 1.25s₂, и выгодность y видна прямо в ней

шаг 2. входящая: y (её коэффициент в пересчитанной цели +2.75, то есть рост выгоден)
       правило отношений: упирается s₁, при x = 2.5 остаётся y <= 2.8
       новый базис {x, y}                       вершина (1.8, 2.8), цель 20.2

шаг 3. входящих переменных нет - рост цели невозможен ни в одну сторону
       ОПТИМУМ: 20.2

Три вершины вместо четырёх - на такой задаче экономия невелика. Но посмотри на закономерность: метод не осматривал вершину (0, 4) вовсе. Он не перебирает, он идёт по рёбрам в сторону роста, и на большой задаче именно это даёт разницу между секундой и «никогда».

Разбор: почему худший случай всё-таки экспоненциален

Кли и Минти в 1972 году построили пример: слегка «покосившийся» n-мерный куб. У куба 2ⁿ вершин, и на этом кубе классический симплекс с правилом «входит переменная с самым выгодным коэффициентом» обходит ВСЕ вершины, прежде чем добраться до оптимума.

куб размерности n: 2ⁿ вершин, симплекс обходит их все, то есть делает 2ⁿ − 1 шаг
n = 3   →   8 вершин,  7 шагов вместо трёх
n = 50  →   2⁵⁰ вершин, это больше 10¹⁵ шагов

Почему так выходит: правило «самый выгодный коэффициент» смотрит только на мгновенную выгоду, а куб построен так, что самый выгодный шаг каждый раз уводит в длинный обход. Это ровно та же болезнь, что и у любой жадности, - только здесь она стоит экспоненты.

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

Что ломается без этого

Первое: писать симплекс руками без правила против зацикливания и получить бесконечный цикл на вырожденной задаче - она встречается чаще, чем кажется. Второе: выбирать выходящую переменную не по правилу отношений, а «первую попавшуюся» - решение станет недопустимым. Третье: забывать про начальную допустимую вершину: если нулевая точка недопустима (есть ограничения >= с положительной правой частью), нужен подготовительный этап - метод двух фаз или большие штрафы. Четвёртое: ожидать от симплекса целых ответов - он даёт вершину, а она бывает дробной. Пятое: считать, что «экспоненциальный худший случай» означает «медленно»: на практике шагов обычно от m до 3m, и именно поэтому метод жив уже восемьдесят лет.

Зачем это в работе

Писать симплекс руками почти никогда не нужно - за тебя это уже написали. Но понимать, что внутри, приходится: когда решатель говорит «задача не ограничена», значит в модели забыто ограничение; когда «несовместна» - значит ограничения противоречат друг другу, и надо искать какое; когда решение оказалось дробным - значит решалась линейная задача, а нужна была целочисленная, и это совсем другое время работы. Плюс словарь: basis - базис, slack - дополнительная переменная, degenerate - вырожденная вершина, pivot - сам шаг смены базиса (и «ведущий элемент», вокруг которого идёт пересчёт). В логах решателей эти слова встречаются постоянно.

Теперь сам

Задача: максимизировать 3x + 2y при x + y <= 4, x <= 3, x, y >= 0. Пройди симплекс от точки (0, 0) и назови вершины, через которые он пройдёт.