МЕТОД ИТЕРАТИВНО-ПОРЯДКОВОЙ ОПТИМИЗАЦИИ МНОГО-КРИТЕРИАЛЬНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ ЛОКАЛЬНОЙ ВАЖНОСТИ КРИТЕРИЕВ

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

Ключевые слова: многокритериальные задачи; оптимизация; важность критериев; системы поддержки принятия решений.

Математический аппарат в данной работе согласен с [1]-[2].

Итеративный подход к оптимизации многокритериальных задач с использованием качественной важности критериев описан в работах [3]-[4]. Сводится он к двум основным положениям:

1. В первую очередь следует получать более простую и надежную информацию о предпочтениях, и лишь потом, в случае необходимости (когда такой информации недостаточно), привлекать более сложную и потому менее надежную информацию;
2. Необходимо проводить проверку ранее накопленной и получаемой дополнительно информации на непротиворечивость и при выявлении противоречий осуществлять ее корректировку; при этом проверку менее надежного сообщения надо проводить при помощи более надежных или хотя бы нескольких столь же надежных сообщений.

Допустим, на k-м шаге имелась информация о предпочтениях Ω(k) и на ее основе были построены на множестве векторных оценок отношения предпочтения P(k) и безразличия I(k). Предположим, далее, что на следующем, k + 1-м шаге получена дополнительная информация и на основе всей накопленной информации Ω(k + 1) построены отношения P(k + 1) и I(k + 1). При этом должно выполняться следующее требование непротиворечивости к уточнению информации о предпочтениях: если на k-м шаге было выявлено, что одна из векторных оценок более предпочтительна, чем другая, или же что они одинаковы по предпочтительности, то такое же соотношение между ними должно остаться и на следующем, k + 1-м шаге, т.е. для любых векторных оценок K(v) и K(v’) должно быть выполнено условие:

K(v) P(k) K(v’) влечет K(v) P(k + 1) K(v’);

K(v) I(k) K(v’) влечет K(v) I(k + 1) K(v’).

На первом шаге процесса в качестве отношения P(0) обычно принимается отношение P⁰, а в роли отношения I(0) выступает отношение равенства. В случае, когда результаты k-го шага не позволяют выделить один наилучший вариант, а указывают несколько недоминируемых и несравнимых между собой вариантов, необходимо перейти к очередному, k + 1-му шагу и организовать получение дополнительной информации о предпочтениях. Если возможности получения информации исчерпаны, то итеративный процесс анализа задачи заканчивается.

Фактически, введение информации о равноважности/локальной равноважности критериев лишь косвенно способствует сужению множества недоминируемых вариантов через отношение транзитивности, ведь при информации Ω = {K₁ ≻ K₂, K₂ ≈ K₃, K₂ ≻ K₃} мы имеем K₁ ≻ K₃. При отсутствии сообщения K₂ ≈ K₃ мы бы не смогли сделать такой вывод. То есть в рассмотренном итеративном подходе подразумевается три возможных отношения между двумя произвольными критериями:

1. Отсутствие информации о предпочтениях;
2. Оба критерия равноважны;
3. Один критерий важнее другого.

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

Однако вместо того, чтобы за начальное условие брать отсутствие какой-либо информации Ω = {} можно сделать начальное предположение о равноважности всех критериев друг относительно друга, то есть Ω = {K_i ≈ K_j} для любых 0 < i, j < m. В силу транзитивности то же самое можно записать как Ω = {K₁ ≈ K₂, K₂ ≈ K₃, ..., K_m-2 ≈ K_m-1, K_m-1 ≈ K_m}.

Рассмотрим следующее определение из работы [1]. Качественные величины (а также и коэффициенты) важности критериев, полностью упорядоченных по важности, т.е. соответствующие полной непротиворечивой информации W, называются порядковыми, или ординальными. Именно такой порядковости мы и добъемся, с самого начала задав равноважность всех критериев.

При этом сохранится итеративный опрос ЛПР, но вносить он будет только сообщения о большей предпочтительности некоего критерия относительно следующего за ним. То есть, внося сообщение K_i ≻ K_i+1, мы будем не добавлять его к множеству Ω, а заменять в информации Ω сообщение K_i ≈ K_i+1 на сообщение K_i ≻ K_i+1. Из K_i ≻ K_i+1 в этом случае следует K_i ≻ K_j для любого i + 1 ≤ j ≤ m. Изначально мы можем расположить критерии в произвольном порядке, что позволит добиться нужных нам соотношений.

Также введём следующее понятие. Важностным разбиением множества критериев называется множество подмножеств, состоящих из равноважных критериев, причём подмножества разделены знаком, соответствующим относительной важности критериев предыдущего подмножества относительно критериев следующего за ним подмножества. Обозначим такое разбиение символом K_Ω.                                                                                                                                                                                          

Рассмотрим пример. Пусть изначально имеется 10 критериев K = {K₁, …, K₁₀}, информация о важности Ω = {K₁ ≈ K₂, K₂ ≈ K₃, ..., K₈ ≈ K₉, K₉ ≈ K₁₀}, K_Ω = {{K₁, K₂, K₃, K₄, K₅, K₆, K₇, K₈, K₉, K₁₀}}.

Таблица 1.

Входные условия примера

На первом шаге опроса ЛПР вносит сообщение K₃ ≻ K₄. Значит, что Ω = {K₁ ≈ K₂, K₂ ≈ K₃, K₃ ≻ K₄, K₄ ≈ K₅, ..., K₈ ≈ K₉, K₉ ≈ K₁₀}, K_Ω = {{K₁, K₂, K₃} ≻ {K₄, K₅, K₆, K₇, K₈, K₉, K₁₀}}.

Таблица 2.

Первый шаг опроса ЛПР

На втором шаге опроса ЛПР вносит сообщение K₈ ≻ K₉. Значит, что Ω = {K₁ ≈ K₂, K₂ ≈ K₃, K₃ ≻ K₄, K₄ ≈ K₅, ..., K₇ ≈ K₈, K₈ ≻ K₉, K₉ ≈ K₁₀}, K_Ω = {{K₁, K₂, K₃} ≻ {K₄, K₅, K₆, K₇, K₈} ≻ {K₉, K₁₀}}.

Таблица 3.

 Второй шаг опроса ЛПР

Назовём рассмотренный метод итеративно-порядковым. Он является частным случаем итеративного подхода. Но почему же он достоин отдельного рассмотрения? Ключевым моментом является избавление от необходимости проверки новых сообщений на непротиворечивость, что кардинально облегчает задачу ЛПР в задачах с большим количеством критериев, т.к. в итеративном методе сложно отслеживать все транзитивные зависимости.

Кажется очевидным, что первая часть условия непротиворечивости «K(v) P(k) K(v’) влечет K(v) P(k + 1) K(v’)» будет в итеративно-порядковом методе выполняться всегда, но докажем это. Пусть на k-м шаге имется некое множество K = {…, K_i, …, K_j, …}, информация о важности Ω = {K_i ≻ K_j, …}. Следовательно, в важностном разбиении критерии K_i и K_j лежат в разных подмножествах B и D соответственно (названия подмножествам даны для удобства), причём подмножество B находится раньше (левее/выше), чем подмножество D. Пусть вероятностное разбиение выглядит следующим образом: K_Ω = {A, B, C, D, E}, причем K_i ∈ B, K_j ∈ D. Другие варианты подмножеств являются частными случаями рассмотренного. Возможны следующие варианты:

1. ЛПР на шаге k + 1 вносит новое сообщение об элементах из подмножества A, то есть некий критерий из A отныне более важен, чем последующий за ним из того же подмножества A. Тогда данное ообщение k + 1 разбивает подмножество A на подмножества A₁, A₂. Тогда получим K_Ω = {A₁, A₂, B, C, D, E}. Очевидно, что отношение между критериями K_i, и K_j из подмножеств B и D не изменится, сохранится отношение предпочтения K_i ≻ K_j.
2. ЛПР на шаге k + 1 вносит новое сообщение об элементах из подмножества B, то есть некий критерий из B отныне более важен, чем последующий за ним из того же подмножества B. Тогда данное ообщение k + 1 разбивает подмножество B на подмножества B₁, B₂. Тогда получим K_Ω = {A, B₁, B₂, C, D, E}. При этом нам не важно, в каком из получившихся подмножеств оказался критерий K_i, ведь в силу транзитивности отношение предпочтения K_i ≻ K_j сохранится.
3. ЛПР на шаге k + 1 вносит новое сообщение об элементах из подмножества С, то есть некий критерий из С отныне более важен, чем последующий за ним из того же подмножества С. Тогда данное ообщение k + 1 разбивает подмножество С на подмножества С₁, С₂. Тогда получим K_Ω = {A, B, С₁, С₂, D, E}. Очевидно, что отношение между критериями K_i, и K_j из подмножеств B и D не изменится, сохранится отношение предпочтения K_i ≻ K_j.
4. ЛПР на шаге k + 1 вносит новое сообщение об элементах из подмножества D, то есть некий критерий из D отныне более важен, чем последующий за ним из того же подмножества D. Тогда данное ообщение k + 1 разбивает подмножество D на подмножества D₁, D₂. Тогда получим K_Ω = {A, B, C, D₁, D₂, E}. При этом нам не важно, в каком из получившихся подмножеств оказался критерий K_j, ведь в силу транзитивности отношение предпочтения K_i ≻ K_j сохранится.
5. ЛПР на шаге k + 1 вносит новое сообщение об элементах из подмножества E, то есть некий критерий из E отныне более важен, чем последующий за ним из того же подмножества E. Тогда данное ообщение k + 1 разбивает подмножество E на подмножества E₁, E₂. Тогда получим K_Ω = {A, B, C, D, E₁, E₂}. Очевидно, что отношение между критериями K_i, и K_j из подмножеств B и D не изменится, сохранится отношение предпочтения K_i ≻ K_j.

Все остальные варианты подмножеств, являясь частными случаями, будут иметь тот же принцип доказательства. Соответственно, мы доказали, что рассматриваемая первая часть условия непротиворечивости в итеративно-порядоковом методе выполняется всегда.

От второй же части условия непротиворечивости «K(v) I(k) K(v’) влечет K(v) I(k + 1) K(v’)» мы вовсе отказываемся в силу изначального предположения о равнозначности всех критериев друг относительно друга и логики внесения сообщений от ЛПР, заключающейся как раз в замене отношения равнозначности на предпочтительность.

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