Математическое программирование — введение и постановка задач

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Архитектору Инженеру

Не путать с «программированием»

Математическое программирование (англ. mathematical programming) — это поиск лучшего решения при ограничениях: максимум прибыли, минимум затрат, оптимальный маршрут. Слово «программирование» здесь историческое (план, программа действий), а не написание кода — хотя результаты потом реализуют в ПО.

Динамическое программирование — два смысла

В разделе 8 — уравнение Беллмана и поэтапная оптимизация (исследование операций). В разделе Алгоритмы и лаборатории — мемоизация и таблицы для задач вроде рюкзака. Термин один, области разные; мы явно разводим их по контексту.

Математическое программирование (МП, исследование операций) отвечает на вопрос: какое решение из допустимых будет лучшим по заданному критерию? В IT это не абстрактная школьная алгебра: те же постановки лежат в планировании релизов, распределении нагрузки, логистике, подборе рекламных бюджетов и в солверах вроде 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	Выпуклость, свойства, графический метод	2
3	Метод Жордана–Гаусса	3
4	Симплекс-метод и таблицы	4
5	Искусственный базис и M-метод	5
6	Двойственность	6
7	Транспортная задача	7
8	Динамическое программирование, Беллман	8
9	Решатели в коде	9

Общая схема задачи оптимизации

Любая задача МП в «инженерном» виде состоит из трёх частей:

1. Переменные решения x₁, …, xₙ — то, что мы выбираем (объёмы производства, маршруты, доли бюджета).
2. Целевая функция F(x) — что улучшаем (прибыль, время, риск, отклонение от плана).
3. Ограничения — что допустимо (ресурсы, законы, SLA, физические лимиты).

Запись в общем виде:

найти   x = (x₁, …, xₙ)
чтобы   F(x) → max   (или → min)
при     gᵢ(x) ≤ 0,  i = 1..m
        hⱼ(x) = 0,  j = 1..k
        (часто ещё x ≥ 0)

Допустимое множество — все x, удовлетворяющие ограничениям. Оптимальное решение — допустимая точка, где F лучше, чем в любой другой допустимой точке (глобальный оптимум; локальный — лучший только в окрестности).

Разбор общей записи по строкам

найти   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)

Зачем единая форма

Симплекс-метод и программные решатели ожидают предсказуемую структуру: где базис, где столбцы единичной матрицы. Приведение к стандарту — подготовка к алгоритму. Подробно — в статьях 3 и 4.

Матричная запись

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 — способ не писать плюсы вручную, когда переменных десятки.

Пошаговое приведение «смешанной» постановки

Исходная задача в «словах»:

max Z = 5x₁ + 4x₂
x₁ + x₂ ≤ 10
2x₁ + x₂ ≥ 6
x₁, x₂ ≥ 0

Шаг	Действие	Результат
1	Цель уже max	коэффициенты (5, 4)
2	≤ 10	добавить s₁ ≥ 0: x₁ + x₂ + s₁ = 10
3	≥ 6	умножить на −1 (чтобы получить ≤): −2x₁ − x₂ ≤ −6, или ввести surplus u₁: 2x₁ + x₂ − u₁ = 6, u₁ ≥ 0
4	Проверить RHS	если после шага 3 RHS отрицательный — нужен M-метод / фаза 1
5	Записать таблицу	столбцы x₁, x₂, s₁, u₁, базис из slack/искусственных

Для солвера linprog (min) часто оставляют как есть: c = [-5,-4], A_ub для ≤, A_ub с отрицательными коэффициентами для ≥ после умножения на −1, b_ub согласован по знаку — см. статью 9.

Пример — план производства двух изделий

Сюжет. Цех выпускает два типа деталей — 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 / облака	линейные затраты + квоты
Планирование спринта (упрощённо)	целочисленные переменные «взять задачу или нет»
Кратчайший путь / поток в сети	специальные структуры; транспортная — частный случай
Кэширование, разбиение на этапы	динамическое программирование (8)

Полный перечень промышленных моделей (стохастика, робастность, многокритериальность) выходит за рамки базового курса; здесь закладывается фундамент, на который опираются солверы и дальнейшее чтение.

Когда ЗЛП «хватает», а когда нет

Подходит, если зависимости в модели реально близки к линейным на рабочем диапазоне: затраты пропорциональны объёму, лимиты — суммарные.

Не подходит без усложнения модели, если:

• есть пороги и скидки (нелинейная цена);
• переменные должны быть целыми (число серверов, бинарный «включить фичу»);
• эффект синергии (x₁·x₂).

Тогда переходят к целочисленному, нелинейному МП или к эвристикам — с пониманием, что оптимум может быть только приближённым.

Краткий словарь раздела

Термин	Значение
План	допустимое решение
Базис	набор переменных, через которые выражают остальные в текущей таблице
Опорный план	допустимое решение в «вершине» (для транспортной — заполненная таблица с m+n−1 клетками)
Двойственная задача	другая ЗЛП, связанная с исходной; двойственные переменные — «тени цен» ресурсов
Симплекс-таблица	компактная запись эквивалентной системы для итераций
Slack (добавочная)	«недоиспользованный» запас ресурса в неравенстве ≤
Surplus (избыточная)	«перевыполнение» нормы в ограничении ≥
RHS (right-hand side)	правая часть ограничения — число b в … ≤ b
Коэффициент цели cⱼ	на сколько изменится Z, если увеличить xⱼ на 1 (в линейной модели, пока базис тот же)

Типичные ошибки при постановке

Ошибка	Как избежать
Перепутали max и min	затраты и время — обычно min; выручка — max
Разные единицы в одной строке	часы и килограммы в одном ограничении без перевода — бессмыслица
Забыли x ≥ 0	если переменная может быть отрицательной (баланс), введите замену x = x⁺ − x⁻
Нелинейность «по привычке»	скидка «после 100 штук» — уже другой класс задач

Что дальше

1. Теория и графический метод — выпуклые множества, почему оптимум ЗЛП часто в вершине, разбор примера со станками на плоскости.
2. Жордан–Гаусс — приведение системы к виду, удобному для старта симплекса.
3. Практика в коде — статья 9.

---