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

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

311

пространстве критериев) утопической точки часто используются

для нормализации соответствующих критериальных функций.

Способы построения множества Парето.

Приведенные свойства множества Парето могут быть ис-

пользованы для построения и последующего исследования дан-

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

три таких способа.

1. Используется 4-е свойство множества Парето.

Тогда последовательно перебирая значения α

, i∈G, в задаче

= arg Max Σ α

(x) , (14.8)

x∈Δ i∈G

можно получать различные точки множества Парето. Вместе с

тем число таких точек может быть бесконечно, поэтому свойство

4 имеет скорее методическое значение, заключающееся в том,

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

(14.7).

2. Алгоритм Джу-Зелени [15, 73].

Для задач линейного программирования был разработан

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

шений. В соответствии с этим алгоритмом

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

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

- формируются недоминируемые грани как линейная комбина-

ция крайних точек;

- формируется множество Парето, как объединение недоми-

нируемых граней.

∇f

2 7

∇f

1 9

Рис.14.2.

312

Здесь недоминируемые крайние точки множества допусти-

мых решений это точки 4,5,6,7, соответственно множество Парето

представляет собой объединение граней (4,5), (5,6), (6,7).

3. Выделение конечного подмножества недоминируемых

решений.

В задачах принятия решений довольно часто встречаются

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

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

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

следующего неформального анализа. Выделение такого множе-

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

чений целевых функций в области Парето, и последующего

ис-

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

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

ным критерием оптимальности в следующем виде:

(x) → max, i=1,...,s,

A x = b,

x ≥ 0.

Для нахождения диапазонов изменения целевых функций

решаем s оптимизационных задач вида

= arg Max f

(x), i=1,...,s ,

x∈Δ

где Δ = { x∈R

⎪ A x = b, x≥0 }.

Пусть s = 2. Тогда диапазон изменения 2-ой целевой функ-

ции в области Парето не превышает значения δf

δf

= f

- f

), здесь f

= f

Зададим число N, характеризующее количество недомини-

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

Множество значений 2-ой целевой функции, которые она прини-

мает в области Парето ϕ

, j=1,...,N, можно задать как

= f

- (j-1) (δf

/ (N-1)

), j = 1,....,N.

Теперь, выбирая первую целевую функцию в качестве ве-

дущей (в качестве функции, по которой ищется оптимум), будем

решать N задач линейного программирования вида

(x) → Max

(x) ≥ ϕ

, j=1,....,N,

A x = b, x≥0.

313

В результате решения N таких задач получим конечное

множество x

решений из области Парето.

В критериальном пространстве данный метод можно пояс-

нить следующим рисунком.

- - - - - - - - - - - - - - - - - - -

- - - - - - - - - - - - - - - - - - - - -

- - - - - - - - - - - - - - - - - - - - - -

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

) - - - - - - - - - - - - - - - - - - - - - -

Рис.14.3.

Можно обобщить данную методику на случай s целевых

функций. Выберем некоторую r-ю целевую функцию в качестве

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

превышает значения δf

δf

= f

- f

), i=1,...,s; i≠r,

здесь f

= f

), где x

- решение исходной задачи;

= arg Max f

(x),

x∈Δ

Множество значений i-ой целевой функции ϕ

, j=1,...,N

ко-

торые она принимает в диапазоне изменения δf

можно опреде-

лить как

= f

- j (δf

/ N

), i=1,...,s; j=1,....,N

Теперь можно решать задачи линейного программирования вида

(x) → Max

(x) ≥ ϕ

, i=1,...,s; j=1,....,N

, i≠r,

A x = b,

x ≥ 0.

314

В результате решения N

таких задач, где N

= Σ N

, i=1,..

..., s; i ≠ r, получим множество решений { x

}, "равномерно" рас-

пределенных в области Парето.

14.3. Принятие решений на основе операторных решающих

правил

При использовании операторного решающего правила про-

цесс принятия решений можно характеризовать схемой (14.2):

ЛПР

S ⎯→ А ⎯→ F ⎯→ f

рез

⎯→ x

В этом случае исходная ситуация принятия решения S = (

Δ,

(x), i=1,...,s}) подвергается анализу лицом, принимающим реше-

ние (ЛПР), во взаимодействии с которым формируется аксиома А

(принцип оптимально\сти, схема компромисса) о том, что следует

понимать под оптимальным решением в ситуации S. Формаль-

ным выражением аксиомы А является решающее правило F, ко-

торый представляет собой оператор, позволяющий сформиро-

вать результирующую целевую функцию f

рез

. Тогда исходная не-

определенная ситуация преобразуется в ситуацию (

Δ, f

рез

), в ко-

торой оптимальное решение x

может быть найдено на основе

традиционных методов оптимизации.

Используемая аксиома (принцип оптимальности) сущест-

венно зависит от информированности ЛПР об относительной

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

ственно или в форме отношений порядка. Здесь можно различать

три ситуации:

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

вует;

2) имеется информация, заданная

количественно, о возмож-

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

за счет значительного улучшения менее важных;

3) имеется информация о важности критериев, заданная в

форме отношения строгого порядка.

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

ситуациях.

315

14.3.1. Решающие правила в задачах бесприоритетной оп-

тимизации

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

мающим решение (ЛПР), вводится некоторая система аксиом А о

том, что следует понимать под оптимальным решением. На осно-

ве системы аксиом А формируется решающее правило F, позво-

ляющее найти в такой "доопределенной" задаче оптимальное

решение x

Рассмотрим конкретные примеры задания аксиом и соот-

ветствующих им решающих правил.

Аксиома 1. "Оптимальное решение соответствует макси-

муму минимальных значений показателей".

Такое решение может быть найдено на основе следующего

решающего правила

= arg Max Min f

(x), (14.9)

x∈Δ i∈G

где Δ - множество оцениваемых альтернатив; G - множество ин-

дексов показателей качества решения; G = {1,..., s}.

В случае, если

Δ = {x

,...,x

} конечное (например, это конеч-

ное множество недоминируемых альтернатив, найдено на основе

процедуры, изложенной в 14.2), можно построить матрицу F зна-

чений показателей из G при различных решениях из

. . . . . f

F = . . . . . . . . . . . . . .

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

. . . . . f

где f

= f

Теперь, используя способы принятия решений в условиях

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

но находить гарантирующие решения (стратегии) ЛПР (в такой

игре ЛПР выступает в качестве второго игрока),

= arg Max Min f

j i

решения, соответствующие определенной доле оптимизма g,

= arg Max(g Max f

) + (1-g) Min f

))

j i i

316

решения, минимизирующие максимальный риск z

)

= arg Min Max z

j i

Отметим, что последние два способа (решающих правила)

нахождения оптимального в целом решения соответствуют само-

стоятельным аксиомам.

Аксиома 2. "Оптимальное решение соответствует миниму-

му суммы относительных отклонений от оптимальных решений по

частным показателям".

Относительное отклонение d

(x) значения i-го показателя

для решения x от оптимального его значения можно вычислить

как

(x)

(x) = ⎯⎯⎯⎯ , (14.10)

)

где

- решение, оптимальное по i-му показателю;

(x) - абсолютное значение отклонения i-го показателя от оп-

тимального значения δ

(x) = f

) - f

(x).

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

= arg Min Σ d

(x), (14.11)

x∈Δ i∈G

Аксиома 3. "Оптимальное решение минимизирует общую

верхнюю грань относительных отклонений от оптимальных реше-

ний по частным показателям".

Пусть w - общая верхняя грань относительных отклонений

от оптимальных решений по частным показателям. Тогда d

(x)≤w,

i∈G.

Оптимальное в целом решение x

находится в результате

решения задачи

= arg Min { w ⎪ d

(x)≤w, i∈G }, (14.12)

x∈Δ

Аксиома 4. "Оптимальное решение cоответствует макси-

мальному приближению к идеальной точке".

317

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

наты f

), i∈G. Тогда квадрат расстояния до идеальной точки в

евклидовой метрике определяется в виде

(x) = Σ (f

) - f

(x))

i∈G

В этом случае оптимальное в целом решение ищется как

= arg Min r

(x) = arg Min Σ (f

) - f

(x))

, (14.13)

x∈Δ x∈Δ i∈G

Аксиома 5. "Оптимальное решение cоответствует "равно-

ценному" снижению всех показателей".

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

вершины многогранника условий, соответствующие оптимальным

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

Направляющий вектор данной гиперплоскости соответствует ре-

зультирующей целевой функцией.

Будем искать f

рез

в виде

рез

(x) = Σ α

(x)

i∈G

Полагаем, что f

(x), i∈G - нормализованные целевые функ-

ции. Тогда, в условиях того, что f

рез

(x) проходит через крайние

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

показателям решений, α

можно найти из системы уравнений

Σ α

) = c

. j∈G.

i∈G

Здесь f

) - значение i-го показателя в вершине многогранника,

оптимальной по j - му критерию. Значение (с) выбирается таким

образом, чтобы выполнялись условия нормировки α

≥0, Σ α

= 1.

В условиях отсутствия информации об относительной важ-

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

и, соответственно, получаются различные решения. В силу наи-

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

лять множество решений, соответствующих различным решаю-

щим правилам, и вычислять оценки этих решений, с тем, чтобы

расширить информационную базу ЛПР для принятия решения,

наиболее полно соответствующего реальной ситуации и его

(ЛПР) предпочтениям.

318

14.3.2. Учет относительной важности критериев

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

вует воэможность компенсации ухудшения значений более важ-

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

Такие ситуации часто называют ситуациями с "гибким" заданием

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

может задаваться и учитываться в двух формах: 1) в виде коэф-

фициентов относительной важности; 2) в виде

компонент вектора

приоритетов.

Рассмотрим особенности задания этих форм относитель-

ной важности критериев.

1).

Коэффициенты относительной важности задаются в

следующем виде.

α = (α

, α

,..., α

); причем α

≥0, i=1,...,s; Σ α

= 1

. (14.14)

i∈G

Здесь α

характеризует относительную важность i-го критерия на

множестве G. Таким образом при задании коэффициентов отно-

сительной важности необходимо оценивать относительную важ-

ность i-го показателя на множестве всех остальных, что для экс-

перта представляется достаточно трудоемкой процедурой. С дру-

гой стороны, задание α

, i∈G, позволяет строить решающее пра-

вило в форме

рез

(x) = Σ α

(x)

i∈G

что является формой неявного задания множества недоминируе-

мых решений (области Парето) (см. 14.7), а, следовательно, ре-

шение, найденное на основе такой f

рез

(x), будет заведомо недо-

минируемым.

2).

Компоненты вектора приоритетов упорядочены по

важности и задаются как

λ =

║ λ

, λ

,..., λ

║; здесь λ

∈ [1, ∞), j = 1,...,s. (14.15)

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

телей компоненты λ

характеризуют количество единиц j показа-

теля, позволяющее скомпенсировать снижение (j-1)-го показателя

на одну единицу (при этом λ

=1). Такая информация может быть

получена в результате экспертного опроса. С другой стороны ко-

319

эффициенты относительной важности α

по известным λ

могут

быть найдены из системы уравнений:

∑

= 1,

= λ

, (14.16)

...........…..

s-1

= λ

или в соответствии с формулой

= ⎯⎯⎯ , (14.17)

Σ λ

i∈G

где λ

коэффициент приоритета i-го показателя по отношению к

1-му показателю

= ( П λ

)

-1

, (14.18)

j=1

здесь λ

= 1.

В этой связи целесообразно первоначально формировать

ряд приоритетов (14.15), а затем с использованием формул

(14.16) или (14.17) вычислять значения коэффициентов относи-

тельной важности с тем, чтобы определить f

рез

(x) и найти опти-

мальное решение x

в результате решения задачи (14.7).

14.3.3. Оптимизация по последовательно применяемым

критериям

Данные ситуации характеризуется наибольшей определен-

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

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

гда можно задать ряд предпочтения критериев f = (f

,...,f

), в ко-

тором каждый предшествующий критерий считается несравненно

более важным, чем последующий (лексикографическое упорядо-

чение критериев); такие ситуации называют "жестким заданием

приоритетов". Вместе с тем довольно часто, исходя из способов

расчета целевых функций, вычислительных погрешностей и с

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

320

ние от оптимальных значений показателей (можно назначить ус-

тупку).

В обоих случаях поиск оптимального решения осуществля-

ется на основе последовательного сужения множества допусти-

мых альтернатив:

∈ Δ

⊆ Δ

s-1

⊆ ... ⊆ Δ

⊆ Δ

⊆ Δ. (14.19)

Здесь x

- оптимальное решение; Δ

- сужение множества

допустимых альтернатив, произведенное на основе i-го показате-

ля. Здесь

= { x ∈ Δ ⎪ f

(x) ≥ max

(x) - ε

x∈Δ

= { x ∈ Δ

⎪ f

(x) ≥ max

(x) - ε

x∈Δ

.................................…...…………… (14.20)

= { x ∈ Δ

s-1

⎪ f

(x)

≥ max f

(x) - ε

x∈Δ

s-1

где ε

, i=1,...,s - уступка по i-му показателю. Если ε

= 0, то послед-

няя схема соответствует оптимизации по лексикографически упо-

рядоченным критериям.

14.4. Принятие решений на основе лингвистического

решающего правила

Анализ процессов принятия решений при управлении воен-

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

анализируемая информация о целесообразном в конкретных ус-

ловиях решении представлена в большинстве случаев в виде по-

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

фессионально-ориентированных языках. Одним из конструктив-

ных способов принятия решения в этих

условиях является спо-

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

лица, принимающего решение. Схему принятия решения (см.

(14.3)) в этом случае можно представить в виде

ЛПР ЛПР

S ⎯→ {M

, i ∈ G} ⎯→ L ⎯→ C(L) ⎯→ M

⎯→ x

, (14.21)

1 2 3 4 5