Линейное программирование: максимизируй прибыль при ограничениях

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

🎮 Netflix рекомендации: Алгоритм должен максимизировать engagement при ограниченном времени пользователя 📱 Uber маршруты: Оптимизация расписания водителей для минимизации времени ожидания
🏭 Производство Tesla: Как распределить ресурсы между Model S и Model 3 для максимальной прибыли?

В machine learning линейное программирование — это основа SVM, LASSO регрессии и многих алгоритмов оптимизации!

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

В 1947 году математик Джордж Данциг работал в Пентагоне над логистикой армии США 🎖️. Ему нужно было оптимально распределить солдат и технику. Так родился симплекс-метод — один из самых важных алгоритмов XX века!

Интересный факт: Google использует линейное программирование для размещения рекламы на $100+ миллиардов в год 💰

💡 Интуиция

Представь, что ты владеешь кафе и делаешь два вида смузи: 🥤 “Тропический” и 🍓 “Ягодный”.

Ограничения (как в жизни):

• У тебя 100 манго и 80 клубничек в день
• Тропический смузи = 2 манго + 1 клубничка, прибыль 150₽
• Ягодный смузи = 1 манго + 3 клубнички, прибыль 200₽
• Рабочий день = 8 часов (максимум 50 смузи)

Вопрос: Сколько делать каждого вида для максимальной прибыли?

Это и есть задача линейного программирования! 🎯

[МЕДИА: image_01] Описание: Визуализация задачи о смузи с ингредиентами и ограничениями Промпт: “business optimization illustration showing smoothie ingredients (mango, strawberry), constraints visualization, profit calculation, modern flat design, educational style, vibrant colors”

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

Задача линейного программирования:

Максимизировать (или минимизировать): c₁x₁ + c₂x₂ + … + cₙxₙ (целевая функция)

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

• a₁₁x₁ + a₁₂x₂ + … + a₁ₙxₙ ≤ b₁
• a₂₁x₁ + a₂₂x₂ + … + a₂ₙxₙ ≤ b₂
• …
• xⱼ ≥ 0 для всех j (неотрицательность)

В машинном обучении:

• SVM: min ½||w||² при условии yᵢ(wᵀxᵢ + b) ≥ 1
• LASSO: min ||y - Xβ||² + λ||β||₁

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

Пример 1: Классическая задача о смузи

Дано:

• x₁ = количество тропических смузи
• x₂ = количество ягодных смузи

Целевая функция: max f(x₁, x₂) = 150x₁ + 200x₂

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

• 2x₁ + x₂ ≤ 100 (манго)
• x₁ + 3x₂ ≤ 80 (клубника)
• x₁ + x₂ ≤ 50 (время)
• x₁, x₂ ≥ 0

Решение графическим методом:

1️⃣ Строим допустимую область (пересечение всех ограничений) 2️⃣ Находим угловые точки: (0,0), (0,20), (40,10), (50,0) 3️⃣ Вычисляем f в каждой точке:

• f(0,0) = 0
• f(0,20) = 4000₽
• f(40,10) = 8000₽
• f(50,0) = 7500₽

Ответ: 40 тропических + 10 ягодных = 8000₽ прибыли! 🎉

[МЕДИА: image_02] Описание: График допустимой области с угловыми точками и линиями уровня целевой функции Промпт: “linear programming feasible region graph, corner points marked, objective function level curves, constraint lines, optimal solution highlighted, mathematical visualization, clean design”

Пример 2: Оптимизация в ML (LASSO регрессия)

# Задача LASSO: min ||y - Xβ||² + λ||β||₁
# Эквивалентная LP формулировка:
# min Σ(yᵢ - Σxᵢⱼβⱼ)² + λΣ|βⱼ|

import numpy as np
from scipy.optimize import linprog

# Преобразуем в стандартную форму LP
# Вводим β⁺ ≥ 0, β⁻ ≥ 0: β = β⁺ - β⁻, |β| = β⁺ + β⁻

[МЕДИА: image_03] Описание: Сравнение обычной и LASSO регрессии, показывающее разреженность решения Промпт: “machine learning comparison showing regular regression vs LASSO regression, sparse solution visualization, feature selection effect, technical diagram, modern ML style”

🎮 Практика

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

Задание 1: Студент готовится к экзаменам по математике и физике. На математику нужно x₁ часов, на физику x₂ часов. Общая польза = 3x₁ + 2x₂. Ограничения: x₁ + x₂ ≤ 10 (всего времени), x₁ ≤ 7, x₂ ≤ 6. Найди оптимальное распределение времени.

Задание 2: Завод выпускает смартфоны (x₁) и планшеты (x₂). Прибыль: 500x₁ + 300x₂. Ограничения: процессоры 2x₁ + x₂ ≤ 100, память x₁ + 2x₂ ≤ 80. Найди максимальную прибыль.

Задание 3: Построй допустимую область для системы: x₁ + 2x₂ ≤ 6, 2x₁ + x₂ ≤ 6, x₁,x₂ ≥ 0. Найди все угловые точки.

Задание 4: Netflix выбирает контент. Фильмы (x₁) привлекают 100 зрителей за 1M$, сериалы (x₂) — 150 за 2M$. Бюджет 10M$. Максимизируй зрителей.

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

Задание 5: ML-инженер настраивает SVM. Нужно минимизировать ½||w||² при условии yᵢ(wᵀxᵢ + b) ≥ 1 для данных: (1,1,+1), (-1,-1,-1), (1,-1,+1). Запиши как задачу LP.

Задание 6: Компания распределяет бюджет между YouTube (x₁), TikTok (x₂), Instagram (x₃). Охват: 1000x₁ + 2000x₂ + 1500x₃. Ограничения: x₁+x₂+x₃ ≤ 100k$, x₁≤40k$, x₂≥20k$, x₃≤50k$. Найди оптимум симплекс-методом.

Задание 7: В Ridge регрессии min ||y - Xβ||² + λ||β||₂². Почему это НЕ задача LP? Как преобразовать в квадратичное программирование?

Задание 8: Uber оптимизирует маршруты. 3 водителя, 4 заказа. Матрица времени доезда: [[5,3,7,2], [4,6,2,8], [3,1,9,4]]. Минимизируй общее время (задача о назначениях).

Челлендж 🔴

Задание 9: Докажи теорему двойственности: если primal задача max cᵀx при Ax≤b имеет оптимум z*, то dual задача min bᵀy при Aᵀy≥c тоже имеет оптимум z*. Что это означает экономически?

Задание 10: Создай LASSO регрессию с нуля, используя только linprog из scipy. Данные: X = [[1,2],[3,1],[2,3]], y = [5,7,8], λ = 0.1. Сравни с sklearn.linear_model.Lasso.

Задание 11: Google Ads задача: максимизируй CTR при бюджете. У тебя n ключевых слов, cᵢ — цена клика, rᵢ — CTR. Как учесть, что CTR падает с ростом показов по логарифмическому закону?

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

❌ Ошибка: Забывают ограничение неотрицательности x ≥ 0 ✅ Правильно: Всегда проверяй, что переменные неотрицательны 💡 Почему: В реальности нельзя производить -10 смартфонов

❌ Ошибка: Думают, что оптимум всегда в угловой точке ✅ Правильно: Это верно только для выпуклых задач LP 💡 Почему: Невыпуклые задачи могут иметь локальные оптимумы

❌ Ошибка: Используют LP для нелинейных целевых функций ✅ Правильно: LP только для линейных f(x) = cᵀx 💡 Почему: Нелинейные задачи требуют других методов (квадратичное, выпуклое программирование)

❌ Ошибка: Не проверяют ограниченность допустимой области ✅ Правильно: Убедись, что область не уходит в бесконечность 💡 Почему: Неограниченная область → неограниченная прибыль (нереально!)

❌ Ошибка: Путают максимизацию и минимизацию в dual задаче ✅ Правильно: max cᵀx ↔ min bᵀy (dual меняет направление) 💡 Почему: Экономический смысл: максимизация прибыли ↔ минимизация затрат

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

✅ LP = максимизация/минимизация линейной функции при линейных ограничениях ✅ Оптимум всегда в угловой точке допустимой области (если существует) ✅ Симплекс-метод = умный перебор угловых точек ✅ В ML: SVM, LASSO, квантильная регрессия используют LP

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

Откуда пришли: Системы линейных неравенств (урок 279) — база для построения допустимой области

Куда ведет:

• Квадратичное программирование (SVM с мягкими отступами)
• Выпуклая оптимизация (градиентный спуск)
• Целочисленное программирование (комбинаторная оптимизация)
• Теория игр (поиск равновесий)