В лекции из курса MIT OpenCourseWare профессор Питер Шор вводит слушателей в мир линейного программирования — одного из ключевых инструментов современной оптимизации. На примере простых бытовых задач он демонстрирует, как перевести реальные ограничения в математические модели и почему понимание теории двойственности важнее для математика, чем умение вычислять алгоритмы вручную.
💰 Линейное программирование как «двигатель» оптимизации 0:00
Линейное программирование (LP) — это не просто абстрактная математическая дисциплина, а огромный бизнес и фундамент для систем оптимизации. В качестве примера коммерческого успеха Питер Шор приводит историю Роберта Биксби, который в 1987 году основал компанию и создал CPLEX — на тот момент лучший инструмент для решения задач линейного программирования. Спустя десять лет компания была продана за сумму около 50 миллионов долларов, а недавно IBM выкупила её уже за 180 миллионов долларов.
Суть линейного программирования заключается в максимизации или минимизации линейной функции при соблюдении набора линейных ограничений. Процесс работы с LP состоит из трёх этапов:
- Выбор переменных.
- Написание целевой функции.
- Определение ограничений.
🐭 Диетическая модель: минимизация затрат на корм 2:54
Профессор рассматривает классическую задачу о диете, адаптированную для кормления лабораторных мышей. У мышей есть минимальные потребности в питательных веществах: 8 единиц крахмала, 15 единиц белка и 7 единиц витаминов.
Для кормления доступны два вида зерна:
- Зерно 1: Содержит 5 ед. крахмала, 4 ед. белка, 2 ед. витаминов. Стоимость — $0,60.
- Зерно 2: Содержит 7 ед. крахмала, 2 ед. белка, 1 ед. витаминов. Стоимость — $0,35.
Математическая модель задачи выглядит следующим образом: необходимо минимизировать общую стоимость $60x_1 + 35x_2$ при условии, что сумма питательных веществ от обоих типов зерна будет больше или равна требуемым нормам. Важным дополнением являются ограничения неотрицательности: количество зерна не может быть отрицательным ($x_1 \ge 0, x_2 \ge 0$).
🍪 Выпечка и «допустимая область» решений 9:58
Второй пример касается максимизации прибыли от продажи печенья и меренг. Здесь ресурсы (яйца, сахар, мука) ограничены, а цель — получить как можно больше денег.
Параметры задачи:
- Ресурсы: 9 яиц, 8 чашек сахара, 15 чашек муки.
- Печенье ($x_1$): Требует 1 яйцо, 2 чашки сахара, 1.5 чашки муки. Цена — $20.
- Меренги ($x_2$): Требуют 3 яйца, 1 чашку сахара, 0 муки. Цена — $20.
На примере этой задачи Шор вводит понятие допустимого решения (feasible solution) — любой точки, удовлетворяющей всем ограничениям. В случае с двумя переменными область допустимых решений можно нарисовать на плоскости. Оптимальное решение всегда находится в одной из экстремальных точек (вершин) этого многоугольника. Интересно, что ограничение по муке в данном примере оказывается избыточным, так как оно не влияет на форму области, заданную другими ресурсами.
📋 Стандартная и каноническая формы 19:39
Для работы алгоритмов задачи линейного программирования должны быть приведены к строгому формату. Профессор выделяет две основные формы:
- Каноническая форма: Все ограничения представлены в виде неравенств ($Ax \le b$), целевая функция максимизируется.
- Стандартная форма: Ограничения представлены в виде строгих равенств ($Ax = b$).
Любую задачу LP можно трансформировать. Например, чтобы превратить неравенство «меньше или равно» в равенство, добавляется слабая переменная (slack variable). Если же нужно сменить минимизацию на максимизацию, достаточно просто инвертировать знаки коэффициентов целевой функции.
🚶♂️ Симплекс-метод и его эффективность 28:44
Хотя Шор не углубляется в технические детали вычислений, он дает обзор симплекс-метода, предложенного Данцигом. Алгоритм начинает работу в одной из вершин допустимой области и «шагает» по рёбрам к соседним вершинам, пока значение целевой функции улучшается.
Профессор отмечает парадокс симплекс-метода:
- На практике: Он работает чрезвычайно эффективно почти во всех случаях.
- В теории: Можно сконструировать примеры, где алгоритму потребуется экспоненциальное количество шагов.
Этот разрыв между теорией и практикой был объяснен лишь недавно Дэном Спилманом (бывшим профессором MIT) и Тенгом, которые разработали «сглаженный анализ» (smoothed analysis). По словам Шора, этот анализ доказывает, что метод работает быстро почти всегда.
⚖️ Теория двойственности: обратная сторона задачи 41:18
Центральная часть лекции посвящена двойственности (duality). У каждой задачи линейного программирования (прямой или примальной) есть «зеркальная» двойственная задача. Если в прямой задаче мы максимизируем прибыль, то в двойственной — минимизируем стоимость ресурсов, необходимых для её получения.
Шор приводит и доказывает две важнейшие теоремы:
- Теорема слабой двойственности: Любое допустимое решение примальной задачи дает нижнюю границу для двойственной, а любое решение двойственной — верхнюю границу для примальной.
- Теорема сильной двойственности: Если оптимальное решение существует, то максимумы прямой задачи и минимумы двойственной в точности равны ($z^ = w^$).
Профессор подчеркивает, что прикладному математику не обязательно знать, что происходит «под капотом» софта вроде CPLEX, но он обязан понимать двойственность. Это позволяет не только находить границы решения, но и глубже понимать интуитивную суть проблемы, будь то экономика, потоки в сетях или игры с нулевой суммой.
