Решение
Решение модели — последний шаг жизненного цикла. Собранная из переменных, ограничений и целевой функции модель передаётся решателю, а из найденного результата извлекаются прикладные значения.
Объект решения содержит статус поиска, значения переменных и значение целевой функции. Из этих данных восстанавливается прикладной ответ.
Запуск поиска
Базовый способ — вызов метода Решить() объекта модели:
Решение = Модель.Решить();
Альтернативный путь — через менеджер библиотеки. Этот вариант принимает не только модель, построенную в коде, но и модель, ранее сохранённую на диск. Полезен при разделении этапов формирования модели и её решения — в том числе через консольную утилиту:
Решение = О2.РешитьМодель(Модель);
// Или загрузка модели из файла
Решение = О2.РешитьМодель("C:\\path\\to\\my\\model.o2m");
Параметры запуска
В метод Решить() (или РешитьМодель()) могут быть переданы параметры поиска: лимит времени, число параллельных потоков, выбор сервиса исполнения (локальный или удалённый), настройки лицензирования.
Состав полей и значения по умолчанию описаны в разделе Программный интерфейс — Решение. Сценарии работы с разными сервисами исполнения — в разделе Использование программного API.
Лимит времени поиска — критически важный параметр для смешанно-целочисленных задач. Он гарантирует, что регламентный расчёт завершится в фиксированное время, даже если оптимальность не доказана. В этом случае возвращается лучшее найденное за отведённое время допустимое решение (см. ниже).
Статусы решения
Перед использованием значений переменных из решения обязательна проверка статуса. Решатель различает четыре статуса:
| Статус | Расшифровка |
|---|---|
| Оптимальное | Решение найдено и доказано, что улучшить значение целевой функции невозможно в пределах модели. |
| Допустимое | Решение найдено и удовлетворяет всем ограничениям, но оптимальность за отведённое время не доказана. Типично для больших MIP-задач с лимитом времени. |
| РешениеОтсутствует | Решатель доказал, что модель несовместна — допустимых решений не существует. Обычно следствие противоречивых или избыточно жёстких ограничений. |
| ОшибочнаяМодель | В данных модели обнаружены ошибки, препятствующие запуску поиска (некорректное выражение, нарушенная структура). |
Обработка статусов:
Решение = Модель.Решить();
Если Решение.Статус() = О2.СтатусыРешений().Оптимальное() Тогда
// решение доказанно оптимальное
ИначеЕсли Решение.Статус() = О2.СтатусыРешений().Допустимое() Тогда
// решение допустимое; оптимальность не гарантируется
ИначеЕсли Решение.Статус() = О2.СтатусыРешений().РешениеОтсутствует() Тогда
// ограничения несовместны
Иначе
// ошибка модели — извлекать значения нельзя
КонецЕсли;
Если различие между оптимальным и допустимым решением не критично — важен сам факт наличия решения, — удобно проверять признак Решение.РешениеНайдено(). Он возвращает Истина для оптимального и допустимого статусов и Ложь для остальных.
Что извлекается из решения
Из объекта решения извлекаются:
- значения отдельных переменных — по объекту переменной, по имени или по индексу регистрации;
- значение любого линейного выражения на найденном решении — без необходимости вычислять выражение в прикладном коде;
- значение целевой функции на оптимальном (или лучшем найденном) решении;
- метаданные поиска — версия и тип решателя, время поиска, идентификатор модели и решения.
Если Решение.РешениеНайдено() Тогда
ОбъёмВыпуска = Решение.ЗначениеПеременной("ОбъёмВыпуска");
СуммарныеЗатраты = Решение.ЗначениеЦелевойФункции();
// прикладной код, использующий найденные значения
КонецЕсли;
Алгоритмы и решатели
Внутри объекта решения работают зрелые алгоритмы линейной оптимизации, проверенные десятилетиями практики и теории операций. Понимание того, какой алгоритм применяется к задаче, помогает интерпретировать поведение решателя и выбирать тактики ускорения.
- Симплекс-метод. Базовый алгоритм для LP-задач. Эффективен на задачах с большим числом переменных и ограничений. На типичных промышленных задачах планирования и логистики работает практически линейно по размеру задачи. Поддерживает горячий старт от близкого решения — это используется при повторных запусках с близкими параметрами.
- Метод внутренней точки. Альтернативный алгоритм для очень больших LP-задач. Имеет полиномиальную сложность в худшем случае, но на задачах среднего размера часто медленнее симплекса. Применяется автоматически при определённых характеристиках задачи или явно по выбору.
- Метод ветвей и границ (branch and bound). Базовый алгоритм для IP- и MIP-задач. На каждом шаге одна из целочисленных переменных фиксируется в одном из допустимых значений, и задача распадается на подзадачи. Для каждой решается вспомогательная LP-релаксация, дающая оценку качества. Подзадачи с оценкой хуже уже найденного решения отсекаются — это даёт приемлемую скорость поиска на типичных промышленных задачах.
Конкретный алгоритм-бэкенд выбирается через настройки решателя. Для большинства задач достаточно значений по умолчанию — выбор бэкенда автоматически согласован с подклассом модели.
Тонкая настройка применяется в задачах с заранее известными свойствами: известная вырожденность, экстремальные размеры, повторяющаяся структура. Это задача опытных пользователей. Полный список доступных бэкендов и их настройки — в разделе Программный интерфейс — Решение.
Загрузка готового решения
Если решение модели было получено отдельно — например, консольной утилитой решателя на стороне сервера или в пакетном режиме, — оно загружается из файла и обрабатывается в коде наравне с решением, возвращённым Модель.Решить():
Решение = О2.ЗагрузитьРешение("C:\\path\\to\\my\\solution.o2s");
Тактики ускорения поиска
При недостаточной скорости поиска прикладные приёмы применяются в порядке от наименее затратного к наиболее затратному:
- Содержательно заданные границы переменных. Самый дешёвый и наиболее эффективный приём. Замена
±∞на значения из бизнес-задачи (мощность, бюджет, оперативный горизонт) даёт ускорение в разы. - Аккуратный выбор констант
Mв big-M-формулировках. Избыточно большиеMослабляют LP-релаксацию и замедляют метод ветвей и границ.Mназначается равным содержательной верхней границе соответствующей переменной. - Линейное масштабирование коэффициентов до сопоставимых порядков (см. приёмы моделирования). Уменьшает численную нестабильность.
- Подсказки для больших MIP-задач при наличии правдоподобного стартового решения (предыдущий план, эвристика).
- Ограничение времени поиска при недопустимой длительности расчёта. Вместо ожидания доказанной оптимальности возвращается лучшее найденное допустимое решение, и используется проверка статуса.
- Декомпозиция модели — разбиение задачи на части (по периодам, по подразделениям, по группам продуктов) с последующим согласованием. Применяется в задачах с десятками тысяч переменных, не помещающихся в один регламентный расчёт.
См. также
- Целевая функция — различие допустимого и оптимального решения
- Подсказки — стартовое решение для больших MIP-задач
- Приёмы моделирования — выбор
Mи масштабирование коэффициентов - Программный интерфейс — Решение