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

НЕ ОБЯЗАТЕЛЬНО

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

Ручной симплекс и метод потенциалов нужны для понимания и экзамена. В проектах ЗЛП решают библиотеками: они масштабируются на тысячи переменных и используют устойчивые реализации (двухфазный старт, 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 (см. введение).

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

from scipy.optimize import linprog

# min -Z  =>  c = [-3, -2]
c = [-3, -2]
A_ub = [
    [2, 1],
    [1, 2],
]
b_ub = [8, 8]
bounds = [(0, None), (0, None)]

res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method="highs")

if res.success:
    x1, x2 = res.x
    z = -res.fun  # вернули max
    print(x1, x2, z)  # ожидаем ~2.666..., 2.666..., 13.333...
else:
    print(res.message)

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)

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver.CreateSolver("GLOP")
x1 = solver.NumVar(0, solver.infinity(), "x1")
x2 = solver.NumVar(0, solver.infinity(), "x2")
solver.Add(2 * x1 + x2 <= 8)
solver.Add(x1 + 2 * x2 <= 8)
solver.Maximize(3 * x1 + 2 * x2)
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
    print(x1.solution_value(), x2.solution_value(), solver.Objective().Value())

Здесь 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» как на бумаге.

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

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

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

Тема в коде	Теория
A_ub, b_ub	стандартная форма 1
slack в ответе	двойственность 6
сеть supply/demand	транспортная 7
dp[t][s]	Беллман 8

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

---