Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму

<

010214 0202 1 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритмуПусть x* – некоторое парето-оптимальное решение и f (x*)– соответствующий ему парето-оптимальный вектор. Если для некоторого решения 010214 0202 2 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму , отличного от x*, оказывается выполненным неравенство 010214 0202 3 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму, то обязательно должен найтись хотя бы один номер j , при котором верно неравенство 010214 0202 4 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму. На основании этого можно сделать следующее заключение: парето-оптимальное решение – это такое допустимое решение, которое не может быть улучшено (увеличено) ни по одному из имеющихся критериев без ухудшения (уменьшения) по какому-то хотя бы одному другому критерию. Иначе говоря, предпочитая одному парето-оптимальному решению другое парето-оптимальное решение, ЛПР вынуждено идти на определенный компромисс, соглашаясь на некоторую потерю хотя бы по одному критерию (получая, разумеется, определенный выигрыш, по крайней мере, по какому-то другому критерию). По этой причине множество Парето нередко называют множеством компромиссов.

В зависимости от структуры множества X и вида векторного критерия f множество парето-оптимальных решений может • оказать пустым (не содержать ни одного элемента);

• быть одноэлементным множеством;

• состоять из некоторого конечного числа решений;

• содержать бесконечное число возможных решений;

• совпадать с множеством возможных решений X .

Вектор f (x*)при парето-оптимальном решении x* называют парето-оптимальным вектором, а множество всех таких векторов – множеством парето-оптимальных векторов (парето-оптимальных оценок). Для этого множества используют обозначение PY () . Таким образом, 010214 0202 5 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму

 

 

25. Принятие решений в условиях риска: особенности постановки задачи и критерий выбора в условиях риска.

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

Каждая выбранная стратегия управления в условиях риска связана с множеством возможных исходов, причём каждый исход имеет определённую вероятность появления, известную заранее человеку, принимающему решение.

При оптимизации решения в подобной ситуации стохастическую ЗПР сводят к детерминированной. Широко используют при этом следующие два принципа: искусственное сведение к детерминированной схеме и оптимизация в среднем.

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

в тех случаях, когда диапазон возможных значений случайных величин сравнительно мал. В тех случаях, когда показатель эффективности управления линейно зависит от случайных параметров, этот приём приводит к тому же результату, что и «оптимизация в среднем».
Приём «оптимизация в среднем» заключается в переходе от исходного показателя эффективности Q, являющегося случайной величиной:

Q=Q(X, A, y1,y2,…,yq),

где: X-вектор управления;

A-массив детерминированных факторов;

y1,y2,…,yq-конкретные реализации случайных фиксированных факторовY1,Y2,…,Yq к его осреднённой, статической характеристике, например, к его математическому ожиданию M[Q]:

 


010214 0202 6 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму

 

B-массив известных статических характеристик случайных величин Y1,Y2,…,Yq;

f(y1,y2,…,yq)-закон распределения вероятностей случайных величин Y1,Y2,…,Yq.

При оптимизации в среднем по критерию в качестве оптимальной стратегии 010214 0202 7 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму будет выбрана такая, которая, удовлетворяя ограничениям на область 010214 0202 8 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму допустимых значений вектора X, максимизирует значение математического ожидания F=M[Q] исходного показателя эффективности Q, то есть

<

010214 0202 9 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму

В том случае, если число возможных стратегий i конечно (i=1,…,I) и число возможных исходов j конечно (j=1,…,J), то выражение записывают в виде:

010214 0202 10 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму, где

 

Qij – значение показателя эффективности управления в случае появления j-го исхода при выборе i-й стратегии управления;

Pij – вероятность появления j-го исхода при реализации i-й стратегии.

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

Сравнение двух рассмотренных принципов оптимизации в стохастических ЗПР показывает, что они представляют собой детерминацию исходной задачи на разных уровнях влияния стохастических факторов. «Искусственное сведение к детерминированной схеме» представляет собой детерминизацию на уровне факторов, а «оптимизация в среднем» — на уровне показателя эффективности.

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

Рассмотрим пример однокритериальной статической задачи принятия решений в условиях риска:

Для создания картографической базы данных необходимо кодировать картографическую информацию. Использование поэлементного кодирования приводит к необходимости использования чрезвычайно больших объёмов памяти Известен ряд методов кодирования, позволяющих существенно сократить требуемый объём памяти (например, линейная интерполяция, интерполяция классическими многочленами, кубические сплайны и т.п.). Основным показателем эффективности метода кодирования является коэффициент сжатия информации. Однако значение этого коэффициента зависит от вида кодируемой картографической информации (гидрография, границы административных районов, дорожная сеть и т.п.). Обозначим через Qij (i=1,…,n;j=1,…,m) значение коэффициента сжатия i-го метода кодирования для j-го вида информации. Конкретный район, подлежащий кодированию, заранее неизвестен. Однако предварительный анализ картографической информации всего региона и опыт предыдущих разработок позволяют вычислить вероятность появления каждого вида информации. Обозначим через Pj вероятность появления j-го вида 010214 0202 11 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму. Тогда, используя метод оптимизации в среднем, следует выбрать такой метод кодирования, для которого:

010214 0202 12 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму

 

 

 

 

 

 

26. Принятие решений в условиях неопределенности: особенности постановки задачи и критерий выбора в условиях неопределенности.

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

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

Принятие решений в условиях разумного противодействия является объектом исследования теории игр. Мы не будем касаться этих вопросов.

Рассмотрим принципы выбора решений при наличии недостаточной осведомлённости относительно условий, в которых осуществляется выбор. Такие ситуации принято называть «играми с природой».

В терминах «игр с природой» задача принятия решений может быть сформулирована следующим образом:

Пусть лицо, принимающее решение, может выбрать один из m возможных вариантов своих решений X1,X2,…,XM и пусть относительно условий , в которых будут реализованы возможные варианты, можно сделать n предположений Y1,Y2,…,YN. Оценки каждого варианта решения в каждых условиях (Xi ,Yi) известны и заданы в виде матрицы выигрышей лица, принимающего решения A=|aij|. Предположим вначале, что априорная информация о вероятностях возникновения той или иной ситуации Yj отсутствует.

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

Критерий Лапласа: поскольку вероятности возникновения той или иной ситуации Yj неизвестны, будем их все считать равновероятными. Тогда для каждой строки матрицы выигрышей подсчитывается среднее арифметическое значение оценок. Оптимальному решению будет соответствовать такое решение, которому соответствует максимальное значение этого среднего арифметического, то есть

 

010214 0202 13 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму

 

Критерий Вальда: в каждой строке матрицы выбираем минимальную оценку. Оптимальному решению соответствует такое решение, которому соответствует максимум этого минимума, то есть

 

010214 0202 14 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму

 

Этот критерий очень осторожен. Он ориентирован на наихудшие условия, только среди которых и отыскивается наилучший, и теперь уже гарантированный результат.

Критерий Сэвиджа: в каждом столбце матрицы находится максимальная оценка и составляется новая матрица, элементы которой определяются соотношением:

 

010214 0202 15 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму

 

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

010214 0202 16 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму

 

Сущность этого критерия заключается в минимизации риска. Как и критерий Вальда, критерий Сэвиджа очень осторожен. Они различаются разным пониманием худшей ситуации: в первом случае – это минимальный выигрыш, во втором – максимальная потеря выигрыша по сравнению с тем, чего можно было бы достичь в данных условиях.

Критерий Гурвица: вводится некоторый коэффициент , называемый коэффициентом оптимизма, 010214 0202 17 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму. В каждой строке матрицы выигрышей находится самая большая оценка 010214 0202 18 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму и самая маленькая 010214 0202 19 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму. Они умножаются соответственно на 010214 0202 20 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму и (1- 010214 0202 21 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму) и затем вычисляется их сумма. Оптимальному решению будет соответствовать такое решение, которому соответствует максимум этой суммы, то есть

 

010214 0202 22 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму

 

При 010214 0202 23 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму =0 критерий Гурвица трансформируется в критерий Вальда. Это случай «крайнего пессимизма». При 010214 0202 24 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму =1 (случай крайнего оптимизма) человек, принимающий решение, рассчитывает на то, что ему будет сопутствовать самая благоприятная ситуация. Коэффициент оптимизма назначается субъективно, исходя из опыта, интуиции и т.п. Чем более опасна ситуация, тем более осторожным должен быть подход к выбору решения и тем меньшее значение присваивается коэффициенту 010214 0202 25 Понятие и алгоритм поиска Парето оптимального (эффективного) решения. Пример поиска решения по алгоритму.

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

<

Комментирование закрыто.

WordPress: 22.78MB | MySQL:120 | 1,368sec