Подклассы линейной модели
Линейная модель в О2 разделена на три подкласса по типу допустимых значений переменных:
- LP — непрерывное линейное программирование (linear programming);
- IP — целочисленное линейное программирование (integer programming);
- MIP — смешанно-целочисленное линейное программирование (mixed-integer programming).
Подкласс задаётся при создании модели. Он определяет, какие методы регистрации переменных доступны и какие алгоритмы применяет решатель. Структура линейных выражений и ограничений во всех трёх подклассах одинакова.
LP — непрерывное программирование
Все переменные принимают вещественные значения в заданных границах. Применяется к задачам с делимыми величинами: объём сырья в килограммах или литрах, доля бюджета, доля смены, мощность установки.
Типовые задачи — задача о смесях, транспортная задача, портфельная оптимизация на линейных ограничениях, распределение производственной мощности.
LP — полиномиально разрешимая задача: время поиска оптимума растёт как полином от размера задачи. Базовый алгоритм — симплекс-метод. На задачах с большим числом переменных и ограничений применяется метод внутренней точки.
Найденное LP-решение гарантированно глобальное. Локальных оптимумов в задаче не существует — допустимая область выпукла.
Задачи с десятками тысяч переменных и ограничений практически решаемы. Они встречаются в промышленных задачах планирования и логистики (production planning, supply chain optimization).
IP — целочисленное программирование
Все переменные принимают только целые значения в заданных границах. Применяется, когда дробные значения теряют прикладной смысл: число рейсов транспортных средств, количество единиц оборудования, число произведённых партий, число выполненных заказов.
IP принадлежит классу NP-трудных задач. Время доказательства оптимальности в худшем случае растёт экспоненциально от числа целочисленных переменных. На практике это означает: чистые IP-задачи на тысячах переменных требуют ограничения времени поиска и работы с подсказками. Доказательство оптимальности часто оказывается существенно дороже нахождения первого допустимого решения.
Базовый алгоритм для IP — метод ветвей и границ. На каждом шаге одна целочисленная переменная фиксируется в одном из своих допустимых значений, и задача распадается на подзадачи. Ветви, в которых вспомогательная LP-задача даёт оценку хуже уже найденного решения, отсекаются.
MIP — смешанно-целочисленное программирование
В одной модели одновременно поддерживаются и непрерывные, и целочисленные, и булевы переменные. Это самый распространённый подкласс на практике.
Подавляющее большинство прикладных задач объединяет «делимые» количественные переменные (объёмы, доли, мощности) и «дискретные» решения «да/нет» (включить ли направление перевозок, открыть ли склад, активировать ли производственную линию).
Алгоритм поиска — метод ветвей и границ с LP-релаксацией. На каждом шаге целочисленные ограничения временно ослабляются: целочисленные переменные считаются непрерывными. Решается вспомогательная LP-задача, и её решение отсекает заведомо неперспективные ветви.
Качество LP-релаксации напрямую влияет на скорость поиска. Чем теснее релаксация к исходной задаче, тем меньше ветвей придётся перебрать.
Большинство промышленных задач планирования — production planning, lot-sizing, capacity planning, facility location — формулируется именно как смешанно-целочисленная линейная модель.
Релаксация и цена целочисленности
LP-релаксация — основной мост между LP и IP/MIP. Её получают удалением требования целочисленности у всех переменных. Релаксация решается проще исходной задачи и даёт оценку для целочисленного оптимума:
- для задачи минимизации — оптимум LP-релаксации служит нижней оценкой целочисленного минимума;
- для задачи максимизации — верхней оценкой целочисленного максимума.
Иногда задача допускает естественное округление LP-решения к целочисленному без существенной потери качества. Это типично для задач с большими целочисленными значениями: тысячи единиц продукции, сотни тысяч рублей. В таких случаях целочисленные ограничения можно не вводить — это многократно ускоряет поиск.
Если же дискретный характер решения принципиально важен (выбор «да/нет», малые целочисленные значения), целочисленные ограничения сохраняются. Платой становится «цена целочисленности» — рост времени поиска.
Как выбрать подкласс
| Природа переменных задачи | Подкласс |
|---|---|
| Все переменные — делимые количественные величины (объёмы, доли, мощности) | LP |
| Все переменные — целые числа, дробные значения теряют смысл (число партий, число рейсов) | IP |
| Часть переменных делимые, часть — целые | MIP |
| Присутствуют булевы переключатели «да/нет» (открыть ли, включить ли) | MIP (или IP, если непрерывных переменных нет) |
Если есть сомнения, какой подкласс выбрать, предпочтительнее MIP: он покрывает все три случая ценой более общего алгоритма поиска. На более узкий подкласс имеет смысл переходить, если профилирование показывает существенный выигрыш по времени.
Создание модели выбранного подкласса
Подкласс модели задаётся выбором соответствующего фасада менеджера моделей:
- LP — непрерывная
- IP — целочисленная
- MIP — смешанно-целочисленная
Модель = О2
.Модели()
.ЛинейнаяНепрерывнаяМодель()
.СоздатьМодель();
Модель = О2
.Модели()
.ЛинейнаяЦелочисленнаяМодель()
.СоздатьМодель();
Модель = О2
.Модели()
.ЛинейнаяСмешанноЦелочисленнаяМодель()
.СоздатьМодель();
Подробнее о способах создания объекта модели — в разделе Создание объекта модели. Полный список методов фасадов и их параметры — в разделе Программный интерфейс — Линейные модели.