Линейная модель

Линейная модель ищет значения числовых переменных, при которых заданный числовой критерий принимает минимум или максимум, а все условия задачи выполнены.

Критерий и ограничения записываются как линейные комбинации переменных:

a₁·x₁ + a₂·x₂ + … + aₙ·xₙ + b

Коэффициенты aᵢ и константа b известны на этапе построения модели. Переменные xᵢ подбирает решатель.

В отличие от модели ограничений, линейная модель работает с числовыми переменными и допускает только линейные арифметические соотношения. Дискретные переменные, булева логика, интервалы и автоматы — за ней не поддерживаются.

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

Область применения

Линейная оптимизация — исторически первый и наиболее зрелый раздел методов исследования операций. На алгоритмах линейного и смешанно-целочисленного программирования (linear programming, mixed-integer programming) построены модули оптимизации в системах класса ERP, APS (Advanced Planning and Scheduling), SCM (Supply Chain Management), MRP (Material Requirements Planning).

Типовые сценарии прикладной автоматизации в 1С:Предприятие:

• Планирование производства и закупок — объёмы выпуска по номенклатуре, расход сырья, размеры партий с учётом мощности оборудования и складских ограничений.
• Распределение ресурсов и нагрузки — бюджет между статьями, нагрузка между подразделениями, транспортные мощности между маршрутами.
• Транспортная задача и плановая логистика — объёмы перевозок между источниками и потребителями при заданных стоимостях доставки.
• Составление смесей и рецептур (blending) — пропорции ингредиентов в смесях, кормах, материалах при ограничениях на состав.
• Раскрой материалов (cutting stock) — выбор шаблонов раскроя с минимизацией отходов.
• Портфельная оптимизация (portfolio optimization) — доли активов в портфеле при заданном уровне риска или доходности.
• Планирование размеров партий (lot-sizing) — размеры производственных или закупочных партий с учётом фиксированных и переменных затрат.

Типовые задачи

Задача о смесях (blending problem)

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

Классическая формулировка задачи о смесях — задача о диете Стиглера: подбор продуктов рациона, дающих заданные нормы питательных веществ при минимальной цене.

Транспортная задача

Распределение объёмов поставки от источников к потребителям. Заданы мощности источников, потребности потребителей и стоимости транспортировки. Минимизируется суммарная стоимость перевозок.

Базовая задача для модулей логистики и распределения товаров.

Задача о назначениях

Сопоставление исполнителей задачам с учётом стоимости или времени каждой пары. Чистая комбинаторная задача решается специальными алгоритмами. С добавлением непрерывных переменных нагрузки или объёма работ задача становится смешанно-целочисленной линейной.

Полный пример — Задача о назначениях.

Задача раскроя (cutting stock)

Выбор шаблонов раскроя исходного материала фиксированной длины или площади. Цель — выполнить заявки на заготовки заданных размеров с минимумом использованных листов.

Полный пример — Оптимальный раскрой материала.

Планирование производства

Определение объёмов выпуска по периодам планирования. Учитываются мощность оборудования, доступность сырья, складские запасы, спрос. Целевая функция — максимизация маржи или минимизация суммарных затрат.

Часто формулируется как смешанно-целочисленная задача. Булевы переменные отвечают за запуск производственных линий.

Портфельная оптимизация

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

Полный пример — Формирование инвестиционного портфеля.

Глоссарий

Термин	Определение
Переменная	Неизвестная числовая величина, значение которой определяет решатель. Бывает непрерывной, целочисленной или булевой.
Границы переменной	Минимально и максимально допустимое значение переменной. Содержательно ограниченные диапазоны заметно ускоряют поиск.
Линейное выражение	Линейная комбинация переменных вида a₁·x₁ + a₂·x₂ + … + c. Коэффициенты и константа — числа, известные на этапе построения модели.
Линейное ограничение	Условие вида Выражение₁ ⩽ Выражение₂, Выражение₁ ⩾ Выражение₂ или Выражение₁ = Выражение₂. Строгие неравенства не поддерживаются.
Целевая функция	Линейное выражение, минимум или максимум которого ищет решатель. Без целевой функции выполняется поиск любого допустимого решения.
Допустимое решение	Набор значений переменных, удовлетворяющий всем ограничениям.
Оптимальное решение	Допустимое решение, для которого решатель доказал наилучшее значение целевой функции за отведённое время поиска.
LP-релаксация	Вспомогательная задача, в которой целочисленные ограничения временно ослаблены до непрерывных. Её оптимум служит границей качества для исходной целочисленной задачи.
Ограничение big-M	Приём моделирования: булева переменная-индикатор включает или выключает действие линейного ограничения через слагаемое с большой константой M. См. Приёмы моделирования.
Индикаторная переменная	Булева переменная (значения 0 или 1), отмечающая принятие или непринятие дискретного решения: открыть ли склад, включить ли позицию, активно ли ограничение. Основной механизм моделирования дискретных решений в смешанно-целочисленных моделях.

Принцип работы

Решение прикладной задачи линейной моделью выполняется в следующей последовательности:

1. Формализация задачи. Из прикладной задачи выделяются неизвестные числовые величины и ограничения, которым они должны удовлетворять. Если требуется не любое допустимое решение, а оптимум — задаётся критерий выбора лучшего варианта.
2. Выбор подкласса модели: LP, IP или MIP. Подкласс определяется тем, какие значения допустимы для переменных: непрерывные (LP), только целые (IP) или смешанные с булевыми (MIP). От подкласса зависят доступные методы регистрации переменных и применяемые алгоритмы.
3. Создание объекта модели. Через фасад менеджера моделей создаётся пустой контейнер выбранного подкласса. В него регистрируются переменные, выражения и ограничения.
4. Регистрация переменных. Каждой неизвестной величине ставится в соответствие переменная подходящего типа с содержательно заданными границами. Содержательные границы — самый дешёвый способ ускорить поиск.
5. Описание ограничений над линейными выражениями. Условия задачи формулируются как линейные соотношения =, ⩽, ⩾. Условные конструкции и нелинейные элементы (абсолютные значения, минимум, максимум, кусочно-линейные функции) выражаются через приёмы моделирования.
6. Задача целевой функции (опционально). Задаётся линейное выражение и направление поиска: минимизация или максимизация. Без целевой функции решатель ищет любое допустимое решение.
7. Передача подсказок (опционально). Стартовое значение переменных из предыдущих итераций или эвристики ускоряет поиск первого допустимого решения в больших смешанно-целочисленных задачах.
8. Запуск поиска и обработка решения. Вызов Модель.Решить() запускает решатель. Из объекта решения извлекаются статус, значения переменных и значение целевой функции. По ним восстанавливается прикладной ответ.

Шаги 4–7 выполняются в произвольном порядке и могут чередоваться: переменные допустимо регистрировать по мере появления связанных с ними ограничений. Существенно лишь то, что к моменту вызова Модель.Решить() в модели зарегистрированы все переменные, на которые ссылаются ограничения и целевая функция.

Сильные и слабые стороны

Сильные стороны

• Зрелость алгоритмов. Линейное программирование разрабатывается с середины XX века. Современные реализации симплекс-метода и метода внутренней точки решают задачи с десятками тысяч переменных и ограничений.
• Глобальная оптимальность для непрерывных задач. В чистой LP-задаче найденное решение гарантированно глобальное. Локальных оптимумов в задаче не существует — допустимая область выпукла.
• Высокая скорость на больших задачах. Линейная структура задачи допускает алгоритмы с полиномиальной сложностью (для LP) и эффективные схемы отсечения (для смешанно-целочисленных задач). Они масштабируются до промышленных размеров.
• Прозрачная связь с прикладной задачей. Линейные ограничения естественно отражают балансы материалов, ресурсные лимиты, нормативные требования. Это типичные конструкции учётных и плановых задач.

Слабые стороны и пределы применимости

• Только линейные соотношения. Произведение переменных, отношения, степени, абсолютные значения, минимум, максимум — напрямую не выразимы. Часть из них моделируется приёмами с введением вспомогательных переменных и булевых индикаторов. Для существенно нелинейных или комбинаторных задач применяется модель ограничений.
• Нелинейный рост времени поиска для целочисленных задач. Целочисленные и смешанно-целочисленные задачи относятся к классу NP-трудных. Время доказательства оптимальности в худшем случае растёт экспоненциально от числа целочисленных переменных. На больших задачах применяется ограничение времени поиска и работа с подсказками.
• Чувствительность к качеству формулировки. Численная стабильность и скорость поиска зависят от выбора границ переменных, масштабирования коэффициентов и величины констант M в big-M-формулировках. Плохо обусловленная модель может решаться многократно медленнее эквивалентной хорошо обусловленной.

Ориентиры по объёмам данных

Точные оценки времени поиска зависят от структуры задачи и качества формулировки. Качественные диапазоны таковы:

• Десятки — сотни переменных. Чистая LP — миллисекунды. Смешанно-целочисленная — секунды без специальной настройки.
• Тысячи переменных. Чистая LP — секунды. Смешанно-целочисленная — секунды или минуты при содержательно заданных границах переменных и аккуратном выборе констант M.
• Десятки тысяч переменных и больше. Чистая LP остаётся практически решаемой. Смешанно-целочисленные задачи требуют декомпозиции, фиксированного бюджета времени и работы с подсказками. Тонкая настройка параметров решателя — задача опытных пользователей.

Сравнение с другими моделями

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

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

Класс задачи	Рекомендованная модель	Почему специализированная модель эффективнее
Дискретные задачи с богатой логикой: расписания, упаковка 2D, конфигурация продукта, последовательности состояний	Модель ограничений (CP-SAT)	Готовые конструкции — интервалы, ресурсы, прямоугольники, автоматы, условные ограничения — выразительнее линейных моделей и не требуют ручного моделирования через big-M.
Выбор подмножества предметов в один контейнер по «весу» и «ценности», без учёта порядка	Задача о ранце	Использует алгоритмы динамического программирования с теоретическими гарантиями качества.
Маршруты транспортных средств с матрицами расстояний, депо, грузоподъёмностью, временными окнами	Модель маршрутизации	Применяет двухфазный поиск со специализированными стратегиями построения первого решения и метаэвристиками локального поиска. Масштабируется до тысяч узлов.
Максимальный поток в сети с пропускными способностями	Модель максимального потока	Использует алгоритмы максимального потока с полиномиальной сложностью.
Минимальная стоимость потока с заданными источниками и стоками	Модель потока минимальной стоимости	Использует алгоритмы поиска потока минимальной стоимости с полиномиальной сложностью.

Составные части модели

• Подклассы LP, IP, MIP
• Создание объекта модели
• Переменные
• Линейные выражения
• Ограничения
• Приёмы моделирования
• Целевая функция
• Подсказки решателю
• Решение

Примеры использования модели

• Составление оптимальной диеты (задача Стиглера) — классическая LP-задача задачи о смесях.
• Расширенная задача о диете — гибрид линейной модели и модели ограничений.
• Формирование инвестиционного портфеля — портфельная оптимизация на линейных ограничениях.
• Оптимальный раскрой материала — целочисленная задача раскроя.
• Назначение исполнителей — задача о назначениях с булевыми переменными.
• Назначение с учётом трудоёмкости — смешанно-целочисленная задача с балансировкой нагрузки.

Программный интерфейс

Полное описание методов линейных моделей приведено в разделе Программный интерфейс — Линейные модели:

• Непрерывная модель (LP);
• Целочисленная модель (IP);
• Смешанно-целочисленная модель (MIP).