Геометрия линейных задач

Линейное программирование — оптимизация линейной цели на многограннике; оптимум всегда сидит в вершине.

Линейная задача (LP) — задача вида $\max c^\top x$ при ограничениях $Ax\le b$, $x\ge 0$, где и цель, и все ограничения линейны.

Где встречается

LP — самый прикладной класс оптимизации в экономике и логистике. Распределить бюджет, спланировать производство при ограниченных ресурсах, составить дешёвую диету с нужными витаминами, раскроить материал — всё это линейные задачи. Их особенность: и то, что максимизируем (прибыль), и ограничения (ресурсы) выражаются линейными функциями переменных.

Каноническая форма

$$\max_{x}\ c^\top x\quad\text{при}\quad Ax\le b,\ x\ge 0.$$

Здесь $x\in\mathbb{R}^n$ — что мы выбираем (объёмы выпуска), $c$ — коэффициенты выгоды, $A,b$ задают ограничения ресурсов. Минимизация (например, стоимости) сводится к максимизации $-c$.

Допустимое множество — многогранник

Каждое неравенство $a_i^\top x\le b_i$ отсекает полупространство. Пересечение всех полупространств плюс условия $x\ge 0$ образуют выпуклый многогранник — допустимое множество. В 2D это многоугольник, в 3D — многогранник, в $n$D — политоп. Поскольку и множество выпукло, и цель линейна, LP — частный (и самый ручной) случай выпуклой оптимизации.

Главная теорема: оптимум в вершине

Линии уровня цели $c^\top x=\text{const}$ — параллельные прямые (гиперплоскости). Сдвигая их в сторону роста, последняя точка касания с многогранником — всегда вершина (угол) или целая грань. Значит, чтобы решить LP, достаточно перебрать вершины — их конечное число. Это превращает непрерывную задачу в комбинаторную.

Пример: производство

Цех делает столы ($x_1$, прибыль 30) и стулья ($x_2$, прибыль 20). Ограничения: дерево $4x_1+2x_2\le 40$, труд $2x_1+3x_2\le 42$, плюс $x_1,x_2\ge0$. Перечислим вершины многоугольника и выберем лучшую.

def feasible(x1, x2):
    return (4*x1 + 2*x2 <= 40 + 1e-9 and
            2*x1 + 3*x2 <= 42 + 1e-9 and
            x1 >= -1e-9 and x2 >= -1e-9)

def profit(x1, x2):
    return 30 * x1 + 20 * x2

# вершины = пересечения пар прямых-ограничений (включая оси)
vertices = [(0, 0), (10, 0), (0, 14), (4.5, 11)]
best = None
for (x1, x2) in vertices:
    if feasible(x1, x2):
        p = profit(x1, x2)
        print(f"вершина ({x1},{x2}): прибыль={p}")
        if best is None or p > best[1]:
            best = ((x1, x2), p)
print("Оптимум:", best[0], "прибыль", best[1])

Вывод:

вершина (0,0): прибыль=0
вершина (10,0): прибыль=300
вершина (0,14): прибыль=280
вершина (4.5,11): прибыль=355.0
Оптимум: (4.5, 11) прибыль 355.0

Лучшая вершина — $(4.5,11)$: делать 4.5 стола и 11 стульев, прибыль 355. Заметьте: оптимум именно в углу, где пересекаются оба ресурсных ограничения — они «связывающие» (активные). Проверьте: $4\cdot4.5+2\cdot11=40$ и $2\cdot4.5+3\cdot11=42$ — оба ресурса исчерпаны.

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

Перебор вершин кажется простым, но их число растёт комбинаторно: у многогранника с $m$ ограничениями в $n$ измерениях вершин может быть до $\binom{m}{n}$. Для больших задач полный перебор невозможен — поэтому нужен симплекс-метод, который умно ходит по рёбрам от вершины к вершине, всегда улучшая цель, и обходит лишь малую долю вершин. Альтернатива — методы внутренней точки, идущие сквозь нутро многогранника.

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

Искать оптимум внутри многогранника. Для линейной цели он всегда на границе (в вершине), внутри — никогда (если цель не нулевая).
Забыть $x\ge0$. Неотрицательность — тоже ограничения, они часть многогранника.
Считать, что решение всегда единственно. Если линия уровня параллельна грани, оптимальна вся грань (бесконечно много решений).

Итоги

LP: линейная цель $c^\top x$ на многограннике $Ax\le b,\ x\ge0$.
Допустимое множество выпукло; оптимум всегда в вершине (или на грани).
Вершин конечно, но их экспоненциально много — нужен симплекс, а не перебор.