Решение задач оптимизации в коде
Математическая модель — это формализованное описание объекта, процесса или системы на языке математических соотношений, включающее переменные, параметры, целевую функцию и ограничения, причём она всегда является упрощённым отражением реальности, где выделены существенные связи и отброшены второстепенные детали; построение математической модели требует баланса между точностью и трактуемостью, и именно она служит мостом между абстрактной теорией и практическим принятием решений, позволяя проводить вычисления, прогнозировать поведение и искать оптимумы в таких областях, как экономика, инженерия и управление.
Это завершающий мост между математической моделью и рабочим инструментом. Главная цель — переносить постановку в код осознанно — понимать, откуда взялись массивы коэффициентов, что означают статусы солвера и как проверять корректность ответа.
Массив коэффициентов — это структурированная совокупность числовых значений, которые определяют величину влияния каждой переменной на соответствующие ограничения и целевую функцию в задаче оптимизации, причём этот массив обычно представляется в виде матрицы для ограничений и отдельного вектора для целевой функции; правильное формирование массива коэффициентов является критическим этапом подготовки задачи, поскольку даже малая ошибка в одном коэффициенте может привести к неверному решению, и именно этот массив является основным входным объектом для численных солверов.
Статус солвера — это итоговый код или сообщение, которое возвращает оптимизационный решатель после завершения своей работы, информирующее пользователя о том, достигнуто ли оптимальное решение, найдено ли допустимое решение, обнаружена ли неограниченность, несовместность или другие особые ситуации; интерпретация статуса солвера является обязательной частью работы с моделями, поскольку без неё численное значение решения не имеет практического смысла, и именно статус позволяет отличить корректно решённую задачу от случая, когда алгоритм остановился из-за превышения времени, ошибок округления или внутренних проблем.
Корректность ответа — это свойство полученного решения, означающее, что оно не только удовлетворяет формальным критериям оптимальности и допустимости, установленным солвером, но и согласуется с содержательным смыслом задачи, не содержит грубых численных аномалий и может быть воспроизведено при повторных вычислениях; проверка корректности включает сравнение с независимыми оценками, анализ чувствительности, проверку размерностей и логическую увязку с ожидаемым поведением системы, поскольку даже математически оптимальный ответ может быть практически неприемлемым из-за неучтённых факторов или ошибок в исходных данных.
В инженерной практике этот переход чаще всего ломается из-за ошибок в коде — неверный знак неравенства, порядок коэффициентов или границы переменных. Поэтому акцент здесь на дисциплине постановки, проверках и интерпретации результата.
Неравенство — это математическое соотношение между двумя выражениями, которое указывает, что одно из них больше, меньше, больше или равно, или меньше или равно другому, и в оптимизационных задачах неравенства служат основным инструментом для задания ограничений на переменные, отражающих ресурсные, технологические или нормативные лимиты; в отличие от равенств, неравенства создают полупространства допустимой области, и именно их совокупность формирует многогранник, внутри которого ведётся поиск оптимума, причём преобразование неравенств в равенства через добавление слак-переменных является стандартным этапом приведения задачи к канонической форме.
Порядок коэффициентов — это строго определённая последовательность, в которой коэффициенты при переменных перечисляются в векторах и строках матрицы, причём этот порядок должен быть согласован между целевой функцией, каждым ограничением и заданием границ переменных; нарушение порядка коэффициентов является одной из самых частых ошибок при постановке задачи в программные интерфейсы, поскольку солвер интерпретирует коэффициенты по позициям, и даже один смещённый элемент превращает задачу в совершенно другую, с иным решением или вообще без допустимого решения.
Границы переменных — это дополнительные односторонние или двусторонние ограничения, налагаемые непосредственно на каждую переменную решения, такие как неотрицательность, верхние и нижние пределы, которые часто выделяются отдельно от основных линейных ограничений из-за их простой структуры и частоты использования; задание границ является важной частью дисциплины постановки, поскольку они не только отражают физическую или экономическую природу переменных, но и улучшают численную стабильность солвера, сужая допустимую область и часто ускоряя сходимость алгоритмов.
Дисциплина постановки — это совокупность правил, стандартов и контрольных процедур, которые необходимо соблюдать при формулировке и вводе оптимизационной задачи в солвер, включая проверку размерностей, согласование порядка коэффициентов, корректное оформление неравенств, установку реалистичных границ и выбор подходящего метода решения; соблюдение этой дисциплины является залогом того, что численный ответ будет осмысленным, а время, потраченное на вычисления, не будет потеряно из-за банальных ошибок ввода, и она требует от аналитика не только математической грамотности, но и аккуратности, системности и понимания внутренней логики используемого программного обеспечения.
Проверка результата — это завершающий этап работы с оптимизационной моделью, заключающийся в подстановке найденных значений переменных обратно в ограничения и целевую функцию для подтверждения допустимости и правильности вычисленного экстремума, а также в сравнении полученного значения с ожидаемым диапазоном и анализом активных ограничений; эта проверка не является формальностью, поскольку численные методы могут давать малые нарушения ограничений из-за погрешностей округления, и только после такой верификации решение может быть принято к практическому использованию, причём полезно также выполнить повторный расчёт с другой начальной точкой или с другим солвером для подтверждения устойчивости.
Интерпретация результата — это процесс перевода формальных математических значений оптимальных переменных, теневых цен и статуса решения на язык исходной предметной области, будь то экономические показатели, технологические параметры или управленческие решения, причём интерпретация включает объяснение, почему именно такие значения получены, какие ресурсы оказались дефицитными, а какие избыточными, и какие изменения в модели могли бы привести к улучшению результата; без качественной интерпретации даже самое точное оптимальное решение остаётся бесполезным набором цифр, и именно этот этап связывает абстрактный расчёт с практическим действием.
Если после главы вы можете воспроизвести путь "текст задачи -> матрицы -> решение -> проверка ограничений -> вывод для бизнеса", значит раздел освоен на рабочем уровне.
Ручной симплекс и метод потенциалов нужны для понимания алгоритма. В проектах ЗЛП решают библиотеками — они масштабируются на тысячи переменных и используют устойчивые реализации (двухфазный старт, pivoting, иногда метод внутренней точки).
Эта статья — мост между постановкой и Python для анализа данных.
Что вы задаёте солверу
Вектор — это упорядоченный одномерный массив чисел, который в задачах оптимизации используется для представления столбца коэффициентов целевой функции, вектора правых частей ограничений, или самого набора переменных решения, причём векторы обладают свойствами сложения и умножения на скаляр, что позволяет записывать линейные выражения и ограничения в компактной матричной форме; в контексте линейного программирования различают вектор переменных, вектор целевых коэффициентов и вектор ресурсов, и работа с ними подчиняется правилам линейной алгебры, что делает их основным строительным блоком численных алгоритмов.
Коэффициент цели — это числовой множитель, стоящий перед соответствующей переменной в выражении целевой функции, который определяет вклад одной единицы данной переменной в общее значение критерия эффективности, причём положительный коэффициент для задачи максимизации означает, что увеличение переменной желательно, а отрицательный — нежелательно, и наоборот для минимизации; совокупность коэффициентов цели составляет вектор, который вместе с переменными задаёт направление и крутизну движения при оптимизации, а их значения непосредственно влияют на то, какая комбинация переменных будет признана оптимальной.
Границы — это в общем смысле пределы, внутри которых могут изменяться переменные или параметры модели, причём в оптимизации различают границы переменных, задаваемые непосредственно в виде неравенств, и границы допустимой области, определяемые системой ограничений; эти границы могут быть жёсткими, нарушение которых недопустимо, или мягкими, допускающими отклонения с определённым штрафом, и их анализ в постоптимизационном исследовании показывает, насколько решение устойчиво к изменениям входных данных и какие факторы являются лимитирующими.
- Вектор
c— коэффициенты цели (дляmaxвlinprog— минус коэффициенты). A_ub,b_ub— каждая строка —a₁x₁ + … ≤ b.A_eq,b_eq— равенства (если есть).bounds— нижняя/верхняя граница каждой переменной (часто(0, None)).- Проверка знаков — ограничение
≥в задаче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.
Рекомендуемая последовательность —
- Настройте цель и ограничения в интерактиве.
- Убедитесь, что найден хотя бы один допустимый план.
- Зафиксируйте значения
c1,c2,b1,b2и проверочный план(x1, x2). - Только после этого переносите данные в массивы
c,A_ub,b_ubв Python.
Play ITЗагрузка интерактивного демо…
Как использовать результат после демо —
- если интерактив показывает недопустимость, код почти наверняка тоже вернёт
infeasible; - при расхождении интерактива и кода проверьте знаки и порядок коэффициентов в матрицах;
- если решение в коде отличается немного, это часто вопрос численной точности и формата округления.
Ниже в разделе linprog используйте эти же числа, чтобы быстро убедиться, что пайплайн "модель -> солвер -> интерпретация" работает корректно.
SciPy — linprog
SciPy — это открытая библиотека языка программирования Python, предназначенная для научных и технических вычислений, которая включает в себя модуль оптимизации scipy.optimize с функцией linprog для решения задач линейного программирования, а также инструменты для нелинейной оптимизации, численного интегрирования, интерполяции и обработки сигналов; SciPy является одним из наиболее распространённых инструментов для быстрого прототипирования и решения учебных и малых промышленных задач благодаря своей доступности, интеграции с экосистемой Python и наличию разнообразных методов, хотя для крупных промышленных задач обычно используются более специализированные коммерческие или открытые солверы, такие как Gurobi, CPLEX или OR-Tools.
Функция 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 и что они значат
Сообщения linprog — это текстовые или числовые коды, возвращаемые функцией линейного программирования из библиотеки SciPy, которые информируют пользователя о статусе завершения алгоритма, например, Optimization terminated successfully при нахождении оптимума, Iteration limit reached при достижении предела итераций, Problem is unbounded при неограниченности целевой функции или Problem appears to be infeasible при несовместности ограничений; эти сообщения являются первой линией диагностики, и их внимательный разбор часто помогает выявить ошибки постановки, поскольку успешный статус не гарантирует содержательной корректности, но его отсутствие явно указывает на проблему в модели или параметрах.
message (типично) | Действие |
|---|---|
| Optimization successful | подставить x, сравнить с ручным примером |
| The problem is unbounded | проверить знаки и лишние ограничения |
| The problem is infeasible | противоречивые строки A, баланс supply/demand |
| Iteration limit | упростить модель, сменить метод, проверить масштаб коэффициентов |
Постановка из "бизнес-языка"
Алгоритм перевода —
- Назвать переменные (
x₁— объём продукта A). - Записать линейную цель.
- Каждое ограничение → строка
A, элементb. - Границы
x→bounds(по умолчаниюx ≥ 0). - Выбрать
minилиmax(знакc).
Нелинейные тарифы, целые количества серверов, бинарные "включить/выключить" — не linprog; нужны milp (целочисленное) или другие солверы.
Google OR-Tools
Google OR-Tools — это мощная открытая библиотека для решения оптимизационных задач, разработанная Google, которая поддерживает линейное программирование, целочисленное программирование, задачи маршрутизации, планирование, задачи о назначениях и многие другие классы моделей; OR-Tools предоставляет унифицированные интерфейсы для вызова различных солверов, включая GLPK, SCIP, а также собственные специализированные алгоритмы, и она широко используется как в академической среде, так и в индустриальных проектах благодаря своей гибкости, производительности и интеграции с языками C++, Python и Java, причём она особенно сильна в задачах дискретной оптимизации.
Библиотека 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)
LP — это общепринятая аббревиатура для линейного программирования, обозначающая класс оптимизационных задач, в которых целевая функция линейна, все ограничения также линейны, а переменные могут принимать непрерывные значения, причём для этого класса существуют эффективные полиномиальные алгоритмы, такие как симплекс-метод и методы внутренней точки; 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-модели
- Формализация — собрать модель в явных структурах данных (переменные, ограничения, коэффициенты).
- Валидация — автотесты на маленьких сценариях с известным ответом.
- Решение — запуск солвера с тайм-аутом и логированием статуса.
- Проверка результата — допустимость, значение цели, sanity-check бизнес-ограничений.
- Мониторинг — хранить метрики оптимизаций (время, gap, частота infeasible).
Такой pipeline делает оптимизацию повторяемой и безопасной для CI/CD на уровне команды.
Когда переходить от LP к MIP
MIP — это аббревиатура для смешанного целочисленного программирования, которое расширяет линейное программирование на случаи, когда некоторые или все переменные должны принимать целые значения, что значительно усложняет задачу, делая её NP-трудной в общем случае и требующей таких методов, как ветви и границы, отсечения и эвристики; MIP является рабочим инструментом для огромного числа практических задач, включая планирование производства, логистику, компоновку оборудования и выбор проектов, где неделимость объектов является естественным свойством, и его решение требует значительно больших вычислительных ресурсов по сравнению с непрерывным LP.
Переход обязателен, если переменные имеют логический или целочисленный смысл —
- число серверов, машин, сотрудников;
- бинарный выбор "включить/не включить";
- пороговые условия и дискретные пакеты ресурсов.
LP часто даёт быстрый ориентир, но дробные ответы в таких задачах нельзя внедрять напрямую без целочисленного этапа.
Чувствительность (связь с двойственностью)
Чувствительность — это анализ влияния изменений параметров модели, таких как коэффициенты целевой функции, правые части ограничений или элементы матрицы, на оптимальное решение и оптимальное значение, причём этот анализ даёт интервалы устойчивости, в пределах которых текущее решение остаётся оптимальным, и позволяет оценить маржинальные ценности ресурсов; чувствительность является важнейшим инструментом постоптимизационного анализа, поскольку в реальных условиях данные редко бывают абсолютно точными, и знание того, насколько решение стабильно к колебаниям цен, спроса или наличия сырья, определяет практическую ценность проведённой оптимизации и позволяет принимать обоснованные рискованные решения.
В ответе linprog (зависит от версии SciPy) могут быть двойственные значения ограничений — аналог yᵢ* из статьи 6 — насколько изменится оптимум при bᵢ → bᵢ + Δ. Для малых Δ в ЛП часто ΔZ ≈ yᵢ* · Δbᵢ. Это основа what-if анализа в Excel Solver и в планировании мощностей.
Связь с разделом
| Тема в коде | Теория |
|---|---|
A_ub, b_ub | стандартная форма Математическое программирование — введение и постановка задач |
slack в ответе | двойственность Двойственность в линейном программировании |
| сеть supply/demand | транспортная Транспортная задача |
dp[t][s] | Беллман Динамическое программирование и уравнение Беллмана |