Москвин Б.В. Теория принятия решений

Подождите немного. Документ загружается.

321

Рассмотрим последовательность действий в соответствии с

этой схемой.

(1). На основе анализа ситуации принятия решения S при

взаимодействии с ЛПР вводится совокупность нечетких мно-

жеств, определяющих смысл понятия "рационального (хорошего)

по i-му показателю решения". Нечеткое множество X задается

конструкцией (см. 13.4.2) вида X = { (x, μ

(x))} , где x∈U (U - уни-

версальное множество), а μ

(x) - степень принадлежности эле-

мента (x) универсального множества U к нечеткому множеству X.

Степень принадлежности задается функцией вида μ

: U → [0,1], и

отражает степень уверенности ЛПР в принадлежности решения

(x) к нечеткому множеству X.

В качестве универсального множества U здесь целесооб-

разно рассматривать конечное подмножество множества недо-

минируемых решений

(14.6), найденное, например, на основе

процедуры, изложенной в 14.2.

Нечеткие множества M

, i∈G "хороших по i-му показателю

решений", задают, по существу, смысл простых первичных тер-

мов из терм множества T лингвистической переменной (13.31)

= {( x, μ

(x) )} , x∈U, i∈G,

где U - подмножество множества недоминируемых альтернатив

Степень принадлежности μ

(x) формируется на основе

взаимодействия с ЛПР и может задаваться, например, как

(x) - f

(x)

(x) =

⎯⎯⎯⎯⎯ , i∈G, (14.22)

) - f

(x)

или

(x) - f

(x))

(x) =

⎯⎯⎯⎯⎯⎯ , i∈G, (14.23)

) - f

(x))

Здесь f

(x) выбирается таким образом, чтобы μ

(x) ∈ (0,1]. Тогда

(x) = Min f(x) - ε. (14.24)

x∈U

Здесь ε некоторое малое число; ε > 0.

(2). Задание первичных простых термов (значений лингвис-

тической переменной "решение") создает основу для формирова-

322

ния составных термов (в соответствии с синтаксическими прави-

лами). Лингвистическое решающее правило L, задаваемое на ос-

нове взаимодействия с ЛПР, и представляет собой составной

терм, который на профессионально-ориентированном языке оп-

ределяет, что следует понимать под оптимальным в целом ре-

шении в исходной неопределенной ситуации S.

(3). Производится синтаксический разбор C(L) лингвистиче-

ского решающего

правила L. Т.е. составной терм представляется

в виде совокупности первичных простых термов, лингвистических

связок и лингвистических неопределенностей.

(4). Вычисляется нечеткое множество M

, описывающее

смысл лингвистического решающего правила. Нечеткие множест-

ва, описывающие смысл первичных простых термов, были по-

строены в п.1. Составной терм (лингвистическое решающее пра-

вило) образуется на основе взаимодействия с ЛПР из простых и

других составных на основе введения лингвистических неопреде-

ленностей (например, "очень", "вполне", "достаточно" и т.д.) и

лингвистических

связок ("и", "или", "не"). Синтаксический разбор,

проведенный в п.3, позволяет вычислить M

. При этом лингвисти-

ческим связкам соответствуют операции над нечеткими множест-

вами: "или" - объединение; "и" - пересечение; "не" - взятие допол-

нения в универсальном множестве U, а лингвистическим неопре-

деленностям соответствуют некоторые функциональные преоб-

разования степени принадлежности. В частности, лингвистиче-

ской неопределенности "очень" часто сопоставляется операция

концентрации нечеткого множества, т.е.

μ ("очень хорошее") =

("хорошее"), (14.25)

лингвистической неопределенности "достаточно" сопоставляется

операция растяжения нечеткого множества,

μ("достаточно хорошее") = μ

1/2

("хорошее").

Таким образом, вычисляется нечеткое множество

= { (x, μ

(x))}, x∈U

(5). Производится выбор оптимального решения x

, которо-

му соответствует максимальная степень принадлежности в M

Т.е.

= arg Max μ

(x) . (14.26)

x∈U

Формируя и модифицируя лингвистические решающие пра-

вила, ЛПР может эффективно влиять на процесс выделения наи-

более "рационального" в целом решения.

323

Контрольные вопросы

1. В чем состоит некорректность задач многокритериального

выбора с точки зрения классической теории оптимизации и при-

нятия решений ?

2. Поясните способы и пути разрешения критериальной неоп-

ределенности.

3. В чем состоит принцип Парето ?

4. Дайте определение недоминируемой по Парето (эффектив-

ной) альтернативы.

5. Перечислите и прокомментируйте основные свойства мно-

жества Парето.

6. В чем

заключается основная идея выделения конечного

подмножества недоминируемых решений ?

7. Какие ситуации принятия решений различаются в зависимо-

сти от информированности ЛПР. Какие ситуации являются самы-

ми определенными? Какие являются самыми неопределенными?

8. В чем смысл проведения операции нормализации целевых

функций и зачем она проводится ? Что может случиться, если

такую операцию не проводить ?

9. Приведите примеры решающих правил в ситуации отсутст-

вия информации об относительной важности критериев.

10. Какая точка критериального пространства называется иде-

альной ? Приведите пример.

11. В каких формах может быть учтена информация об отно-

сительной важности критериев? В чем достоинства и недостатки

различных форм ?

12. На каком принципе основывается выбор решения в ситуа

ции последовательно применяемых критериев?

13. В чем суть метода последовательных уступок? Покажите

на примере задач линейного программирования, как реализуется

этот метод.

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

в ситуациях векторной оптимизации ?

15. Что представляет из себя лингвистическое решающее пра-

вило с точки зрения лингвистической переменной ?

16. Что представляют из

себя и каким образом используются

синтаксические и семантические правила лингвистической пере-

менной в задачах векторной оптимизации ?

17. Каким образом создается необходимая информационная

база для принятия решения в задачах векторной оптимизации ?

324

15. ПРИНЯТИЕ РЕШЕНИЙ В ИЕРАРХИЧЕСКИХ

ВОЕННО-ТЕХНИЧЕСКИХ СИСТЕМАХ

15.1. Принцип декомпозиции в задачах выбора

Большинство современных военно-технических систем от-

носится к классу, так называемых, сложных (больших) систем или

систем крупного масштаба. Развитие систем управления в них

связано с ростом сложности и масштабности решаемых целевых

задач. Существенной особенностью такого развития является

специализация функций, которая приводит к тому, что сущест-

вующая система управления разбивается на

совокупность под-

систем, решающих специализированные задачи, которые имеют

информационную, методическую и алгоритмическую общность.

Это сопровождается децентрализацией процесса обработки ин-

формации и, как следствие этого, децентрализацией принятия

решения. Действительно, динамичность обстановки и связанный

с этим рост потоков информации может привести к тому, что пол-

ностью централизованный сбор и обработка информации либо

технически

невозможны, либо приводят к значительному запаз-

дыванию в принятии решения. Указанные особенности требуют

разбиения исходной системы на совокупность связанных, но са-

мостоятельно функционирующих подсистем.

Появление в системе отдельных звеньев, способных с не-

обходимой оперативностью перерабатывать всю поступающую

информацию и принимать решения в рамках своей компетенции

означает, по существу, появление в

системе иерархической

структуры, при которой одни подсистемы подвергаются декомпо-

зиции, а процесс управления децентрализации. Однако такое

разбиение исходной системы служит источником н о в о й н е -

о п р е д е л е н н о с т и. Действительно, каждая подсистема

принимает решение в соответствии со своими

собственными це-

лями, не тождественными в общем случае целям других подсис-

тем и системы в целом. В этой ситуации возникает задача с о г -

325

л а с о в а н и я (координации) решений подсистем, и одна из

подсистем вышестоящего иерархического уровня (Центр) наде-

ляется специальными полномочиями по решению этой задачи.

По существу, координационная задача служит для учета эмерд-

жентных свойств системы, подвергнутой декомпозиции.

Формально, с теоретико-множественных позиций декомпо-

зиция системы представляет собой

следующее.

Пусть система S задана множеством допустимых альтерна-

тив

и заданными на этом множестве отношениями предпочте-

ния F; S = (

Δ, F). Произведем декомпозицию системы S на (р+1)

подсистем S

, i=0,..., p.

При этом используем правила последова-

тельной и параллельной теоретико-множественной декомпозиции

систем, рассмотренные, например, в [40] .

Проведем последовательную декомпозицию системы S,

тогда S = S

◦ S

, где

= (Δ

× P,

)

= (P × Δ

×··· × Δ

, F

здесь P - множество связующих сигналов; F = F

◦ F

Далее, используя правила параллельной декомпозиции, S

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

= S

◦ S

◦ ··· ◦ S

где S

= (P

× Δ

, F

= (P × Δ

, F

.....................

= (P

× Δ

, F

= F

◦ ··· ◦ F

Таким образом, система S в целом задается как S = S

◦ S

◦

··· ◦ S

, т.е. исходная система S представлена в виде совокупно-

сти подсистем. Такое представление можно иллюстрировать

схемой

. . . . . . .

Рис.15.1.

Здесь S

- подсистема более высокого, чем подсистемы S

, j = 1,...,

p уровня. S

решает задачу (Δ

), подсистемы S

, j = 1,...,p

326

решают задачи S

= (P

× Δ

, F

). Здесь P - множество связующих

(координирующих) сигналов. Подсистему вышестоящего уровня

часто называют ц е н т р о м (координатором), а соответст-

вующую ему задачу - к о о р д и н и р у ю щ е й задачей. Задачи

подсистем S

называют л о к а л ь н ы м и (задачами подсис-

тем). Задачу принятия решений в системе S в целом называют

г л о б а л ь н о й задачей. Таким образом, произведена декомпо-

зиция глобальной задачи на координирующую и локальные зада-

чи подсистем. Поясним особенности задачи

Центра и задач под-

систем, возникающих при таком разбиении.

Пусть отношение предпочтения F задается с использова-

нием функции f:

Δ → R

, тогда задача принятия решения в систе-

ме в целом имеет вид

= arg

max f(x).

x∈Δ

При этом Δ = Δ

× Δ

× ··· × Δ

; тогда x = (x

,...,x

); F = F

◦F

◦ · ◦ F

;

тогда f = (f

,...,f

Задача центра (координирующая задача)

= (Δ

× P,

)

имеет вид

m a x f

( x

, π)

∈Δ

π∈P

Задачи подсистем (локальные задачи) S

= (P×Δ

, F

), могут

различаться в зависимости от способа учета координирующих

сигналов, рассчитанных в координирующей задаче. При этом

различают две ситуации:

- модификация целевой функции m a x f

(π, x

);

∈Δ

- модификация альтернатив m a x f

( x

) .

∈Δ

(π)

В целом процедура выработки решения строится по итера-

ционной схеме. На каждом шаге Центр решает свою оптимизаци-

онную задачу и вычисляет координирующий сигнал π, который

сообщается подсистемам. Подсистемы на основе полученного

координирующего сигнала π решают свои оптимизационные за-

дачи и сообщают свои решения Центру, что является основой

для последующего уточнения π

. Процесс заканчивается, когда

координирующий сигнал перестает изменяться. В результате оп-

ределяются оптимальные решения подсистем x

,j = 1,...,p и опти-

мальный координирующий сигнал π

327

Развитие исследований, связанных с проблемами декомпо-

зиции и координации в сложных системах, началось сравнитель-

но недавно, но прошло достаточно сложный путь, связанный с

различием подходов научных школ, занимающихся этими вопро-

сами. При этом можно сделать ряд замечаний.

В о - п е р в ы х, следует различать вопросы иерархической

организации вычислительных

процедур оптимизации, которые по

своей форме являются процедурами выбора с мультипредпочте-

нием, и вопросы иерархической по своему содержанию оптими-

зации, связанные с адекватным моделированием и оптимизацией

некоторой реальной иерархической системы. Во многих случаях

иерархическая организация вычислений связана с исследовани-

ем исходной иерархической системы, и тогда можно говорить об

определенном соответствии

формы процедур оптимизации ре-

альному содержанию решаемой задачи. Здесь можно говорить о

применении декомпозиции и координации в чисто вычислитель-

ных интересах, когда исходная оптимизационная задача большой

размерности подвергается декомпозиции и разбивается на зада-

чи существенно меньшей размерности. В этом случае координа-

ция служит для учета общих связей подсистем и позволяет дос

тигать адекватности решений исходной задачи и задач подсистем

(локальных задач), выделенных в результате декомпозиции. В

ходе решения координирующей задачи вырабатываются сигналы

(координирующие), которые учитываются при решении локальных

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

глобальному оптимальному решению.

В о - в т о р ы х, применение координации, когда она

имеет

содержательное значение, т.е. когда выбор окончательных реше-

ний в координирующей задаче и в локальных задачах соответст-

вует выбору в реальных звеньях организационно-технической

структуры сложной системы. Здесь следует обратить внимание

на существование двух классов задач оптимизации, связанных с

реальными исходными иерархическими системами:

а) задачи выбора, в которых в постановочной

части задачи для

иерархической системы вводится единое отношение предпочте-

ния, тогда целевые функции подсистем строятся на основе де-

композиции глобальной целевой функции системы и как бы "на-

вязываются" подсистемам;

б) задачи выбора с независимо вводимыми отношениями

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

своему содержанию (а не только по форме

организации вычисли-

328

тельной процедуры) задачами выбора в иерархической структуре

с мультипредпочтением. Такие задачи можно разделить на два

подкласса:

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

2) задачи, связанные с вводом координирующих воздейст-

вий, формируемых подсистемой верхнего уровня.

Межуровневый равновесный выбор имеет место в тех слу-

чаях, когда осуществляется приведение задачи выбора в двух-

уровневой (многоуровневой) системе

к одноуровневой схеме

равновесия по Нэшу. В данном случае элементы верхних и ниж-

них уровней с точки зрения вводимых предпочтений объявляются

равноправными. Такого рода решение задач выбора называется

равновесным согласованием выбора в иерархической системе.

Рассмотрим задачи выбора в иерархической системе, свя-

занные с введением координирующих сигналов.

К о о р

д и н а ц и о н н ы м в ы б о р о м называется такой

выбор в иерархической системе, при котором подсистема верхне-

го уровня воздействует на подсистемы нижних уровней посредст-

вом координирующих сигналов, влияющих на выбор этих подсис-

тем. Для игровых постановок задач координационного выбора

подсистема верхнего уровня в указанной ситуации изменяет пра-

вила игры (в настоящее время интенсивно развиваются так назы-

ваемые иерархические игры). В случае оптимизационных поста-

новок задач координационного выбора "механизмы" выбора,

имеют различные интерпретации: "механизм штрафов", "меха-

низм цен", "механизм распределения ресурсов" и др. В рамках

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

ситуации:

1) глобальная целевая функция строится на основе компози-

ции целевых функций подсистем с учетом их относительных важ-

ностей, а центр координирует (согласует) действия подсистем на

основе учета совместной операционной области их решений (ог-

раниченность общих ресурсов, логическая зависимость решений

и др.);

2) подсистемы и центр имеют собственные интересы и соот-

ветствующие

им целевые функции, которые учитываются цен-

тром при выборе координирующих воздействий. Об этих задачах

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

тем интеграции нескольких исходных моделей (объединением их

общей координирующей схемой).

Различают следующие подходы к организации информаци-

онного обмена в процессе координации:

329

а) осуществляется реальный обмен информацией между

центром и подсистемами на каждом шаге итеративного процесса;

б) после получения и анализа информации от подсистем

центр осуществляет весь итеративный процесс самостоятельно и

вырабатывает координирующий сигнал, который сообщается

подсистемам.

П е р в ы й подход позволяет упростить координирующую

задачу по сравнению со вторым и

может быть реально связан с

ограниченными вычислительными мощностями и пропускными

способностями каналов связи (проще - передать координирую-

щий сигнал и частные решения подсистем, чем передавать и пе-

рерабатывать всю информацию о совместной операционной об-

ласти в подсистемах).

В т о р о й подход связан с более глубокими соображе-

ниями – c учетом

факторов неопределенности. Действительно, в

этом случае центр лишен возможности принимать решение по

подсистемам, поскольку он не располагает полными сведениями

об обстановке в них (эта обстановка на момент решения коорди-

нирующей задачи может быть вообще неизвестна). Центр при

этом самостоятельно ведет итеративный процесс и вырабатыва-

ет координирующий сигнал, учитывая неопределенность обста-

новки

на основе прогнозирования ее развития с использованием

методов принятия решений в неопределенной обстановке (веро-

ятностных, игровых, в условиях неизвестности). Подсистемы не

участвуют в итеративном процессе (или ограниченно привлека-

ются к нему), но принимают окончательные решения на основе

знания координирующего сигнала и реально складывающейся

обстановки.

Исторически первыми начали развиваться процедуры де-

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

цедур оптимизации. Наиболее известен здесь декомпозиционный

алгоритм Данцига-Вулфа [26, 59], разработанный для задач ли-

нейного программирования с матрицей ограничений блочной

структуры. Дальнейшее развитие этих методов осуществлялось в

направлении развития декомпозиционных процедур для нели-

нейных оптимизационных задач (алгоритм Розена [59]) и для за-

дач с целочисленными и

частично целочисленными переменны-

ми (алгоритм Бендерса [85]). Развиваются вычислительные про-

цедуры, построенные на основе совместного применения идей

декомпозиции и агрегирования.

330

Методы декомпозиции и координации, имеющие содержа-

тельный характер, т.е. связанные с проблемами управления в

реальных иерархических системах развивались в работе [62], где

была сделана попытка создания общей теории оптимизации ие-

рархических систем. Большие возможности изучения содержа-

тельных задач координации открываются в связи с исследова-

ниями Ю.Б.Гермейера [22] и Н.Н

.Моисеева [63, 80] и их учеников,

проводимыми с позиций теории игр с непротивоположными инте-

ресами. Координационный (согласованный) выбор, учитывающий

активность и собственные интересы подсистем изучался в рабо-

тах по теории активных систем В.Н.Бурковым [11]. Задачи коор-

динационного выбора в иерархических системах решались И. А.

Багриновским [6] на основе введения межуровневого согласова-

ния

по Нэшу.

Первыми, получившими широкую известность, оптимизаци-

онными алгоритмами с иерархической организацией вычисли-

тельного процесса и координацией решений подсистем на основе

введения соответствующих координирующих сигналов были де-

композиционные алгоритмы Данцига-Вулфа [26] и Корнаи-

Липтака [85]. В первом алгоритме использовалась интерпретация

вычислительного процесса как процесса координации, построен-

ного на основе модификации целевой функции

с использованием

механизма цен; во-втором - как процесса координации с модифи-

кацией пространства альтернатив, построенной на основе рас-

пределения ресурсов.

15.2. Координация с модификацией целевой функции

Алгоритм Данцига-Вулфа [26] строится на основе развития

идей симплекс-метода, точнее метода обратной матрицы (моди-

фицированный алгоритм симплекс-метода), для задач линейного

программирования с блочно-диагональной структурой матрицы

условий. В этом случае модель принятия решения (Δ, f), где

Δ = { x∈R

⏐ Ax = b, x≥0.}; f = c

x .

Иначе, если задачу линейного программирования представить в

виде:

= arg max c

x , (15.1)

x∈Δ

где