Батищев Д. - Многокритериальный выбор с учетом индивидуальных предпочтений

РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРИКЛАДНОЙ ФИЗИКИ
В монографии рассматриваются человеко-машинные процедуры решения задач многокритериального выбора.
Основное внимание уделяется анализу и использованию качественной информации об относительной важности критериев оптимальности при принятии решений. Описывается диалоговая программная система многокритериального выбора и приводятся примеры решения конкретных задач.

ВВЕДЕНИЕ

Задачи принятия решений представляют собой широкий класс задач в различных предметных областях, в частности в системах автоматизированного проектирования (САПР) и в автоматизированных системах научных исследований (АСНИ). При этом проектировщик (исследователь, разработчик) должен, во-первых, подготовить множество допустимых для выбора вариантов решения, во-вторых, сформулировать цели принятия решения и, в-третьих, осуществить выбор либо одного, либо множества решений, оптимальных с его точки зрения. Одной из возможностей решения поставленной задачи является переход от задачи принятия решения к задаче нелинейной оптимизации.
Однако такой переход связан с рядом трудностей. Основная трудность - преодоление неопределенности целей. Для сведения задачи принятия решения к задаче нелинейной оптимизации проектировщик должен оценить качество каждого варианта в виде числовой характеристики (критерия) и выбрать лучший вариант с наибольшим (или наименьшим) значением.
Но дать такую оценку довольно сложно. Техническое устройство характеризуется несколькими критериями качества, зачастую противоречивыми, т. е. улучшение одной характеристики приводит к ухудшению другой.
Для решения подобной многокритериальной задачи необходимо учитывать относительную важность частных критериев оптимальности.
Наиболее распространенный способ учета предпочтений проектировщика назначение критериям весовых коэффициентов. Но неопределенность остается: одинаковые предпочтения могут определить совершенно разный набор весовых коэффициентов.
В данной монографии описываются эффективные человеко-машинные процедуры многокритериального выбора, обеспечивающие сочетание экспертной информации об отношениях предпочтения на множестве критериев с результатами решения экстремальных задач, обеспечивающих эффективность по Парето.
Описываются различные методы решения многокритериальных задач оптимизации, использующие качественную и количественную информацию о предпочтениях на множестве критериев. Основное внимание уделено методу свертывания векторного критерия оптимальности с использованием весовых коэффициентов относительной важности частных критериев.
В качестве обобщенных критериев рассматриваются аддитивный критерий оптимальности; обобщенные логические критерии оптимальности; среднестепенной обобщенный критерий.
Описываются существующие способы назначения весовых коэффициентов, при использовании которых от лица, принимающего решение (ЛПР), требуется либо дать точные численные оценки, либо сравнить по важности все частные критерии между собой.
Предлагается подход, при котором учитывается зависимость весовых коэффициентов от значения частных критериев в каждой точке области допустимых решений. В этом случае весовые коэффициенты можно рассматривать как неконтролируемые факторы с областью допустимых значений и вычислить их, применяя принцип гарантированного результата.
Подробно рассматриваются виды дополнительной качественной информации об относительной важности частных критериев и их влияние на область допустимых значений весовых коэффициентов.
Вторая глава содержит решение задач по определению по принципу гарантированного результата оптимальных значений весовых коэффициентов важности для различных типов обобщенных критериев и-дополнительной информации о бинарных отношениях предпочтения при заданных значениях векторных оценок альтернатив. В п. 2.1 приводится решение задачи вычисления весовых коэффициентов для аддитивного критерия оптимальности. В п. 2.2 приводится решение задачи вычисления весовых коэффициентов для обобщенных логических критериев оптимальности.
В п. 2.3 приводится решение задачи вычисления весовых коэффициентов для среднестепенного обобщенного критерия. Решения приводятся в аналитическом виде или в виде алгоритмов вычисления.
Все решения приводятся в виде теорем с доказательствами.
Третья глава посвящена характеристике диалоговых систем поддержки принятия решений. Описывается диалоговая программная система, построенная на основе разработанных моделей и методов: архитектура, возможности, средства ведения диалога.
В четвертой главе приведены примеры решения конкретных практических задач.
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований. Грант 94-01-01465.

Глава 1 ПОСТАНОВКА И МЕТОДЫ РЕШЕНИЯ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА

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

Задачи многокритериального выбора и подходы к их решению

В связи с развитием автоматизированных систем проектирования (САПР) и управления (АСУ) все больше внимание ученых и специалистов привлекают новые информационные технологии, основанные на использовании ЭВМ и математического моделирования, включающего в себя методы построения и анализа математических моделей. Особое место в новых информационных технологиях занимает проблема принятия решений при наличии нескольких критериев оптимальности, которые обычно являются противоречивыми в том смысле, что не существует решения наилучшего одновременно по каждому из них.
Для построения математической модели принятия решений в условиях многокритериального выбора введем ряд вспомогательных определений.
Под сложной системой будем понимать материальный или абстрактный объект, относительно которого может приниматься одно решение из множества возможных на основе анализа описывающей данный объект информации.
Данное весьма абстрактное определение охватывает широкий круг конкретных задач (оптимизацию режимов функционирования конкретной технической или технологической системы; выбор конкретного типа приобретаемого оборудования; определение параметров проектируемого устройства и т. д.). Однако, несмотря на различие описывающих эти сложные системы математических моделей, характерной общей чертой в них является наличие качественной информации о предпочтениях между вариантами сложной системы и формирование на ее основе критериев оптимальности, позволяющих сравнивать варианты решения.
Под лицом, принимающим решения (ЛПР), будем понимать исследователя (разработчика, проектировщика, инженера и т. д.), который стремится поставить и решить задачу (принять решение) в конкретной предметной области на основе своих представлений относительно важности параметров х = {х_?..., х_п) и характеристик у = (у_?
.... у_т) описываемой сложной системы.
ЛПР определяет наилучшее, с его точки зрения, рациональное решение, под которым понимается наличие рациональных, понятных другим людям причин, приведших к выбору данного решения из множества альтернативных.
Под математической моделью сложной системы будем понимать зависимость характеристик у = {у_{.....у_т) системы от ее параметров х - (х_?...,х_п):
Уі= Уу(х .....х_п),
(1.1)
Зависимости у_{ = у₍ (лс), і = 1, т, могут быть описаны различными способами (с помощью аналитических выражений, совокупности таблиц, алгоритмов или программных систем). В дальнейшем будем считать, что математическая модель сложной системы представляет собой черный ящик (рис.
1).
Под математической моделью принятия решения будем понимать следующий набор элементов:
список варьируемых параметров,
область допустимых решений задачи,
список критериев оптимальности,
метод выбора рационального решения из множества допустимых.
В процессе принятия решений (выбора конкретных числовых
значений вектора варьируемых параметров х) необходимо учитывать только допустимые значения, соответствующие характеристикам предметной области. Эти ограничения могут быть сформулированы как система линейных и нелинейных выражений:
У,
Математическая модель объекта
Параметры управления х Характеристики У
Рис. I. Схема математической модели объекта
a_j Xj Ь., / = Т7л,
у~ Уі(х) у*, і = TTm, (1.2)
где dj, bj фиксированные значения /-го параметра, характеризующие область его допустимых значений и зависящие от эксплуатационных, технологических, физических требований и других условий;
у~, у. ограничения на значения требований, налагаемых на і-ю характеристику в соответствии с техническим заданием.
В общем случае область D допустимых решений, удовлетворяющих системе (1.2), может быть представлена в виде следующего множества:
D = {* I g_k (х) 0, k = ТГК}.
В дальнейшем будем считать, что область D непуста. Тогда для оценки относительной важности одного допустимого решения
хк е D по сравнению с другим допустимым решением х1 е D введем частный критерий оптимальности Q_{ (х), і = 1, N, который
k
позволяет считать, что решение х не менее предпочтительно, чем
і
решение х, если выполняется соотношение
хк }¦ х1 Q, (Л (1.3)
где Q_{ (х) численная оценка решения х в соответствии с частным критерием оптимальности Q_{, измеренным в некоторой шкале А (Q_t) множестве числовых значений.
В таком случае математическая модель принятия решений
представляет собой задачу нелинейного программирования:
Q\= Q_t{x)= mina (де). (1.4)
же D
Если в задаче принятия решений существует несколько частных критериев оптимальности Q. (ж), і = N, то ЛПР должно выбрать
допустимое решение ж е Д обеспечивающее наименьшее значение N частным критериям оптимальности одновременно. Тогда математическая модель принятия решений представляет собой задачу многокритериальной (векторной) оптимизации:
min Q. (ж), min Д(ж), .... min Q„(x). (1.5)
же D же/) ж е?
В частном случае задача принятия решений может представлять собой выбор рационального проекта, характеризуемого набором параметров ж из множества нескольких технических проектов с
параметрами ж , k = 1, М, определенными в табл. 1 альтернативы критерии, где Q_t (ж*) значение і-го частного критерия оптимальности для ?-го вект^оа варьируемых параметров.

Таблица 1

Альтернативы Параметры Ж* Критерии 01 02 Qn Проект 1 ж1 Qi О*1) 02 (Л1) ... Qn (л1) ... ... Проект М Xм 01 (Ж*1) 02 (***) ... 0* (Ж*)

Здесь математическая модель принятия решений представляет собой задачу многокритериального выбора:
(1.6)
min Д(ж), Ж 6 { ж1, ....Ж*}
/т/п mxQn(x)-же{ ж1.....ж}
Далее будем считать, что шкалы измерений частных критериев оптимальности (^(ж), і = 1, N определены и численное значение
вектора Q (ж) = (?_L (ж),..., Q_N (ж)) может быть получено для любого
допустимого решения же D. Допустим также, что частные критерии оптимальности имеют одинаковую шкалу измерения [а, Р], О а р, и приведены к безразмерному типу при помощи, например, положительного линейного преобразования, сохраняющего отношения предпочтения на множестве численных оценок А (QJ):
(1.7)
_ Q, (.х) - QJ
V, (Q, (*)) = $,(*)= ;1 (Р - а)+ а,
Q_t - Q_{
Q+i = max Q_t (де); QJ = min (де); Qj * QJ, i = TJJ. xeD xeD
В данной модели коэффициент a_f = (Р - ol)/(QJ - QJ) характеризует шкалу, коэффициент b_{ = (aQj - р(?7)/(?; - QJ) позволяет привести частные критерии оптимальности к общему началу отсчета и к одинаковому интервалу измерения.
Областью критериев D_Q назовем отображение области допустимых решений D cz Rn в пространстве RN:
D_q= {?!?,= ?,(*), i=T7N; хе D}. (1.8)
k k k k
Любые два векторных критерия Q = (Q_l.....Q^= (@i (* )
Q_n (**)) и Ql = (Qp ..., Ql_N) = (Q_{ (x‘),.... Q_n (x')) являются противоречивыми, если Q!, i e I_v Q* Q*, / e /₂, I_XU1₂ = {1 N} и
по крайней мере одно из этих соотношений является строгим. В случае доминирования Qk над Ql: Qk Ql_f, i = 1, N, и хотя бы для
одного из і это неравенство строгое, альтернатива х может быть
и
исключена из рассмотрения, так как альтернатива Q лучше альтернативы Q1 по всем частным критериям.
Совокупность векторов Q е Dq, для которых нет ни одного доминирующего их вектора из области критериев D_Q, образует область компромиссов D_k с D_Q, а соответствующие им значения параметров х образуют область решений, оптимальных по Парето D_pcz D :
D_k= {Q е DjnBQ'tQ'e D_q,Q* * Q): Q. Q., i= TJJ),
D_p = {xe D\Q(x)e D_k}. (1.9)
Решение задач многокритериальной оптимизации привлекает большое внимание как ученых, так и практиков. Основные результаты в этом направлении связаны с работами Гермеера Ю. Б. [20], Моисеева Н. Н. [30], Емельянова С. В. [23], Михалевича В. С. [29], Краснощекова П. С. [26], Ларичева О. И. [27] и их многочисленных учеников.
Известно несколько подходов к решению многокритериальных задач оптимизации. Отметим некоторые их них.
1. Развитие в рамках абстрактной модели выбора многошкальных экстремальных механизмов, позволяющих осуществлять рациональный выбор по векторному критерию (Айзерман М. А. [1], Емельянов С. В. [23], Макаров И. М. [37], Березовский Б. А. [15] и др.).
2. Применение теории полезности для многокритериального выбора альтернатив из дискретного множества в условиях риска и неопределенности (Кини Р. Л. [25], Райфа X. [25], Фишберн Р. С. [39], Борисов А. Н. [16, 17], Жуковин В. Е. [24]).
3. На основе некоторой системы требований, предъявляемой к оптимальному решению, формализованной в виде совокупности аксиом, выводится схема многокритериального выбора как следствие этой системы аксиом (Подиновский В. В. [35], Вилкас Э. И. [18] и др.).
4. Сведение многокритериальной задачи выбора к скалярной оптимизации с помощью некоторой свертки векторного критерия (Гермейер Ю. Б. [20], Краснощеков П. С. [26], Евтушенко Ю. Г. [22], Штойер Р. [41], Cohon J. L. [46]).
5. Разработка человеко-машинных процедур решения многокритериальных задач оптимизации в интерактивном режиме (Емельянов В. Л. [23], Джоффрион А. М. [21], Штойер Р. [41]).
6. Построение области компромиссов и соответствующего ей множества Парето-оптимальных решений для некоторых классов многокритериальных задач оптимизации (Cohon J. L. [46], Villareal В. [48], Karwan М. Н. [47], Zionts S. [49]).
В связи с развитием вычислительной техники, в частности ПЭВМ, большое распространение получили человеко-машинные методы решения многокритериальных задач.
Человеко-машинная процедура представляет собой циклический процесс взаимодействия ЛПР и ЭВМ. Цикл состоит из фазы анализа и принятия решений, выполняемой ЛПР (фаза постановки задачи для ЭВМ), и фазы оптимизации, выполняемой ЭВМ (фаза поиска решения и вычисления его характеристик). В процессе взаимодействия ЛПР уточняет свои предпочтения и параметры задачи. Процесс заканчивается, когда получено приемлемое для ЛПР решение и при этом ЛПР убеждается в нецелесообразности дальнейших попыток улучшить его.
Существующие человеко-машинные процедуры принятия решений в условиях многокритериального выбора обладают в болыпин-стве случаев серьезным недостатком: в качестве ЛПР должен выступать человек, компетентный в заложенных в процедуру моделях и методах, поскольку для получения более совершенного решения от ЛПР требуется детальное знание алгоритмов и детальная формулировка своих предпочтений.
Описываемая в дальнейшем интерактивная система мнбгокри-териального выбора в значительной степени лишена этих недостатков. От ЛПР не требуется детального знания математических и алгоритмических вопросов принятия решений. Информация, необходимая системе, вводится в доступной форме парных сравнений по важности частных критериев. При работе с системой ЛПР имеет возможность детального и всестороннего анализа задачи с целью выбора метода и принятия наилучшего решения.
Система, в частности, предоставляет пользователю ряд графических возможностей: отображение численных значений векторных оценок альтернатив в виде диаграмм Кивиата, графическое изображение области компромиссов и т. д. Подробнее визуализация исходных и результатных данных рассматривается в гл. 3.

Общая схема сведения многокритериальных задач к задаче нелинейного программирования

Рассмотрим решение задачи многокритериальной оптимизаций:
min ?. (ж),.... min Q_N (ж), (1.10)
х s О xgD
где
D = {x\g_t(x)0, і = Т77С}. (1.11)
В частном случае область D может быть дискретным множеством решений ж:
D = {xl.....ж*}. (1.12)
Методы поиска рационального решения ж0 задачи (1.10)(1.11) получили широкое развитие и отражение в литературе. Важное значение имеют методы, использующие качественную информацию о множестве частных критериев.
Среди них можно отметить следующие.
1. Метод выделения главного критерия. Основная идея этого метода минимизация наиболее важного (главного) критерия (ж), при условии, что значения других критериев Q. (ж), і = 2, N,
не превышают пороговых значений
(1.13)
D' = Dn{x\Q_l(x)ZQ_i,i = ZJI}. (1.14)
Основная трудность этого метода состоит в определении пороговых значений Q_r для вычисления которых, в свою очередь, применяются специальные методы.
2. Метод лексикографического упорядочения критериев. В данном методе оптимизация А-го частного критерия начинается только тогда, когда получены минимальные значения всех предыдущих (?-1) частных критериев. Метод позволяет получить сколь угодно малое приращение более важного критерия за счет сколь угодно больших потерь по остальным, менее важным критериям.
Однако на практике очень часто уже после первого шага оптимизации (решения задачи оптимизации по первому критерию) решение вырождается в точку и остальные критерии не учитываются.
3. Метод последовательных уступок представляет собой мо
дификацию метода лексикографического упорядочения, заключающуюся в том, что на каждом А-м шаге последовательной оптимизации вводится уступка характеризующая допустимое откло
нение (А-І)-го частного критерия от его минимального значения.
Все перечисленные выше методы предполагают наличие подавляющего превосходства одного критерия над другим.
4. Метод свертывания векторного критерия [6, 20, 26, 27, 36 и др.]. Этот метод является наиболее распространенным методом, учитывающим относительную важность частных критериев оптимальности с помощью построения скалярной функции F, являющейся обобщенным критерием относительно векторного критерия Q (х), и решения однокритериальной задачи оптимизации:
min\F(w,Q(x)), (1.15)
хе ГУ
где w = { w_y ш^} весовые коэффициенты относительной важности
частных критериев [6, 27, 33 и др.]. В качестве обобщенных критериев могут быть использованы функции F следующего вида:
а) аддитивный критерий оптимальности:
N
(1.16)
F_z (да, Q (*)) = X wi Qi (*);
=1
б) мультипликативный критерий оптимальности:
N
F_z(w, Q (x)) = [[,?,(*); (1.17)
i= 1
в) обобщенные логические критерии оптимальности:
^max (®* Q (*)) = ПІЯХ { ОУ,- ?/ (*) }; (1-18)
1 1 Л
^min (w'?(*)) = , тіп ( w. Qi (х)}; (1.19)
mto 1iN
г) среднестепенной обобщенный критерий оптимальности:
N
F_p (, Q (*)) = (jj X ш, Q? {x))i/p, p 0. (1.20)
і= l
5. Метод идеальной точки" [10, 11, 43]. При использовании этого метода ЛПР должно задать дополнительную информацию в
виде идеального решения Q* = (QJ,..., Q*_N), учитывая следующее соотношение:
- о Q* min Q, (х), і = 1, N. (1.21)
xeD
Тогда исходная задача может быть решена путем построения обобщенного критерия в виде
F* (w. Q (х), ?*) = F (да, (Q (х) - (?*)), (1.22)
и решения однокритериальной задачи оптимизации в виде
min F* (да, Q (ж), (?*), (1.23)
хе D
обеспечивающей наилучшее приближение к идеальному решению. Здесь в качестве обобщенного критерия оптимальности F может использоваться одно из выражений (1.16)(1.20), например:
N
F = 'Lwi (Qi (*) - ?,-) или /=1
F = max {w_{ (Q₍ (x) - Q'_t)}.
1 ійп
В обобщенный критерий F (w, Q (x)) входят неотрицательные
N
весовые коэффициенты tt₍ ? 0, i = 1, N\ ^ ш_/ = 1 отражающие отно-
/=і
сительную важность частных критериев. Здесь важность критериев понимается в смысле аксиоматической теории важности [35], что позволяет считать: если известна дополнительная информация вида і-й критерий не менее важен, чем j-й критерий (?, Qj), то для весовых коэффициентов и_{ и Wj справедливо соотношение:
Q_f Qj =w₍ Wj. (1-24)
Способы назначения весовых коэффициентов широко описаны в литературе. Среди них можно отметить следующие:
упорядочение критериев по важности;
определение отношений весовых коэффициентов, при этом ЛПР задает отношение w./Wj в числовом виде;
построение таблиц на основе попарного сравнения критериев по важности;
метод определения весов при помощи совокупности последовательных сравнений (метод Черчмена-Акоффа);
методы, использующие информацию о качестве оптимальных значений частных критериев;
теоретико-игровые методы назначения весовых коэффициентов и другие.
Кроме перечисленных методов назначения весовых коэффициентов существуют способы указания области допустимых значений весовых коэффициентов: оценки предпочтительности вариантов; применение принципа гарантированного результата; существуют методы, при которых значения коэффициентов важности оцениваются на основе информации о сравнении контрольных векторных оценок, затем составляется система неравенств и выбираются коэффициенты по принципу гарантированного результата и т. д.
Во всех вышеперечисленных методах определения численных значений весовых коэффициентов от ЛПР требуется либо дать точные численные оценки, либо сравнить по важности все частные критерии между собой, причем в последнем случае различные методы дадут различные значения коэффициентов при одних и тех же предпочтениях на множестве критериев.
Кроме этого, в указанных методах предполагается, что назначенные значения весовых коэффициентов важности да остаются неизменными для всей области допустимых решений D.
Однако в ряде случаев [6, 44] в процессе принятия решения приходится учитывать зависимость весовых коэффициентов от значения частных критериев в каждой точке области допустимых решений D. Допуская, что ЛПР не может точно определить численные значения весовых коэффициентов да, их можно рассматривать как неконтролируемые факторы и, применяя принцип гарантированного результата [20], перейти к следующей модели принятия решения:
min {max F (да, Q (ж))}, (1.25)
xeD wbD_w
где D = {x I g_{ (ж) 0, t - T7K},
N
D_w = {ю I да, 0, i = T7N-, ? да, = 1}.
i = 1
В частности, при использовании обобщенного критерия оптимальности аддитивного типа приходим к следующей экстремальной задаче:
N
min {max ?да,0,(ж)}. (1.26)
xeD toe D_Wi__t
Если предположить, что структура области допустимых значений весовых коэффициентов D_w остается неизменной в процессе
поиска оптимального решения задачи (1.25), то весовые коэффициенты да являются функциями от параметров х:
да, = да, (ж), і = 1, N, (1.27)
численные значения которых при постоянных значениях ж можно определить из решения экстремальной задачи относительно вектора да
да (ж) = arg max {F (да, Q (ж))} (1.28).
xeD_w
Таким образом, исходная многокритериальная задача оптимизации (1.10)(1.11) сводится к задаче нелинейного программирования:
min {F (да (ж), Q (ж))}. (1.29)
xeD
В дальнейшем будем считать, что в общем случае (при отсутствии качественной информации о предпочтениях частных критериев) весовые коэффициенты w_p і = 1, N, отнормированы относительно положительного параметра R о и могут принимать численные значения не меньше некоторой неотрицательной величины w_Q:

Диаграмма решения задачи

оставшуюся величину. Такой расчет производится в соответствии с (2.
41) и (2. 42).
В случае использования обобщенного критерия максимальной осторожности численные значения весозых коэффициентов близки. Такое вычисление весовых коэффициентов часто приводит к другому решению, как и в приведенном примере: здесь оптимальным вариантом является вариант 6.
В случае линейного упорядочения частных критериев оптималь-




ности в порядке убывания важности F (?₂ ^ ^ Ф7) область
допустимых значений весовых коэффициентов важности имеет вид (1. 33).
В данном случае реализуется принцип: более предпочтительными при выборе ПЭВМ являются вычислительные возможности.
В табл. 11 и на рис. 16 приведены результаты определения весовых коэффициентов важности и значения обобщенного критерия при использовании аддитивного обобщенного критерия оптимально-
Процессор Тактовая частота Сопроцессор Кэш-памятъ Оперативная память Жесткий диск Стоимость


Знамения обобщенного критерия


Рнс. 16. Диаграмма решения задачи при использовании аддитивного обобщен* ного критерия и линейного упорядочения по важности частных критериев
сти, а в табл. 12 и на рис. 17 при использовании обобщенного критерия максимальной осторожности".
Оптимальными вариантами являются варианты 6 и 1 соответственно.
При использовании уточняющего коэффициента %_t - 1.5,
I = Т|Б, для каждого введенного бинарного отношения получаем

Частные критерии	Коэффициенты важности по вариантам
1	2	3	4	5	6*
1. Процессор	0.94	0.165	0.165	0.165	0.94	0.1429
2. Тактовая частота	0.01	0.165	0.165	0.165	0.01	0.1429
3. Сопроцессор	0.01	0.165	0.165	0.165	0.01	0.1429
4. Кэш-память	0.01	0.165	0.165	0.165	0.01	0.1429
5. Оперативная память	0.01	0.165	0.165	0.165	0.01	0.1429
6. Винчестер	0.01	0.165	0.165	0.165	0.01	0.1429
7. Стоимость	0.01	0.01	0.01	0.01	0.01	0.1429
Значение обобщенного критерия	1.8481	1.4993	1.3862	1.2708	1.2824	0.1429

Таблица 12

Частные критерии Коэффициенты важности по вариантам 1* 2 3 4 5 6 1. Процессор 0.1429 0.1455 0.1503 0.1531 0.1590 0.1538 2. Тактовая частота 0.1429 0.1455 0.1503 0.1531 0.1590 0.1538 3. Сопроцессор 0.1429 0.1455 0.1503 0.1531 0.1590 0.1538 . 4. Кэш-память 0.1429 0.1409 0.1503 0.1531 0.1590 0.1538 5. Оперативная память 0.1429 0.1409 0.1329 0.1291 0.1590 0.1538 6. Винчестер 0.1429 0.1409 0.1329 0.1291 0.1136 0.1538 7. Стоимость 0.1429 0.1409 0.1329 0.1291 0.0912 0.0769 Значение обобщенного критерия 0.1429 0.1455 0.1503 0.1531 0.1590 0.1538

Таблица 13

Частные критерии Коэффициенты важности по вариантам 1 2 3 4 5 6* 1. Процессор 0.7922 0.7922 0.5209 0.3541 0.7922 0.3541 2. Тактовая частота 0.0759 0.0759 0.3472 0.2360 0.0759 0.2360 3. Сопроцессор 0.0506 0.0506 0.0506 0.1574 0.0506 0.1574 4. Кэш-память 0.0337 0.0337 0.0337 0.1049 0.0337 0.1049 5. Оперативная память 0.0225 0.0225 0.0225 0.0699 0.0225 0.0699 6. Винчестер 0.015 0.015 0.015 0.0466 0.015 0.0466 7. Стоимость 0.01 0.01 0.01 0.0311 0.01 0.0311 Значение обобщенного критерия 1.8275 1.4178 1.3173 1.0993 1.2582 1.0311

область допустимых значений весовых коэффициентов вида (1.35). Решение задачи для этого случая приведено в табл. 13 и 14 (для аддитивного обобщенного критерия и обобщенного критерия максимальной осторожности соответственно) и на рис. 18 и 19. Оптимальными являются варианты 6 и 1.
Рассмотрим другую ситуацию линейное упорядочение част-
.. Сопроцессор с Кэш-память _? Оперативная память Жесшии диск Стоимость


Значения обобщенного критерия


Рис. 17. Диаграмма решения задачи при использовании обобщенного критерия "максимальной осторожности" и линейного упорядочения по важности частных критериев
Процессор Тактовая частота Сопроцессор Кэш-память Оперативная память Жесткий диск Стоимость


Знамения обобщенного критерия


ных критериев по возрастанию важности (Q₇ ^ Q₆ ... (pj), т. е.
наиболее предпочтительными качествами являются дешевизна и объем памяти всех видов. Решение задачи для этого случая при использовании тех же типов обобщенных критериев и без использо

Частные критерии	Коэффициенты важности по вариантам
1*	2	3	4	5	6
1. Процессор	0.3541	0.3541	0.3541	0.3541	0.3541	0.3568
2. Тактовая частота	0.2360	0.2360	0.2360	0.2360	0.2360	0.2379
3. Сопроцессор	0.1574	0.1574	0.1574	0.1574	0.1574	0.1586
4. Кэш-память	0.1049	0.1049	0.1049	0.1049	0.1049	0.1057
5. Оперативная память	0.0699	0.0699	0.0699	0.0699	0.0699	0.0705
6. Винчестер	0.0466	0.0466	0.0466	0.0466	0.0466	0.0470
7. Стоимость	0.0311	0.0311	0.0311	0.0311	0.0311	0.0235
Значение обобщенного критерия	0.0311	0.0321	0.0351	0.0369	0.0542	0.0470

Таблица 15

Частные критерии Коэффициенты важности по вариантам 1 2* 3 4 5 6 1. Процессор 0.01 0.01 0.01 0.01 0.01 0.01 2. Тактовая частота 0.01 0.01 0.01 0.01 0.01 0.01 3. Сопроцессор 0.196 аоі 0.01 0.01 0.01 0.01 4. Кэш-память 0.196 0.01 0.01 0.01 0.01 0.01 5. Оперативная память 0.196 0.32 0.32 0.32 0.01 0.01 6. Винчестер 0.196 0.32 0.32 032 0.01 0.01 7. Стоимость 0.196 0.32 0.32 0.32 0.94 0.94 Значение обобщенного критерия 1.7653 1.5682 1.5775 1.5810 1.7083 1.94

Таблица 16

Частные критерии Коэффициенты важности по вариантам 1 2 3 4 5 6* 1. Процессор 0.1051 0.1091 0.1186 0.1429 0.1182 0.1429 2. Тактовая частота 0.1399 0.1118 0.1186 0.1429 0.1223 0.1429 3. Сопроцессор 0.1399 0.1558 0.1525 0.1429 0.1519 0.1429 4. Кэш-память 0.1399 0.1558 0.1525 0.1429 0.1519 0.1429 5. Оперативная память 0.1399 0.1558 0.1525 0.1429 0.1519 0.1429 6. Винчестер 0.1399 0.1558 0.1525 0.1429 0.1519 0.1429 7. Стоимость 0.1951 0.1558 0.1525 0.1429 0.1519 0.1429 Значение обобщенного критерия 0.1951 0.1558 0.1525 0.1429 0.1519 0.1429

вания уточняющих коэффициентов приведено в табл. 15 и 16 и на рис. 20 и 21 соответственно. Оптимальным вариантом для аддитивного критерия является вариант 2, а для критерия максимальной осторожности вариант 6.
Рассмотрим решение задачи выбора ПЭВМ в ситуации, когда ЛПР определяет свои предпочтения по следующему принципу: наиболее предпочтительным качеством являются вычислительная




Рис. 19. Диаграмма решения задачи при использовании обобщенного критерия максимальной осторожности и линейного упорядочения по возрастанию важности критериев с уточняющими коэффициентами
мощность, затем стоимость. Реализуя этот принцип, в систему вводятся следующие попарные предпочтения: тип процессора, тактовая частота и наличие сопроцессора предпочтительнее стоимости (?! ^ ?7 ?2 ^ ?з ^ Ф7)* стоимость предпочтительнее кэш-памя
ти и оперативной памяти (?₇ ?₄, Q₇ ^ Q₅); кэш-память и опера-




тивная память предпочтительнее объема жесткого диска (Q₄ ^ (?₆, Q_s }- Q₆). Таким образом вводится 7 пар предпочтений, которые располагаются в четырех слоях (рис. 22).
Решение задачи при использовании аддитивного обобщенного критерия оптимальности приведено в табл. 17 и на рис. 23. Оптимальным вариантом при этом является вариант 6 (самый мощный, но и самый дорогой). Нетрудно видеть, что значения весовых коэффициентов удовлетворяют введенным соотношениям.
При введении уточняющего коэффициента ^ 1.5, Z = ТГ7, зна-
Процессор Тактовая частота Сопроцессор Кэш-память Оперативная память Жесткий диск Стоимость


Значения обобщенного критерия


чения весовых коэффициентов будут иные, иным будет и решение -вариант 4 (табл. 18 и рис. 24). В этом случае играет роль тот факт, что шестой вариант значительно хуже четвертого по стоимости, равен по вычислительным возможностям и уступает по объему памяти (оперативной и дисковой). Ухудшение по стоимости оказалось более важным, чем улучшение по памяти, хотя в предыдущем случае (без использования уточняющих коэффициентов) более важным оказался объем памяти.

Таблица 17

Частные критерии Коэффициенты важности по вариантам 1 2 3 4 5 6 1. Процессор 0.01 0.01 0.01 0.1429 0.01 0.2425 2. Тактовая частота 0.01 0.94 0.94 0.1429 0.94 0.2425 3. Сопроцессор 0.94 0.01 0.01 0.1429 0.01 0.2425 4. Кэш-память 0.01 0.01 0.01 0.1429 0.01 0.01 5. Оперативная память 0.01 0.01 0.01 0.1429 0.01 0.01 6. Винчестер 0.01 0.01 0.01 0.1429 0.01 0.01 7. Стоимость 0.01 0.01 0.01 0.1429 0.01 0.2425 Значение обобщенного критерия 1.99 1.9687 1.9626 1.2792 1.5934 1.2425

Таблица 18

Частные критерии Коэффициенты важности по вариантам 1 2 3 4* 5 6 1. Процессор 0.0337 0.87 0.0337 0.2061 0.87 0.2618 2. Тактовая частота 0.0337 0.0337 0.87 0.2061 0.0337 0.2618 3. Сопроцессор 0.87 0.0337 0.0337 0.2061 0.0337 0.2618 4. Кэш-память 0.015 0.015 0.015 0:0916 0.015 0.015 5. Оперативная память 0.015 0.015 0.015 0.0916 0.015 0.015 6. Винчестер 0.01 0.01 0.01 0.0611 0.01 0.01 7. Стоимость 0.0225 0.0225 0.0225 0.1374 0.0225 0.1745 Значение обобщенного критерия 1.95 1.4151 1.3756 1.1480 1.2775 1.1745

Процессор актовая часто Сопроцессор Кэш-память Оперативная память Жесткий диск Стоимость



Знамения обобщенного критерия

Рис. 23. Диаграмма решения задачи при использовании аддитивного обобщенного критерия и введенной группы предпочтений
Процессор Тактовая частота Сопроцессор Кэш-память Оперативная память Жесткий диск Стоимость


Значения обобщенного критерия


Рис. 24. Диаграмма решения задачи при использовании аддитивного обобщенного критерия и введенной группы предпочтений с уточняющими коэффициентами

ЛИТЕРАТУРА

1. Айзерман М. А., Алескеров Ф. Т. Выбор вариантов: основы теории. - М.: Наука, 1990. - 240 с.
2. Анучин В. Ф. Построение индивидуальных коэффициентов важности на основе уточненной качественной информации о важности критериев // Моделирование и оптимизация сложных систем. -Воронеж: Воронежск. политехи, ин-т, 1985.
3. Анучин В. Ф. Анализ непротиворечивости информации о важности частных критериев // Анализ и проектирование систем управления производством: Межвуз. сб. науч. тр. - Горький: Горьк. гос. ун-т, 1988. - С. 89 - 92.
4. Батищев Д. И. Поисковые методы оптимального проектирования. - М.: Сов. радио, 1975. - 215 с.
5. Батищев Д. И. Принятие оптимальных решений в экономических исследованиях. - Горький: Горьк. госун-т, 1982. - 108 с.
6. Батищев Д. И. Методы оптимального проектирования. - М.: Радио и связь, 1984. - 248 с.
7. Батищев Д. И., Шапошников Д. Е. Сравнение вариантов технических проектов с помощью среднестепенного обобщенного критерия // Оптимизация и моделирование в автоматизированных системах: Межвуз. сб. - Воронеж: ВПИ, 1988. - С. 44 - 48.
8. Батищев Д. И., Шапошников Д. Е. Об одной реализации принципа гарантированного результата // Математическое и программное обеспечение задач многокритериальной оптимизации и их применение (Ереван, 26-30 сентября 1988 г.): Тез. докл. межресп. школы-семинара. - Ереван, 1988. С. 73 - 75.
9. Батищев Д. И., Шапошников Д. Е. Система поддержки принятия многокритериальных решений в задачах проектирования // Методы искусственного интеллекта в САПР: Тез. докл. Всесоюз. школы-семинара молодых ученых и специалистов. - Воронеж: ВПИ, 1990. - С. 169 - 170.
10. Батищев Д. И., Шапошников Д. Е. Реализация метода идеальной точки, использующего качественную информацию о важности частных критериев // Международная школа-семинар по методам оптимизации и их приложениям (Иркутск, 1989): Тез. докл. - Иркутск: Сибирск. энерг. ин-т, 1989. - С. 20 - 21.
11. Батищев Д. И., Шапошников Д. Е. Решение многокритериальных задач методом идеальной точки // Модели и алгоритмы оптимизации в автоматизированных системах. - Воронеж, ВПИ, 1989. - С. 48 - 53.
12. Батищев Д. И., Шапошников Д. Е. Диалоговая процедура решения задач многокритериальной оптимизации // Экстремальные задачи и их приложения: Тез. докл.
Межгосудар. науч. конф. -Н. Новгород: ННГУ, 1992. - С. 14.
13. Батищев Д. И., Шапошников Д. Е, Диалоговая программная система ВЫБОР (CHOICE) // Компьютерная геометрия и графика в образовании КОГРАФ-93: / Тез. докл. и сообщений междунар. выставки-семинара. - Н. Новгород, НГТУ, 1993. - С. 31.
14. Беллман Р. Динамическое программирование. - М.: ИЛ, 1960. - 400 с.
15. Березовский Б. А., Гнедин А. В. Задача наилучшего выбора.
- М.: Наука, 1984. - 196 с.
16. Борисов А. Н., Левченков А. С. Методы интерактивной оценки решений. - Рига: Зинатне, 1982. - 139 с.
17. Борисов А. Н., Вилюмс Э. Р., Сукур Л. Я. Диалоговые системы принятия решений на базе мини-ЭВМ: Информационное, математическое и программное обеспечение. - Рига: Зинатне, 1986.
- 195 с.
18. Вилкас Э. Й., Майминас Е. 3. Решения: теория, информация, моделирование. - М.: Радио и связь, 1981. - 328 с.
19. Виноградская Т. М. Принципы построения автоматизированной системы ВЫБОР // Автоматизация проектирования систем управления. - М.: Статистика, 1979, вып.
2. - С. 176 - 184.
20. Гермейер В. Б. Введение в теорию исследования операций. М.: Наука, 1971. - 383 с.
21. Джоффрион А., Дайер Дж., Файнберг А. Решение задач оптимизации при многих критериях на основе человеко-машинных процедур // Вопросы анализа и процедуры принятия решений. -М.: Мир, 1976. - С. 126 - 145.
22. Евтушенко Ю. Г. Методы решения экстремальных задач и их применение в системах оптимизации. - М.: Наука, 1982.
23. Емельянов С. В., Наппельбаум Э. Л. Логика рационального выбора // Техническая кибернетика. - М.: ВИНИТИ, 1977. - Т. 8. С. 5 - 101.
24. Жуковин В. С. Модели и процедуры принятия решений. -Тбилиси: Мецниереба, 1981. - 118 с.
25. Кини Р. Л„ Райфа X. Принятие решения при многих критериях: замещения и предпочтения / Пер. с англ. - М: Радио и связь, 1981. - 560 с.
26. Краснощеков П. С. Математические модели в исследовании операций. - М.: Наука, 1984.
27. Ларичев О. И. Объективные модели и субъективные решения. - М.: Наука, 1987. - 144 с.
28. Му шик Э., Мюллер П. Методы принятия технических решений / Пер. с нем. - М.: Мир, 1990. - 208 с.
29. Михалевич В. С., Волкович В. J1. Вычислительные методы исследования и проектирования сложных систем. - М.: Наука, 1982. - 286 с.
30. Моисеев Н. Н. Математические задачи системного анализа. - М.: Наука, 1981.- 156 с.
31. Озерной В. М., Гафт М. Г. Методология решения дискретных многокритериальных задач // Многокритериальные задачи принятия решений. - М.: Машиностроение, 1978. - С. 14 - 47.
32. Оре О. Теория графов / Пер. с англ. - М.: Наука, 1968. - 352 с.
33. Подиновский В. В. Об относительной важности критериев в многокритериальных задачах принятия решений // Многокритериальные задачи принятия решений. - М.: Машиностроение, 1978. -С.
48 - 92.
34. Подиновский В. В. Коэффициенты важности критериев в задачах принятия решений.
Порядковые, или одинарные, коэффициенты важности // Автоматика и телемеханика. 1978. N 10. -С.
130 - 141.
35. Подиновский В. В. Аксиоматическое решение проблемы оценки важности критериев в многокритериальных задачах // Современное состояние теории исследования операций / Под ред.
Н. Н. Моисеева. - М.: Наука, 1979. - С. 117 - 145.
36. Подиновский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. - М.: Наука, 1982. - 256 с.
37. Теория выбора и принятия решений / И. М. Макаров, Т. М. Виноградская, А. А. Рубчинский, В. Б. Соколов. - М.: Наука,1982. - 328 с.
38. Феррари Дж. Оценка производительности вычислительных систем / Пер. с англ. - М.: Мир, 1981. - 576 с.
39. Фишберн П. С. Теория полезности для принятия решений / Пер. с англ. - М.: Наука, 1977. - 352 с.
40. Шапошников Д. Е. Выбор рационального варианта технического проекта с использованием принципа гарантированного результата // Создание комплексов электротехнического оборудования высоковольтной, преобразовательной, сильноточной и полупроводниковой техники: Тез. докл.
2-й всесоюз. конф. - М.: Всесоюз. электротехн. ин-т, 1990. - С. 149.
41. Штойер Р. Многокритериальная оптимизация.
Теория, вычисления и приложения / Пер. с англ. - М.: Радио и связь, 1992.
42. Batishchev D. /., Anuchin V. F., Shaposhnikov D. E. Weighting Coefficients Determination from the Qualitative Information on the Importance of Particular Criteria of Optimality // Internationale Tagung Mathematische Optimierung - Theorie und Anwendungen.
Eisenach, 16-20 November, 1987. - Ilmenau, 1987. - P. 87 - 90.
43. Batishchev D. I., Shaposhnikov D. E. Implementation of the Ideal Point Method Using Qualitative Information on the Importance of Particular Criteria // International School-seminar Optimization Methods and Their Applications, USSR, Baical, 10 - 19 September, 1989.: Volume Abstracts. - Viena: IASI, 1989. - P. 12 - 13.
44. Batishchev D. I., Anuchin V. F., Shaposhnikov D. E. The Use of the Qualitative Information on the Importance of Particular Criteria for the Weighting Coefficients // Multiobjective Problems of Mathematical Programming: Lecture Notes in Economic and Mathematical Systems, V. 351. - Springer-Verlag, 1991.- P. 2 - 7.
45. Chankong V., Haimes Y._t Thadathil I., Zionts S. Multiple Criteria Optimization: a State of the Art Rewiew // Lecture Notes in Economic and Mathematical Systems, 1985, V. 242. - P. 36 - 90.
46. Cohon /. L. Multiobjective Programming and Planning. - New York: Academic Press, 1978.
47. Karwan M. H., Zionts S. On finding starting feasible solutions for some specially structured linear programming problems // Working Paper No.
445, School of Management, State University of New York at Buffalo, 1980.
48. Villareal B., Karwan M. H„ Zionts 5. A branch and bound approach to interactive multicriteria integer linear programming // Paper presented at Joint National Meeting TIMS/ORSA, Washington, D. C., 1980.
49. Zionts S. Multiple Criteria Decision Making for Discrete Alternatives with Ordinal Criteria / Working Paper N299, School of Management. - New York: State University of New York at Buffalo, 1977.

НАЗНАЧЕНИЕ ВЕСОВЫХ КОЭФФИЦИЕНТОВ ВАЖНОСТИ

N^ = {ю|ш_;да₀^0. = T7W; ?/, = #}- (1.30)
i= 1
1.3. Анализ и использование качественной информация об относительной важности частных критериев
Будем считать, что от ЛПР получена дополнительная качественная информация, устанавливающая для некоторых L пар частных
критериев (необязательно для всех допустимых пар) предпочтение
і-го критерия над /-м на всем множестве D допустимых решений:
со, = {?,- }¦ Q,}. / = Т7Х N (N - 1)/2. (1.31)
Информация (1.31) является качественной, так как из нее следует, что і-й критерий важнее /-го критерия, но нельзя сказать, во сколько раз. Тогда качественная информация (1.31) в соответствии с соотношением (1.24) позволяет определить область допустимых значений весовых коэффициентов w следующим образом:
, . _ со/ _
Ег_и = {т8|а,.?да₀?0, г' = Т^; = w_{w_r l = T~L}. (1.32)
i = i
В частном случае, когда частные критерии оптимальности располагаются (ранжируются) в порядке убывания важности (?і ^ ?₂ ^ - ' область D_w принимает следующий вид:
N
= {w | ш. ш₀ 0, i = T7W; ?а/. = /?;
=1
w.w_l+l, 1 = 0^1}. (1.33)
Если область D_w непуста, то информация (1.24) непротиворечива. В этом случае весовые коэффициенты w е D_w будем называть согласованными с качественной информацией [33].
Качественная информация может быть представлена в виде ориентированного графа G (/, ?2), где I множество вершин, соответствующих частным критериям, ?2 множество ребер, соединяющих (-ю вершины с /-й тогда и только тогда, когда выполняется соотношение Q. }¦ Q_f. В дальнейшем будем считать, что информационные сообщения (1.31) удовлетворяют условию транзитивности, то есть в графе G (/, ?2) отсутствуют замкнутые циклы.
Разобьем все вершины I графа G (/, ?2) на слои следующим образом: к первому слою (s = 1) отнесем те вершины, в которые не входит ни одна дуга; ко второму слою (з = 2) те и только те вершины, в которые входят дуги из вершин первого слоя; к третьему слою (з = 3) те и только те вершины, в которые входят дуги из вершин первого и второго слоев, и т. д. При этом у вершин последнего слоя (s = SN) не будет ни одной выходной дуги.
В частном случае отсутствия качественной информации (1.31) граф G (/, ?2) не будет иметь ни одной дуги и будет представлять собой совокупность из N точек (рис. 2, а).
В частном случае линейной упорядоченности по важности частных критериев оптимальности (рис. 2, б) граф G (/, ?2) будет иметь число слоев, равное числу вершин (S = N).
Для набора парных сравнений частных критериев по важности:
®1 = (*?2 ^ Ю2 = ? ^ @5 Ь М3 = { @3 ^ ^6
= {@4 ^ Qj}; ®5= {@5 ^ Qg}; ®g= {Qg ^ Qg};
граф G (/, ?2) приведен на рис. 2, в.
Для каждой вершины і е { 1,..., N}, соответствующей частному критерию Q., введем следующие параметры: /. множество вершин
графа G (/, ?2), из которых имеется путь в вершину і, включая ее саму; п. мощность множества І_г Тогда в частном случае отсутствия
качественной информации (1.31) получим І.= {і}, п. = 1, і = 1, N\ а в частном случае линейной упорядоченности по важности частных критериев получим I. = { 1,.... і}; п₍ = і, і= 1, N.
В некоторых случаях ЛПР имеет возможность уточнить информацию о взаимосвязях весовых коэффициентов w. и w_jt связанных
бинарным отношением Q. ^ Q_/t с помощью параметра 1: о)/
w. \_tw_r (1.34)
CD ? ? (D
S=1
а) отсутствие информации (1.30)
О ----- ’
ф
CD2
0-------51
sU
CD s
б) линейное упорядочение критериев по важности
В этом случае приходим к области допустимых значений весовых коэффициентов вида
= {w I и₀ ? 0, i = T7W;
N (О/
Y,wi= R’ Щ* ^Iwp i = T7X. 1 }- (1.35)
=1
Введем следующие обозначения.
Пусть р произвольный путь в графе G (/, ?2) [32]: р = {/_р /_п(р)}, где I. дуга, входящая в путь р;п(р) число дуг в пути р. Обозначим через Р* множество всех путей из вершины і в вершину k. Тогда введем величины 'к
и ^ следующим образом:
Іі =
(1.36)
(1.37)
max* П ?- если * 0;
Up
1, если Р? = 0, для всех i, k е /; І = ™axif-
А € У ЯФІ
Нетрудно видеть, что является обобщенной оценкой относительной важности частного критерия і в условиях качественной информации (1.31).
'к
Приведем пример вычисления величин и ?_f.
Для всех дуг графа, изображенного на рис.2, в введем уточняющие
'у
коэффициенты / = 176. Вычисление величин ^ и \_х приведено на рис. 3.
'к
Нетрудно видеть, что величины и %. можно легко вычислить с помощью следующего алгоритма.
1. Полагаем s = S; = 0, k, i е {1.....N}.
2. Для всех вершин k, принадлежащих слою s, полагаем 1.
3. Полагаем s s 1. Если s = 0 (т. е. все слои пройдены), то переходим к п. 5. В противном случае переходим к п. 4.

Номер дуги /	Уточняющий коэффициент
1	1.2
2	2
3	1
4	1.3
5	1.3
6	2

Вершины 7	Величины при pf Ф 0	Величины
1	-	1
2	?5 = 1.2-1.3 = 1.56;^ = 1.2	1.56
3	?*3 = 2; = 1; ?® = тах{2 - 1.3; 1 - 2} = 2.6	2.6
4	?1 = 1-5	1-5
5	?*5 = 1.3	1.3
6	?*6=2	2
7	-	1
8	-	1

Рис. 3. Пример уточнения качественной информации о предпочтениях
4. Для каждой вершины k, принадлежащей слою s, выполняем
следующие действия. Пусть У* множество вершин слоя (s + 1), в которых есть дуга из вершины k. Тогда для каждой вершины
/ € У* полагаем
'і
5* = где I - номер дуги (k, /);
І‘к = }-
/ € J
и повторяем все вычисления с п. 3.
*к
5. Для всех для которых выполняется условие 0, к,
'k *k **
і 6 {1,,N}, полагаем %_t 1. Все величины и %_t вычислены.
В следующей главе рассмотрим вопросы назначения весовых коэффициентов важности для допустимых областей их изменения
Dl_w (1.30), D*_m (1.32), Db_w (1.33) и Z)* (1.35) при различных типах
обобщенных критериев F (tv, Q (х)) с помощью решения экстремальной задачи (1.28).

Глава 2 НАЗНАЧЕНИЕ ВЕСОВЫХ КОЭФФИЦИЕНТОВ ВАЖНОСТИ ПРИ РАЗЛИЧНЫХ ТИПАХ ОБОБЩЕННЫХ КРИТЕРИЕВ

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

Вычисление весовых коэффициентов важности при использовании аддитивного обобщенного критерия оптимальности

Рассмотрим решение задачи определения весовых коэффициентов важности w, принадлежащих области допустимых решений ?* (1.35), при использовании аддитивного критерия оптимальности (1.16)
N
w (ж) = arg { max Fj. (w, Q (ж))} = arg { max Y wt ?,(*)}- (2.1) we D_w weD_Wi=l
где
D_w= {w I Wj Z w₀ Z 0, / = T7N;
N (0/
Y wi = #; w. - %i ¦ w_r * 1. L = T7X}. (2.2)
f=i
При фиксированных значениях варьируемых параметров ж е D значения векторного критерия Q (ж) определены.
х 6 D значения векторного критерия Q (х) определены.
Будем считать, что качественная информация о предпочтениях на множестве критериев
(*, = {?, ?,}. l = Tj:N(N- 1)/2, (2.3)
может быть представлена в виде ориентированного графа G (/, Q), где I множество вершин, соответствующих частным критериям; Q множество ребер, соединяющих і-ю вершину с /-й тогда и только тогда, когда выполняется соотношение Q. }- Qj.
Для каждой вершины і е {1,.... N}, соответствующей частному критерию Q_{, введены следующие параметры: I. множество вершин
графа G (/, ?2), из которых имеется путь в вершину і, включая ее саму; л, мощность множества /_;. Тогда в частном случае отсутствия качественной информации о важности частных критериев получим
= {*'}. л,= 1, і = 1, N, (2.4)
а для линейной упорядоченности по важности частных критериев /, = {1.....і}, л,= 1, і 1, N. (2.5)
Пусть р произвольный путь в графе G (/, Q): р = {І_? .... /_п(р)), где 1₍ дуга, входящая в путь р, п (р) число дуг в пути р. Обозначим
через множество всех путей из вершины і в вершину к. Тогда *k
величины ^ и определяются следующим образом: (2.7)
тах* П */ если ф
Р^Рі _Ыр
1, если Pj = 0, для всех і, к е /;
рх/5-'
k* і
Для экстремальной задачи (2.1)(2.2) может быть сформулирована следующая теорема.
Теорема 2.1. Оптимальным решением задачи (2.1)(2.2) является вектор хи* с компонентами
Af
/ //
^'o iG/r5
*е/
Г
О- іе/\/_г;
(2.8)
w_{ = *
где
(2.9)
*=і
при этом величины ^ вычисляются с помощью выражений (2.6)-(2.7) соответственно, а индекс г определяется из соотношения
q = max а., (2.10)
r )kzN *
где
q_k = q_k(.R,w₀,N) =
х[?(дс)(4гл-+ V , i6/* ,Г#'
о)]
+ X ?(*)
tel\I_k
¦it
(2.11)
W_n
Доказательство
Доказательство проведем по индукции по слоям.
1. Пусть в графе предпочтений имеется всего один первый слой (S = 1). В этом случае справедливость теоремы очевидна. Поскольку бинарные отношения предпочтения на множестве частных критериев отсутствуют, то соотношения (2.8)(2.11) сводятся к выражению
q_r = max { X * Q, (*)} = we Ц _/e/ ' '
= max {[/? - (IV- 1) а₀] - Q_f (х) + w₀ ¦ ??*(*)}. (2.12)
/€/ *€/\/
Из (2.12) видно, что для S 1, так как I. = / и = 1 для всех / = 1,..., IV, сформулированная теорема справедлива:
w_r= R - (N - 1)100. Wj w_Q, /= 1, IV, j* г. (2.13)
2. Пусть теорема справедлива для k слоев, т. е. для любой вершины 1 из слоев 1,..., k получим
q_t (R, w_Q, N_k) q_r(R,w₀,N_k) для всех ie J_k, (2.14)
где J_k множество вершин на первых к слоях, N_k = | J_k |, до₍. вычисляются по формулам (2.8)(2.11).
Докажем справедливость теоремы для (к + 1)-го слоя. Рассмотрим произвольную вершину / из (k + 1)-го слоя. Эта вершина соединена в общем случае дугами с несколькими вершинами из первых к слоев графа предпочтений {t,,.... і_т } так, что
І_} = I_t u /, и ... и І₍ u j = /у и /, (2.15)
I S iKy
соединяющие дуги имеют номера к_р t - 1,.... m_;.; /у множество вершин, из которых есть путь в вершину /, включая ее саму. Оценим значение обобщенного критерия F_z (w, Q (х)):
F_z (w, Q (x)) = Yjwk'Qk + wj' (¦*-
(2.16)
*e
Для первого слагаемого можно применить сформулированную теорему, положив
R- Шу, ш,, W = (2.17)
Тогда для выражения (2.15) можно записать
F_z(w,Q(x))Z q_r (R, до, N) + w,Q_/(x) = f(wj), (2.І8)
где
{R- w. w_j ¦ Yj'ii) ¦
f (wj) = X {Q_t (*) ¦ [
IK
IS /
tel
(2.19;
‘',4
(2.20)
/ / до_п до, ? max { до, -l. }. 0 1 V
Функция (2.19) является линейной относительно параметра до₍.,
поэтому она достигает своего максимального значения в одной из граничных точек: либо в точке Wj = ш₀, либо в точке
ад. = max {ад, - ?*}= ад. (2.21)
Непосредственной подстановкой граничных точек ад₀ и ад в (2.19) получим
/(ад₀)= q_r(R,N_k+ 1 ,ад₀);/(ад)= q_j(.R,N_k + 1 ,wj. (2.22) Следовательно,
F_z (ад, Q (ж)) = max {q_f (R, N_k + 1 ,w_a); qj(R, N_k+ 1, ад„) . (2.23)
Если q_r qp то условие (2.10) выполняется в первых k слоях и выражения (2.8)(2.11) справедливы и для (k + 1)-го слоя. Если q_r q_f, то в качестве индекса г принимаем индекс /-й вершины. В этом случае выражение (2.8) также имеет место, так как для всех he І_}
а величины R, определяются через выражения (2.9) и (2.7) соответственно, что и требовалось доказать.®
В частном случае линейной упорядоченности по важности частных критериев оптимальности область допустимых значений весовых коэффициентов имеет следующий вид:
N
D_w= {ад | ад_у ад₀ 0, / = T77J; ? w. = R-,
i= i
(2.27)
В этом случае решением задачи (2.1) является вектор ?о* с компонентами, определяемыми следующими выражениями:
(2.28)
(2.29)
(2.30)
(2.31)
(Л'-^)/Х?*+ і= Ь2.....г,
, к = 1
Кі -W₀, і = r+ 1 N-,
где
R'= R- ovX^ 0,
=i
а индекс г определяется из соотношения
q. = max q_k, r 1kN k
k ₁ t * N _{f f}
Q_k = X [?, (*) - (-5L + C- - М + X 0* (*) - w₀ - К
,=i x^; ,=t+i
/=i
Выражения (2.28)(2.31) аналогичны результату, полученному в работе [2].
При отсутствии дополнительной уточняющей информации, т. е. при?_{ = l,t= Т7Т, получим область допустимых значений коэффициентов важности вида
(Of
D_w = {w\ w.w₀0,i = ТТЛ; X w.^ w., I = TTT}. (2.32)
/=i
. і е I;,
е /\/_Л;
В этом случае решением задачи (2.1) является вектор w* с компо-R - (N - n_r)- w_Q
(2.33) где индекс г определяется из соотношения
(2.34)
q_r = max q., r 1 k?N к
R- (N- n_t)w_n
??,(*)
? Q_t (x).
(2.35)
+ w_n
e/U
ie /.
Выражения (2.33)-(2.35) нетрудно получить из выражений
(2.8)-(2.11), учитывая, что все величины определенные выражением (2.6), равны единице. Выражения (2.33)-(2.35) аналогичны результату, полученному в [5]. Там же показано, что для случая линейной упорядоченности частных критериев оптимальности при отсутствии уточняющей информации ?, т. е. области допустимых значений весовых коэффициентов важности D_w вида
D3_W = {ш | w_Q 0, і = 1, N;
N _
Xwi= Л; w. w_l+ j, i= 1 ,N- 1}, (2.36)
i = i
оптимальным решением экстремальной задачи (2.1) является вектор w* с компонентами
R- (N- г) -w₀ . _т_
a/_f‘ = г ’ _ (2.37)
te;₀, i= r+ 1 ,N,
где индекс г определяется из соотношения
а= шах о., (2.38)
r ]k?N к
q_k = R~ {N~_k k)W IQ, (*) + w₀-^Q_t (x). (2.39)
i=i =*+i
Выражения (2.37)-(2.39) нетрудно получить из выражений
(2.28)(2.31), подставив значения = 1, i, k е /.
При отсутствии дополнительной качественной информации (2.3) и области допустимых значений коэффициентов важности вида [5]
N
Dl_w= {w|w₍2: w₀ 0, i = T7N\ Yjwt = Я) (2.40)
i=i
оптимальным решением экстремальной задачи (2.1) является вектор tv с компонентами
(2.41)
(2.42)
. _ f/? - (N - 1) - cv₀, i = r,
W‘ ~ [tv₀, i = TTN, i * r,
где индекс г определяется из соотношения
ч'=іШк(х)-

Вычисление весовых коэффициентов важности при использовании обобщенного логического свертывания частных критериев оптимальности

Рассмотрим решение задачи
w (ж) = arg { max F (tv, Q (ж))}, (2.43)
we D_w
где
N
D_w = {tvlo^S w₀ 0, / = 1, N\ ?iv,= R\
i= 1
w_t?1 w_p l= T7X}, (2.44)
при использовании обобщенных логических критериев оптимальности двух типов:
обобщенного критерия максимальной осторожности
Fmin (w. Q (*)) =, min {w. Q. (ж)}; (2.45)
1 tN
обобщенного критерия максимального риска
Fmax Q (* = ,га.ах {, Q_t (*) }- (2-46)
1 iN
Для нахождения весовых коэффициентов w₍ (ж), і = 1, N, при использовании обобщенного критерия вида (2.45) и в случае условия неотрицательности весовых коэффициентов важности Wj 0, т. е. решения задачи
w* (ж) = arg { max F_mln (tv, Q (ж))} = tve D_w
= arg { max min (w, Q (*))}, we

(2.47)
где
_ п СО/ _
D_w = {u I w_{ ? 0, i = 1, N; Y,wi= R’ wi - wj, I = TT}, (2.48)
может^быть применен следующий алгоритм.
Алгоритм 1
1. Граф отношений предпочтения G (/, Q) разбиваем на слои s = 1,5.
2. Каждой вершине / графа G (I, Q) приписываем начальное значение w'j =0, / = 1, N.
3. В качестве первого слоя рассматриваем самый нижний слой, т. е. полагаем s =* S.
4. Для каждой вершины s-ro слоя полагаем
w'. = max {w'., R/Q_j (x)}.
5. Проводим корректировку значений w'j для вершин более высоких слоев:
w'j = max {w'j, maxw_k}, kel j
где I'j множество вершин, в которые есть путь из вершины /.
6. Полагаем s = s 1. Если s = 0 (т. е. рассмотрены все слои), то переходим к п. 7, в противном случае повторяем вычисления с п. 4.
7. Вычисляем итоговые значения весовых коэффициентов по формуле
w* = R- w'j/ (X w\).
Для доказательства корректности данного алгоритма докажем следующую лемму.
Лемма 2.1. Вектор весовых коэффициентов w, построенный с помощью алгоритма 1, обладает следующим свойством: для любой вершины / е I_s, принадлежащей s-му слою (s 1) и такой, что
всегда найдется вершина k е І_? принадлежащая нижнему по отношению к s-му слою (t s), такая, что
w_kx_k = F и w_k = w_p т. е. для которой x_k Xj.
Доказательство
Пусть вектор w построен по алгоритму 1. Тогда для всех вершин самого нижнего (5-го) слоя, согласно пунктам 4 и 7, получим
до₍ х_{ = F для всех I е I_s.
Рассмотрим произвольную вершину / е I_s (S 1) такую, что Wj Xj F. Построим путь из вершины / е I_g в вершину I е f_s следующим образом (построение такого пути всегда возможно в силу определения слоя). Среди всех вершин множества найдем
такую вершину j_v что
w, = max до..
7 kelj *
Если і\ не принадлежит то выбираем следующую вершину j₂ такую, что до, = max до.
и так до тех пор, пока не найдем вершину I, принадлежащую нижнему (s-му) слою:
W_{ Wj ... Wj Wj Wj,
где / e I_s,l e I_s, w_t x_t = F, Wj Xj F. Согласно построению весового коэффициента до, по алгоритму 1 возможно два случая.
Случай 1. Для всех k = /,, /₂,..., j_m имеем w_k x_k F. Тогда из построения алгоритма 1 следует, что
до. = до. = ... = до. = до. = до.,
'т ' Л '
т. е. требуемая по лемме k-я вершина нижнего слоя определена ею является вершина I е I_s.
Случай 2. Найдется такая вершина /₀ 6 {..., j_m}, что
Wj Xj = F и w_k x_k F для всех k e {/„ - 1,j\ }. Тогда из алгоритма 1 следует, что
W! = ?і= - - - = ¦/. wr
т. е. искомой (А-й вершиной нижнего слоя) будет вершина /. Что и требовалось доказать.®
Лемма 1 позволяет доказать следующую теорему.
Теорема 2.2. Вектор весовых коэффициентов да, построенный с помощью алгоритма /, является оптимальным решением экстремальной задачи (2.47)(2.48).
Доказательство
Пусть вектор да построен с помощью алгоритма 1. Тогда
min (да, х.) = F.
11N 1 1
Причем Wj Xj = F для / е /_ш1п и да, x_t F для / е / \ І_тіп. Предположим от противного, что имеется вектор да' е D_w, который является оптимальным решением задачи (2.47)-(2.48):
min (да', х.) = F F. (2.49)
1 /А7 11
Так как F' F, то
w'j да₄ для всех k е /_т1п. (2.50)
Покажем, что в этом случае будет иметь место и система неравенств да'₇? Wj для всех /е /\/_ш1п.
Действительно, предположим, что найдутся такие / е / \ /_т1п, что да'₇ да^. Так как / е I_s, s 1, то согласно лемме 1 найдется вершина / е І_р t s, такая, что
да,х,= F я w,= w_jt I в /_ш1п.
Таким образом, получаем, что да', да'₇ w_f= да,, т. е. да', да, для всех I € /_т|п, что противоречит условию (2.50). Следовательно,
да'₇ да₇ для всех /е І\і_тіп. (2.51)
Просуммировав по / от 1 до N значения w'j и or и учитывая неравенства (2.50) и (2.51), получим, что
X w'k + X "'/ X wk + X ®/ - (2.62)
*в/Ы. *6/_mta /еЛ/ші„
Так как вектора ю' и w принадлежат области d_w, то их сумма
равняется величине R. Тогда из неравенства (2.52) следует, что R R. Полученное противоречие говорит о том, что сделанное предположение неверно и, следовательно, вектор w, построенный с помощью алгоритма 1, является оптимальным решением экстремальной задачи (2.47)-(2.48). Что и требовалось доказать.*
Рассмотрим обобщение задачи (2.47)(2.48) на случай w_{ w₀ 0, і = 1, N, где w₀ R/N:
w* (.x) = arg { max\F , (w, Q (x))} = toe D_w
= arg {max min (w,Q(x))}, (2.53)
weD_w 1 iN
где
D_w= {да|ш₍. w₀ 0, i= T7N; ^wi=
=i
w. Wj, 1= 1, L}. (2.54)
Для решения этой задачи может быть построен следующий алгоритм.
Алгоритм 2
1. Полагаем Г = / = {1.....N}\ R’ = R; fl' = ?2.
2. Для графа предпочтений G (Г, Q') с помощью алгоритма 1 с параметром R’ = R находим значение w'., j е Г.
3. Если для всех j е Г выполняется условие w'j w₀, то полагаем w*j = w'j, j е Г и задача решена; в противном случае переходим к п. 4.
4. Для каждой вершины т е Г, для которой выполняется условие w'_m ш₀, осуществляем следующие действия:
а) полагаем w'_m = w_Q, R' = R' - ш₀;
б) исключаем вершину т из рассмотрения, для этого полагаем Г = І\т и из множества ?2' исключаем дуги, инцидентные вершине т (если они есть).
После выполнения указанных действий для всех вершин, в которых выполнилось условие w'_m w_Q, повторяем вычисления с п. 2.
Для доказательства корректности алгоритма 2 докажем следующую лемму.
Лемма 2.2. Операция исключения вершины т из графа G (/, ?2) на 4-м шаге алгоритма 2 не изменяет частичное попарное отношение предпочтения на множестве /'.
Доказательство
Дуга (і, /) в графе G (/', ?2') качественно соответствует соотношению w_i Wp i, j e /'. Возможны два случая.
Случай 1. Если подлежит исключению вершина /, то в этом случае согласно шагу 4 алгоритма 2 Wj= w_Q и из построения области
D_w следует соотношение Wp
Случай 2. Если подлежит исключению вершина і, то в этом случае выполняется соотношение ад₀ w. Wp и вершина / также будет исключена на этом же шаге алгоритма и будет выполнено wo ~ wi ~ wp что является частным случаем w. Wp Из этого следует, что исключение вершины m на 4-м шаге алгоритма 2 не изменяет попарное частичное отношение предпочтения на множестве /'.¦
Теорема 2.3. Вектор весовых коэффициентов хи*, построенный с помощью алгоритма 2, является оптимальным решением задачи
w* (х) = arg { шах F_mln {w, Q (ж))} =
WE D_w
= arg { max min (w, Q (x))}, (2.55)
гveD_w ]tN
где
N
D_w = {тг/|ю. w₀ 0, i= T7W; Y,wi=
= i Wf Wp l= ITT}.
(2.56)
Доказательство
Обозначим через / множество вершин, исключенных из рассмотрения в шаге 4 алгоритма 2.
1. Покажем, что ?о* допустимый вектор,
а) Очевидно, что для всех / е Г выполняется условие w]= до₀,
а для всех / е Д/ в силу шага 3 алгоритма 2 выполняется условие w* до₀.
Следовательно,
W* Ш₀, / G /.
б) Обозначим через г мощность множества Тогда
N
= z + х wr
1=1 /е 1 }е І\І
В силу построения алгоритма
X а) = ш₀ - (ЛГ - г); /6 г
Y,wj= Я'= Я - (N- г) ¦ до₀.
/ € / \ /
Следовательно,
N
(2.57)
Yjw)= R- (N - r)- w0+ (N~ r) - wo ~ Я. /=1
в) Для каждого соотношения
(О/ __
ш. Wp 1= 1, L, (2.53)
может иметь место одна из трех возможных ситуаций.
Ситуация 1. Если і е / \ Г и / е I \ /, то условие (2.58) выполняется в силу шага 3 алгоритма 2.
Ситуация 2. Если і е /V и / е /, то условие (2.58) выполни ется в силу шага 4 алгоритма 2: до! до₀ и до^ = до₀.
Ситуация 3. Если і е Г и / е /, то до* = до* = до₀, следователь-нJ, условие (2.58) также выполняется.
Таким образом, доказано, что до* допустимый вектор задачи v2.55H2.56).
2. Покажем, что до* оптимальный вектор.
Допустим (от противного), что существует вектор до (до * до*) такой, что
mm {до - Q. (х)} min {до* - Q_t (де)}. i?iN ‘ ‘ 1iN
Тогда для і е / из шага 4 алгоритма 2 следует, что
- Q, (*) * Щ - Qf (х), і е

РЕШЕНИЕ ЗАДАЧИ МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА

1= 1,L\
5 - отображение множества недоминируемых и выбранных рациональных вариантов.
Окно характеристик критериев (/) представляет собой прямоугольную таблицу, содержащую следующие текстовые характеристики: наименование критерия, размерность критерия и его тип (минимизация (min) или максимизация (max)).
Окно характеристик альтернатив (2) представляет собой таблицу с двумя столбцами, в каждом из которых могут отображаться следующие данные: исходные значения оценок альтернатив; оценки, приведенные к одному типу (минимизации); значения оценок, нормализованные к заданному интервалу; лучшие значения для данного критерия оптимальности по всем вариантам с указанием альтернативы, в которой эта оценка достигается; значение вектора идеальной точки"; значения введенных или вычисленных коэффициентов важности частных критериев оптимальности.
В третьем окне информация, отображаемая во втором окне, представляется в графическом виде диаграмм Кивиата. При этом отмеченные для конкретной альтернативы точки соединяются в виде многоугольника.
В данной системе принято, что дальние от центра точки соответствуют лучшим (в соответствии с заданным типом) значениям по частным критериям.
В четвертом окне отображается граф дополнительной качественной информации о бинарных отношениях предпочтения между частными критериями в послойном виде (к первому слою относятся вершины, в которые не входит ни одна дуга; ко второму слою те и только те вершины, в которые входят дуги из вершин первого слоя; к третьему слою те и только те вершины, в которые входят дуги из вершин первого и второго слоев и т. д.; при этом у вершин последнего слоя не будет ни одной выходящей дуги).
Пятое окно предназначено для отображения результатов анализа на принадлежность вариантов области недоминируемых решений (области решений, оптимальных по Парето) и ьыбранных рациональных вариантов.
Кроме рассмотренных окон, на экран при необходимости могут выводиться следующие окна:
окно вывода помощи Help (рис. 6);
окно ввода и редактирования параметров задачи (рис. 7);
окно отображения результатов решения задачи в табличном виде и в виде столбиковых диаграмм (рис. S).
Кроме диалогового ввода исходных данных возможен и ввод информации из заранее подготовленного текстового файла. Исходные данные для решения задачи в этом случае описываются на специальном входном языке системы.
Такая возможность позволяет использовать данную систему совместно с другими системами, в результате работы которых появляется таблица многокритериального выбора типа альтернативы -- критерии для окончательного принятия решения пользователем.
В качестве иллюстративного примера рассмотрена задача, сформулированная в [38]. ЛПР должно принять решение по выбору рационального варианта вычислительной системы из трех возможных. Варианты имеют количественные оценки по семи критериям
Аппаратные.средства Операиионная.оыстема Лингв_процессоры Возмохности_лереиоса Управление ланными Надехностьластав^ Средетв --
F2 - Параметры ALT-F2 - Решение Предпочтения:
F3 - добавить ALT-F3 - удалить Критерии:
F4 - добавить ALT-F4 - удалить
CTRL-F4 - изменить
Альтернативы:
F5 - добавить ALT-F3 - удалить
CTRL-F5 - изменить в правом столбце
F6 - Отображение левого столбца
F7 - Отображение правого столбца
F8 - Свести или изменить коэффициенты важности
Памп:
F9 - Читать с диска ALT-F9 - писать на диск F10 - Pyc/L?t ALT-F10 - конец работы
Нахмите_либук клавишу для продолжения=
\
Qua


Рис. в. Окно помощи системы
(Q = Q_r ..., Q₇), и задача заключается в максимизации каждого из
них. Варианты экспертно оцениваются в баллах. Исходные данные задачи приведены в табл.
2. В скобках представлены те же оценки, приведенные к типу минимизации и нсрмализованные к интервалу [1, 2]. В последней графе таблицы приведены фиксированные числовые значения весовых коэффициентов важности, предлагаемые в работе [38] для решения задачи многокритериального выбора. Табл.
2 показывает, что данные варианты можно характеризовать как имеющие противоречивые оценки по различным частным критериям.
В качестве обобщенного критерия оптимальности будем использовать аддитивный критерий.
Содержимое файла данных, подготовленных на входном языке системы, приведено ниже. В разделе критериев (.crt) описываюіся критерии (наименование, размерность и тип). В разделе альтерна-

Таблица 2

Критерий Характеристика Вариант -, 1 2 3 [38] 2і Аппаратные 7 8 6 0.27 средства (1-bj О) (2) Оі Операционная 5 6 7 0.27 система (2) (1.5) (1) Оз Лингвистические 5 7 8 0.16 процессоры (2) (1-3) (1) 0* Возможности 9 6 7 0.1? переноса на другую 0) (2) (1.7) систему Оь Управление 6 4 4 0.08 данными О) (2) (2) Qb Надежность б 7 5 0.08 поставщика (1.5) (1) (2) Or Общие средства 7 5 7 0.02 программирования (1) (2) (1)

тив (.ait) находятся данные о вариантах (имя варианта и его оценки для различных частных критериев в порядке, установленном в предыдущем разделе). В разделе предпочтений (.prf) указываются пары номеров критериев, для которых вводится бинарное отношение предпочтения с указанием уточняющего коэффициента ?. Если последний не указан, то он принимается равным единице. В разделе параметров (.par) указываются параметры задачи в том же порядке, в каком они перечислены в окне ввода и корректировки парамегров. Разделы предпочтений и параметров в исходном файле могут отсутствовать. При этом значения параметров устанавливаются по умолчанию, а предпочтения считаются отсутствующими.
.crt
Аппаратные средства, балл, 1 Операционная система, балл, 1 Лингвистические процессоры, балл, 1 Возможности переноса, балл, 1 Управление данными, балл, 1 Надежность поставщика, балл, 1 Общие средства программирования, балл, 1 .alt
Первый, 7. 5, 5, 9, 6, 6, 7;
Второй, 8, 6, 7, 6, 4, 7, 5;
Третий. 6, 7, 8, 7, 4, 5, 7;
?/

Диалоговая система многокритериального выбора

N Наименование Размерность Тип ІІИ 1: Первый К 1: Первый і 1 Аппаратные средства балл Пах 7 0.475 2 Операционная система балл Нах 5 0.01 3 Лингв_лроцессоры балл Мах 5 0.475 3 Возмохности_лереноса Управление.данными балл балл Иах Мах 1 8:81 б Надехность_поставщ балл Мах 6 0.01 7 Средства_программ балл Мах 7 0.01

ПАРАМЕТРЫ ЗАДАЧИ

1. Применято нормирование


2. Левая граница
3. Правая граница
4. Тип обобщенного критерия
5. Показатель степени
6. Применять дополнительную і
7. Автоматическое вычисление
8. Суммарный коэффициент
9. Минимальный коэффициент


Для корректировки параметров решения задачи на экран выводится окно ввода и изменения параметров задачи, в котором имеются 0 параметров решения (см. рис. 7):
1. Применять ли нормализацию да/нет, т. е. приводить ли значения оценок альтернатив к указанному пользователем интервалу [а, р].
2. Левая граница а значение интервала нормализации.
3. Правая граница Р значение интервала нормализации.
4. Тип обобщенного критерия


N
суммарный F_z = ? w. Qj,
;=i
максимальный риск F_ma = ipax^ (ur ?,);
максимальная осторожность F_mln = ^oir^ (w. Q.)\
N
среднестепенной F_p = [ ? (ш. Qf) ]1/,p;
= i N
мультипликативный F_n = П("і^)
i=l
тип обобщенного критерия оптимальности, используемого при решении задачи.
5. Показатель степени значение показатель степени р среднестепенного обобщенного критерия
?жіІоівМ17'
/=1
6. Применять дополнительную информацию да/нет" ис
пользовать ли при расчетах дополнительную уточняющую информацию о попарных предпочтениях на множестве критериев типа СО, = {?, )¦ Q/},1= 1.....L.
7. Автоматическое вычисление коэффициентов да/нет. Если значение параметра да, то весовые коэффициенты вычисляются автоматически по принципу гарантированного результата на основе введенной качественной информации о попарных предпочтениях, формирующих область допустимых значений весовых коэффициентов D_w:
w* = arg { max F (w, .....Q_N)}, (3.1)
we D_w
где
D_w= w\w_i w_Q 1, i = 1, N-, ’?,w_i = Л;
=i
w. l Wj, l = 1, L}. (3.2)
Если значение параметра нет, то при определении рационального решения в качестве весовых коэффициентов важности w используются значения весовых коэффициентов, явно заданные пользователем в произвольной шкале.
8. Суммарный коэффициент значение значение R суммы весовых коэффициентов при расчетах.
9. Минимальный коэффициент значение значение минимально возможного коэффициента w₀ при решении экстремальной задачи (1)(2).
При запуске системы значения параметров считываются из исходного файла, а в случае его отсутствия устанавливаются значения по умолчанию.
При выборе типа обобщенного критерия оптимальности в ниж-


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

Диалоговая система многокритериального выбора

N Наименование Размерность Тип I И 1: Первый К 1: Первый 1 Аппаратною средства балл Max 1 7 0.475 а Операционная система балл Мах \ 5 0.01 з Лингв_лроцессорм балл Max 1 5 0.475 4 Возмохност и_переноса балл Max 1 9 0.01 5 Управление_данными балл Мах 1 6 0.01 6 На дежност ь_пост эвні балл Мах 6 0.01 7 Средст ва_лРограмм балл Мах 7 0.01

ПАРАМЕТРЫ ЗАДАЧИ
1. Применять нормирование	Да
2. /Іевая граница	і
3. Правая граница	2
4. Тип обобщенного критерия	Суммарный
5. Показатель степени	3
6. Применять дополнительным информацию	Нет
7. Автоматическое вычисление коэфф-тов	Да
8. Сыммармми коэффициент	1
9. Минимальный коэффициент	0.01

Новое значение: ВВИДа
Рис. 10. Меню ДА/НЕТ
Пользователь имеет возможность визуализации исходной и результатной информации в следующих вариантах:
отображение характеристик альтернатив в числовом виде во втором окне;
отображение характеристик альтернатив в графическом виде диаграмм Кивиата в четвертом окне;
отображение результатов анализа на принадлежность вариантов области недоминируемых решений (области решений, оптимальных по Парето) и выбранных рациональных решений (пятое окно);
отображение результатов решения в табличном виде и в виде столбиковых диаграмм в окне, появляющемся по требованию пользователя.
Во втором окне производится отображение информации в двух столбцах, в каждом из которых независимо может быть отображена следующая информация:
исходные значения оценок альтернатив (И или S);


значения оценок, приведенные к одному типу критериев (ГГ или R");
значения оценок, нормализованные к заданному интервалу (Н" или N);
лучшие значения для данного критерия оптимальности по всем вариантам с указанием номера альтернативы, в которой данное значение достигается;
значение вектора идеальной точки;
значения введенных или вычисленных коэффициентов важности частных критериев (К или С).
Для изменения вида выводимой информации в первом и втором столбцах необходимо нажать клавишу F6 или F7 соответственно. Дальнейшие действия для обоих столбцов одинаковы. В нижней части экрана появляется окно вывода меню, в котором перечислены 6 возможных типов информации. При этом строковый маркер находится на позиции, соответствующей выбранному ранее типу (рис.
11).
Выбор типа информации в меню производится аналогично выбору типа обобщенного критерия оптимальности. После выбора типов идеальная точка и лучшие оценки информация в соответствующем столбце второго окна изменяется. Если произведен выбор исходных, приведенных, нормализованных оценок или значений весовых коэффициентов, система выводит запрос номера альтернативы в специальном окне.
После ввода номера отображение изменяется.
В четвертом окне системы информация, отображаемая в числовом виде во втором окне, предстает в виде диаграмм Кивиата. Выводятся две диаграммы, соответствующие двум столбцам, в нужном цвете.
Отображение результатов решения задачи производится в пятом окне системы, где выводятся номера альтернатив с указанием принадлежности их к множеству:
доминируемых альтернатив (синий цвет);
недоминируемых альтернатив (множество решений, оптимальных по Парето красный цвет);
оптимальных решений (черный цвет на белом фоне).
В данном окне выводятся только номера критериев без какой-либо дополнительной информации. Для подробного вывода с указанием численного значения обобщенного критерия оптимальности и графического отображения в виде столбиковых диаграмм необходимо вызвать окно с помощью комбинации клавиш Alt-F2.
Для стирания окна можно нажать любую клавишу.
Система имеет следующие дополнительные возможности:
возможность работы на русском или английском языках (язык работы изменяется путем нажатия клавиши F10);
вывод исходных данных задачи в текстовый файл.

Глава 4 ПРИМЕР РЕШЕНИЯ ЗАДАЧИ МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА КОНФИГУРАЦИИ ПЕРСОНАЛЬНОЙ ЭВМ

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

Постановка задачи

Рассмотрим решение задачи выбора приобретаемой персональной ЭВМ (ПЭВМ) типа IBM PC. Для выбора предлагается шесть вариантов, каждый из которых характеризуется семью критериями качества (табл.
3).

Таблица 3

Наименования критерия Тип Размерность 1. Тип процессора МАХ Баллы 2. Тактовая частота процессора МАХ МГц 3. Наличие сопроцессора МАХ 1есть; 0нет 4. Объем кэш-памяти МАХ Кбайт 5. Объем оперативной памяти МАХ Мбайт 6. Объем жесткого диска (винчестера) МАХ Мбайт 7. Стоимость MIN Доллары

В табл. 3 приведены частные критерии выбора. Критерий 1 (тип процессора) имеет качественный характер (лингвистическая переменная) и его значение у вариантов измеряется в баллах Балльные оценки отображают количественное представление ЛПР о качестве процессоров ПЭВМ Один из возможных вариантов оценивания приведен в табл. 4.

Таблица 4

Тип процессора Бальная оценка 386SX 1 386DX 4 486 DX 5 486DX2 7

Критерий 3 (наличие математического сопроцессора) в принципе является качественным, но может легко преобразовываться в количественный (1 есть сопроцессор, 0 нет сопроцессора), так как сопроцессор в ПЭВМ может быть только один.
Остальные критерии количественные и оценки по ним являются соответствующей технической характеристикой (критерии 2, 4, 5 и 6) либо ценой компьютера данной конфигурации (критерий 7).
Все критерии, кроме последнего (стоимости), имеют тип максимизации, что соответствует принципу: более мощный компьютер является более предпочтительным. Критерий стоимости наоборот: предпочтительнее купить компьютер подешевле.
Шесть предлагаемых вариантов имеют оценки по критериям, указанные в табл. 5.

Таблица 5

Частные критерии Исходные оценки вариантов по критериям 1 2 3 4 5 6 1. Процессор 1 4 5 7 5 7 2. Тактовая частота 40 40 40 66 50 66 3. Сопроцессор 0 1 1 1 1 1 4. Кэш-память 0 128 256 256 256 256 5. Оперативная память 2 4 4 4 16 16 6. Винчестер 120 170 340 420 2100 3500 7. Стоимость 995 1198 1804 2145 5599 7186

После приведения всех критериев к одному типу (минимизации) и к интервалу [1,2], получаем нормализованные безразмерные оценки, отображенные в табл. 6.
Нетрудно видеть, что с точки зрения используемых семи частных критериев оптимальности все варианты являются Парето-оптималь-ными, т. е. нет варианта, который бы имел по всем частным критериям оценки хуже, чем некоторый другой вариант. Убедиться в этом также можно, сравнив численные оценки частных критериев для каждой пары вариантов с помощью диаграммы на рис. 12.
Стоимость Жесткий диск Оперативная память Кэш-память Сопроцессор Тактовая частота Процессор
Рис. 12. Диаграмма нормализованных численных оценок вариантов по частным критериям оптимальности
Таблица 6

Частные критерии Нормализованные оценки по критериям 1 2 3 4 5 6 1. Процессор 2 1.5 1.333 1 1.333 1 2. Тактовая частота 2 2 2 1 1.615 1 3. Сопроцессор 2 1 1 1 1 1 4. Кэш-па’мять 2 1.5 1 1 1 1 5. Оперативная память 2 1.857 1.857 1.857 1 1 6. Винчестер 2 1.985 1.935 1.911 1.414 1 7. Стоимость 1 1.033 1.131 1.186 1.744 2

2. Решение задачи при использовании фиксированного набора весовых коэффициентов важности

Рассмотрим решение поставленной п. 4. 1 задачи при использовании явно заданного ЛПР набора весовых коэффициентов важности частных критериев и аддитивного обобщенного критерия оптимальности. Диалоговая система многокритериального выбора позволяет пользователю определить набор весовых коэффициентов важности w = (ш_р ..., ш₇) в произвольной шкале, преобразование их к нужному виду [ X wi ~ 1* - 0 1 = ТГ7 ] будет произведено
= 1
автоматически. Допустим, что ЛПР использует два набора весовых коэффициентов важности, отображенных в табл.
7, где указаны также нормированные значения коэффициентов важности после автоматического преобразования их системой.

Таблица 7

Частные критерии Набор 1 Набор 2 Балл Коэффициент Балл Коэффициент 1. Процессор 1 0.142857 1 0.04 2. Тактовая частота 1 0.142857 4 0.16 3. Сопроцессор 1 0.142857 3 0.12 4. Кэш-память 1 0.142857 1 0.04 5. Оперативная память 1 0.142857 1 0.04 6. Винчестер 1 0.142857 5 0.2 7. Стоимость 1 0.142857 10 0.4

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

Таблица 8

Варранты Значение обобщенного критерия Набор 1 Набор 2 1 1.85714 1.6 2 1.55359 1.44444 3 1.46515 1.44687 4 1.27916 1.29084 5 1.30094 1.4921 6 1.14286 1.4

частоте и наличию сопроцессора. Значения обобщенного критерия для каждого варианта приведены в табл. 8. Оптимальным вариантом в этом случае является вариант 4, т. е. достигнут компромисс


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

3. Решение задачи с использованием дополнительной качественной информации об относительной важности частных критериев

Рассмотрим решение задачи при определении весовых коэффициентов важности по принципу гарантированного результата:
min { max F (w,Q (x))}, x e D weD_w
где
D={ 1 6}, (4.1)
7
D_w= w₀ 0. i= T77; 1;
i=l
(Of _
w. 5, w_r l = T7T, 1}. (4. 2)
Далее приведены результаты решения задачи при использовании аддитивного обобщенного критерия (1. 16) и обобщенного критерия максимальной осторожности (1. 19) при параметрах
R - 1 и w₀ 0.01 для различных типов дополнительной качественной информации и различных значений уточняющих коэффициентов
При отсутствии дополнительной качественной информации (1.31) получаем область допустимых значений весовых коэффициентов вида (1. 30), которая может интерпретироваться как безразличие ЛПР. Весовые коэффициенты важности частных критериев в этом случае, вычисленные для каждого варианта при использовании аддитивного обобщенного критерия оптимальности, приведены в табл.
9. В последней строке таблицы содержатся значения обобщенного критерия оптимальности. Диаграмма полученного решения приведена на рис.
14.
Оптимальным вариантом в этом случае является вариант 5.
Расчет весовых коэффициентов важности и оптимального варианта при использовании обобщенного критерия максимальной осторожности приведен в табл. 10 и на рис. 15.
Соотношения численных значений коэффициентов носят иной характер. Если при использовании аддитивного обобщенного критерия оптимальности все весовые коэффициенты, кроме одного, получают минимальное значение (установленное в данном случае в 0.01), то один критерий

Таблица 9

Частные критерии Коэффициенты важности по вариантам 1 2 3 4 5* 6 1. Процессор 0.01 0.01 0.01 0.01 0.01 0.01 2. Тактовая частота 0.01 0.01 0.01 0.01 0.01 0.01 3. Сопроцессор 0.94 0.01 0.01 0.01 0.01 0.01 4. Кэш-память 0.01 0.01 0.01 0.01 0.01 0.01 5. Оперативная память 0.01 0.01 0.01 0.01 0.01 0.01 6. Винчестер 0.01 0.94 0.94 0.94 0.01 0.01 7. Стоимость 0.01 0.01 0.01 0.01 0.94 0.94 Значение обобщенного критерия 1.9809 1.9154 1.8643 1.8366 1.7083 1.94

Таблица 10

Частные критерии Коэффициенты важности по вариантам 1 2 3 4 5 6* 1. Процессор 0.1253 0.1363 0.1420 0.1682 0.1325 0.1538 2. Тактовая частота 0.1669 0.1397 0.1310 0.1682 0.1371 0.1538 3. Сопроцессор 0.1163 0.1947 0.1826 0.1682 0.1703 0.1538 4. Кэш-память 0.1163 0.1298 0.1826 0.1682 0.1703 0.1538 5. Оперативная память 0.1241 0.1113 0.1043 0.0961 0.1703 0.1538 6. Винчестер 0.1184 0.0998 0.0959 0.0894 0.1217 0.1538 7. Стоимость 0.2327 0.1885 0.1615 0.1418 0.0977 0.0769 Значение обобщенного критерия 0.2327 0.1947 0.1826 0.1682 0.1703 0.1538

Вычисление весовых коэффициентов важности

Для і = / \ / в силу работы алгоритма 1 следует, что
- Q_t (х) до* - Q. (де), і е I \ /.
Іаким образом получим N неравенств*
wi ¦ Q_t (х) до,* - (ж), і е /. (2.59)
Каждое неравенство (2.59) разделим на положительную величину Qfx) к просуммируем по і:
Ы N
?!= R R;
i=i і=і
следовательно,
до, - до!, і = 1, N,
что противоречит условию до * до*.
Следовательно, до* оптимальный вектор задачи (2.55)(2.56).И При до₀ = 0 получаем однократное применение алгоритма 1, что соответствует теореме 2.2.
Лемма 2.3. В случае отсутствия дополнительной качественной информации (2.58) решением задачи (2.55), где
N
D_w= {до I до, до₀ 0, і = TJ3; ? wi = R }. (2.60)
=i
и при условии перенумерации критериев таким образом, чтобы выполнялось условие Q_x (х) - - - - - Qn (х), является вектор х?*, компоненты которого определяются по формуле
w₀, у = ТТпR - г¦ ш₀ -
-Л-, у = г + 1 ,Ы,
?,(*)¦ L (!/?(*))
і = л+ 1
где г наибольший индекс к, при котором выполняется условие
(2.62)
R- г - w₀
-В-9-5 "('
Q_t (X) - ? (l/Q. (X))
i=r+l
Доказательство
В случае отсутствия дополнительной качественной информации выполняется условие ?2 = 0 и граф G (/, ?2) состоит из одного слоя (S = 1). Рассмотрим работу алгоритма 2 в этом случае. Так как граф G (/, Q) состоит из одного слоя, то в результате применения алгоритма 1 получим
Г N
?/(*)- X (!/?,(*)
і=і
Так как по предположению (дг) ... Q_N (х), то нетрудно убедиться, что
w'_x ... w’_N.
Обозначим через г максимальный индекс к, при котором выполняется условие w'_k гг₀. Согласно построению алгоритма 1 (шаг 4) для
всех w*_k, к - 17?. получим ?и*_к = а₀; для всех w_k, к = г + 1, N, получим
, R - г - w,
'/ ~ N
Q, (*)- I (1/?,W)
. = .-+і
что соответствует (2.61 )Л
При R = 1 и w₀ = 0 выражения (2.61 )-(2.62) аналогичны результату, полученному в [20]:
w] = -^-, j = ГЖ (2.63)
Q_j(x)J_j(l/Q.(x))
/= 1
При использовании обобщенного критерия оптимальности (2.46) задача нахождения весовых коэффициентов формулируется следующим образом.
в** (х) = arg { max F (w, Q (де))} = we D_w
= arg { max max (w, Q (x))}, (2.64)
we D_w 1iN
где область допустимых значений весовых коэффициентов D_w имеет вид (2.44).
Для сформулированной задачи (2.64) справедлива следующая теорема.
Теорема 2,4. Оптимальным решением задачи
w* (ж) = arg { rnaxf _х (w, Q (x))} = we D_w
= arg { max max (w, Q (ж))}, (2.65)
we D_w liN
где
N
D_w= {w I w₀ 0, i= 1, N; ?w. = Я;
i=l
(2.66)
(2.67)
(?[ _
w. w., 1= T7T},
является зектор w* с компонентами R- (//- n_r)-w₀
J П_г ’ 1 G !r'
W₀, ie !\l_r,
где индекс г определяется из соотношения
Доказательство
Нетрудно видеть, что ?а* является допустимым вектором задачи (2.65)(2.66). Покажем, что w* является ее оптимальным решением.
Допустим (от противного), что существует вектор w' е D_w, являющийся допустимым вектором задачи (2.65)-(2.66), такой, что выполняется соотношение
^max^ w\ Q_{ (ж) = ш'₍ Q, (ж)
(2.G8)
Я_г =
max 1kN
Я_к
R- (N - n.) ¦ w₀
Q_k (*)-
(2.69;
Як =
(2.70)
. R - (N - п ) - w_a
max w. Q. (ж) = ---a Q. (ж).
1iN 11 nr
Далее, из соотношений (2.68)(2.69) следует, что
R- (N- n_r) wо R- (N- n_k)-w₀
n_r n_k
Из (2.70) и (2.71) следует, что R- (N- n_k) ¦ w₀
Q.(x), k= T7W. (2.71)
(2.72)
Q. (ж), k = 17W,
w', Q, (x)
в частности, при k = l получим , R- (N- n,)- w₀
(2.73)
Для всех i t имеет место соотношение w. w_v откуда можно записать
(2.74)
(2.75)
R - (N - n,) ¦ w₀
w . -----,
l n.
w'_{ W₀, t€ I \ /,. Из (2.74) следует, что
, R- (N- n_r) w₀
n_r= R- (N - n_r)- ш₀;
іб I,
а из (2.75) следует, что
Отсюда получаем неравенство
N
Y,wi= X w\ + Y,wi R
/=1 ie I_f ie /\/₍
что противоречит предположению о допустимости вектора w' и доказывает теоремуЛ
В случае линейной упорядоченности частных критериев оптимальности и области допустимых значений весовых коэффициентов вида (2.36) оптимальным решением задачи (2.65) является вектор
весовых коэффициентов хи с компонентами
R- (N - г) - w₀
і = Т77; і= т + 1 ,N,
(2.76)
wi =
w,
о*
где индекс г определяется из соотношения
qr = ,m?x_xl (2.77)
]?kN
R - (N - k) - w_Q k
Q_k{x).
(2.78)
Это следует из того, что в случае линейной упорядоченности по важности частных критериев оптимальности выполняются соотношения І_г=т- { 1.....г}, |/J = г.
При отсутствии дополнительной качественной информации о предпочтениях на множестве частных критериев и области допустимых значений весовых коэффициентов Dx_w (2.40) оптимальным решением задачи (2.65) является вектор весовых коэффициентов хи* с компонентами, определяемыми выражениями
, 17? - (N - 1) - w_Q, i = r,
W. = s ,
' [ш₀, i UN, i* r,
где индекс г определяется из соотношения
7 = max Q_k(x) r 1 kN *

Вычисление весовых коэффициентов важности при использовании среднестепенного обобщенного критерия оптимальности

Рассмотрим решение задачи вычисления весовых коэффициентов важности при использовании среднестепенного обобщенного критерия.
Для экстремальной задачи
w (ж) = arg { max F (хм, Q (.x))}, (2.79)
we Da, и
где
N
F_p (хм, Q (x)) = [ ? w. ?? (x) }l/p, (2.80)
D_w= {w\wj w₀ 0, i = TTN-, Y,wi=
/=1
со/ , _
w_{ w., (!),= {?_fi Qj}, l= Т7Г} (2.81)
может быть сформ?лирована следующая теорема.
Теорема 2.5. Для любых р (0 р ) оптимальным решением
задачи (2.79)- (2.81) является вектор хм* с компонентами
[R- (N - п_г) - ш₀
хм* = \ п_г ’ (2.82)
1®о* іе Л/-
где индекс г определяется из соотношения
(2.83)
Доказательство
Проведем доказательство данной теоремы с помощью метода динамического программирования [14]. Для этого обобщим задачу (2.79)(2.81) следующим образом. Требуется распределить ресурс R_k между k объектами, каждый из которых характеризуется значением Qj частного критерия так, чтобы выполнялось условие
max F (w, ? (ж)), (2.85)
Р
где
(fi- n_r) w₀^„
n 2u
r
R-
(*)+ VI ?/(*) fP-
tel\l_k
(2.84)
q_u= [
1Wi= Rk’ (=1
= {w\wj w₀ 0, i = 1, М\
(О/ _
w. Wj, /= 1, L}. (2.86)
Разобьем граф G (/, Q) на 5 слоев и перенумеруем вершины, начиная со слоя S и выше. Внутри каждого слоя будем нумеровать вершины в произвольном порядке. Введем следующие обозначения:
множество вершин графа G (/, ?2), находящихся на слоях s t, из которых есть путь в вершину j, включая ее саму: /' = 1, N,
t= T7S\
l_t множество вершин на слое t, t = 1, S;
множество вершин, в каждую из которых есть путь из вершины j, / = 1, JV;
nij мощность множества І*ц
Qt = Q_t (х), i = 1, N, для фиксированных значений х.
Используя введенные обозначения, построим многошаговую модель принятия оптимального решения.
1. В качестве управляемого параметра выбирается количество ресурса, выделяемого і-му объекту, т. е. значение весового коэффициента важности t-го частного критерия.
2. Область решений определяется выражением (2.85).
3. В качестве фазовой переменной R_t выбирается количество ресурса, распределяемого по остальным (і 1) объектам.
4. Начальное состояние: R_N+l = R-
5. Уравнение состояния: R₍ = R_i+l~ w_p i= 1, N.
6. Результат:
Y(wi,Ri+1= u_rtf(x).
7. Семейство функциональных уравнений:
f_k я*₊1 = max (H wi Qi *) ]1/Pb
wi.....wk j=i
X = #*+ p wi - wo i=
i= 1
w_t Wp l= T7L, *, / e {1.....?}.
Нетрудно видеть, что рекуррентное соотношение динамического программирования имеет следующий вид:
N
f_k +0= max { max {tZ wi Qi W]1/p} =
Щ .....Wk-l i= 1
N
max {[ w_t Qf (x) + max {? wp Qp (x)} ]l/p} =
Щ _i=l
= max {[ ®. Qp (x) + f_k__l (R_k) ]i/p}. wk
Очевидно также, что на каждом шаге оптимизации на значение управляемого параметра накладывается ограничение:
R_l+l- (i- l)w₀ w_t w'.,
где
(2.87)
_# [max ,w„ если Л* 0;
w f = ^ 6 / 1 a _n
Іш₀, если 1=0. Для слоя 5 можно записать:
U (Л₂) =
max
wqs is R 2 R1= R2~ і=
/₂(/?₂)= max {[*2^2+ /?(*s~ w₂)]l/p} =
* * WQiW^R2~WQ 1 * 1 *
/?2= J?3- ®2= 0
= max {[ (/?₃ - a₀) Q\ + ш₀ Qp]l/p; [ (*₃ - w₀)Qp + w₀Qp]l/p}-,
'(*- .*„T*,- J.0 (1"з?а+ "$)l'7')-
Лз= Л 4- ш3= О
= max {[ (R₃ - 2а/₀) + ш„ (?? + Q%\l/p;
[(/?з- 2w₀)Qp+ w₀(gf+ ]1/p;
К*- 2ш₀)?' + ш₀^₊ ]1/p;
// *i + i = ,F_rax,{ I *i₊ i " *. - 1)",₀)^ +
IS Га *5 s
(2.88)
=i
it r
Итак, очевидно, что для последнего слоя 5 сформулированная теорема справедлива.
Рассмотрим произвольную вершину п на слое s S в предположении, что для слоя (s + 1) теорема справедлива.
Тогда можно записать:
К (Rn₊ 0 = та* . UwnQPn+ fn-i (*_я+1 wn ]l/P} =
w_nz w _n Rn= RiH-l-Wn
771
= шах {|a max ([-
w_ni w _n IS tuS /- 1
Rn= Я/Н- Г
+ "V ? ФЛ17' = Jjax r„ /?„,,,.).
*л=Л/н-1- w„
л* *лі-1- (я- l)0
w_nS/J„₊1- (n- 1) wo -1
7=1 i* m
Функция f'_n является монотонной относительно w_n и, следовательно, достигает своего максимального значения на одном из концов интервала [ '_n; R_n+l - (я - 1) до₀ ].
а) Функция /'_д достигает максимального значения при w_n = R_n+l - (я - 1) w₀. Тогда
- o’ief]17'.
1=1
б) Функция f'_n достигает максимального значения при м/_п = w'_n. В этом случае
шах +
1 /I 1
*₊l~ (Я- - О,
л- I
- х
1 = 1
/!
іе /*
+1
т.
Если w_n = w_Q, тогда
¦о о:+
в-1
(2.89)
т.
1=1 іе /!
іе I
Если w_n = в/_п = w_k, где вершина с номером к находится на слое, лежащем ниже слоя s, тогда
*_я+1- Wn~ (Я- тГ1 Uw,
до = ч
S+ 1
тя
или
Wn *в₊і (Я- тг + 1- D®!
n s +1 тг
S+ 1
т.
тогда
/ *+1 ч
(2.90)
/^=/^+1u{n}, то
(я- т_г - l)w₀
*+і , ,
т_г +1
Так как выполняется условие т*= т* + 1 + 1, и из этого следует, что
(я - тг)Щ w = ---
п s -
тг
а значение функции
іе Г1
Г
тЛ w_n „
-d-*][Qp_n
{[JW
(я-
5% п-\
т.
+ (2-91)
/= 1
/;
Таким образом, выражения (2.88), (2.89), (2.91) показывают, что теорема справедлива и для слоя з.
Для вершины с номером N, учитывая, что R_n+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 D_w
F (да, Q (ж), Q*) = X wt (? (*) ~
і= l
или
F (да, Q (ж), Q*) = max { да, (?, (ж) - ?*)}; ]iN ' ‘
- oo min Q, (ж), i = 1, N; xeD
D_w= {да I да_у S да₀ 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

Рис. 5. Отображение информации на экране при работе диалоговой систе мы многокритериального выбора
зуются как оси для представления соответствующих численных значений частных критериев);
4 отображение графа предпочтения, содержащего дополнительную информацию о частных предпочтениях типа to, = {Q_t )- Q.},





    Нейросети: Нейролингвистика - Логика

• Нейросети
  
• Теория нейросетей
  
• Справочник по нейросетям
  
• Софт для нейросети
  
• ANSYS - нейросеть
  
  
• Обучение нейросети
  
• Классификация нейросетей
  
• Искуственный интелект и нейросети
  
• Финансы и нейросети
  
• Железо нейросети
  
  
• Построение нейросети
  
• Инструменты нейросети
  
• Применение нейросетей
  
• Нейросетевой анализ
  
  
• Нейролингвистика
  
• Нейролингвистика на практике
  
• Нейролингвистическое программирование
  
  
• Логика
  
• Нечеткая логика