Рис. Выбор оптимального пути

• Название: Рис. Выбор оптимального пути
• Дата: 17.12.2022
• Размер: 0.71 Mb.
• Имя файла: 2 (1).doc
• Тип: Документы; #849239

Пример 1. Чтобы попасть из пункта А (остановка автобуса) в пункт В (лодочная станция) (рис. 1), человек должен пройти сначала по ас­фальтовой дороге (отрезок Ах), а затем по песчаному пляжу {отрезок хВ). Известны скорости передвижения по асфальтовой дороге и по песку. Спрашивается, в каком месте нужно свернуть с асфальтовой дороги, чтобы затратить меньше времени на весь путь.



Рис. 1. Выбор оптимального пути
Сформулированную задачу можно рассматривать как задачу принятия решения: множество альтернатив состоит из множества точек прямой ОС, т. е. из множества вещественных чисел х. Каждому решению соот­ветствует исход, или результат,— маршрут АхВ. Таким образом, имеем задачу принятия решения в условиях определенности. Каждый исход (т. е. маршрут) оценивается числом — временем передвижения по маршруту.
Пример 2. Предположим, что при разработке некоторой логической электронной схемы нас кроме функциональных требований интересуют два показателя: потребляемая схемой мощность (f₁) и время задержки распространения сигнала (f₂), причем мы хотим минимизировать оба эти показателя. Мы можем варьировать параметры (номиналы) части резистивных элементов схемы R₁, …,R_L в некоторых заданных границах. При этом каждому фиксированному набору R=(R₁, …,R_L) этих параметров соответствуют определенные значения f₁, (потребляемая мощность) и f₂ (время задержки). Таким образом, взяв за альтернативы наборы значе­ний R, а затем в качестве исходов — соответствующие им пары чисел (f₁ ,_,f₂) приходим к задаче выбора решения в условиях определенности. Изобразив все возможные пары чисел (f₁ ,_,f₂) на плоскости, получим не­которую область F, каждая точка которой представляет собой один из возможных исходов (рис. 2).



Рис. 2. Оптимизация по двум критериям
Поскольку для принятия решений в условиях определенности выбор аль­тернативы равнозначен выбору исхода, принятие решения состоит здесь в выборе конкретной точки множества F. Какую точку надо взять в каче­стве оптимальной в данном случае?
По сравнению с примером 1 это уже более трудная задача, т. к. при наличии не одного, а двух показателей, оценивающих исход, ответить на вопрос, какое решение является наилучшим, гораздо сложнее. Например, в точке А (см. рис. 2) значение показателя f₁ лучше (меньше), чем в точке В, но зато в точке В лучше значение показателя f₂. Какую из них предпочесть? В данном случае речь идет не столько о том, как найти оптимальное решение, сколько о том, что следует понимать под оптимальным решением, т. е. здесь мы сталкиваемся с трудностями не технического, а концептуального характера.
Пример 3. Пассажир, войдя в трамвай, решает, брать ли билет. Здесь исход определяется двумя об­стоятельствами: решением пассажира и фактом появления контролера. Та­ким образом, пассажир выступает в качестве лица, принимающего реше­ние, а факт появления контролера — в качестве среды. Имеются всего две альтернативы у принимающего решение и два состояния среды. Как численно оценить "полезности" исходов? Проще всего в качестве оценок взять выраженные в условных единицах денежные потери, как указано в табл. 2.
Таблица 2

Альтернатива	Состояние среды
	Контролер появится	Контролер не появится
Брать билет	15 руб.	15 руб.
Не брать билета	100 руб. + 15 руб.	0 руб.

Какое решение следует принять, если целью считать минимизацию потерь? Это пример задачи принятия решений в условиях неопределенности.

Методы решения подобных задач существенно зависят от наличия до­полнительной информации, например, о том, можно ли каждому состоя­нию среды приписать вероятность его наступления или нет. Принципи­альным также является вопрос о том, многократным или однократным является производимый выбор.
Пример 4. (дилемма заключенного). Арестованы два подозреваемых в совершении серьезного преступления. У прокурора нет полного доказа­тельства их вины, и результаты судебного разбирательства дела полно­стью зависят от стратегии поведения подозреваемых. У каждого из них есть две альтернативы — сознаться в совершении преступления или нет. Возможные исходы представлены в табл. 3 (Н- непризнание, П-признание; 1,2 — номера задержанных).
Таблица 3

1	2
	Н	П
Н	(1.1)	(10,0)
П	(0,10)	(7,7)

Таблица интерпретируется следующим образом. Если оба арестован­ных не сознаются, то им будет предъявлено обвинение в совершении относительно незначительного преступления, и оба они получат по 1 году лишения свободы. Если один сознается, а второй — нет, то первый за выдачу сообщника и помощь в расследовании дела будет полностью освобож­ден от ответственности, а второй получит полный срок — 10 лет лише­ния свободы. Если же оба сознаются, то оба понесут наказание, но за чистосердечное раскаяние срок заключения будет уменьшен до 7 лет. Какое решение следует принять каждому из заключенных, чтобы ми­нимизировать наказание?

Здесь, как мы видим, тоже есть неопределенность, но в отличие от пре­дыдущего примера, где присутствовала так называемая "природная" не­определенность, или неопределенность среды, в данном случае мы имеем неопределенность типа "контрагент". Эффективность решения в такой задаче существенно зависит от стратегии поведения второго лица, а также от информированности обоих субъектов о намерениях другой стороны.
Пример 5. Во многих случаях лицо, принимающее решение, может ука­зать лишь множество всех тех пар исходов, для которых первый исход в паре предпочтительнее второго. При этом какие-либо численные оценки исходов в принципе отсутствуют. Приведем конкретный пример. Молодой ученый выбирает место своей будущей работы, исходя из следующе­го множества альтернатив:

1. 
   x₁: ассистент в очень известном университете с окладом 250 у. е.
   
2. 
   х₂: доцент в электротехническом институте с окладом 350 у. е.
   
3. 
   х₃: профессор в малоизвестном периферийном институте с окладом 450 у. е.
   

Легко представить себе ситуацию, когда ученый предпочтет x₁, по срав­нению с x₂, рассудив, что престиж известного университета и контакты с ведущими специалистами в данной области науки стоят 100 у. е. разницы в окладе. Данное предпочтение можно обозначить (x₁, х₂) или x₁ > х₂ (x₁ лучше х₂). Точно так же можно предположить, что х₂ > х₃. И в то же вре­мя, сравнивая x₁ и х₃, можно понять и выбор х₃ по сравнению с x₁, (слишком велика разница в окладе). Таким образом, система предпочте­ний задается множеством пар: (x₁, х₂), (x₂, х₃), (x₃, х₁). Следовательно, здесь нет самой предпочтительной альтернативы. Какими принципами следует руководствоваться для принятия решений в подобных ситуациях?
Пример 6. Большой класс практических задач составляют трудно фор­мализуемые задачи принятия решений, не имеющие адекватного тради­ционного математического описания.

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

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

Характер­ным примером таких правил могут служить выражения типа "ЕСЛИ (условие), ТО (действие)", например:
ЕСЛИ х любит тепло, ТО х понравится в Тайланде.
Указанный формат записи знаний характерен для важнейшего класса экспертных систем — продукционных экспертных систем.
Пример 7. Существуют проблемы группового выбора решений, когда основная задача состоит в том, чтобы указать "справедливые" принципы учета индивидуальных выборов, приводящие к разумному общественному (или групповому) решению. В качестве содержательного примера можно привести заседание военного совета, когда каждый участ­ник заседания высказывает свое мнение относительно плана проведения будущей операции, а в конечном итоге должен быть выбран один, опти­мальный вариант. Как это сделать? Какой результат выбора считать "хорошим", каким свойством он должен обладать? Здесь у нас, как и в примере 2, в первую очередь возникают концептуальные трудности, т. е. сначала нужно определить, какими показателями должен обладать разум­ный результат согласований индивидуальных предпочтений.
Простая модель задачи группового выбора формулируется следую­щим образом. Пусть множество вариантов решений X конечно: Х = {x₁, x₂, ..., x_m}. Имеется группа из n членов, принимающих (выби­рающих) решение. Каждый член группы с номером i = 1, ..., n имеет свою систему предпочтений на множестве X, задаваемую с помощью бинарно­го отношения R_i С X*X,

R_i={(x_j,x_k),…,(x_p,x_m)}
Здесь R_i — множество упорядоченных пар элементов из X, причем вклю­чение некоторой пары (х_s, х_t) в множество R_i, означает, что с позиций i-го

члена группы вариант х_s, предпочтительнее варианта x_t: х_s > х_t Требуется

по заданной системе R₁, …, R_n индивидуальных предпочтений построить групповую (коллективную) систему предпочтений R=f(R₁, …, R_n), где f— некоторая функция, реализующая принятый принцип согласования индивидуальных предпочтений.
Казалось бы, достаточно использовать логически очевидное правило большинства (что обычно и происходит на практике при коллективном решении проблем). Однако есть определен­ные трудности, связанные с естественными принципами согласования, типа правила большинства или оценивания по среднему баллу. В частно­сти, хорошо известны парадоксы голосования, которые продемонст­рируем на следующих задачах.
Принятие законопроекта в парламенте. Пусть три парламентские группы, обладающие приблизительно одинаковым числом голосов, обсуждают три варианта некоторого законопроекта a, b, c с целью утверждения од­ного "наилучшего" варианта. Пусть системы предпочтений групп имеют соответственно следующий вид:

1. 
   a>b>c, R₁={(a,b),(b,c),(a,c)}.
   
2. 
   b>c>a, R₂={(b,c),(c,a),(b,a)}.
   
3. 
   c>a>b, R₃={(c,a),(a,b),(c,b)}.
   

Решено действовать по правилу простого большинства. Тогда в резуль­тате голосования получим а>b, потому что пара (а,b) присутствует в R₁ и в R₃, а пара (b,a) — только в R₂. Аналогично устанавливаем, что b>c и c>a, т. е. а>b>c>a.
Получаем "порочный круг" и потерю свойства транзитивности в группо­вом предпочтении. По результатам данного голосования по-прежнему нельзя выбрать наилучший законопроект. Более того, очевидно, что при умелом ведении заседания парламента председатель может обеспечить утверждение большинством голосов любого из трех вариантов. Действи­тельно, председатель может предложить обсудить сначала какие-то два варианта, проголосовать и худший отсеять. Далее для обсуждения снова останутся два варианта — оставленный при первом рассмотрении и еще не рассматривавшийся. Тогда, очевидно, если на первое обсуждение вы­носятся варианты а, b, то оказывается а>b и вариант b отбрасывается. Далее конкурируют а и с. В результате по принципу большинства имеем c>a и в качестве окончательного варианта парламент выбирает вариант c. Если же, напротив, на первое обсуждение вынесем варианты b и с, то в итоге наилучшим окажется а. Точно так же можно обеспечить выбор b в качестве наилучшего. Невинное на первый взгляд предложение о поряд­ке рассмотрения оказывает решающее влияние на результат!
Выборы президента (парадокс многоступенчатого голосования). Допус­тим, что на выборах президента некоторой компании (или государства) борются две партии, стремящиеся сделать победителем своего предста­вителя. Далее показано, что при умелом ведении дела меньшинство мо­жет навязать свое мнение большинству, хотя голосование всегда будет проводиться по правилу большинства. Чтобы понять идею, достаточно изучить рис. 3.

Из рис. 3 видно, что группа, владеющая восемью голосами, в итоге на­вязала свое мнение группе из девятнадцати выборщиков. Все дело, ко­нечно, заключается в умелом группировании сил. Но с помощью совре­менных избирательных технологий это можно реализовать, и это делается повсеместно с помощью целенаправленного вложения средств, организации агитационных поездок в нужные регионы и т. д. Как пока­зал анализ, несколько президентов США в указанном смысле действи­тельно представляли меньшинство в результате реализации системы многоуровневого голосования. При этом чем больше ступеней, тем ярче проявляется указанный эффект.


Рис. 3. Система многоступенчатого голосования

И, наконец, последний пример.

Задача распределения ресурсов. Пусть некоторый ресурс (например, де­нежный) распределен между n членами некоторого сообщества. При этом состоянием сообщества (системы) будем называть вектор (a₁, a₂,..., а_n), где a_i,— объем ресурса, которым владеет i-ый член сообщества. Общий объ­ем ресурса постоянен и равен:



Рассмотрим другое состояние той же системы b = (b₁, b₂,..., b_n). Очевидно, состояние b не хуже состояния а для i-го субъекта, если b_i>=а_i,. Будем те­перь производить перераспределение ресурсов на основе очень сильного большинства: переход системы из некоторого состояния а в состояние b разрешен, если новое состояние будет не хуже старого для всех членов сообщества кроме, может быть, одного (тотально-мажоритарное прави­ло). Последовательность состояний a₁, а₂, ..., аn будем называть тотально-мажоритарным путем из а₁ в а_m если каждый промежуточный пере­ход из a_i в а_i+1 был осуществлен на основе тотально-мажоритарного правила. Достаточно неожиданным является утверждение, что тотально-мажоритарный путь может связывать любые два состояния системы.

Таким образом, опираясь на мнение "всего общества" можно производить любые перераспределения ресурса, в том числе и представленные на рис. В.4.



Рис. 4. Распределение ресурса по принципу большинства
Приведенные примеры не исчерпывают всех типов задач теории приня­тия решений.