Элементы теории статистических решений

ЭЛЕМЕНТЫ ТЕОРИИ СТАТИСТИЧЕСКИХ РЕШЕНИЙ Постановка задачи. Иногда требуется принять решение в условиях неопределенности. Для выработки решения используется как количественный, так и субъективный подход. При проведении количественного анализа поиск проходит по следующей схеме: 1) определяется цель решения; 2) рассматриваются возможные варианты решения проблемы; 3) определяются возможные исходы каждого решения; 4) оценивается каждый исход; 5) выбирается оптимальное решение на основе поставленной цели. Но, в конечном итоге, выбор решения зависит от точки зрения того, кто его принимает. Следует отметить, что неопределенность бывает разного рода. Ранее были рассмотрены неопределенные ситуации, связанные с сознательным противодействием противника. Однако встречается неопределенность другого рода, исходящая от недостаточной осведомленности об условиях, в которых будет проходить действие. Например, может быть неизвестен заранее покупательский спрос на определенный вид продукции, или объем перевозок пассажиров в летний период. Такие ситуации иногда называют «играми с природой», а посвященный им раздел теории игр называется теорией статистических решений. Пусть сторона А имеет m возможных стратегий А1, А2,...,Аm, об условиях прохождения операции можно сделать n предположений П1,П2,...,Пn. Эти условия в теории статистических решений принято называть «природой», а предположения о состоянии природы называют «стратегиями природы». Выигрыш стороны А при каждой паре стратегий AiПj, задается матрицей, представленной в таблице 1: Элемент 𝑎𝑖𝑗 равен выигрышу игрока А, если он использует стратегию А i, при состоянии природы Пj. Требуется выбрать для стороны А наиболее выгодную стратегию. Несмотря на схожесть постановки задачи и терминологию, к этой задаче не применимы абсолютно все методы теории антагонистических игр. Методы решения антагонистических инр требуют адаптации к задачам игр с природой. Так, например, при упрощении матрицы игры, возможны действия лишь со строками, поскольку у природы нельзя отбросить невыгодные стратегии. Для решения игр с природой разработаны критерии. Выбор критерия – субъективен. Некоторые критерии напоминают решение антагонистических игр в чистых стратегиях, основаны на анализе результата игры, некоторые используют оценку опасности ситуации и отношение к риску. Риском 𝑟𝑖𝑗 игрока А при использовании стратегии Аi называется разность между выигрышем, который получил бы игрок А, если бы знал состояние Пj, и выигрышем, который он получит, не зная условий и применяя стратегию Аi: 𝑟𝑖𝑗 =βj-aij (1) где 𝛽𝑗 – максимальное значение выигрыша при стратегии Пj. Значение риска отражает удачность выбора данной стратегии в данной ситуации. Риск – это плата за отсутствие информации. Задача 1. Хлебозавод поставляет хлеб на продажу магазинам. Себестоимость одной булки хлеба составляет 30 руб., ее продают за 50 руб. Если булка изготовлена, но не продана, то после переработки черствого хлеба убытки составляют 10 руб. за штуку. В различные дни наблюдался спрос на булки такого типа в количествах 10, 12, 14, 16, 18 тыс. штук. Построить матрицу риска для этой задачи. Решение. Стратегии хлебозавода – выпекать в день булки этого типа в количествах 10, 12, 14, 16 и 18 тыс. штук. В роли природы выступит покупательский спрос с теми же стратегиями. Составим матрицу доходов для любой комбинации стратегий (табл 1). Расчет значений a21 =20∙10-10∙2=180 (тыс.руб.) a31 =20∙10-10∙4=160 (тыс.руб.) a32 =20∙12-10∙2=220 (тыс.руб.) a53 =20∙14-10∙4=240 (тыс.руб.) и т.д. Спрос на хлеб в день (тыс. шт.) Количество поступившего 10 12 14 16 18 в продажу хлеба (тыс.шт.) 10 200 200 200 200 200 12 180 240 240 240 240 14 160 220 280 280 280 16 140 200 260 320 320 18 120 180 240 300 360 На основании матрицы доходов, пользуясь формулой (1), составим матрицу риска, которую называют еще матрицей упущенного дохода (табл.2,3): Спрос на хлеб в день (тыс. шт.) Количество поступившего 10 12 14 16 18 в продажу хлеба (тыс.шт.) 10 200 200 200 200 200 12 180 240 240 240 240 14 160 220 280 280 280 16 140 200 260 320 320 18 120 180 240 300 360 max 200 240 280 320 360 Спрос на хлеб в день (тыс. шт.) Количество поступившего 10 12 14 16 18 в продажу хлеба (тыс.шт.) 10 40 80 120 160 12 20 40 80 120 14 40 20 40 80 16 60 40 20 40 18 80 60 40 20 max 200 240 280 320 360 При выборе решения в одних случаях стараются максимизировать доход, в других – минимизировать риск, сопровождающий выбор решения. В целом правила выбора решения делятся на две группы: а) правила выбора решения без использования численных значений вероятностей исходов; б) правила принятия решения с использованием численных значений вероятностей исходов. Критерии теории игр Критерий ММ (Вальда). Mаксиминное решение (критерий Вальда) получается при максимизации минимума дохода. Такой подход продиктован крайним пессимизмом при оценке состояний спроса. Согласно этому критерию выбирается стратегия, гарантирующая выигрыши, не меньшие чем   max min aij . i j Критерий Н (крайнего оптимизма). Максимаксное решение– максимизация максимума доходов. Для каждой стратегии ( в каждой строке) максимальный доход (заносится в последний столбец таблицы). Из полученных максимумов выбирается максимальное значение. Этот критерий продиктован крайним оптимизмом при оценке состояния спроса. Критерий N (Критерий Гурвица, нейтральный). При использовании принципа минимакса не учитывается априорная информация о состояниях природы и тем самым ограничивается тот выигрыш, который эта информация может дать. При выборе стратегии логично вместо двух крайних взглядов выбрать промежуточный. Такого рода компромиссное правило предложил Гурвиц. Согласно принципу Гурвица неразумно, приняв во внимание самый маленький выигрыш, не учитывать самый большой. Для этого субъективным образом вводится коэффициент оптимизма 𝛾(0 ≤ 𝛾 ≤ 1) и стратегия выбирается из условия H  max    min aij  (1   )  max aij  j i j   При 𝛾 = 1 критерий Гурвица превращается в критерий перестраховщика Вальда; при 𝛾 = 0 – в критерий «крайнего оптимизма». При 0<𝛾< 1 получается нечто среднее между тем и другим. Коэффициент 𝛾 выбирается из субъективных соображений – чем опаснее ситуация, тем он ближе к 1. Критерий S (Сэвиджа). Критерий Сэвиджа основан на анализе рисков. Риском rij игрока А при использовании стратегии Ai называется разность между выигрышем, который получил бы игрок А, если бы знал состояние Вj , и выигрышем, который он получит, не зная условий и применяя стратегию Ai : rij   j  aij где  j – максимальное значение выигрыша при спросе В j . Значение риска отражает удачность выбора данной стратегии в данной ситуации. Риск – это плата за отсутствие информации. При выборе оптимальной стратегии принцип Сэвиджа советует не допускать чрезмерно высоких потерь, к которым могут привести ошибочные решения. Он рекомендует выбирать стратегию, при которой величина риска принимает наименьшее значение в самой неблагоприятной ситуации s  min max rij i j Критерий Сэвиджа, как и критерий Вальда, основан на самой пессимистической оценке обстановки. Критерий Байеса. Критерий Байеса используется, если известны вероятности состояний природы. В соответствии с критерием Байеса оптимальной считается чистая стратегия Ai, при которой максимизируется средний выигрыш: С помощью такого приема задача о выборе решения в условиях неопределенности превращается в задачу о выборе решения в условиях определенности, только принятое решение является оптимальным не в каждом отдельном случае, а в среднем. Критерий Лапласа. Если игроку представляются в равной мере правдоподобными все состояния природы, то иногда полагают и, учитывая, «принцип недостаточного основания» Лапласа, оптимальной считают чистую стратегию Ai, обеспечивающую: Решение игры о производстве хлеба. Спрос на хлеб в день (тыс. шт.) Количество поступившего 10 12 14 16 18 в продажу хлеба (тыс.шт.) 10 200 200 200 200 200 12 180 240 240 240 240 14 160 220 280 280 280 16 140 200 260 320 320 18 120 180 240 300 360 Критерий ММ (Вальда). Mаксиминное решение (критерий Вальда) α=max{200; 180; 160;140; 120} =200, стратегия А1 - максиминная γ=0,6 γ=0,7 γ=0,5 Критерий N (Критерий Гурвица, нейтральный). Количество Спрос на хлеб в день min 𝑎𝑖𝑗 max 𝑎𝑖𝑗 𝑗 𝑗 поступившего (тыс. шт.) в продажу 10 12 14 16 18 хлеба (тыс.шт.) 10 200 200 200 200 200 200 200 200 γ=0,4 Критерий Н (крайнего оптимизма). Максимаксное решение Н=max{200; 240; 280; 320; 360} =360, стратегия А5 - максимаксная 200 200 200 12 180 240 240 240 240 180 240 210 216 204 198 14 160 220 280 280 280 160 280 220 232 208 196 16 140 200 260 320 320 140 320 230 248 212 194 18 120 180 240 300 360 120 360 240 264 216 192 Критерий S (Сэвиджа). Критерий Сэвиджа основан на анализе рисков. Он рекомендует выбирать стратегию, при которой величина риска принимает наименьшее значение в самой неблагоприятной ситуации s  min max rij i j Спрос на хлеб в день (тыс. шт.) Количество поступившего 10 12 14 16 18 в продажу хлеба (тыс.шт.) 10 40 80 120 160 160 12 20 40 80 120 120 14 40 20 40 80 80 16 60 40 20 40 60 18 80 60 40 20 80 Стратегия А4 – оптимальная. Критерий Байеса. Критерий Байеса используется, если известны вероятности состояний природы. Критерий Лапласа. Спрос на хлеб в день (тыс. шт.) Количество поступившего 10 12 14 16 18 в продажу хлеба (тыс.шт.) 10 200 200 200 200 200 200 12 180 240 240 240 240 228 14 160 220 280 280 280 244 16 140 200 260 320 320 248 18 120 180 240 300 360 240 А4 – оптимальная стратегия. Многокритериальные задачи оптимизации В многокритериальных задачах оптимизации заданы не одна, а одновременно несколько целевых функций (критериев). Поэтому многокритериальные задачи наряду со множеством X допустимых решений (альтернатив), X € Rn, характеризуются набором целевых функций F1, F2, … ,Fm , заданных на множестве Х. Если m > 1, то существует набор целевых функций, образующих векторфункцию. Обозначим еѐ как F(x) = (F1(x), F2(x), …,Fm(x)). Рассмотрим также множество оценок Y, элементами которого являются оценки у = F(x). Каждому решению х, принадлежащему множеству Х соответствует одна оценка у = F(x), принадлежащая множеству оценок Y, а каждой оценке у из множества Y соответствует не менее, чем одно решение х из множества Х, для которых F(x) = y. Пространство Rn, которое содержит множество решений Х называется пространством решений, а пространство R m, в котором задано множество оценок, называется пространством оценок или критериальным пространством. Множество решений и множество оценок взаимосвязаны и выбор решения х из множества Х означает выбор соответствующей оценки у из множества оценок Y. В процессе принятия решения осуществляются действия над множеством решений (альтернатив), которые позволяют выделить подмножество или одну альтернативу, т. е. сужать множество решений. Для этого необходимо произвести сравнение альтернатив между собой и определить наиболее предпочтительные альтернативы. Множество решений может быть в общем случае конечным, счетным или несчетным, а оценка решений может осуществляться по ряду критериев как количественного, так и качественного характера. Выбор может осуществляться в условиях определенности и может иметь вероятностный характер. Если х – некоторое решение из множества Х, F(x) – целевая функция (критерий качества, функция предпочтения, функция полезности и т. д.), то в том случае, когда F(x1) > F(x2) решение x1 предпочтительнее решения x2 и наоборот. Когда выбор осуществляется в условиях определенности (выбор любого решения влечет однозначный результат), а целевая функция численно выражает оценку данного действия, то наилучшим решением х*является то, которое обладает наибольшим значением критерия x* = arg max F(х) х€Х Когда для оценивания альтернатив используются несколько целевых функций F(xi) i = 1, 2, …m, то может в принципе быть такой случай, когда на множестве решений существует такое, которое обладает наибольшими оценками по всем критериям. Это решение и является наилучшим. Но если такого решения нет, то возникает проблема неоднозначности выбора. Для устранения неоднозначности используются различные способы решения многокритериальных задач. Наиболее употребительным из них является способ сведения многокритериальной задачи к однокритериальной. Он заключается во введении обобщенного критерия (суперкритерия), который является скалярной функцией векторного аргумента F0(x) = F0(F1(x), F2(x), … ,Fm(x)) Обобщенный критерий позволяет упорядочить решения по значениям F0(x) и выделить наилучшее решение. Поэтому для принятия решения в многокритериальной задаче оптимизации необходима определенная информация о предпочтениях ЛПР. Рассмотрим далее случаи, когда дополнительная информация о предпочтениях заключается в том, что известна относительная значимость оценок. В этом случае для нахождения оптимального решения используются методы, основанные на свертках различного типа. Одним из наиболее употребительных способов преодоления неопределенности целей является представление обобщенного критерия в виде линейной (аддитивной) свертки: где сi – весовые коэффициенты, 𝑐𝑖 ≥ 0 , . Наряду с аддитивной сверткой применяется также мультипликативная свертка вида: Весовые коэффициенты определяются экспертными методами и отражают предпочтения ЛПР. Устранение неопределенности целей в данном случае достигается их ранжированием на основе применения метода экспертных оценок. Другим методом устранения неопределенности целей является использование пороговых (контрольных) критериев. Он заключается в том, что задается система нормативных значений критериев F1*,F2*,…, Fi*,…,FN* , а ограничения задачи имеют вид: Fi ≥ Fi*, I = 1,2, …N Целевая функция определяется в виде: F(x) = min Fi(x)/ Fi* Задача заключается в нахождении решения x* = arg max F(х) х€Х Метод использования главного критерия предполагает, что введена система нормативных значений критериев F1*,F2*,…, Fi*,…,FN*, а система ограничений имеет вид: Fi ≥ Fi*, I = 1,2, …N Кроме того среди критериев выделяется один основной критерий Fк(x). В этом случае задача сводится к однокритериальной задаче – определить max Fк(x), х € Х при выполнении ограничений Fi ≥ Fi*, при i ≠ k. Метод идеальной точки. Метод решения многокритериальных задач, основанный на ведении метрики пространстве целевых функций предполагает, что известно идеальное решение F1,F2,…,FN как предельная точка абсолютного максимума в пространстве критериев, не достижимая при различных значениях альтернатив. Вводится метрика, например, в виде евклидова расстояния от точки {F1(x), F2(x),…, FN(x)} до точки {F1,F2,…,FN} в пространстве критериев d(x) = ∑[ Fi(x) – Fi ]2 Функция d(x) принимается в качестве скалярного критерия. Наилучшей альтернативой является альтернатива, определяемая из условия: x* = arg min d(х) х€Х Кроме методов решения многокритериальных задач, основанных на различных свертках критериев существуют методы, основанные на сокращении множества альтернатив за счет сокращения неперспективных вариантов. Одним из таких методов является метод, предложенный итальянским экономистом В. Парето в 1904 г. выделение множества Парето. Альтернатива принадлежит множеству Парето, если она не хуже остальных по всем критериям и хотя бы по одному критерию лучше. Альтернативы из множества Парето называются эффективными (недоминируемыми). Принцип Парето, используемый при решении многокритериальных задач, заключается в том, что наилучшее решение принадлежит множеству Парето. Таким образом, в результате применения принципа Парето исходное множество альтернатив сужается, а окончательных выбор производится с использованием предпочтений ЛПР.