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

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

351

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

1). По каким причинам необходимо координировать решения в

сложной иерархической системе ?

2). Какими способами и за счет чего может осуществляться ко-

ординация решений ?

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

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

4) В чем состоит смысл координирующих сигналов в алгорит-

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

5). Кто

является инициатором обмена в алгоритме Данцига-

Вулфа и какую информацию он сообщает ?

6). При каких условиях заканчивается итерационный процесс

координации в соответствии с алгоритмом Данцига-Вулфа ?

7). Каким образом формируется окончательное решение в ал-

горитме Данцига-Вулфа ?

8). Кто является инициатором обмена в алгоритме Корнаи-

Липтака и какую информацию он сообщает ?

9). При

каких условиях заканчивается итерационный процесс

координации в соответствии с алгоритмом Корнаи-Липтака ?

10). Какие задачи решает Центр и подсистемы в координаци-

онном алгоритме Корнаи-Липтака ?

11). В чем заключается практический смысл релаксации в за-

дачах координационного планирования ?

12). По каким причинам необходимо координировать решения

в АСУ КА ?

13). Каким образом можно формализовать

конфликты при

управлении операциями проводимыми КА ?

14). В чем состоит специфика решения координирующей зада-

чи в задачах планирования операций в АСУ КА ?

15). Какие отличия в решении задач подсистем в алгоритме

координационного планирования операций КА по сравнению с

алгоритмом Данцига-Вулфа ?

352

16. ПРИМЕРЫ ЗАДАЧ ПРИНЯТИЯ РЕШЕНИЙ В СЛОЖНЫХ

СИСТЕМАХ

16.1. Принятие решений в условиях неопределенного

воздействия внешней среды

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

ская модель ситуации принятия решения (1.2) в составе мно-

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

ет множество Ω, описывающее состояния среды, т.е.

Δ = Δ

× Δ

× ⋅ ⋅ ⋅ × Δ

× Ω .

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

но и целевая функция f: Δ

× Δ

× ⋅ ⋅ ⋅ × Δ

× Ω → R

, зависят от

состояний среды

(Δ(ω), f(ω)), ω∈Ω .

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

этих альтернатив зависят от степени знания среды, и, если со-

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

решений Δ(ω) и целевая функция f(ω) неопределены. В этих

условиях важно выяснить, что известно о

среде. И в зависимости

от этого строить ту или иную модель принятия решения. Разли-

чают три вида среды с неопределенностью (см.13.1): 1)

стохас-

тическая

среда - это среда, состояния которой повторяются в

массовых явлениях (статистически устойчивы), следовательно,

частоту появления состояний можно описывать количественно

(задавать вероятность состояний); 2)

целенаправленная среда -

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

состояния, и в зависимости от того, каковы эти цели можно стро-

ить рациональное поведение; 3)

неизвестная среда - это среда

353

относительно которой отсутствуют объективные данные о воз-

можных состояниях или целях, которые она преследует, а имеют-

ся лишь предположения лица, принимающего решение (или экс-

пертов).

Рассмотрим примеры задач принятия решений.

16.1.1. Стохастическая среда.

Задача 16.1.1.

Результаты анализа состояния космического

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

вать для их последующего анализа в Главный центр. При этом

может использоваться четыре независимых направления связи

, x

, эффективность использования которых зависит от

времени суток и состояния ионосферы. Анализ факторов,

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

6 различных состояний среды w

, причем много-

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

состояний задается как p = (0.05 0.1 0.35 0.1 0.15 0.25). Необхо-

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

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

среды задается таблицей

300 700 400 500 800 600

400 600 500 600 900 400

500 700 600 700 300 700

800 600 300 500 400 700

Анализ ситуации показывает, что среда не влияет на

имеющиеся альтернативы выбора, а влияет на оценку качества

альтернатив. Т.е. имеет место ситуация (Δ={x

}, f(x,ω)),

ω∈Ω = {ω

,ω

}, при которой f(x,ω), является случайной

функцией. Тогда можно произвести детерминизацию задачи и

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

данию целевой функции. В этом случае (см.(13.2))

= arg max f

(x), f

(x) = М f(x, ω) .

x∈Δ

Или

) =

∑

f(x

, ω

) p

, i = 1,...,4.

354

Значения f(x

,ω

), i=1,...,4, j=1,...,6 заданы в таблице. Произ-

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

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

(x) = (545,

550, 595, 490), откуда оптимальное решение x

= x

, т.к. f

) =

595.

16.1.2. Целенаправленная среда.

Задача 16.1.2.

Для анализа состояния сил и средств противника в районе

ведения боевых действий необходимо осуществлять сбор ин-

формации и передачу формализованных сообщений в Центр, при

этом может использоваться четыре независимых направления

связи А

,А

. Противник обладает аппаратурой и возможно-

стями создания пяти видов помех В

,В

, В

. Качество пере-

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

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

0.3 0.7 0.4 0.5 0.8

0.4 0.6 0.5 0.6 0.9

0.5 0.7 0.6 0.7 0.9

0.8 0.6 0.8 0.5 0.4

Необходимо найти рациональный вариант передачи сооб-

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

Анализ задачи показывает, что неизвестен вариант созда-

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

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

меньшим, В этих условиях ситуация может быть формально

представлена в виде матричной игры с платежной

матрицей F.

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

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

(см.13.3.2). Это вариант, на котором достигается нижняя цена иг-

ры (см.(13.14))

= arg max F

(-)

= arg max min f

i i j

В рассматриваемой задаче F

(-)

= (0.3 0.4 0.5 0.4), следова-

тельно, гарантирующая стратегия – третья i

=3, а нижняя цена

игры - гарантированное качество передачи информации, F

(-)

= 0.5.

355

В тоже время верхняя цена игры, характеризующая макси-

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

нальном выборе вида помех противником (см.(13.15)), равна

(+)

= arg min max f

= min {0.8 0.7 0.8 0.7 0.9} = 0.7.

i j

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

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

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

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

ная комбинация, в соответствии с основной теоремой теории игр

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

тегией p

Найдем такую смешанную стратегию, для чего вначале

произведем преобразование платежной матрицы (умножим ее

элементы на 10 и вычтем из результата 3). Анализируя стратегии

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

тегии доминируются третьей. Тогда

2 4 3 4 6

F =

5 3 5 2 1

Анализируя стратегии второго игрока, можно сделать вы-

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

гия доминируется четвертой. Тогда

2 4 6

F =

5 2 1

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

нет.

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

на основе решения задачи линейного программирования сле-

дующего вида

L = x

+ x

→ min

2х

+ 5х

≥ 1,

4х

+ 2х

≥ 1,

6х

+ 1х

≥ 1,

≥ 0, i = 1,2.

356

Решим данную задачу графо-аналитическим способом.

0.3

0.1

0 0.1 0.3 х

∇L

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

L = 0.3125; x

= 0.1875; x

= 0.125. Тогда С = 3.2; p = (0.6 0.4).

Решим данную задачу с использованием итерационного ал-

горитма Брауна-Роббинсон (см. 13.3.3), для чего проделаем 10

итераций.

2 4 6

F =

5 2 1

к i Z

j Z

1 1

4 6 1 2

2.0 5.0 3.5

2 2 7

7 2 6

3.0 3.5 3.3

3 2 12

8 2

9 2.7 3.3 3.0

4 1 14

14 2

11 3.0 3.5 3.3

5 1 16

20 2

13 3.2 3.6 3.4

6 1

20 26 1

18 3.0 3.3 3.2

7 1

24 32 1 22

2.9 3.3 3.1

8 2

26 33 1 24

3.1 3.5 3.3

9 2 30

34 2 28

3.1 3.3 3.2

10 2 35

35 2 32

3.0 3.2 3.1

357

Анализируя полученные результаты, делаем заключение,

что цена игры С=3.1; смешанные стратегии игроков p = (0.5 0.5);

q = (0.4 0.6). Данные результаты отличаются от предельных зна-

чений, полученных на основе линейного программирования, что

объясняется небольшим количеством проведенных итераций.

После 100 итерац\ий, проведенных по методу Брауна-Роббинсон

получим, что цена игры С = 3.2; смешанные стратегии игроков

p = (0.6 0.4); q = (0.4 0.6), что полностью соответствует результа

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

мирования.

Произведем анализ полученных результатов в терминах

исходной постановки задачи:

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

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

ношении 0.6 и 0.4.

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

вертый виды помех в соотношении 0.4 и 0.6.

- качество передачи сообщений определяется

ценой игры и

составляет 0.62 (для вычисления цены исходной игры необходи-

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

3 и разделить на 10).

16.1.3. Неизвестная среда.

Задача 16.1.3.

Ведутся боевые действия в горах. Необхо-

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

имеющую важное тактическое значение. Погодные условия неус-

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

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

и средства. Проведенный анализ позволил выявить 4 варианта,

которые могут привести к успеху при

соответствующем состоянии

погодных условий R

, i = 1,..,5, и различаются привлекаемым со-

ставом сил и средств. Матрица F характеризует эффективность

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

боя и различных погодных условиях.

0.9 0.5 0.3 0.2 0.2

F = x

0.3 0.6 0.9 0.7 0.3

0.4 0.8 0.5 0.7 0.6

0.5 0.4 0.7 0.6 0.6

358

Если предполагать, что состояния среды равновероятны,

то исходная ситуация принятия решения в условиях неизвестнсти

сводится к принятию решений в стохастической среде. Тогда ис-

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

ское ожидание эффективности решения боевой задачи, и в этих

условиях наиболее предпочтителен вариант 3 (математическое

ожидание ээфективности операции 0.6).

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

будут наиболее

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

Вальда позволяет выделить две стратегии (3 и 4), на которых

достигается гарантированное значение эфективности выполне-

ния боевой задачи (максимин) равное 0.4.

По критерию максимального оптимизма наиболее предпоч-

тительны стратегии 1 и 2; значение функции выигрыша равно

0.9.

По критерию Гурвица стратегия 3 оптимальна при значени-

ях меры оптимизма

g в пределах 0.0 - 0.5; стратегия 2 оптималь-

на в пределах 0.5 -1.0 ( в точке g = 1.0 стратегии 1 и 2 равноцен-

ны). Стратегия 4 по данному критерию доминируется стратегией

Для анализа стратегий по критерию Сэвиджа построим

матрицу риска Z. Элементы данной матрицы получаются из эле-

ментов платежной матрицы F путем вычитания значения элемен-

та f

каждого j–го столбца из значения, которое является макси-

мальным для данного столбца (см. 13.4.1).

0.0 0.3 0.6 0.5 0.4

Z = x

0.6 0.2 0.0 0.0 0.3

0.5 0.0 0.4 0.0 0.0

0.4 0.4 0.2 0.1 0.0

По критерию Сэвиджа оптимальной является 4-ый вариант

проведения боя, при этом максимальный риск составляет 0.4; для

стратегии 3 максимальный риск 0.5; для 1-ой и 2-ой стратегий 0.6.

Анализ результатов проведенного исследования позволяет

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

дачи. Это обусловлено тем, что

- данный вариант наиболее предпочтителен при равных веро-

ятностях состояний среды (

оценка математического ожидания

эффективности 0.6);

359

- соответствующая стратегия является гарантирующей (значе-

ние эффективности решения боевой задачи 0.4 );

- по критерию Гурвица данная стратегия доминирует другие в

диапазоне пессимистического ожидания благоприятного состоя-

ния погоды g=0,...,0.5 (особый оптимизм при анализе возможных

вариантов боевых действий не уместен);

- по критерию Сэвиджа 3-я стратегия уступает 4-ой (величина

разности критериальных функций равна 0.1), но при

трех вариан-

тах состояния погодных условий (более, чем в 50%) использова-

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

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

способа ведения боевых действий. Окончательное решение при-

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

16.2. Принятие решений в условиях критериальной

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

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

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

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

торым должно удовлетворять решение. Каждое требование опи-

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

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

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

мального

в некотором смысле решения на основе нескольких це-

левых функций. С точки зрения традиционной математики (мате-

матических методов оптимизации) такие задачи являются некор-

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

ния некоторого решающего правила, формально представляюще-

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

результирующую целевую функцию, либо некоторый алгоритм,

позволяющий

выделить оптимальное решение. Естественным

требованием для всех таких решающих правил является требо-

вание выделения на их основе недоминируемых решений (реше-

ний, лежащих заведомо в области Парето).

Итак, традиционная для принятия решений схема (концеп-

туальная модель, формальная модель, алгоритмическая модель,

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

цедурами выбора решающего правила, которые

проводятся на

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

360

и несущим за него ответственность. Акт выбора решающего пра-

вила обычно существенно неформальный, поэтому по результа-

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

ной оптимизации может возникнуть необходимость некоторого

изменения (модификации) решающего правила.

Рассмотрим следующую задачу.

Задача 16.2.1. Для оперативного восполнения орбитальной

группировки разведывательных КА необходимо в кратчайшие

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

туры. Основу аппаратуры составляют комплектующие изделия

двух типов А

и А

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

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

мальных объемах в рамках ограничений имеющихся на предпри-

ятии ресурсов В

, В

. При этом технические возможности

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

более

400 единиц, а комплектующих А

более 300 единиц. С другой сто-

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

нее 80 и 40 единиц соответственно не имеет смысла.

Количество ресурсов В

, В

, которые могут быть выде-

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

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

тующих изделий А

, А

представлены как

= 1760 4 2

= 1080 2 2

= 1320 1 4

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

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

Решение (план выпуска) в такой задаче можно описать век-

тром x = (x

), где x

- объем выпуска комплектующих первого

типа; x

- объем выпуска комплектующих второго типа. Тогда

80 ≤ x

≤ 400; 40 ≤ x

≤ 300. С учетом потребностей выпуска про-

дукции в ресурсах ограничения можно представить в виде

+ 2x

≤ 1760, 2x

+ x

≤ 880,

+ 2x

≤ 1060, или x

+ x

≤ 540,

+ 4x

≤ 1320, x

+ 4x

≤ 1320.

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

функции вида