2.1. Численный метод решения многокритериальной задачи дискретного нелинейного программирования

При совершенствовании ССМП значительное место отводится задачам формирования эффективных управленческих решений с помощью задачи дискретной векторной оптимизации вида:

,	(2.1)
,	(2.2)
,	(2.3)

где – вектор целевых функций (показателей эффективности) решаемой задачи; – ограничения, накладываемые на переменные рассматриваемой задачи; – вектор искомых решений.

Под эффективным решением в данной работе понимается решение, являющееся наилучшим (предпочтительным) по сравнению с остальными решениями. Согласно теории оптимизации решений по Парето [23, 24] таких решений может быть более одного. Поэтому в результате решения многокритериальных задач формируется множество компромиссных (эффективных, оптимальных по Парето) решений, из которых лицо принимающее решение (ЛПР) выбирает конкретный вариант, наиболее полно удовлетворяющий неформализованным целям или интересам данного ЛПР.

В работе [23] приведена значительная библиография работ, посвященных методам решения линейных задач вида (2.1) – (2.3). Как отмечено в работе [25], решение однокритериальных «задач о назначениях» практически значимой размерности традиционными численными методами требует значительных затрат машинного времени.

В работе [26] утверждается, что использование линейной свертки критериев в задачах линейного дискретного программирования приводит к потере 40% точек паретооптимального множества решения таких задач.

В связи с тем, что множество допустимых решений задачи (2.1) – (2.3), которое определяется как:

,

(2.4)

является дискретным множеством, то множество достижимости [27] этой задачи также будет дискретным множеством. Для дискретного множества не выполняются условия выпуклости множества, что не позволяет корректным образом применять при решении задачи (2.1) – (2.3) классический метод линейной свертки целевых функций [26], основанный на применении теоремы С.Карлина [28].

Предположим, что множество (2.4) содержит конечное число векторов , сформированных путем полного перебора значений векторов [19], или использования рандомизированных методов генерации таких векторов [21], удовлетворяющих условиям (2.2) – (2.3).

Формируя для каждого вектора значения целевых функций , , получаем задачу, которая в практических приложениях конкретизируется как:

,

(2.5)

Как известно [27, 23], оптимизация решений по Парето основывается на выделении во множестве наилучших (паретооптимальных) точек с использованием отношения предпочтения, заданного на множестве возможных решений.

,

(2.6)

причем хотя бы одно неравенство строгое.

Последовательное сравнение возможных решений между собой с исключением из рассмотрения непредпочтительных решений составляет основу метода решения задачи (2.5). Отметим, что множество эффективных (компромиссных) решений (множество Парето) состоит из несравнимых между собой вариантов решений [29].

В работах [23, 29] для выделения оптимальных по Парето точек в континуальном множестве использовалось понятие ортанта, который представляет собой выпуклый острый конус без вершины, порожденный единичными ортантами пространства целевых функций (оценок). При этом утверждается, что рассматриваемая точка является паретооптимальной тогда и только тогда, когда во внутренность ортанта, сдвинутого в эту точку, не попадет ни одна из точек множества .

В связи с дискретностью задачи (6) для выделения в нем эффективных точек будем использовать выпуклый многогранный ортогональный конус, сдвинутый из начала координат в вершину рассматриваемой точки , который формально определим как:

(2.7)

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

10.

20. Формирование в пространстве критериев (6) соответствующего приближенного представления множеств достижимости (множества оценок) путем вычисления значений критериев (2.1).

30. Выделение в множестве подмножества паретооптимальных (эффективных, неулучшаемых) решений с использованием понятия ортогонального конуса вида (2.7).

В предлагаемом методе, существенное значение, с точки зрения точности получаемых результатов, имеет объем выполняемых статистических экспериментов. Для получения приемлемых для практики результатов в данном методе предлагается использовать следующее правило останова: «Процесс последовательного выполнения этапов 10 – 30 завершается, если при статистических экспериментах достигается заданная точность сходимости», т.е. полученное решение при статистических экспериментах отличается от решения при -1 статистических экспериментах в пределах заданной точности.

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

Однако, как показала практика, количество паретооптимальных решений может быть настолько большим, что разработчику системы будет сложно выбрать такое решение. В этом случае предлагается использовать принцип «близости к идеальной точке», который заключается в следующем. Из всего множества паретооптимальных решений выбираются следующие значения критериев , и , . Тогда близким к идеальному решению будет решение из паретооптимального множества, координаты которого находятся на минимальном расстоянии от идеальной точки (см. рис.2.1).

Рис. 2.1.