Математическое программирование — введение и постановка задач
Зачем нужна именно эта вводная глава
Эта статья кажется "базовой", но фактически это фундамент всего раздела — если здесь не выстроены понятия "переменная - цель - ограничение", дальше симплекс, двойственность и код будут восприниматься как набор механических шагов без смысла.
Главная задача главы — научить вас видеть за формулами прикладную конструкцию — что мы выбираем, что пытаемся улучшить и какие реальные ограничения среды нас сдерживают. Когда этот каркас понятен, любая новая задача (даже в другой отрасли) разбирается по тем же правилам.
Читайте так — каждый новый термин связывайте с бытовым или рабочим сценарием, каждую формулу — с конкретной интерпретацией коэффициентов. Это снижает "математический шум" и превращает материал в рабочий инструмент.
Математическое программирование (англ. mathematical programming) — это поиск лучшего решения при ограничениях — максимум прибыли, минимум затрат, оптимальный маршрут.
Слово "программирование" здесь историческое — речь о плане и программе действий. Результаты затем реализуют в ПО.
В разделе Динамическое программирование и уравнение Беллмана — уравнение Беллмана и поэтапная оптимизация (исследование операций).
В разделе Алгоритмы и лаборатории — мемоизация и таблицы для задач вроде рюкзака. Термин один, области разные; мы явно разводим их по контексту.
Математическое программирование (МП, исследование операций) отвечает на вопрос — какое решение из допустимых будет лучшим по заданному критерию? В инженерной практике те же постановки встречаются в планировании релизов, распределении нагрузки, логистике и в солверах вроде scipy.optimize или Google OR-Tools.
Предварительно полезны — линейная алгебра, дискретная математика (графы для транспортных и сетевых задач). Глубокая алгебра для старта не обязательна — ниже — минимум обозначений, которого хватит, чтобы читать остальные статьи раздела.
Как читать записи, если математика давно не вспоминалась
В этом разделе встречаются буквы с индексами, суммы и знаки сравнения. Их можно читать как "таблицу в Excel", только записанную компактно.
| Запись | Читается по-русски | Простой смысл |
|---|---|---|
x₁, x₂ | "икс один", "икс два" | переменные — числа, которые мы подбираем (объёмы, доли, маршруты) |
3x₁ + 2x₂ | "три икс один плюс два икс два" | линейная цель — прибыль или затраты складываются из вкладов каждой переменной |
≤ 8 | "меньше или равно восьми" | потолок — суммарный расход ресурса не больше запаса |
≥ 0 | "неотрицательные" | отрицательный объём производства в модели обычно запрещён |
max Z / min Z | максимизировать / минимизировать Z | Z — значение цели (прибыль, стоимость, время) в выбранном плане |
cᵀx | "цэ транспонированное на икс" | сокращение для c₁x₁ + … + cₙxₙ — та же цель в компактном виде |
Ax ≤ b | "А икс меньше или равно бэ" | несколько ограничений сразу — каждая строка матрицы A — одно правило |
Линейность в бытовом смысле — если удвоить выпуск изделия A, удваивается и его расход станка (без "скидки за объём" и без квадратов). В формулах — только умножение переменной на число-коэффициент, без x₁², 1/x₁, sin(x₁).
План — конкретный набор чисел (x₁, …, xₙ), который удовлетворяет всем ограничениям. Оптимальный план — среди допустимых тот, у которого цель Z лучше всех (больше при max, меньше при min).
В задаче max Z = 5x₁ + 4x₂ при x₁=1, x₂=2 подставьте: Z = 5·1 + 4·2 = 13. Ограничение x₁ + x₂ ≤ 10 при этих значениях: 1+2=3 ≤ 10 — план допустим по этому правилу (нужно ещё проверить остальные).
Маршрут по разделу
| № | Тема | Статья |
|---|---|---|
| 1 | Постановка, формы ЗЛП | эта статья |
| 2 | Выпуклость, свойства, графический метод | Выпуклые множества, свойства ЗЛП и графический метод |
| 3 | Метод Жордана–Гаусса | Метод Жордана–Гаусса в задачах линейного программирования |
| 4 | Симплекс-метод и таблицы | Симплекс-метод и симплекс-таблицы |
| 5 | Искусственный базис и M-метод | Искусственный базис и M-метод |
| 6 | Двойственность, двойственный симплекс | Двойственность в линейном программировании |
| 7 | Транспортная задача | Транспортная задача |
| 8 | Динамическое программирование, Беллман | Динамическое программирование и уравнение Беллмана |
| 9 | Решатели в коде | Решение задач оптимизации в коде |
Термины раздела — в итогах и терминологии.
Общая схема задачи оптимизации
Любая задача МП в "инженерном" виде состоит из трёх частей —
- Переменные решения
x₁, …, xₙ— то, что мы выбираем (объёмы производства, маршруты, доли бюджета). - Целевая функция
F(x)— что улучшаем (прибыль, время, риск, отклонение от плана). - Ограничения — что допустимо (ресурсы, законы, SLA, физические лимиты).
Запись в общем виде —
АЛГОРИТМ ЗадачаОптимизации()
выбрать числа x1, x2, …, xn // план: объёмы, маршруты, доли бюджета
пока не все_ограничения_выполнены(x)
отбросить этот план
конец
среди оставшихся максимизировать Цель(x) // или минимизировать затраты
вернуть лучший_план
КОНЕЦ
найти x = (x₁, …, xₙ)
чтобы F(x) → max (или → min)
при gᵢ(x) ≤ 0, i = 1..m
hⱼ(x) = 0, j = 1..k
(часто ещё x ≥ 0)
Справочно — та же пекарня в формулах: max Z = 3x₁ + 2x₂ при 2x₁ + x₂ ≤ 100, x₁ + x₂ ≤ 80, x₁, x₂ ≥ 0.
Допустимое множество — все x, удовлетворяющие ограничениям. Оптимальное решение — допустимая точка, где F лучше, чем в любой другой допустимой точке (глобальный оптимум; локальный — лучший только в окрестности).
Схема построения экономико-математической модели
В учебниках по ЗЛП экстремальную задачу из текста переводят в формулы по одному и тому же каркасу —
- Выбрать переменные
xⱼ— числа, однозначно задающие план (объёмы продукции, килограммы корма, объёмы перевозок). - Записать ограничения — линейные равенства и неравенства, отражающие запасы, нормы, балансы.
- Ввести целевую функцию
Z— критерий, который нужно максимизировать или минимизировать.
Дальше модель приводят к стандартной или канонической форме для симплекса или солвера.
Разбор общей записи по строкам
найти x = (x₁, …, xₙ)
чтобы F(x) → max (или → min)
при gᵢ(x) ≤ 0, i = 1..m
hⱼ(x) = 0, j = 1..k
(часто ещё x ≥ 0)
| Строка | Что означает на практике |
|---|---|
найти x | подобрать числа (объёмы, маршруты, доли бюджета) |
F(x) → max | сделать прибыль/полезность как можно больше |
gᵢ(x) ≤ 0 | семейство ограничений-"потолков" (ресурсы, квоты, SLA) |
hⱼ(x) = 0 | жёсткие равенства (баланс "вошло = вышло", закон сохранения) |
x ≥ 0 | переменные не могут быть отрицательными в этой модели |
В учебниках по ЗЛП чаще пишут Ax ≤ b и x ≥ 0 — это тот же смысл, только ограничения записаны в виде неравенств с неотрицательными правыми частями b.
| Вид задачи | Целевая функция и ограничения | Типичный метод |
|---|---|---|
| Линейное программирование (ЗЛП) | всё линейно | симплекс, внутренние точки |
| Целочисленное (ЗЦЛП) | линейно + часть переменных целые | отсечения, ветви и границы |
| Квадратичное | квадратичная цель, линейные ограничения | специализированные солверы |
| Нелинейное | нелинейные F или g | градиентные, эвристики |
| Динамическое (Беллман) | решение по этапам | уравнение Беллмана |
В этом разделе основной упор — на линейное программирование и связанные классические алгоритмы, плюс динамическое программирование в смысле Беллмана.
Линейное программирование (ЗЛП)
Задача линейного программирования — F и все ограничения линейны по переменным — только суммы вида a₁x₁ + … + aₙxₙ, без x₁², sin(x), произведений x₁·x₂.
Стандартная форма максимизации (часто используют в учебниках и в симплекс-таблицах) —
max Z = c₁x₁ + c₂x₂ + … + cₙxₙ
при a₁₁x₁ + … + a₁ₙxₙ ≤ b₁
…
aₘ₁x₁ + … + aₘₙxₙ ≤ bₘ
x₁, …, xₙ ≥ 0
Минимизацию сводят к максимизации: min F ⇔ max (−F) (с теми же ограничениями, если только меняется знак цели).
Другие формы записи
| Форма | Суть | Как привести к стандарту |
|---|---|---|
| Каноническая | только равенства =, переменные ≥ 0 | неравенства ≤ → добавочные (slack) переменные; ≥ → избыточные (surplus) |
С ограничениями ≥ | "не меньше" ресурса | surplus-переменная со знаком "минус" в строке или умножение строки на −1 |
| Свободные переменные (любой знак) | баланс, разница доход−расход | замена x = x⁺ − x⁻, обе ≥ 0 |
| Минимизация | затраты, время | min Z → max (−Z) |
Приведение неравенств к равенствам (slack, surplus), смешанные ограничения и каноническая форма — в главе 3.
Матричная запись
max cᵀx
при Ax ≤ b
x ≥ 0
Здесь c — коэффициенты цели, A — матрица ограничений, b — правые части (запасы ресурсов). Одна строка A — одно ограничение.
Пример чтения одной строки. Пусть c = (5, 4), первая строка A — (1, 1), b₁ = 10. Тогда —
- цель:
Z = 5x₁ + 4x₂(каждая единицаx₁даёт +5 кZ); - ограничение:
1·x₁ + 1·x₂ ≤ 10, то естьx₁ + x₂ ≤ 10— сумма двух величин не больше 10.
Вектор x = (x₁, x₂) — столбец значений переменных; запись cᵀx — способ не писать плюсы вручную, когда переменных десятки.
Три классических примера постановки
Ниже — три шаблона постановки. Числа можно менять, структура остаётся той же.
Сюжет. Выпускают n видов продукции Pⱼ, расходуя m видов сырья Sᵢ с запасами bᵢ. На единицу Pⱼ уходит aᵢⱼ единиц Sᵢ, прибыль с единицы — cⱼ.
Переменные — xⱼ ≥ 0 — объём выпуска продукта j.
max Z = c₁x₁ + … + cₙxₙ
при a₁₁x₁ + … + a₁ₙxₙ ≤ b₁
…
aₘ₁x₁ + … + aₘₙxₙ ≤ bₘ
xⱼ ≥ 0
В табличном виде — строки "сырьё", столбцы "продукты", в ячейке aᵢⱼ, справа запас bᵢ, внизу прибыль cⱼ.
2. Рацион питания (диета, смесь)
Сюжет. Смесь из кормов P₁, P₂, P₃ должна содержать не меньше норм по питательным веществам Sᵢ, стоимость 1 кг корма j — cⱼ. Нужно минимизировать стоимость.
Переменные — xⱼ — килограммы корма j.
min Z = c₁x₁ + c₂x₂ + c₃x₃
при a₁₁x₁ + a₁₂x₂ + a₁₃x₃ ≥ b₁ (норма по веществу 1)
…
a₅₁x₁ + … + a₅₃x₃ ≥ b₅
xⱼ ≥ 0
Типичная таблица — строки "питательные вещества", столбцы "корма", нормы bᵢ, цены cⱼ в последней строке. Ограничения ≥ — признак задачи на минимум затрат при обязательных нормах.
3. Транспортная задача
Перевозки от поставщиков к потребителям при линейных тарифах — частный случай ЗЛП со своей таблицей и алгоритмами. Полная постановка, балансировка и метод потенциалов — в главе 7.
Пример — план производства двух изделий (частный случай n = 2)
Сюжет. Цех выпускает два типа деталей — A и B. Нужно выбрать объёмы x₁, x₂ (тысячи штук в месяц), чтобы максимизировать прибыль, не превысив фонд времени станков и склад сырья.
| Ресурс | Норма на 1000 шт. A | Норма на 1000 шт. B | Запас |
|---|---|---|---|
| Станки (ч) | 2 | 1 | 8 |
| Сырьё (кг) | 1 | 2 | 8 |
Прибыль — 3 у.е. за 1000 шт. A, 2 у.е. за 1000 шт. B.
Переменные — x₁ — тысячи шт. A, x₂ — тысячи шт. B.
Цель —
max Z = 3x₁ + 2x₂
Ограничения —
2x₁ + x₂ ≤ 8 (станки)
x₁ + 2x₂ ≤ 8 (сырьё)
x₁, x₂ ≥ 0
Разбор левой части первого ограничения. Если выпустить x₁ = 2 (тыс. шт. A) и x₂ = 1 (тыс. шт. B) —
2x₁ + x₂ = 2·2 + 1 = 5 ≤ 8
Станки заняты на 5 часов из 8 — запас есть. Второе ограничение — x₁ + 2x₂ = 2 + 2 = 4 ≤ 8 — сырьё тоже не исчерпано. План (2, 1) допустим — прибыль 3·2 + 2·1 = 8. Оптимум в статье 2 — около 13,33.
План (x₁, x₂) | Z = 3x₁ + 2x₂ | Станки 2x₁+x₂ | Сырьё x₁+2x₂ |
|---|---|---|---|
| (0, 0) | 0 | 0 ≤ 8 ✓ | 0 ≤ 8 ✓ |
| (4, 0) | 12 | 8 ≤ 8 ✓ | 4 ≤ 8 ✓ |
| (8/3, 8/3) | 40/3 ≈ 13,33 | 8 ✓ | 8 ✓ |
Это типичная учебная ЗЛП на две переменные — её удобно решать графически (статья 2), а затем проверить симплексом (статья 4).
Интерпретация в IT — те же числа могут означать "сколько инстансов сервиса A и B поднять", если каждый потребляет CPU/RAM по таблице, а цель — максимизировать обработанные запросы при лимите кластера.
Пример — смешивание (диета, два компонента)
Частный случай рациона из блока выше — два корма, две нормы. Нужно набрать смесь так, чтобы минимизировать стоимость, но выполнить нормы по нутриентам.
min Z = 40x₁ + 30x₂
при 2x₁ + x₂ ≥ 12 (белок)
x₁ + 3x₂ ≥ 18 (углеводы)
x₁, x₂ ≥ 0
Здесь ограничения "≥" — типичный повод ввести избыточные переменные или переписать строку (см. статью 3). Для симплекса часто переходят к эквивалентной задаче максимизации с преобразованными строками.
Смысл коэффициентов в диете. Строка 2x₁ + x₂ ≥ 12 читается так — в смеси из x₁ порций продукта 1 и x₂ порций продукта 2 суммарный белок (условно — 2 г на порцию первого + 1 г на порцию второго) должен быть не меньше 12. Цель 40x₁ + 30x₂ — минимизировать стоимость (40 и 30 — цены порций). Переменные задают "сколько порций каждого компонента взять"; белок считается линейно через нормы в строках ограничений.
Проверка допустимости на пальцах — план x₁=6, x₂=0 даёт белок 2·6+0=12 (ровно норма) и углеводы 6+0=6 < 18 — план недопустим по второму ограничению. Значит, одной "нормы по белку" мало — нужен баланс всех строк.
Связь с задачами в разработке
| Прикладная задача | Аналог в ЗЛП / МП |
|---|---|
| Распределение задач по серверам | переменные "сколько нагрузки на узел", линейные лимиты CPU/RAM |
| Выбор тарифов CDN / облака | линейные затраты + квоты |
| Планирование спринта (упрощённо) | целочисленные переменные "взять задачу или нет" |
| Кратчайший путь / поток в сети | специальные структуры; транспортная — частный случай |
| Кэширование, разбиение на этапы | динамическое программирование (Динамическое программирование и уравнение Беллмана) |
Полный перечень промышленных моделей (стохастика, робастность, многокритериальность) выходит за рамки базового курса; здесь закладывается фундамент, на который опираются солверы и дальнейшее чтение.
Когда применять ЗЛП и когда выбирать другой класс моделей
Подходит, если зависимости в модели реально близки к линейным на рабочем диапазоне — затраты пропорциональны объёму, лимиты — суммарные.
Не подходит без усложнения модели, если —
- есть пороги и скидки (нелинейная цена);
- переменные должны быть целыми (число серверов, бинарный "включить фичу");
- эффект синергии (
x₁·x₂).
Тогда переходят к целочисленному, нелинейному МП или к эвристикам — с пониманием, что оптимум может быть только приближённым.
Типичные ошибки при постановке
| Ошибка | Как избежать |
|---|---|
Перепутали max и min | затраты и время — обычно min; выручка — max |
| Разные единицы в одной строке | часы и килограммы в одном ограничении без перевода — бессмыслица |
Забыли x ≥ 0 | если переменная может быть отрицательной (баланс), введите замену x = x⁺ − x⁻ |
| Нелинейность "по привычке" | скидка "после 100 штук" — уже другой класс задач |
Практический шаблон постановки задачи
Когда формулируете новую модель из бизнес-текста, удобно идти по фиксированному шаблону —
- Цель в одном предложении — что оптимизируем (прибыль, затраты, срок, риск).
- Переменные с единицами — что означает каждая
x, в каких единицах измеряется. - Ограничения по группам — ресурсы, обязательства по спросу, технологические правила.
- Проверка размерностей — в каждой строке должны складываться сопоставимые величины.
- Проверка знаков —
max/min, тип≤/≥/=, неотрицательность или свободные переменные. - Тестовый план — подставьте 1-2 простых плана и убедитесь, что модель ведёт себя ожидаемо.
Хорошая модель отвечает на вопросы "какой план лучший" и "почему именно он" — какие ограничения стали узкими местами, какие ресурсы недоиспользованы, как меняется результат при небольшом изменении входных данных.
Интерактив — постановка и поиск оптимума
Попробуйте настроить задачу и сразу проверить, как меняется оптимальный план при новых коэффициентах цели и лимитах ресурсов.
Мини-сценарий перед запуском —
- Введите свою "бизнес-идею" через коэффициенты цели (
c1,c2) — что именно выгоднее системе. - Задайте реалистичные лимиты (
b1,b2) как ограничения ресурсов. - Подставьте тестовую точку
(x1, x2)и проверьте, допустима ли она. - Сравните ручной тест с автоматически найденным лучшим планом.
Play ITЗагрузка интерактивного демо…
Как читать результат —
- если тестовая точка недопустима, проверьте нарушение ресурсного ограничения в постановке;
- если оптимум резко уходит в одну переменную, значит ваша цель сильно асимметрична;
- если в лучшем плане один запас почти ноль, это потенциальное узкое место процесса.
Этот паттерн (постановка -> проверка допустимости -> оптимум) используйте как шаблон перед переходом к коду и симплексу.
Что дальше
- Теория и графический метод — выпуклые множества, почему оптимум ЗЛП часто в вершине, разбор примера со станками на плоскости.
- Жордан–Гаусс — приведение системы к виду, удобному для старта симплекса.
- Практика в коде — статья 9.