# Введение в линейное программирование: от диеты для мышей до теорем двойственности Источник: https://www.youtube.com/watch?v=qKNkP6IfjvY Канал: MIT OpenCourseWare Опубликовано: 17.12.2025 --- В лекции из курса MIT OpenCourseWare профессор Питер Шор вводит слушателей в мир линейного программирования — одного из ключевых инструментов современной оптимизации. На примере простых бытовых задач он демонстрирует, как перевести реальные ограничения в математические модели и почему понимание теории двойственности важнее для математика, чем умение вычислять алгоритмы вручную. ## 💰 Линейное программирование как «двигатель» оптимизации [[JUMP:0:00]] Линейное программирование (LP) — это не просто абстрактная математическая дисциплина, а огромный бизнес и фундамент для систем оптимизации. В качестве примера коммерческого успеха Питер Шор приводит историю Роберта Биксби, который в 1987 году основал компанию и создал CPLEX — на тот момент лучший инструмент для решения задач линейного программирования. Спустя десять лет компания была продана за сумму около 50 миллионов долларов, а недавно IBM выкупила её уже за 180 миллионов долларов. Суть линейного программирования заключается в максимизации или минимизации линейной функции при соблюдении набора линейных ограничений. Процесс работы с LP состоит из трёх этапов: 1. Выбор переменных. 2. Написание целевой функции. 3. Определение ограничений. ## 🐭 Диетическая модель: минимизация затрат на корм [[JUMP: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$). ## 🍪 Выпечка и «допустимая область» решений [[JUMP:9:58]] Второй пример касается максимизации прибыли от продажи печенья и меренг. Здесь ресурсы (яйца, сахар, мука) ограничены, а цель — получить как можно больше денег. Параметры задачи: * **Ресурсы:** 9 яиц, 8 чашек сахара, 15 чашек муки. * **Печенье ($x_1$):** Требует 1 яйцо, 2 чашки сахара, 1.5 чашки муки. Цена — $20. * **Меренги ($x_2$):** Требуют 3 яйца, 1 чашку сахара, 0 муки. Цена — $20. На примере этой задачи Шор вводит понятие **допустимого решения** (feasible solution) — любой точки, удовлетворяющей всем ограничениям. В случае с двумя переменными область допустимых решений можно нарисовать на плоскости. Оптимальное решение всегда находится в одной из экстремальных точек (вершин) этого многоугольника. Интересно, что ограничение по муке в данном примере оказывается избыточным, так как оно не влияет на форму области, заданную другими ресурсами. ## 📋 Стандартная и каноническая формы [[JUMP:19:39]] Для работы алгоритмов задачи линейного программирования должны быть приведены к строгому формату. Профессор выделяет две основные формы: * **Каноническая форма:** Все ограничения представлены в виде неравенств ($Ax \le b$), целевая функция максимизируется. * **Стандартная форма:** Ограничения представлены в виде строгих равенств ($Ax = b$). Любую задачу LP можно трансформировать. Например, чтобы превратить неравенство «меньше или равно» в равенство, добавляется **слабая переменная** (slack variable). Если же нужно сменить минимизацию на максимизацию, достаточно просто инвертировать знаки коэффициентов целевой функции. ## 🚶‍♂️ Симплекс-метод и его эффективность [[JUMP:28:44]] Хотя Шор не углубляется в технические детали вычислений, он дает обзор симплекс-метода, предложенного Данцигом. Алгоритм начинает работу в одной из вершин допустимой области и «шагает» по рёбрам к соседним вершинам, пока значение целевой функции улучшается. Профессор отмечает парадокс симплекс-метода: * **На практике:** Он работает чрезвычайно эффективно почти во всех случаях. * **В теории:** Можно сконструировать примеры, где алгоритму потребуется экспоненциальное количество шагов. Этот разрыв между теорией и практикой был объяснен лишь недавно Дэном Спилманом (бывшим профессором MIT) и Тенгом, которые разработали «сглаженный анализ» (smoothed analysis). По словам Шора, этот анализ доказывает, что метод работает быстро почти всегда. ## ⚖️ Теория двойственности: обратная сторона задачи [[JUMP:41:18]] Центральная часть лекции посвящена двойственности (duality). У каждой задачи линейного программирования (прямой или примальной) есть «зеркальная» двойственная задача. Если в прямой задаче мы максимизируем прибыль, то в двойственной — минимизируем стоимость ресурсов, необходимых для её получения. Шор приводит и доказывает две важнейшие теоремы: 1. **Теорема слабой двойственности:** Любое допустимое решение примальной задачи дает нижнюю границу для двойственной, а любое решение двойственной — верхнюю границу для примальной. 2. **Теорема сильной двойственности:** Если оптимальное решение существует, то максимумы прямой задачи и минимумы двойственной в точности равны ($z^* = w^*$). Профессор подчеркивает, что прикладному математику не обязательно знать, что происходит «под капотом» софта вроде CPLEX, но он обязан понимать двойственность. Это позволяет не только находить границы решения, но и глубже понимать интуитивную суть проблемы, будь то экономика, потоки в сетях или игры с нулевой суммой.