Задачи целочисленного программирования. Метод Гомори. 3 страница

Отличительная особенность игры с природой состоит в том, что в ней сознательно действует только один из участников, в большинстве случаев называемый игроком 1. Игрок 2 (природа) сознательно против игрока 1 не действует, а выступает как не имеющий конкретной цели и случайным образом выбирающий очередные «ходы» партнер по игре. Поэтому термин «природа» характеризует некую объективную действительность, которую не следует понимать буквально, хотя вполне могут встретиться ситуации, в которых «игроком» 2 действительно может быть природа (например, обстоятельства, связанные с погодными условиями или с природными стихийными силами).

Природа безразлична к выигрышу и не стремится обратить в свою пользу промахи статистика. Пусть статистик имеет m стратегий, а природа может реализовать n своих состояний. Если статистик имеет возможность оценить численно последствия каждой своей чистой стратегии при любом состоянии природы, то игру можно задать платежной матрицей. При упрощении платежной матрицы имеется специфика: нельзя отбрасывать те или иные стратегии “природы”, так как она может реализовать их вне зависимости от того, выгодны они статистику или нет.

При решении таких игр могут быть 2 ситуации:

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

- вероятности pj известны.

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

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

Например, критерий Лапласа основан на более оптимистичных предположениях, чем критерий Вальда, но на практике встречается редко.

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

1. Критерий Лапласа

Этот критерий опирается на принцип недостаточного обоснования, по которому считается, что наступление всех состояний природы равновероятно, то есть p 1= p 2=...= p n=1/ n, а оптимальной считается стратегия Ai, обеспечивающая

Рисунок 55.

2. Критерий Ваальда (минимаксный или максминный критерий)

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

– в случае нахождения выигрыша;

– в случае нахождения потерь.

Рисунок 56.

Это пессимистические критерии.

3. Критерий Сэвиджа (минимаксного риска)

Критерий Вальда настолько пессимистичен, что может привести к нелогичным выводам. Рассмотрим следующую матрицу потерь, которая обычно приводится в качестве классического примера для обоснования “менее пессимистичного” критерия Сэвиджа.

Таблица 4.

	В1	В2
А1
А2

Применение минимаксного критерия приводит к выбору стратегии А2, хотя интуитивно можно выбрать А1, так как при этом выборе можно надеется проиграть 90, тогда как выбор А2 всегда приводит к потерям в 10000 единиц при любом состоянии погоды.

Критерий Сэвиджа “исправляет” положение введением новой матрицы потерь, в которой заменяются на , определяемые следующим образом:

Рисунок 57.

Это означает, что есть разность между наилучшим значением в столбце j и значением .

По существу, выражает риски лица, принимающего решение, по поводу того, что он не выбрал наилучшего действия относительно состояния j. МатрицаR=() называется матрицей риска.

Найдем оптимальную стратегию предыдущей задачи по этому критерию:

.

Рисунок 58.

Применим к матрице “риска” R минимаксный критерий. Получим, что оптимальной стратегией будет– А1.

Отметим, что независимо от того, – доход или потери, – всегда потери. Поэтому к матрице “риска” всегда применяется минимаксный критерий.

4. Критерий Гурвица (пессимизма-оптимизма)

Этот критерий охватывает ряд различных подходов к принятию решений: от наиболее оптимистичного до наиболее пессимистичного.

При оптимистичном подходе выбирают стратегию, дающую:

, если

Рисунок 59

Если – прибыль, то выбирается стратегия по правилу:

Рисунок 60

Если – затраты, критерий выбирает стратегию, дающую

Рисунок 61.

Параметр интерпретируется как показатель оптимизма; при ά=1 критерий слишком оптимистичный, при ά=0 он слишком пессимистичный. Значение ά между 0 и 1 может определяться в зависимости от склонности лица, принимающего решение, к пессимизму или оптимизму. ά=0,5 представляется наиболее разумным.

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

Пример.

Одно из предприятий должно определить уровень предложения услуг, чтобы удовлетворить потребности клиентов. Точное число клиентов не известно, однако ожидается, что оно может принимать одно из следующих значений: 200, 250, 300, 350. Для каждого из этих возможных значений существует наилучший уровень предложения (с точки зрения затрат). Отклонения от этих уровней приводят к дополнительным затратам либо из-за превышения предложения над спросом, либо из-за неполного удовлетворения спроса.

Потери в зависимости от ситуации приведены в следующей таблице 5:

Таблица 5.

Клиенты Предложен.					max
a 1
a 2
a 3
a 4

 

Критерий Вальда. Так как – потери, применяем минимаксный критерий.

(34)

Оптимальной стратегией будет А3.

Критерий Лапласа. Пусть стратегии 2-го игрока равновероятны.Следовательно . (35)

Тогда:

Рисунок 62

Очевидно, что наилучшим уровнем предложения в соответствии с критерием Лапласа будет стратегия А2.

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

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

Формаль­ная схема изложена в работе американского математика Ваальда и состоит из следующих элементов.

1. Конечный или бесконечный случайный вектор наблюде­ний Х= (Х, Х₂,...). (Более строго, X - измеримое отображение, определенное на некотором исходном измеримом пространстве элементарных событий.)

2. Семейство возможных распределений вероятностей век­тора наблюдений X. Как правило, полагают , где - неизвестный параметр, произвольной природы; - множеству возможных значений параметра.

3. Пространство возможных решений D = {d). Так, если = {0,1} (неизвестный параметр = 0 или 1), и задача состоит в различе­нии двух гипотез: ={истинное значение = 0} и = {истин­ное значение = 1}, то естественно положить D = {0, 1}, считая, что решение d = 0 (1) соответствует принятию ().

4. Решающая функция или статистика , принимаю­щая значения в пространстве решений , т. е. правило соответ­ствия между значением вектора наблюдений и принимаемым ре­шением.

Задача состоит в определении понятия «разумной» решающей функции и её поиске. Обычно, для этого вводится дополни­тельный элемент схемы:

5. Функция потерь - потери при решении и истинном значении неизвестного параметра .

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

Если принимаемое решение , то потери суть случай­ная величина , и нужно выбрать решающую функцию Т, порождающую наиболее «устраивающее» распределение вероят­ностей случайной величины . Иначе, мы должны устано­вить отношение предпочтения на множестве возможных распре­делений указанной случайной величины.

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

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

Первыйсостоит в уточнении и обогащении самого принципа оптимальности. Говорят, что решающая функция ( «луч­ше» ), если для всех , и хотя бы в одном случае неравенство строго. Решающая функция Парето - оптимальна или допустима, если не существует решающей функции лучше её. Ясно, что класс рассматриваемых решающих функций можно сузить до класса Парето - оптимальных решающих функ­ций, но, диапазон последнего ещё достаточно широк.

Выбор из этого класса одного представителя должен определяться какими то, но опредеденными до­полнительными соображениями.

Один из самых распространённых подходов основан на известном прин­ципе минимакса и состоит в минимизации максимального по от­ношению к риска, точнее, к минимизации . Такой минимаксный подход правомерен при так называемой «равной значимости» потерь при разных значениях неизвестного параметра. В иных случаях нуж­ны соответственно другие подходы. Так, если = {0, 1}, очень часто экзогенно вводит­ся значение максимально допустимых потерь при , то есть вводится условие , и уже при этом условии нужно минимизи­ровать (подход Неймана — Пирсона). В такой постановке к потерям при = 0 отношение более осторожное, чем при =1. Возможны также и иные подходы, например, минимизация функциона­ла , где - суть представляют собой веса, и тому подобное.

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

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

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

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

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

Рисунок 63.

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

Динамические модели, в основном, укладываются в построенную схему, но при этом и обладают некоторой спецификой. Компонента вектора на­блюдений интерпретируется как собственно наблюдение в момент времени t=l,...,n, где или (конечное время наблю­дений), или (время наблюдений бесконечно). Каждому t соответствует пространство решений . Соответственно решение в момент t определяется функцией , принимающей значения в . (В рамках предыдущей схемы сказанному соответствуют соотноше­ния и ). При этом однако предполагается, что то есть решение принимается лишь на основе значений вектора наблюдений. Типичным при­мером функции потерь в динамической ситуации служит функция — , где интерпретируется как поте­ри в момент при наблюдении и решении , а всё выраже­ние понимается - как средние потери на единицу времени при общем време­ни . Если , можно рассматривать, скажем, верхний пре­дел последнего выражения. Необходимо отметить, что динамическая схема принятия ре­шений содержит все перечисленные выше подходы.

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

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

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

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