Вычисление весовых коэффициентов важности
Для і = / \ / в силу работы алгоритма 1 следует, что
- Qt (х) до* - Q. (де), і е I \ /.
Іаким образом получим N неравенств*
wi ¦ Qt (х) до,* - (ж), і е /. (2.59)
Каждое неравенство (2.59) разделим на положительную величину Qfx) к просуммируем по і:
Ы N
?!= R R;
i=i і=і
следовательно,
до, - до!, і = 1, N,
что противоречит условию до * до*.
Следовательно, до* оптимальный вектор задачи (2.55)(2.56).И При до0 = 0 получаем однократное применение алгоритма 1, что соответствует теореме 2.2.
Лемма 2.3. В случае отсутствия дополнительной качественной информации (2.58) решением задачи (2.55), где
N
Dw= {до I до, до0 0, і = TJ3; ? wi = R }. (2.60)
=i
и при условии перенумерации критериев таким образом, чтобы выполнялось условие Qx (х) - - - - - Qn (х), является вектор х?*, компоненты которого определяются по формуле
w0, у = ТТпR - г¦ ш0 -
-Л-, у = г + 1 ,Ы,
?,(*)¦ L (!/?(*))
і = л+ 1
где г наибольший индекс к, при котором выполняется условие
(2.62)
R- г - w0
-В-9-5 "('
Qt (X) - ? (l/Q. (X))
i=r+l
Доказательство
В случае отсутствия дополнительной качественной информации выполняется условие ?2 = 0 и граф G (/, ?2) состоит из одного слоя (S = 1). Рассмотрим работу алгоритма 2 в этом случае. Так как граф G (/, Q) состоит из одного слоя, то в результате применения алгоритма 1 получим
Г N
?/(*)- X (!/?,(*)
і=і
Так как по предположению (дг) ... QN (х), то нетрудно убедиться, что
w'x ... w’N.
Обозначим через г максимальный индекс к, при котором выполняется условие w'k гг0. Согласно построению алгоритма 1 (шаг 4) для
всех w*k, к - 17?. получим ?и*к = а0; для всех wk, к = г + 1, N, получим
, R - г - w,
'/ ~ N
Q, (*)- I (1/?,W)
. = .-+і
что соответствует (2.61 )Л
При R = 1 и w0 = 0 выражения (2.61 )-(2.62) аналогичны результату, полученному в [20]:
w] = -^-, j = ГЖ (2.63)
Qj(x)Jj(l/Q.(x))
/= 1
При использовании обобщенного критерия оптимальности (2.46) задача нахождения весовых коэффициентов формулируется следующим образом.
в** (х) = arg { max F (w, Q (де))} = we Dw
= arg { max max (w, Q (x))}, (2.64)
we Dw 1iN
где область допустимых значений весовых коэффициентов Dw имеет вид (2.44).
Для сформулированной задачи (2.64) справедлива следующая теорема.
Теорема 2,4. Оптимальным решением задачи
w* (ж) = arg { rnaxf х (w, Q (x))} = we Dw
= arg { max max (w, Q (ж))}, (2.65)
we Dw liN
где
N
Dw= {w I w0 0, i= 1, N; ?w. = Я;
i=l
(2.66)
(2.67)
(?[ _
w. w., 1= T7T},
является зектор w* с компонентами R- (//- nr)-w0
J Пг ’ 1 G !r'
W0, ie !\lr,
где индекс г определяется из соотношения
Доказательство
Нетрудно видеть, что ?а* является допустимым вектором задачи (2.65)(2.66). Покажем, что w* является ее оптимальным решением.
Допустим (от противного), что существует вектор w' е Dw, являющийся допустимым вектором задачи (2.65)-(2.66), такой, что выполняется соотношение
^max^ w\ Q{ (ж) = ш'( Q, (ж)
(2.G8)
Яг =
max 1kN
Як
R- (N - n.) ¦ w0
Qk (*)-
(2.69;
Як =
(2.70)
. R - (N - п ) - wa
max w. Q. (ж) = ---a Q. (ж).
1iN 11 nr
Далее, из соотношений (2.68)(2.69) следует, что
R- (N- nr) wо R- (N- nk)-w0
nr nk
Из (2.70) и (2.71) следует, что R- (N- nk) ¦ w0
Q.(x), k= T7W. (2.71)
(2.72)
Q. (ж), k = 17W,
w', Q, (x)
в частности, при k = l получим , R- (N- n,)- w0
(2.73)
Для всех i t имеет место соотношение w. wv откуда можно записать
(2.74)
(2.75)
R - (N - n,) ¦ w0
w . -----,
l n.
w'{ W0, t€ I \ /,. Из (2.74) следует, что
, R- (N- nr) w0
nr= R- (N - nr)- ш0;
іб I,
а из (2.75) следует, что
Отсюда получаем неравенство
N
Y,wi= X w\ + Y,wi R
/=1 ie If ie /\/(
что противоречит предположению о допустимости вектора w' и доказывает теоремуЛ
В случае линейной упорядоченности частных критериев оптимальности и области допустимых значений весовых коэффициентов вида (2.36) оптимальным решением задачи (2.65) является вектор
весовых коэффициентов хи с компонентами
R- (N - г) - w0
і = Т77; і= т + 1 ,N,
(2.76)
wi =
w,
о*
где индекс г определяется из соотношения
qr = ,m?xxl (2.77)
]?kN
R - (N - k) - wQ k
Qk{x).
(2.78)
Это следует из того, что в случае линейной упорядоченности по важности частных критериев оптимальности выполняются соотношения Іг=т- { 1.....г}, |/J = г.
При отсутствии дополнительной качественной информации о предпочтениях на множестве частных критериев и области допустимых значений весовых коэффициентов Dxw (2.40) оптимальным решением задачи (2.65) является вектор весовых коэффициентов хи* с компонентами, определяемыми выражениями
, 17? - (N - 1) - wQ, i = r,
W. = s ,
' [ш0, i UN, i* r,
где индекс г определяется из соотношения
7 = max Qk(x) r 1 kN *
Вычисление весовых коэффициентов важности при использовании среднестепенного обобщенного критерия оптимальности
Рассмотрим решение задачи вычисления весовых коэффициентов важности при использовании среднестепенного обобщенного критерия.
Для экстремальной задачи
w (ж) = arg { max F (хм, Q (.x))}, (2.79)
we Da, и
где
N
Fp (хм, Q (x)) = [ ? w. ?? (x) }l/p, (2.80)
Dw= {w\wj w0 0, i = TTN-, Y,wi=
/=1
со/ , _
w{ w., (!),= {?fi Qj}, l= Т7Г} (2.81)
может быть сформ?лирована следующая теорема.
Теорема 2.5. Для любых р (0 р ) оптимальным решением
задачи (2.79)- (2.81) является вектор хм* с компонентами
[R- (N - пг) - ш0
хм* = \ пг ’ (2.82)
1®о* іе Л/-
где индекс г определяется из соотношения
(2.83)
Доказательство
Проведем доказательство данной теоремы с помощью метода динамического программирования [14]. Для этого обобщим задачу (2.79)(2.81) следующим образом. Требуется распределить ресурс Rk между k объектами, каждый из которых характеризуется значением Qj частного критерия так, чтобы выполнялось условие
max F (w, ? (ж)), (2.85)
Р
где
(fi- nr) w0^„
n 2u
r
R-
(*)+ VI ?/(*) fP-
tel\lk
(2.84)
qu= [
1Wi= Rk’ (=1
= {w\wj w0 0, i = 1, М\
(О/ _
w. Wj, /= 1, L}. (2.86)
Разобьем граф G (/, Q) на 5 слоев и перенумеруем вершины, начиная со слоя S и выше. Внутри каждого слоя будем нумеровать вершины в произвольном порядке. Введем следующие обозначения:
множество вершин графа G (/, ?2), находящихся на слоях s t, из которых есть путь в вершину j, включая ее саму: /' = 1, N,
t= T7S\
lt множество вершин на слое t, t = 1, S;
множество вершин, в каждую из которых есть путь из вершины j, / = 1, JV;
nij мощность множества І*ц
Qt = Qt (х), i = 1, N, для фиксированных значений х.
Используя введенные обозначения, построим многошаговую модель принятия оптимального решения.
1. В качестве управляемого параметра выбирается количество ресурса, выделяемого і-му объекту, т. е. значение весового коэффициента важности t-го частного критерия.
2. Область решений определяется выражением (2.85).
3. В качестве фазовой переменной Rt выбирается количество ресурса, распределяемого по остальным (і 1) объектам.
4. Начальное состояние: RN+l = R-
5. Уравнение состояния: R( = Ri+l~ wp i= 1, N.
6. Результат:
Y(wi,Ri+1= urtf(x).
7. Семейство функциональных уравнений:
fk я*+1 = max (H wi Qi *) ]1/Pb
wi.....wk j=i
X = #*+ p wi - wo i=
i= 1
wt Wp l= T7L, *, / e {1.....?}.
Нетрудно видеть, что рекуррентное соотношение динамического программирования имеет следующий вид:
N
fk +0= max { max {tZ wi Qi W]1/p} =
Щ .....Wk-l i= 1
N
max {[ wt Qf (x) + max {? wp Qp (x)} ]l/p} =
Щ i=l
= max {[ ®. Qp (x) + fk_l (Rk) ]i/p}. wk
Очевидно также, что на каждом шаге оптимизации на значение управляемого параметра накладывается ограничение:
Rl+l- (i- l)w0 wt w'.,
где
(2.87)
# [max ,w„ если Л* 0;
w f = ^ 6 / 1 a n
Іш0, если 1=0. Для слоя 5 можно записать:
U (Л2) =
max
wqs is R 2 R1= R2~ і=
/2(/?2)= max {[*2^2+ /?(*s~ w2)]l/p} =
* * WQiW^R2~WQ 1 * 1 *
/?2= J?3- ®2= 0
= max {[ (/?3 - a0) Q\ + ш0 Qp]l/p; [ (*3 - w0)Qp + w0Qp]l/p}-,
'(*- .*„T*,- J.0 (1"з?а+ "$)l'7')-
Лз= Л 4- ш3= О
= max {[ (R3 - 2а/0) + ш„ (?? + Q%\l/p;
[(/?з- 2w0)Qp+ w0(gf+ ]1/p;
К*- 2ш0)?' + ш0^+ ]1/p;
// *i + i = ,Frax,{ I *i+ i " *. - 1)",0)^ +
IS Га *5 s
(2.88)
=i
it r
Итак, очевидно, что для последнего слоя 5 сформулированная теорема справедлива.
Рассмотрим произвольную вершину п на слое s S в предположении, что для слоя (s + 1) теорема справедлива.
Тогда можно записать:
К (Rn+ 0 = та* . UwnQPn+ fn-i (*я+1 wn ]l/P} =
wnz w n Rn= RiH-l-Wn
771
= шах {|a max ([-
wni w n IS tuS /- 1
Rn= Я/Н- Г
+ "V ? ФЛ17' = Jjax r„ /?„,,,.).
*л=Л/н-1- w„
л* *лі-1- (я- l)0
wnS/J„+1- (n- 1) wo -1
7=1 i* m
Функция f'n является монотонной относительно wn и, следовательно, достигает своего максимального значения на одном из концов интервала [ 'n; Rn+l - (я - 1) до0 ].
а) Функция /'д достигает максимального значения при wn = Rn+l - (я - 1) w0. Тогда
- o’ief]17'.
1=1
б) Функция f'n достигает максимального значения при м/п = w'n. В этом случае
шах +
1 /I 1
*+l~ (Я- - О,
л- I
- х
1 = 1
/!
іе /*
+1
т.
Если wn = wQ, тогда
¦о о:+
в-1
(2.89)
т.
1=1 іе /!
іе I
Если wn = в/п = wk, где вершина с номером к находится на слое, лежащем ниже слоя s, тогда
*я+1- Wn~ (Я- тГ1 Uw,
до = ч
S+ 1
тя
или
Wn *в+і (Я- тг + 1- D®!
n s +1 тг
S+ 1
т.
тогда
/ *+1 ч
(2.90)
/^=/^+1u{n}, то
(я- тг - l)w0
*+і , ,
тг +1
Так как выполняется условие т*= т* + 1 + 1, и из этого следует, что
(я - тг)Щ w = ---
п s -
тг
а значение функции
іе Г1
Г
тЛ wn „
-d-*][Qpn
{[JW
(я-
5% п-\
т.
+ (2-91)
/= 1
/;
Таким образом, выражения (2.88), (2.89), (2.91) показывают, что теорема справедлива и для слоя з.
Для вершины с номером N, учитывая, что Rn+i = R, можем записать:
l/P
м*-
о I
іе l\l
(2.92)
+ w.
max
1гй N
іе I
откуда следует справедливость сформулированной теоремы в целом для всех возможных ситуациЗЛ
При р-1 выражения (2.82)-(2.84) аналогичны оптимальному решению (2.33)~(2.35) для аддитивного обобщенного критерия оптимальности.
Вычисление значений весовых коэффициентов важности при использовании метода идеальной точки сводится к решению экс-тремальной задачи:
(2.93)
w (*. ?*) = arg { max F (w, Q (ж), Q*)}, we Dw
F (да, Q (ж), Q*) = X wt (? (*) ~
і= l
или
F (да, Q (ж), Q*) = max { да, (?, (ж) - ?*)}; ]iN ' ‘
- oo min Q, (ж), i = 1, N; xeD
Dw= {да I дау S да0 0, i = TJf; ? да, =
где
i= l
да, S да^, / = 1, L }.
Применение положительного линейного преобразования \|/ = (?,,сохраняющего истинность отношений предпочтения (Q (ж) = у (Q (ж))), с компонентами
V,- (*) = V/ (?і W. ?¦) = ?,- (*) - * = TTW, (2.94)
позволяет перейти к эквивалентной (2.93) экстремальной задаче следующего вида:
да* (ж) = arg { max F (да, \р (ж)}, (2.95)
даеДр
оптимальное решение которой может быть получено одним из вышеописанных способов.
Глава 3 ДИАЛОГОВАЯ ПРОГРАММНАЯ СИСТЕМА МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА
В настоящей главе дадим общую характеристику диалоговых систем поддержки принятия решений в условиях многокритериального выбора и представим диалоговую программную систему, построенную на основе описанных моделей и методов: архитектура, возможности и средства организации человеко-машинного интерфейса.
Назначение и архитектура системы
Развитие теории и методов принятия решений в условиях мно-гокритериальности, с одной стороны, и развитие персональной вычислительной техники, позволяющей приблизить ЭВМ к реальному пользователю - с другой, дали толчок развитию систем поддержки принятия решений (СППР) как диалоговых программных систем (ДСППР).
ДСППР предназначены для оказания помощи пользователям в ситуациях выбора: во-первых, ДСППР выступают в роли помощников ЛПР, расширяющих его возможности, но не заменяющих его мнение и систему предпочтений; во-вторых, они предназначены для использования в ситуациях, когда процесс принятия решений ввиду учета субъективного мнения ЛПР не может быть полностью формализован на ЭВМ.
ДСППР можно определить следующим образом: ДСППР это человеко-машинная информационная система, используемая для поддержки действий ЛПР в ситуациях выбора, когда невозможно или нежелательно иметь автоматическую систему представления и реализации всего процесса оценки и выбора альтернатив.
Наиболее полные обзоры существующих ДСППР приведены в работах [17,45]. В частности, среди них можно отметить следующие:
- ДИСО/ПК-МКНЛП (Евтушенко Ю.Г., ВЦ РАН): диалоговая система, реализованная на ПЭВМ типа IBM PC, позволяющая строить одну из эффективных точек многокритериальной задачи оптимизации путем решения задачи нелинейного программирования с заданным обобщенным критерием;
ВЕКТОР (Растригин Л. А., Рижский политехнический институт): система, реализованная на СМ ЭВМ, ориентированная на проектирование сложных систем в многокритериальной постановке с помощью схем скалярной свертки и векторно-релаксационных алгоритмов поиска;
ВЫБОР (Виноградская Т. М.): система, реализованная на ПЭВМ ИСКРА-220, позволяющая выделять недоминируемые альтернативы с помощью свертки;
DISMOP (Михалевич В. С., Волкович В. Л., Институт кибернетики АН Украины): система для решения многокритериальных задач с помощью метода ограничений и человеко-машинных процедур;
MUFCAP: система, реализующая методологию теории полезности для принятия решений по многим критериям в условиях риска и неопределенности;
CRITERIUM: система для решения многокритериальных задач путем построения и анализа дерева целей;
EXPERT CHOICE: система, предназначенная для решения многокритериальных задач с помощью анализа предпочтительности критериев.
Имеются и другие системы поддержки принятия решения, однако они, как и вышеуказанные системы, ориентированы на квалифицированного пользователя, который должен быть хорошо осведомлен в методах оптимизации.
Описываемая диалоговая система многокритериального выбора проста и доступна для широкого круга пользователей, не требует от них знаний в области математики и программирования.
ДСППР можно классифицировать по различным признакам, в частности [17]:
а) по характеру поддержки решения:
ДСППР специального назначения, рассчитанные на решение определенного класса задач;
универсальные ДСППР, обеспечивающие возможность быстрой настройки на конкретную задачу конкретной предметной области;
б) по характеру взаимодействия человек ЭВМ:
инициатором диалога при работе системы является ЭВМ, пользователь лишь пассивный исполнитель;
инициатор диалога пользователь, ЭВМ пассивный исполнитель;
управление диалогом попеременно ведут пользователь и ЭВМ;
в) по наличию и характеру базы данных:
система не предусматривает хранение и накопление информации;
система имеет базу данных в виде совокупности файлов;
система имеет развитые средства управления базами данных.
Описываемая диалоговая система поддержки принятия решений относится к типу универсальных систем, инициатором диалога в которых выступает пользователь, а ЭВМ лишь пассивный исполнитель. Для управления системой (рис. 4) можно использовать команды, реализованные с помощью функциональных клавиш. Система предназначена для выбора одной из множества альтернатив, каждая из которых оценивается по нескольким критериям.
Исходные данные при этом представляются в виде таблицы варианты критерии.
Программная поддержка полного цикла принятия решения в многокритериальной задаче оптимизации с учетом индивидуальных предпочтений обеспечивается подсистемами, реализующими выполнение четырех взаимосвязанных этапов.
1. Ввод и обработка исходных данных.
На первом этапе пользователь формирует множество критериев, создает тезаурус и осуществляет проблемную ориентацию системы на терминологию конкретной предметной области.
Исходные данные для решения задачи многокритериального выбора представляются в виде таблицы номер варианта частные критерии. Элементами таблицы являются оценхи векторного критерия, измеренные для каждого варианта либо с помощью объективных измерений (численные значения), либо с помощью субъективных измерений (лингвистические переменные, балльные оценки).
Диалоговая система представляет программные средства, чтобы
удалять или вставлять как конкретные варианты, так и отдельные частные критерии;
изменять оценки частных критериев;
преобразовывать субъективные оценки в количественные по шкале желательности Харрингтона;
приводить значения частных критериев к безразмерному виду с общим началом отсчета и единым интервалом изменения.
2. Выделение подмножества решений, оптимальных по Парето.
На втором этапе пользователь формирует исходное множество
альтернатив путем ввода численных значений оценок альтернатив по частным критериям.
Для визуализации векторных критериев строится диаграмма Кивиата круговой график, радиусы которого используются как оси для представления соответствующих численных значений частных критериев. При этом отмеченные для конкретного варианта точки соединяются в виде многоугольника (принято, что дальние от
центра точки соответствуют лучшим значениям частного критерия).
Диалоговая система позволяет исключать из дальнейшего рассмотрения все доминируемые варианты и оставляет для сравнения только варианты с противоречивыми частными критериями.
3. Выбор оптимально-компромиссного решения.
Свертывание векторного критерия осуществляется путем построения скалярного обобщенного критерия, в котором относительная важность частных критериев учитывается с помощью весовых коэффициентов.
Диалоговая система предоставляет программные средства, чтобы
выбирать разные типы обобщенного критерия (критерий максимальной осторожности, среднестепенной критерий, мультипликативный критерий, аддитивный критерий и др.);
- задавать в интерактивном режиме конкретные численные значения весовых коэффициентов.
В качестве оптимально-компромиссного решения диалоговая система выбирает тот вариант из множества противоречивых вариантов, который обеспечивает минимальное значение заданного пользователем обобщенного критерия с фиксированными значениями весовых коэффициентов.
4. Задание отношений предпочтения между частными критериями.
Четвертый этап работы с системой включает ввод качественной информации о попарных частичных предпочтениях на множестве критериев и построение графа относительной важности частных критериев оптимальности.
Диалоговая система предоставляет пользователю программные средства для задания на множестве частных критериев бинарных отношений предпочтения. Качественная информация о парных сравнениях между частными критериями (заданная необязательно для всех возможных пар) анализируется на непротиворечивость и используется для автоматического вычисления весовых коэффициентов. При этом весовые коэффициенты считаются неконтролируемыми факторами и их назначение производится путем решения экстремальной задачи, реализующей принцип гарантированного результата.
В этом случае оптимально-компромиссным решением является вариант, который обеспечивает наименьшее значение обобщенного критерия при вычисленных для наихудшего случая весовых коэффициентах.
Для удобства анализа и наглядности качественная информация отображается в виде графа бинарных отношений, где вершины представляют собой частные критерии, а дуги соответствуют парным предпочтениям, введенным пользователем.
5. Отображение результатов решения задачи.
Визуализация данных и результатов решения задачи осуществляется в режиме многооконного интерфейса.
Диалоговая система представляет программные средств? для
выполнения следующих действий:
отображение значений частных критериев в численном виде или в графической форме в виде диаграмм Кивиата;
отображение результатов анализа на принадлежность альтернатив множеству доминируемых вариантов или множеству противоречивых вариантов:
отображение весовых коэффициентов в табличной форме или в виде диаграмм Кивиата;
отображение результатов минимизации обобщенного критерия, с выделением оптимально-компромиссного решения, в табличной форме и в виде столбиковых диаграмм.
Система реализована на персональной ЭВМ IBM PC. Мощность системы составляет 15 критериев и 50 альтернатив.
Организация взаимодействия человек - ЭВМ
Важную роль в современных системах поддержки принятия решений играют средства организации и ведения диалога человек ЭВМ
Под диалогом подразумевается процесс непосредственного и быстрого обмена сообщениями между двумя субъектами, при котором существует постоянная смена ролей информатора (посылающего сообщение) и реципиента (воспринимающего сообщение). В литературе отмечается, что в диалоговых системах описываемого типа общение человека с ЭВМ на языке, близком к естественному, неудобно: во-первых, высока трудоемкость такого диалога, т. е. затраты на ввод информации со стороны человека и на обработку ее со стороны ЭВМ; во-вторых, применение такого режима увеличивает вероятность неоднозначного толкования информации и возникновения ошибок. Поэтому наибольшее распространение получили режимы общения человек ЭВМ типа меню (при котором пользователь осуществляет выбор одного из предлагаемых системой вариантов) и команд фиксированной структуры.
На персональных ЭВМ типа IBM PC команды часто передаются через функциональные клавиши. Оба эти режима используются в описываемой системе.
Визуализация данных и результатов в системе осуществляется в режиме многооконного интерфейса, под которым понимается разделение экрана дисплея на семантически независимые части. В данной системе на экране отображаются пять окон (рис. 5):
1 окно характеристик критериев;
2 окно характеристик альтернатив;
3 визуализация характеристик указанных альтернатив в виде диаграммы Кивиата (кругового графика, радиусы которого исполь-
| Диалоговая система многокритериального выбога | |||||
| N | Наименование | Размерность | Тип | И 1: Первый | К 1: Первый ! |
| 1 2 3 4 5 6 7 |
Йппаратнне_сродства Операционная_система Лингв лроцессоры Возмохности_переноса Управление_данными Надехность_поставщ Средотвалрограмм 1 |
балл балл балл балл балл балл балл |
Нах Нах Пах Нах Нах Нах Нах |
7 5 5 9 6 6 7 2 |
0.475 0.01 0.475 0.01 0.01 0.01 0.01 |
| ______ - | |||||
| 1 Диаграмма Кивиага ¦ W- |
Предпочтения V 5 6 7 \\ 4 |
||||
| 3 5 |
зуются как оси для представления соответствующих численных значений частных критериев);
4 отображение графа предпочтения, содержащего дополнительную информацию о частных предпочтениях типа to, = {Qt )- Q.},
