«Многокритериальные решения задачи выбора ТПС»

 

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

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

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

Рассмотрим метод выбора системы доставки грузов при наличии нескольких критериев на основе нечетких множеств.

Постановка задачи представляется следующим образом. Пусть задано множество возможных вариантов доставки X:

Каждый вариант характеризуется множеством параметров оценки качества Y:

Между каждым членом множества и каждым членом множества Y имеет место нечеткое отношение, обозначенное через xy или μ_ij. Иными словами, μ_ij отражает уровень соответствия i-го варианта доставки требованиям по j-ому параметру (μ_ij  [0,1]; i = 1,..., n; j = 1,..., m). Если собрать вместе все нечеткие отношения между x_i и у_j, то получим матрицу нечетких отношений R размером пт:

Требуется выбрать лучший вариант х* из множества X.

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

х* = opt (X, У, R, М), (5.15)

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

1) ЛПР не располагает информацией об ограничениях на значение параметров и информацией об уровне их важности. Применяется модель максиминной свертки для решения задачи;

2) ЛПР выбирает вариант, обеспечивающий значения .всех параметров не хуже требуемых. Эта ситуация соответствует модели абсолютного решения;

3) ЛПР может указать желаемые ограничения по некоторым основным параметрам. Это модель основного параметра;

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

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

Рассмотрим эти модели более подробно.

Модель максиминной свертки. Сущность модели заключается в следующем: оптимальным считается вариант, имеющий минимальные недостатки по всем параметрам. Данная модель основана на операции пересечения нечетких множеств:

D = y₁ ∩ y₂ ∩ ......... ∩ y_m                                                                         (1)

где D – конечная оценка качества варианта, определенная операцией пересечения частных параметров y_i, j = l,...,m.

Операция пересечения нечетких множеств может быть реализована различными способами. Обычно этой операции соответствует взятие минимума:

Μ _D(x_i) = min μ_ij, j = 1,…, m                                                                       (2)

Задача преобразуется в следующий вид:

                                       (3)

В алгоритм решения задачи (3) входят следующие шаги.

Шаг 1. Для каждого варианта x_i вычисляется значение конечной оценки качества μ _D(x_i) по формуле (2).

Шаг 2. Определяется максимальное значение конечной оценки качества:

Вариант x_k является решением задачи (3).

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

Преимущества модели:

q      модель и алгоритм ее решения довольно просты;

q      при использовании модели требуется минимальный объем входной информации;

q      использование данной модели всегда дает решение.

Модель абсолютного решения. При применении данной модели лицом, принимающим решение (ЛПР), задается минимальное допустимое значение mj_min для каждого параметра Y_j. Математическая запись задачи имеет следующую форму:

Алгоритм решения задачи имеет следующие шаги:

Шаг 1. Устанавливается минимальное допустимое значение  для параметра Y_j.: [0,1], j = 1,..., m.

Шаг 2. Рассматриваются варианты x-_t множества х, начиная с первого варианта x₁.

Шаг 3. Проверяется условие  начиная c j = 1.

Если условие выполняется, то переходим к шагу 4, иначе переходим к шагу 6.

Шаг 4. Определяется, все ли параметры проверены для варианта x_i.

Если j < т, то повторяем шаг 3 для следующего параметра (j = j + 1), иначе (все параметры проверены) переходим к шагу 5.

Шаг 5. Включается вариант x_i в множество X*.

Шаг 6. Определяется, все ли варианты проверены.

Если i < п, то повторяем шаг 2 для следующего варианта (i = i + 1), иначе (все варианты проверены) переходим к шагу 7.

Шаг 7. Проверяется пустота множества X*.

Если X* = Ø, т.е. ни один вариант не отвечает всем ограничениям, то переходим к шагу 8, иначе переходим к шагу 9.

Шаг 8. Перед ЛПР имеется два способа выйти из положения:

1) смягчить ограничение на один или несколько параметров я вернуться к шагу 2 для пересмотра вариантов;

2) расширить множество X, т.е. найти новые варианты: х_i’  X, и вернуться к шагу 2 для рассмотрения новых вариантов x_i’.

Шаг 9. Если множество X* содержит только один вариант, то решение задачи заканчивается, в противном случае (имеется несколько вариантов) у ЛПР есть два следующие пути;

1) выбрать один из вариантов множества X* и закончить решение задачи;

2) ужесточить ограничение на один или несколько параметров и вернуться к шагу 2 для пересмотра вариантов, входящих во множество X*, при этом на шаге 3 проверка проводится только для тех параметров, у которых ожесточается ограничение.

Недостатки модели: не учитываются уровни важности параметров. Возможен случай, когда вариант удовлетворяет ограничениям по важным параметрам, но не включается во множество X* из-за того, что не выполняется ограничение по менее важному параметру.

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

Задача принимает следующий вид:

                                                                             (4)

В алгоритм решения задачи (4) включаются следующие шаги.

Шаг 0. (подготовительный шаг). Сортируются параметры множества у по убыванию уровня их важности. Изменяются соответственно порядковые номера параметров, то есть первый параметр y₁ – самый важный, у₂ – чуть менее важный и т.д.

Шаг 1. Оптимизируется множество Х₀* по основному параметру. На данном шаге – это самый важный параметр, то есть первый параметр y₁. Лицом, принимающим решение (ЛПР), устанавливается минимальное допустимое значение по основному параметру .

Поиск оптимального решения на этом шаге ведется по формуле:

Шаг 2. Оптимизируется множество X₁* по следующему основному параметру у₂. Аналогично первому шагу, здесь устанавливается  и определяется множество Х₂*.

Шаг 3. Оптимизируется множество Х₂* по основному параметру

… шаги 4 + (m – 1) ...

Шаг m. Оптимизируется множество X*_т-1 по основному параметру у_m.

На каждом j-м шаге (j = 1,..., m) возможны следующие случаи:

q      найдется вариант, удовлетворяющий (по мнению ЛПР) требованиям по всем параметрам. Решение задачи (4) закончится на данном шаге;

q      множество решений не пустое (X*_j ≠ Ø) и не все параметры рассмотрены (j < m). Переходим на следующий шаг (j = j + 1);

q      множество решений пустое (X*_j = Ø). Смягчается ограничение па данном шаге и повторяем проверку либо возвращаемся к предыдущему шагу (j = j –1) со смягчением его ограничения.

После шага т, если множество решений Х_т* имеет несколько вариантов, то ЛПР может принимать одно из действий:

1) выбрать один из вариантов множества и закончить задачу;

2) вернуться к шагу 1, при этом начальное множество возможных решений определяется следующим образом: Х₀* = Х_m* и ужесточается ограничение на значение параметров. Решение проводится до того шага, когда во множестве решений останется только один вариант.

Преимущества модели (по сравнению с двумя рассмотренными моделями):

q      учитывается уровень важности параметров;

q      у ЛПР имеется возможность корректировать ограничение на значение параметра непосредственно на каждом шаге, что ускоряет процесс решения задачи.

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

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

Пусть уровни важности параметров заданы в векторном виде:

W = (w₁, w₂, ...., w_j,..., w_m),

где W_j – уровень важности параметра y_j; w_j принимает значение от нуля (параметр не имеет влияние на выбор) до единицы (параметр оказывает максимальное влияние на выбор). После установления значений w,- проводится их нормализация:

                                                                                                      (5)

Интегральный параметр качества вариантов будем обозначать через функцию F:

где F_i – значение интегрального параметра качества для варианта x_i. Функция F определяется по следующей формуле:

F = R × W,

или

т.е.                                                                                                          (6)

Задача при применении модели компромиссного решения преобразуется в следующую форму:

                                                            (7)

Алгоритм решения задачи (7):

Шаг 1. Установление уровня важности параметров w_j, j = 1, ..., m.

Шаг 2. Нормализация значение w_j по формуле (5)

Шаг 3. Вычисление для каждого варианта значения интегрального параметра f_i, i = 1, .... и по формуле (7).

Шаг 4. Определение максимального значения интегрального параметра.

Вариант x_k – это решение задачи (7).

Преимущества модели:

q      модель не только учитывает уровень важности параметров, но и долю влияния каждого параметра на общее решение, что устраняет недостатки модели основного параметра;

q      модель всегда обеспечивает наличие решения задачи.

Недостатки модели: высокое значение интегрального параметра f_i не гарантирует того, что вариант полностью соответствует всем выдвинутым требованиям. Низкое значение одного параметра (ниже, чем требуется при использовании модели абсолютного решения) может быть компенсировано высоким значением другого значимого параметра.

Модель эталонного сравнения. Модель разработана для устранения недостатков моделей, рассмотренных выше. Сущность модели заключается в следующем: строится эталонный вариант доставки грузов х₀. Параметры этого варианта принимают минимальные допустимые значения μ₀, j = 1, .... т. Каждый вариант множества X сравнивается с эталоном х₀. Если качество варианта x_i не хуже, чем у эталона х₀ по всем параметрам, то вариант х_i включается во множество решения и для него рассчитывается интегральный параметр качества f_i;. Для эталонного варианта интегральный параметр принимает нулевое значение f₀ = 0. Оптимальное решение – вариант с максимальным значением интегрального параметра f_max.

Математическая запись модели:

                                                                                  (8)

где

                                                                                              (9)

Алгоритм решения задачи (9):

Шаг 1. Построение эталонного варианта x₀ – установление минимальных допустимых значений μ_0j для параметра y_j, j = 1,..., т.

Шаг 2. Установление уровня важности параметров w_j, = 1, . . ., m.

Шаг 3. Нормализация значения w_j no формуле (5.21).

Шаг 4. Сравнение варианта *; множества X с эталонным вариантом x₀, начиная с первого варианта i = 1.

Проверяется условие: μ_ij ≥ μ_0j, j = l, ..., m.

Если не все условия выполняются, то переходим к шагу 6, иначе (все условия выполнены) переходим к шагу 5.

Шаг 5. Включение варианта х_i в множество X* и вычисление для данного варианта значения интегрального параметра качества f, по формуле (5.25).

Шаг 6. Определяется, все ли варианты проверены.

Если i < п, то повторяем шаг 4 для следующего варианта (i = i + 1), иначе (все варианты проверены) переходим к шагу 7.

Шаг 7. Проверяется пустота множества X*.

Если X* = Ø, то есть качество у всех вариантов множества X хуже, чем у эталонного варианта x₀, то переходим к шагу 8, иначе переходим к шагу 9.

Шаг 8. Перед ЛПР имеются два способа выйти из положения:

1) смягчить ограничение на один или несколько параметров путем перестроения эталонного варианта x₀ и вернуться к шагу 4 для пересмотра вариантов;

2) расширить множество X, то есть найти новые варианты: x_i’  X, и вернуться к шагу 4 для рассмотрения новых вариантов x_i’.

Шаг 9. Определение максимального значения интегрального параметра

Вариант x_k – это решение задачи (8).

На рис. 1 представлена блок-схема решения многокритериальной задачи при применении модели эталонного сравнения.

Недостатки модели: требуется больше информации (по сравнению с остальными моделями) от ЛПР.

Замечание. Модель эталонного сравнения является сочетанием модели абсолютного решения и модели компромиссного решения.

При установлении  т.е. не учитывается важность параметров, данная модель превращается в модель абсолютного решения.

Когда ЛПР задает:

или в более общем случае

модель эталонного сравнения действует аналогично модели компромиссного решения.

Из вышеизложенного можно утверждать, что модель абсолютного решения и модель компромиссного решения являются частными случаями модели эталонного сравнения.

 

 

 

Рассмотрим применение вышеизложенных моделей для решения задачи многокритериального выбора системы доставки грузов. Было предложено четыре варианта доставки грузов: x₁, x₂, x₃, x₄. Определено также три параметра качества доставки:

y₁ – срок доставки грузов;

у₂ – стоимость доставки;

y₃ – сохранность грузов при доставку.

 

Результаты опенки уровня качества каждого варианта по указанным параметрам показаны в табл. 1. Рассмотрим решения задачи выбора при применении разработанных моделей.

                                                                                        Таблица 1

 

Решение задачи по модели максиминной свертки

Определяются конечные оценки качества вариантов:

вариант 1: μ _D(x_t) = min {μ_1j; j = 1,2,3} = min (0,62; 0,70; 0,80) = 0,62;

вариант 2: μ _D(x₂) = min {μ_2j; j = 1,2,3} = min (0,50; 0,60; 0,70) = 0,50;

вариант 3: μ _D(х₃) = min {μ_3j; j = 1,2,3} = min (0,90; 0,80; 0,50) = 0,50;

вариант 4: μ _D(x₄) = min {μ_4j; j = 1,2,3} = min (0,80; 0,70; 0,60) = 0,60.

Максимальное значение конечной оценки качества вариантов:

 = max { 0,62; 0,50; 0,50; 0,60 } = μ _D(x₁) = 0,62.

Результат решения задачи– первый варианту.

Решение задачи по модели абсолютного решения

Установлены следующие минимальные допустимые значения параметров:

 =0,60;  = 0,50 и  = 0,60

Результат при проверке вариантов по формуле (2):

вариант x₂ (0,50; 0,60; 0,70) не отвечает требованию по параметру у₁.

вариант х₃ (0,90; 0,80; 0,50) не отвечает требованию по параметру y₃.

Оба варианта удаляются из множества решений.

Результат решений X* = {х₁, x₄} = {(0,62; 0,70; 0,80), (0,80; 0,70; 0,60)}

По параметру y₂ оба варианта x₁ и х₄ имеют одинаковое значение. По остальным параметрам у₁ и у₃ у вариантов различные значения. Однако ни один из вариантов не может быть оценен как более предпочтительный.

Решение задачи по модели основного параметра

Минимальные допустимые значения параметров были установлены, как в предыдущей модели. Кроме того, определено, что самый важный параметр – срок доставки грузов у₁, следующий параметр по уровню важности – стоимость доставки у₂. Параметр у₃ – сохранность грузов при доставке имеет самый низкий уровень важности.

Шаг 1. Оптимизируется по параметру y₁. Вариант х₂ исключается из множества решений (μ₂₁ = 0,50 <  = 0,60). Результат данного шага: X₁* = {x₁, х₃, x₄}.

Шаг 2. Оптимизируется по параметру у₂. Все три вариант соответствуют требованиям. Х₂* = {x₁, x₂, х₄}.

Шаг 3. Оптимизируется по параметру у₃. Вариант х₃ исключается из множества решений (μ₃₃ = 0,50 <  0,60). Х₃* = {x₁, x₄}.

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

Решение задачи по модели компромиссного параметра

Определены уровни важности трех параметров. После их нормализации вектор W имеет следующий вид:.

W = (0,50; 0,30; 0,20)^Т.

Вычисляем значения интегрального параметра:

или

F = {0,68; 0,57; 0,79; 0,73}.

f_max = f₃ = 0,79.

Вариант x₃ является оптимальным решением задачи по данной модели, хотя в предыдущих моделях он исключается из множества решений.

Решение задачи по модели эталонного сравнения

Чтобы не изменять условия задачи, принимаем эталонный вариант x₀ = (0,60; 0,50; 0,60) и вектор W= (0,50; 0,30; 0,20)^Т.

Как в случае применения второй и третьей моделей, варианты х₂ и x₃ исключаются из множества решений. Остаются два варианта: х₁ и х₄.

X* = {х₁, х₄}. Их интегральный параметр принимает следующие значения:

f₁ = (0,62 – 0,60) × 0,50 + (0,70 – 0,50) × 0,30 + (0,80 – 0,60) × 0,20 = 0,11,

f₄ = (0,80 – 0,60) × 0,50 + (0,70 – 0,50) × 0,30 + (0,60 – 0,60) × 0,20 = 0,16.

Результат решения задачи – вариант х₄ = (0,80; 0,70; 0,60).

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