Перейти к основному содержимому

Решение задач оптимизации в коде

НЕ ОБЯЗАТЕЛЬНОВ РАЗРАБОТКЕ
Инженеру Архитектору

Роль этой главы в разделе​

Это завершающий мост между математической моделью и рабочим инструментом. Главная цель — переносить постановку в код осознанно — понимать, откуда взялись массивы коэффициентов, что означают статусы солвера и как проверять корректность ответа.

В инженерной практике этот переход чаще всего ломается из-за ошибок в коде — неверный знак неравенства, порядок коэффициентов или границы переменных. Поэтому акцент здесь на дисциплине постановки, проверках и интерпретации результата.

Если после главы вы можете воспроизвести путь "текст задачи -> матрицы -> решение -> проверка ограничений -> вывод для бизнеса", значит раздел освоен на рабочем уровне.

Ручной симплекс и метод потенциалов нужны для понимания алгоритма. В проектах ЗЛП решают библиотеками — они масштабируются на тысячи переменных и используют устойчивые реализации (двухфазный старт, pivoting, иногда метод внутренней точки).

Эта статья — мост между постановкой и Python для анализа данных.

Что вы задаёте солверу​

  1. Вектор c — коэффициенты цели (для max в linprog — минус коэффициенты).
  2. A_ub, b_ub — каждая строка — a₁x₁ + … ≤ b.
  3. A_eq, b_eq — равенства (если есть).
  4. bounds — нижняя/верхняя граница каждой переменной (часто (0, None)).
  5. Проверка знаков — ограничение ≥ в задаче min часто переводят в ≤ умножением на −1 (см. введение).
// Из текста задачи в массивы для солвера (пекарня: max 3x1 + 2x2)

цель_c := [-3, -2]                    // linprog ищет min, для max — минус коэффициенты
ограничения_A := [[2, 1], [1, 1]]
правая_часть_b := [100, 80]
границы := [(0, бесконечность), (0, бесконечность)]

ответ := Солвер_Линейный(цель_c, ограничения_A, правая_часть_b, границы)

если ответ.статус = "оптимум" то
  для каждого i проверить A[i]·x ≤ b[i]
  вывести x1, x2, прибыль := 3·x1 + 2·x2
иначе
  разобрать: несовместно / неограничено / ошибка постановки
конец

Справочно на Python (scipy.optimize.linprog) — ниже в статье.

Интерактив перед запуском кода​

Сначала подберите рабочую постановку в браузере, потом перенесите эти коэффициенты в linprog.

Рекомендуемая последовательность —

  1. Настройте цель и ограничения в интерактиве.
  2. Убедитесь, что найден хотя бы один допустимый план.
  3. Зафиксируйте значения c1, c2, b1, b2 и проверочный план (x1, x2).
  4. Только после этого переносите данные в массивы c, A_ub, b_ub в Python.

Play ITЗагрузка интерактивного демо…

Как использовать результат после демо —

  • если интерактив показывает недопустимость, код почти наверняка тоже вернёт infeasible;
  • при расхождении интерактива и кода проверьте знаки и порядок коэффициентов в матрицах;
  • если решение в коде отличается немного, это часто вопрос численной точности и формата округления.

Ниже в разделе linprog используйте эти же числа, чтобы быстро убедиться, что пайплайн "модель -> солвер -> интерпретация" работает корректно.

SciPy — linprog​

Функция scipy.optimize.linprog принимает задачу в форме минимизации —

min  cᵀx
при  A_ub x ≤ b_ub
     A_eq x = b_eq
     lb ≤ x ≤ ub

Для max Z = cᵀx передают c_min = -c.

Пример — станки и сырьё​

Та же задача, что в введении —

max  3x₁ + 2x₂
2x₁ +  x₂ ≤ 8
 x₁ + 2x₂ ≤ 8
x₁, x₂ ≥ 0

Код ITЗагрузка примера кода…

method="highs" (по умолчанию в новых SciPy) — современный солвер; внутри не «ваша» симплекс-таблица с листа, но двойственные оценки доступны в res (см. документацию версии).

На что смотреть в ответе​

ПолеСмысл
successнайден ли оптимум
xзначения переменных
funзначение минимизируемой цели
slackзапасы по неравенствам A_ub x ≤ b
messageнесовместность, неограниченность и т.д.

Всегда подставляйте x в исходные ограничения — как после ручного симплекса.

Ограничение "не меньше" (диета из введения)​

Задача — min 40x₁ + 30x₂ при 2x₁ + x₂ ≥ 12, x₁ + 3x₂ ≥ 18, x ≥ 0.

Умножаем каждое ≥ на −1, получаем форму ≤ для linprog —

−2x₁ − x₂ ≤ −12
−x₁ − 3x₂ ≤ −18
c = [40, 30]
A_ub = [[-2, -1], [-1, -3]]
b_ub = [-12, -18]
bounds = [(0, None), (0, None)]
res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method="highs")
# res.fun — минимальная стоимость; res.x — порции x₁, x₂

Частая ошибка — забыть минус у b_ub — солвер сообщит о несовместности или неверном плане.

Сообщения linprog и что они значат​

message (типично)Действие
Optimization successfulподставить x, сравнить с ручным примером
The problem is unboundedпроверить знаки и лишние ограничения
The problem is infeasibleпротиворечивые строки A, баланс supply/demand
Iteration limitупростить модель, сменить метод, проверить масштаб коэффициентов

Постановка из "бизнес-языка"​

Алгоритм перевода —

  1. Назвать переменные (x₁ — объём продукта A).
  2. Записать линейную цель.
  3. Каждое ограничение → строка A, элемент b.
  4. Границы x → bounds (по умолчанию x ≥ 0).
  5. Выбрать min или max (знак c).

Нелинейные тарифы, целые количества серверов, бинарные "включить/выключить" — не linprog; нужны milp (целочисленное) или другие солверы.

Google OR-Tools​

Библиотека OR-Tools (ortools.linear_solver) подходит для LP/MIP в продакшене —

  • выбор backend — GLOP (LP), CBC, SCIP (MIP);
  • удобно для назначения, маршрутизации, расписаний.

Типичный паттерн — solver = pywraplp.Solver.CreateSolver("GLOP"), переменные NumVar, ограничения Add, цель Maximize.

Документация Google OR-Tools — эталон для инженерных задач; энциклопедию не дублируем построчно, но после раздела 3.12 вы понимаете, что задаёте солверу.

Скелет OR-Tools (LP)​

Код ITЗагрузка примера кода…

Здесь NumVar(0, inf) — то же, что bounds=(0, None) в SciPy; Add — строка A; Maximize — цель без смены знака (в отличие от linprog, где max через min(-c)).

Excel / LibreOffice Solver​

Тот же ЗЛП — ячейки — переменные, формула — цель, ограничения через "Solver". Полезно аналитикам; для CI/CD и больших данных — код.

Когда что использовать​

СитуацияИнструмент
Учебный разбор, 2–5 переменныхграфика, симплекс
Скрипт, прототип, ≤ сотни переменныхscipy.optimize.linprog
MIP, логистика, планированиеOR-Tools, Gurobi, CPLEX
ML-обучение (нелинейно)PyTorch / JAX, не LP

Ограничения численного решения​

  • Округление — почти оптимальные x могут чуть нарушать ограничения на 1e-9 — в продакшене округляют и проверяют.
  • Плохая шкала — коэффициенты 10⁻⁶ и 10⁹ в одной задаче — нормируйте единицы.
  • Несовместность — success=False — пересмотрите модель, не "крутите M" как на бумаге.

Инженерный workflow для production-модели​

  1. Формализация — собрать модель в явных структурах данных (переменные, ограничения, коэффициенты).
  2. Валидация — автотесты на маленьких сценариях с известным ответом.
  3. Решение — запуск солвера с тайм-аутом и логированием статуса.
  4. Проверка результата — допустимость, значение цели, sanity-check бизнес-ограничений.
  5. Мониторинг — хранить метрики оптимизаций (время, gap, частота infeasible).

Такой pipeline делает оптимизацию повторяемой и безопасной для CI/CD на уровне команды.

Когда переходить от LP к MIP​

Переход обязателен, если переменные имеют логический или целочисленный смысл —

  • число серверов, машин, сотрудников;
  • бинарный выбор "включить/не включить";
  • пороговые условия и дискретные пакеты ресурсов.

LP часто даёт быстрый ориентир, но дробные ответы в таких задачах нельзя внедрять напрямую без целочисленного этапа.

Чувствительность (связь с двойственностью)​

В ответе linprog (зависит от версии SciPy) могут быть двойственные значения ограничений — аналог yᵢ* из статьи 6 — насколько изменится оптимум при bᵢ → bᵢ + Δ. Для малых Δ в ЛП часто ΔZ ≈ yᵢ* · Δbᵢ. Это основа what-if анализа в Excel Solver и в планировании мощностей.

Связь с разделом​

Тема в кодеТеория
A_ub, b_ubстандартная форма Математическое программирование — введение и постановка задач
slack в ответедвойственность Двойственность в линейном программировании
сеть supply/demandтранспортная Транспортная задача
dp[t][s]Беллман Динамическое программирование и уравнение Беллмана

Итоги раздела · Чек-лист

Содержание