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

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

Целевая функция определяет критерий оптимальности решения. Целевая функция задаётся одним линейным выражением и направлением: минимизация или максимизация. При наличии целевой функции среди множества допустимых решений отбирается решение с её минимумом или максимумом.

Модель допускает не более одной целевой функции. Повторный вызов методов установки замещает ранее установленную функцию.

Поиск без целевой функции​

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

  • Проверка совместимости ограничений — определение, существует ли допустимое решение в принципе. При несовместности ограничений решатель возвращает статус РешениеОтсутствует.
  • Перечисление решений — задача состоит в нахождении конкретного решения, удовлетворяющего правилам, без сравнения решений между собой.
  • Логические головоломки — Sudoku, N ферзей, расстановки фигур по правилам. У таких задач либо одно решение, либо несколько эквивалентных, и оптимальность не требуется.

В подобных задачах методы установки целевой функции не вызываются. Метод Решить при этом возвращает объект решения; значение ЗначениеЦелевойФункции равно 0.

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

Установка целевой функции выполняется одним из двух методов объекта модели:

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

// Простой случай: минимизация выражения, заданного строкой
Модель.ЦелеваяФункция().Минимизировать("2*x - y");

// Составной случай: минимизация заранее построенного выражения
СуммаОпозданий = Модель.Выражения().ВзвешеннаяСумма(
    ОпозданияПоРаботам,
    ВесаКлиентов
);

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

После завершения поиска значение целевой функции на найденном решении доступно через метод Решение.ЗначениеЦелевойФункции() — см. Решение модели.

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

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

// Целевая функция: 1·длительность + 100·число_просрочек + 10·разброс_нагрузки
ЦелеваяФункция = Модель.Выражения().ВзвешеннаяСумма(
    О2.Утилиты().Массив(
        ОбщаяДлительность,
        ЧислоПросрочек,
        РазбросНагрузки
    ),
    О2.Утилиты().Массив(1, 100, 10)
);

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

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

Штрафы за нарушение мягких условий​

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

ЗаказОтгруженВовремя = Модель.Переменные().ДобавитьБулеву("вовремя");

// Условие действует только при истинности индикатора.
// Если условие нарушается, к целевой функции добавляется штраф.
Модель.Ограничения().ЗначениеМеньшеИлиРавно(
    ФактическийСрок,
    ОбещанныйСрок,
    ЗаказОтгруженВовремя
);

ШтрафЗаОпоздание = Модель.Переменные().Отрицание(ЗаказОтгруженВовремя);

// Целевая функция: общая стоимость + 1000 за каждое опоздание
Модель.ЦелеваяФункция().Минимизировать(
    Модель.Выражения().ВзвешеннаяСумма(
        О2.Утилиты().Массив(ОбщаяСтоимость, ШтрафЗаОпоздание),
        О2.Утилиты().Массив(1, 1000)
    )
);

Этот приём применяется в задачах с заведомо нерешаемой жёсткой формулировкой: условие признаётся допустимым к нарушению, за каждое нарушение начисляется штраф, и решатель самостоятельно определяет приемлемый компромисс.

Иллюстрация: минимизация просрочек​

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

// Для каждой работы вводится переменная "опоздание" и её вес "приоритет клиента"
ОпозданияПоРаботам   = Новый Массив();
ПриоритетыКлиентов   = Новый Массив();

Для Каждого Работа Из СписокРабот Цикл

    Опоздание = Модель.Переменные().ДобавитьИзДиапазона(0, ГоризонтПланирования);

    // Связь "Опоздание = max(Конец работы - Обещанный срок, 0)" задаётся
    // через вспомогательные ограничения; см. примеры в разделе примеров.

    ОпозданияПоРаботам.Добавить(Опоздание);
    ПриоритетыКлиентов.Добавить(Работа.ПриоритетКлиента);

КонецЦикла;

ВзвешенноеОпоздание = Модель.Выражения().ВзвешеннаяСумма(
    ОпозданияПоРаботам,
    ПриоритетыКлиентов
);

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

Полные примеры с минимизацией:

Полный перечень методов​

Полный набор методов работы с целевой функцией приведён в разделе Программный интерфейс — Целевая функция.