Вся электронная библиотека >>>

Моделирование рисковых ситуаций  >>

 

СВЯЗЬ МАТРИЧНЫХ ИГР С ЛИНЕЙНЫМ ПРОГРАММИРОВАНИЕМ (ОСНОВНАЯ ТЕОРЕМА ТЕОРИИ ИГР). ПРИМЕР РЕШЕНИЯ ЗАДАЧИ

 

Первоначально развитие теории стратегических матричных игр осуществлялось параллельно и независимо от линейного программирования. Позже было установлено, что стратегичес­кая матричная игра может быть сведена к паре двойственных задач линейного программирования. Решив одну из них, полу­чаем оптимальные стратегии игрока 1; решив другую, получа­ем оптимальные стратегии игрока 2. Математическое соответ­ствие между стратегическими матричными играми и линейным программированием было установлено Дж. Б. Данцигом, сфор­мулировавшим и доказавшим в 1951 г. основную теорему тео­рии игр [23].

Теорема. Каждая матричная игра с нулевой суммой всегда имеет решение в смешанных стратегиях, т.е. существуют такое число v и такие стратегии U* и W* игроков 1 и 2 соответственно, что выполняются неравенства:

Поясним смысл доказываемых неравенств: если игрок 1 от­клоняется от своей оптимальной стратегии, то его выигрыш не увеличивается по сравнению с ценой игры; если от своей опти­мальной стратегии отклоняется игрок 2, то по сравнению с це­ной игры его проигрыш не уменьшается.

Доказательство. Пусть матрица игры равна A =  . Всегда можно считать, что все коэффициенты а_ij > 0. Если это не так, то предположим, что наименьший из всех отрицательных коэффициентов есть а⁰ < 0. Тогда увеличим все элементы платежной матрицы на произвольное положительное число а > – а⁰ . Функция выигрыша при этом окажется равной

Из этого следует, что от увеличения всех элементов матрицы A =  на величину a цена игры увеличивается на эту величи­ну, причем оптимальные смешанные стратегии не изменяются.

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

 

 

Рассмотрим теперь пару двойственных задач линейного про­граммирования с матрицей условий A =  (a_ij > 0), совпадаю­щей с платежной матрицей игры. Введем вектор ограничений прямой задачи В = (1, 1, ... , 1)^T, состоящий из т единиц (это вектор-столбец, для удобства записи представленный в виде транспонированной строки. Т - символ транспонирования мат­рицы), и вектор-строку коэффициентов линейной формы или функционала С = (1, 1,..., 1), состоящий из п элементов. Тогда в векторно-матричной форме соответствующая задача линей­ного программирования может быть записана следующим образом:

где Х- вектор искомых переменных задачи (П1). То же в скалярной форме:

Двойственная задача к задаче линейного программирования (П1) может быть записана следующим образом:

где Y - вектор искомых переменных задачи (П2).

То же в скалярной форме:

Все элементы матрицы А по предположению положительны, поэтому многогранные множества задач (П1) и (П2) ограниче­ны. Многогранник задачи (П1) не пуст, так как Х = 0 является допустимым планом. Следовательно, задача (П1), а с ней (по первой теореме двойственности) и задача (П2) разрешимы, и их функционалы в оптимальных планах совпадают (вторая теорема двойственности):

(С, X*) = (У* В).

С учетом выбранных единичных векторов С и В получаем следующее соотношение:

Из условия YA ³ С следует, что Y*¹ 0, поэтому

Положительность значения v обеспечивается положительно­стью всех значений элементов платежной матрицы А.

Обозначим U* = vY*, W* = vX*. Поскольку v, X*, Y* неотри­цательны, то U* ³ 0, W* ³ 0.

Кроме того, , , так как по определению это частоты использования смешанных стратегии, а сумма частот равна единице. По условиям прямой и двойственной задач АХ £ В и YA ³ С. Оптимальные планы этих задач обозначим X* и Y*, причем по предположению X* = W*/v , Y*= U*/v. Поэтому

или

Умножим обе части неравенства (ПЗ) слева на произвольный w-мерный вектор U ³ 0, для которого справедливо

где В - единичный вектор.

Получим:

UAM* ³ v(U,B) = v,

т.е. имеет место неравенство

UAM* ³  v.                                          (П5)

Также умножим обе части неравенства (П4) справа на произ­вольный n-мерный вектор W > 0 , для которого справедливо

где С - единичный вектор.

Получим:

U*AM ³ v(C,W) = v,

т.е. справедливо неравенство

U*AM ³ v.                                           (П6)

Сравнивая неравенства (П5) и (П6), приходим к соотноше­нию

UAW* £ v £ U*AW,

т.е. U* и W* - оптимальные стратегии, а v - цена игры с платеж­ной матрицей А, что и требовалось доказать.

Следствие (С1). В процессе доказательства основной теоре­мы теории игр с платежной матрицей A =  (a_ij > 0) игре приведена в соответствие следующая пара задач линейного про­граммирования:

Составляющие оптимальных стратегий  и  игры связа­ны с компонентами  и  оптимальных планов двойственных задач линейного программирования (П7) формулами:

Цена игры

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

1. Прямая задача. Игрок 1 стремится увеличить цену игры:

v ® mах                                                                     (П8)

при условиях:

т. е. игрок 1 действует так, чтобы его средний выигрыш при использовании его стратегий с частотами u_i для любой j-й стра­тегии игрока 2 был не меньше величины v, которую он стремит­ся увеличить;

т. е. сумма частот применения стратегий игрока 1 равна единице.

2. Двойственная задача. Игрок 2 стремится уменьшить свой проигрыш:

v  ® min                                                                     (П9)

при условиях:

т. е. игрок 2 действует так, чтобы его средний проигрыш при использовании его стратегий с частотами w_j для любой i-й стра­тегии игрока 1 не превышал величины v, которую он стремится уменьшить;

т. е. сумма частот применения стратегий игрока 2 равна единице.

В такой постановке каждая из задач (П8) и (П9) содержит на одно переменное (v) и на одно ограничение ( или ) больше, т.е. размерности прямой и двойственной задач соответ­ственно увеличиваются, что может сыграть определенную роль при ручном решении задач линейного программирования, но не имеет практического значения при решении задач линейного про­граммирования на ЭВМ.

Пример решения задачи. Решить аналитически (используя мажорирование) игру с платежной матрицей

 

Решение. Если для первых двух строк матрицы взять ве­совые коэффициенты соответственно 0,25 и 0,75, то получим:

0,25 * 24 + 0,75 * 0 + 6 > 4;

0,25 * 0 + 0,75 * 8 = 6 > 4.

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

В матрице есть два нуля. Для того чтобы все элементы мат­рицы стали больше нуля, прибавим к каждому элементу по еди­нице. Матрица примет вид:

Далее ставим и решаем пару задач (двойственных) линейно­го программирования:

Для первой задачи (игрока 2) из условия угловой точки следует:

25x₁ + x₂ = 1;

х₁ + 9x₂ = 1,

откуда получаем оптимальное решение:

Находим оптимальные смешанные стратегии игрока 2:

Для второй задачи (игрока 1) из условия угловой точки следует:

25y₁ + y₂ = 1;

y₁ + 9 y₂  = 1,

откуда оптимальное решение равно:

Оптимальными смешанными стратегиями игрока 1 будут:

Цена игры рассчитывается с учетом ее поправки на единицу:

v = 1:0,1427-1=6,008.

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

 

К содержанию книги:   Моделирование рисковых ситуаций в экономике и бизнесе

 

Смотрите также:

 

    ПРЕДПРИНИМАТЕЛЬСКИЙ РИСК предпринимательская ...

Такие предприниматели готовы рисковать, в рисковой ситуации они маневрируют ресурсами, способны очень быстро находить новых партнеров bibliotekar.ru/biznes-41/29.htm

 

  Риск-менеджмент. Организация риск-менеджмента

Одна и та же рисковая ситуация воспринимается разными людьми по- разному. Поэтому оценка риска и выбор финансового решения во многом ... bibliotekar.ru/finance-2/102.htm

 

  СТРАХОВАНИЕ. Организационная структура страхования

Страхование как экономическая категория включает следующие элементы: рисковые обстоятельства, ситуация риска, стоимость (оценка) объекта ... bibliotekar.ru/risk-menedgment/7.htm

 

  Риск-менеджмент - часть финансового менеджмента

Объектом управления в риск-менеджменте являются риск, рисковые вложения .... При отсутствии типовых ситуаций финансовый менеджер bibliotekar.ru/risk-menedgment/4.htm

 

  Потребность делать нечто лучше, чем оно было сделано вчера ...

В отличие от менеджера, для предпринимателя поиск рисковых ситуаций и умение их разрешать обладают самодостаточной ценностью. Только на ... bibliotekar.ru/menedzhment-2/195.htm

 

  КЛАССИФИКАЦИЯ ПРЕДПРИНИМАТЕЛЬСКИХ РИСКОВ С ...

С риском предприниматель сталкивается на разных этапах своей деятельности, и, естественно, причин возникновения рисковой ситуации ... bibliotekar.ru/biznes-41/30.htm

 

  Расчетно-кассовое обслуживание населения. Чековая книжка ...

В магазин не надо везти крупные суммы денег и покупатель избавлен от рисковых ситуаций в дороге. В свою очередь магазин освобождается от ... bibliotekar.ru/bank-4/36.htm

 

  Транснациональная корпорация (ТНК) представляет собой ...

... системы, коммунальные услуги; экономические и финансовые условия; восприятие культуры; рисковые ситуации, включая политический риск (рис. ... bibliotekar.ru/teoriya-organizacii/140.htm

 

  Управление риском. Понятие и виды экономических рисков ...

«Ситуация риска» отличается от «ситуации неопределенности». ... Эти мероприятия и составляют содержание рисковой политики. ... bibliotekar.ru/biznes-38/16.htm

Политика доходов и заработной платы 

 

Разработка управленческого решения

 

Исследование систем управления 

 

Организационное поведение и управление персоналом