Оптимизация
Линейное программирование
Цели урока
- Формулировать задачу LP в стандартном виде
- Понимать геометрическую интерпретацию и почему оптимум в вершине
- Знать логику симплекс-метода: pivot, entering/leaving переменные
- Интерпретировать теневые цены и анализ чувствительности для бизнес-решений
Предварительные знания
Delta Airlines в 2021 году сэкономила более 100 млн долларов на оптимизации расписания рейсов и назначения экипажей. Алгоритм в основе - линейное программирование, придуманное в 1947 году для военных. Тот же математический инструмент управляет рекламными аукционами Google (100+ млрд запросов в день), маршрутами 10 тысяч грузовиков Walmart и динамическим ценообразованием Uber.
- **Авиация:** Delta Airlines экономит 100 млн долларов в год на оптимизации расписаний через LP
- **Реклама:** Google Ads распределяет рекламный бюджет между площадками через LP-солвер в реальном времени
- **Supply Chain:** Walmart оптимизирует маршруты 10 000+ грузовиков ежедневно с помощью LP
Данциг, Канторович и триллионная индустрия
1939 - Леонид Канторович в СССР разрабатывает LP для планирования производства. 1947 - Джордж Данциг в США независимо изобретает симплекс-метод для военной логистики. 1972 - пример Кли-Минти показывает: worst-case симплекса экспоненциален. 1975 - Нобелевская премия по экономике Канторовичу. 1984 - Karmarkar находит полиномиальный interior-point метод. Сегодня рынок LP-оптимизации - десятки миллиардов долларов в год.
Формулировка LP
1947 год. Холодная война только начинается. Военные США хотят оптимально распределять ресурсы: самолёты, топливо, боеприпасы на тысячи задач. Математик Джордж Данциг формализует это как **линейное программирование** (LP) - задачу оптимизации, где и целевая функция, и все ограничения линейны. Алгоритм, рождённый для войны, сегодня управляет ценами на Uber.
**Линейное программирование** - "программирование" здесь означает "планирование" (от military programming), а не написание кода. LP - одна из наиболее изученных задач оптимизации с гарантированно полиномиальными алгоритмами решения.
| Элемент LP | Фабрика стульев/столов | Математика |
|---|---|---|
| Переменные | x1 = стулья, x2 = столы | x в R^n |
| Цель | Максимизировать прибыль | max 20x1 + 50x2 |
| Ограничение 1 | Рабочие часы <= 120 | x1 + 3x2 <= 120 |
| Ограничение 2 | Дерево <= 400 кг | 4x1 + 8x2 <= 400 |
| Неотрицательность | Нельзя сделать -5 столов | x1, x2 >= 0 |
Геометрически: каждое ограничение - полупространство. Их пересечение - **многогранник** (polytope). Целевая функция - плоскость, которую двигают в одном направлении. Оптимум всегда в **вершине** многогранника. Это фундаментальная теорема - не эвристика.
Почему оптимум LP всегда лежит в вершине допустимого многогранника?
Симплекс-метод
Оптимум LP - в вершине многогранника. Можно перебрать все вершины. Проблема: вершин $C(m+n, n)$ - экспоненциально много. **Симплекс-метод** Данцига (1947) хитрее: начинает с одной вершины и переходит к соседней, только если это улучшает цель. На практике посещает $O(m)$ вершин из миллиардов. Gurobi решает LP с миллионом переменных за секунды.
Данциг и случайное домашнее задание
В 1947 году Джордж Данциг опоздал на лекцию и принял две задачи на доске за домашнее задание. Решил их за выходные - оказалось, это нерешённые проблемы статистики. Тот же человек создал симплекс-метод, который ежедневно решает миллионы задач планирования - от расписаний авиакомпаний до распределения рекламных бюджетов Google Ads.
**Сложность:** worst-case симплекс экспоненциальный (пример Кли-Минти, 1972). Но на практике - $O(m)$ итераций, где m - число ограничений. Альтернатива - **метод внутренней точки** (Karmarkar, 1984) с полиномиальной worst-case сложностью $O(n^{3.5})$. Gurobi автоматически выбирает между ними.
Симплекс-метод на каждом шаге переходит из вершины в соседнюю. Как он выбирает куда идти?
Двойственность
Каждая LP имеет "зеркальное отражение" - **двойственную задачу** (dual). Прямая задача - "максимизировать прибыль при ограниченных ресурсах". Двойственная - "минимизировать стоимость ресурсов, чтобы она покрывала прибыль". Оптимальные значения обеих задач совпадают - это **сильная двойственность**.
| Свойство | Описание | Значение |
|---|---|---|
| Слабая двойственность | c^Tx <= b^Ty для любых допустимых x, y | Dual даёт верхнюю границу Primal |
| Сильная двойственность | c^Tx* = b^Ty* для оптимальных x*, y* | Оптимумы совпадают! |
| Комплементарная нежёсткость | x_i*(A^Ty* - c)_i = 0 | Если x_i > 0, ограничение dual активно |
| Теневые цены | y_i* = d(opt)/d(b_i) | Сколько стоит +1 единица ресурса i |
**Сильная двойственность** - одна из красивейших теорем оптимизации. Два совершенно разных взгляда на одну задачу (максимизация прибыли и минимизация затрат) дают одинаковый ответ. Это используется для проверки оптимальности: если primal value = dual value, обе задачи решены оптимально.
Двойственность - не абстракция. **SVM** в machine learning решается именно через двойственную задачу, что позволяет применить kernel trick и работать в бесконечномерных пространствах - одна из причин почему SVM доминировал до deep learning.
Двойственность и Нобелевская премия по экономике
Леонид Канторович получил Нобелевскую премию по экономике (1975) за применение LP к планированию производства в СССР. Двойственные переменные y - это "теневые цены" ресурсов, показывающие их истинную экономическую ценность. Если y_i = 0, ресурс i избыточен и не влияет на прибыль. Канторович разработал это независимо от западных учёных в 1939 году.
В двойственной задаче y1* = 15 (теневая цена рабочих часов). Что это означает?
Анализ чувствительности
Решение LP найдено. Но поставщик поднял цену дерева. Появился новый станок. Спрос вырос. **Анализ чувствительности** отвечает: насколько устойчиво решение к изменениям параметров? Не нужно перерешивать - достаточно проверить диапазоны.
| Параметр | Текущее значение | Допустимый диапазон | Shadow price |
|---|---|---|---|
| Рабочие часы (b1) | 120 | [100, 160] | 15/час |
| Дерево (b2) | 400 кг | [300, inf) | 0/кг (избыток!) |
| Прибыль стула (c1) | 20 | [12.50, 37.50] | - |
| Прибыль стола (c2) | 50 | [26.67, 80] | - |
**Shadow price = 0** означает, что ресурс в избытке (non-binding constraint). В примере дерева хватает с запасом - покупать ещё бессмысленно. Рабочие часы - узкое место (binding constraint), каждый дополнительный час приносит 15 прибыли. Delta Airlines использует этот анализ для оценки: стоит ли нанимать ещё одного пилота?
Анализ чувствительности критически важен для бизнес-решений. Не нужно перерешивать задачу при каждом изменении - достаточно проверить, остаётся ли значение параметра в допустимом диапазоне. Если да - оптимальная стратегия не меняется.
Анализ чувствительности валиден только **локально** - в окрестности текущего решения. При больших изменениях параметров оптимальная вершина может измениться (другой набор binding constraints), и нужно перерешивать задачу заново.
Симплекс-метод имеет экспоненциальную сложность и непрактичен для больших задач
Хотя worst-case сложность симплекса экспоненциальная, на практике он работает за линейное или почти линейное число шагов и решает задачи с миллионами переменных.
Пример Кли-Минти (1972) - патологический случай. Средняя сложность O(m), что подтверждено теоретически (smoothed analysis, Spielman & Teng, 2004) и практически: Gurobi и CPLEX решают промышленные LP с миллионами переменных за секунды.
Shadow price дерева = 0. Поставщик предлагает дополнительные 50 кг дерева за 100. Стоит ли покупать?
Ключевые идеи
- **LP** = линейная цель + линейные ограничения; оптимум всегда в вершине многогранника
- **Симплекс-метод** обходит вершины, на каждом шаге улучшая цель; worst-case экспоненциальный, на практике быстрый
- **Двойственность:** каждая LP имеет зеркальную задачу; сильная двойственность гарантирует равенство оптимумов; dual variables = теневые цены
- **Анализ чувствительности** показывает как изменения параметров влияют на решение без перерешивания задачи
Связанные темы
LP - фундамент для более сложных задач оптимизации:
- Градиентный спуск — Для непрерывных нелинейных задач; LP решается точно, без итераций
- SVM — Обучение SVM сводится к квадратичному программированию (QP), обобщению LP
- Графы и потоки — Задача максимального потока в графе - частный случай LP
Вопросы для размышления
- Почему теневые цены (dual variables) так важны для бизнес-решений? Чем они отличаются от рыночных цен?
- Если симплекс-метод экспоненциален в worst-case, почему он всё ещё используется вместо полиномиальных interior point методов?
- Как LP помогает авиакомпании составить расписание на 1000 рейсов с 500 экипажами?
Связанные уроки
- opt-02 — Gradient descent для нелинейных задач; LP решается точно без итераций
- opt-04 — Integer LP (ILP) - LP с целочисленными переменными, NP-hard
- opt-05 — Quadratic programming (QP) - обобщение LP, используется в SVM
- ml-13 — Обучение SVM сводится к QP, расширению LP
- alg-15 — Задача максимального потока в графе - частный случай LP
- sci-03 — LP-солверы используют LU-шаги при каждом Simplex pivot
- cvx-01 — Convex optimization - обобщение LP на выпуклые задачи
- la-01-vectors-intro