Симплекс-метод: находим оптимум среди ограничений

🎯 Зачем это нужно?

Представь: Netflix нужно распределить $100M на производство фильмов и сериалов 💰. У них есть ограничения: не больше 50 фильмов в год, не меньше 20 сериалов, каждый фильм стоит $3M, сериал - $2M. Как максимизировать количество контента? Это классическая задача, которую решает симплекс-метод!

🚗 Uber Eats: оптимальные маршруты курьеров при ограничениях по времени и топливу 📱 TikTok: распределение рекламного бюджета между регионами для максимизации просмотров
🏭 Tesla: планирование производства Model S vs Model 3 при ограниченных ресурсах завода

📚 История вопроса

В 1947 году математик Джордж Данциг работал в Пентагоне над планированием военной логистики ⚔️. Ему нужно было оптимально распределить ресурсы между тысячами военных баз. Классические методы не работали - слишком много переменных!

Данциг придумал гениальную идею: не проверять все возможные решения, а “прыгать” по углам допустимой области. Как в игре-паркуре - от одной точки опоры к другой, пока не достигнешь цели! 🎮

Сегодня симплекс-метод работает в каждом GPS-навигаторе, системе управления складами Amazon, алгоритмах машинного обучения.

💡 Интуиция

Представь многоугольник на плоскости - это твоя “допустимая область” 🔷. Все точки внутри удовлетворяют ограничениям задачи. Нужно найти точку, где целевая функция достигает максимума.

Ключевое открытие Данцига: оптимум всегда находится в углу (вершине) многоугольника! Значит, не нужно проверять бесконечно много точек - только углы.

[МЕДИА: image_01] Описание: Геометрическая интерпретация симплекс-метода - многоугольник допустимой области с отмеченными вершинами и градиентом целевой функции Промпт: “geometric visualization of simplex method, convex polygon feasible region, vertices highlighted, gradient lines of objective function, arrows showing movement between vertices, modern mathematical illustration, clean style”

Симплекс-метод = умный способ обхода углов: 1️⃣ Начинаем с любого угла 2️⃣ Смотрим на соседние углы
3️⃣ Переходим к тому, где значение функции больше 4️⃣ Повторяем, пока не найдем лучший угол

Как в игре “Царь горы” - карабкаешься вверх, пока не достигнешь вершины! ⛰️

📐 Формальное определение

Задача линейного программирования: Максимизировать: f(x₁, x₂, …, xₙ) = c₁x₁ + c₂x₂ + … + cₙxₙ

При ограничениях:

• a₁₁x₁ + a₁₂x₂ + … + a₁ₙxₙ ≤ b₁
• a₂₁x₁ + a₂₂x₂ + … + a₂ₙxₙ ≤ b₂
• …
• aₘ₁x₁ + aₘ₂x₂ + … + aₘₙxₙ ≤ bₘ
• x₁, x₂, …, xₙ ≥ 0

Симплекс-метод решает эту задачу за конечное число итераций, перемещаясь по вершинам допустимого множества.

Ключевые понятия:

• Базисное решение - точка в углу допустимой области
• Симплексная таблица - удобная форма записи системы ограничений
• Опорный элемент - показывает направление следующего шага

🔍 Примеры с разбором

Пример 1: Производство смартфонов

Apple планирует выпуск iPhone и iPad 📱. Ограничения:

• Процессоры: iPhone нужен 1 чип, iPad - 2 чипа, всего 100 чипов
• Память: iPhone - 4GB, iPad - 8GB, всего 320GB
• Прибыль: iPhone - $200, iPad - $300

Найти оптимальный план производства.

Математическая модель: Переменные: x₁ = количество iPhone, x₂ = количество iPad

Максимизировать: f = 200x₁ + 300x₂ (прибыль)

Ограничения:

• x₁ + 2x₂ ≤ 100 (процессоры)
• 4x₁ + 8x₂ ≤ 320 (память)
• x₁, x₂ ≥ 0 (неотрицательность)

[МЕДИА: image_02] Описание: Пошаговое построение симплексной таблицы для примера с производством смартфонов Промпт: “step-by-step simplex table construction, showing initial tableau, pivot operations, optimization steps, highlighted optimal solution, educational mathematical diagram, clear typography”

Решение симплекс-методом:

Шаг 1: Приводим к канонической форме, добавляя слабые переменные:

• x₁ + 2x₂ + s₁ = 100
• 4x₁ + 8x₂ + s₂ = 320
• f - 200x₁ - 300x₂ = 0

Шаг 2: Строим начальную симплексную таблицу:

     x₁   x₂   s₁  s₂  |  b
s₁ |  1    2    1   0  | 100
s₂ |  4    8    0   1  | 320  
f  |-200 -300   0   0  |   0

Шаг 3: Находим опорный столбец (наибольший отрицательный коэффициент в строке f): Это столбец x₂ (-300).

Шаг 4: Находим опорную строку (минимальное отношение b/коэффициент):

• Строка s₁: 100/2 = 50
• Строка s₂: 320/8 = 40 ← минимум

Шаг 5: Выполняем жордановы исключения…

Результат: x₁ = 20, x₂ = 40, максимальная прибыль = $16,000

Пример 2: Оптимизация рекламного бюджета

YouTube Music выделяет $50,000 на рекламу в Instagram и TikTok 📺:

• Instagram: $10 за 1000 показов, конверсия 2%
• TikTok: $5 за 1000 показов, конверсия 1%
• Цель: максимизировать число новых подписчиков
• Ограничение: хотя бы 30% бюджета на Instagram (для имиджа)

Решение аналогично первому примеру…

🎮 Практика

Базовый уровень 🟢

Задание 1: Кондитерская печет торты и пирожные. Торт: 2 часа работы, прибыль $15. Пирожное: 1 час, прибыль $8. Рабочий день 8 часов. Сколько чего печь для максимума прибыли?

Задание 2: Стример выбирает игры для трансляции. CS:GO приносит 100 подписчиков/час, Dota 2 - 80 подписчиков/час. Ограничения: максимум 10 часов в день, минимум 2 часа на CS:GO. Составь задачу линейного программирования.

Задание 3: Uber планирует закупку автомобилей двух типов. Эконом: $20k цена, 30 поездок/день дохода. Комфорт: $35k цена, 40 поездок/день. Бюджет $500k. Максимизировать суточный доход.

Продвинутый уровень 🟡

Задание 4: Реши симплекс-методом: Максимизировать f = 3x₁ + 2x₂ При ограничениях: x₁ + x₂ ≤ 4, 2x₁ + x₂ ≤ 6, x₁,x₂ ≥ 0

Задание 5: Netflix выбирает между производством фильмов (F) и сериалов (S). Ограничения: F + 2S ≤ 20 (бюджет), 2F + S ≤ 16 (время), F ≥ 2 (контракты). Прибыль: 5F + 4S. Найди оптимум.

Задание 6: Докажи, что если задача линейного программирования имеет оптимальное решение, то оно достигается в вершине допустимого множества.

Челлендж 🔴

Задание 7: TikTok оптимизирует показ рекламы трех типов (A, B, C) пользователю. Ограничения на внимание: 2A + B + 3C ≤ 10, на бюджет: A + 2B + C ≤ 8. Доходность: 4A + 3B + 5C. Есть ли альтернативные оптимумы?

Задание 8: Модифицируй симплекс-метод для случая, когда некоторые переменные могут быть отрицательными. Как изменится алгоритм?

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

❌ Ошибка: Забывают добавить слабые переменные для неравенств типа ≤ ✅ Правильно: Каждое неравенство a₁x₁ + a₂x₂ ≤ b превращается в a₁x₁ + a₂x₂ + s = b 💡 Почему: Без слабых переменных невозможно найти начальное базисное решение

❌ Ошибка: Выбирают опорную строку по максимальному, а не минимальному отношению ✅ Правильно: Опорная строка = min{bᵢ/aᵢⱼ : aᵢⱼ > 0}
💡 Почему: Иначе можем выйти за границы допустимой области

❌ Ошибка: Думают, что симплекс-метод работает только для максимизации ✅ Правильно: Минимизация f(x) = максимизация (-f(x)) 💡 Почему: Достаточно поменять знаки коэффициентов целевой функции

❌ Ошибка: Не проверяют условие неотрицательности для свободных переменных ✅ Правильно: Если xᵢ может быть любого знака, заменяют на xᵢ⁺ - xᵢ⁻, где xᵢ⁺,xᵢ⁻ ≥ 0 💡 Почему: Симплекс-метод требует неотрицательности всех переменных

❌ Ошибка: Останавливаются при первом улучшении целевой функции ✅ Правильно: Продолжают итерации, пока все коэффициенты в строке f неотрицательны 💡 Почему: Локальный оптимум может не быть глобальным

🎓 Главное запомнить

✅ Симплекс-метод находит оптимум, “прыгая” по вершинам допустимой области ✅ Оптимальное решение всегда находится в угловой точке (базисном решении)
✅ Алгоритм: выбираем опорный элемент → жордановы исключения → проверяем критерий оптимальности

🔗 Связь с другими темами

Откуда пришли: Системы линейных уравнений и неравенств (урок 280) заложили основу для понимания ограничений и допустимых областей.

Куда ведет: Симплекс-метод - основа для двойственности в линейном программировании, целочисленного программирования, и современных методов оптимизации в машинном обучении (градиентный спуск - это симплекс-метод для непрерывных задач!).

Практическое применение: Каждый раз, когда Яндекс.Маршруты строит оптимальный путь, а Wildberries планирует поставки на склады - работает потомок симплекс-метода! 🚀