Перейти к основному содержимому

Целевая функция

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

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

Этот режим применяется в двух случаях: проверка совместности ограничений (есть ли вообще решение?) и поиск любой допустимой конфигурации без сравнения вариантов.

Минимизация и максимизация​

Направление поиска задаётся методом задания целевой функции:

  • Минимизация — типична для задач затрат (стоимость закупок и перевозок, стоимость рациона, отклонение от плана), штрафов, длительности процесса.
  • Максимизация — типична для задач прибыли и маржи, обслуженного спроса, утилизации мощностей, доходности портфеля.

Математически направления эквивалентны: задача максимизации f эквивалентна задаче минимизации −f с тем же множеством оптимальных решений. На практике направление выбирается по содержательному смыслу. Это делает целевую функцию читаемой и упрощает анализ результата.

// Минимизация суммарных затрат
Модель.ЦелеваяФункция().Минимизировать(СуммарныеЗатраты);

// Максимизация маржи
Модель.ЦелеваяФункция().Максимизировать(СуммарнаяМаржа);

Допустимое и оптимальное решение​

При наличии целевой функции решатель различает два качественно разных результата:

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

Различие критично прежде всего для смешанно-целочисленных задач: на больших MIP-задачах доказательство оптимальности часто оказывается существенно дороже нахождения первого допустимого решения.

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

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

Решение = Модель.Решить();

Если Решение.Статус() = О2.СтатусыРешений().Оптимальное() Тогда
    // решение доказанно оптимальное
ИначеЕсли Решение.Статус() = О2.СтатусыРешений().Допустимое() Тогда
    // решение допустимое; оптимальность не гарантируется
Иначе
    // решение не найдено; статусы — в разделе «Решение»
КонецЕсли;

Подробное описание статусов решения — в разделе Решение.

Многокритериальная оптимизация​

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

В линейной модели несколько критериев сворачиваются в одну целевую функцию через взвешенную сумму:

Σ wᵢ · fᵢ → min (или max)

Здесь fᵢ — линейные выражения отдельных критериев, wᵢ — весовые коэффициенты, отражающие относительную важность каждого. Для критериев, направленных к минимизации, веса берутся со своим знаком; для критериев на максимизацию — с противоположным.

Масштабирование критериев. Критерии разной природы — рубли затрат и часы выполнения, число обслуженных заявок и километры маршрута — имеют разные порядки величины. Без масштабирования один критерий «съедает» другие, и оптимизация фактически идёт только по нему.

Стандартный приём: до сворачивания каждый критерий нормируется на свой характерный масштаб — типичное значение, ожидаемый максимум, известный нижний предел. После этого веса задают уже относительные приоритеты.

// Сворачивание двух критериев: минимизация затрат и минимизация отклонения от плана
ЦелеваяСвёртка = Модель.Выражения().ВзвешеннаяСумма(
    О2.Утилиты().Массив(СуммарныеЗатраты,        СуммарноеОтклонение),
    О2.Утилиты().Массив(ВесЗатрат / МасштабРубли, ВесОтклонения / МасштабПлан)
);

Модель.ЦелеваяФункция().Минимизировать(ЦелеваяСвёртка);

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

Этот подход требует нескольких запусков решателя. Он применяется, когда веса критериев не могут быть согласованы заранее.

См. также​