Главная Случайная страница


Полезное:

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


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Приведение матричной игры к задаче линейного программирования





 

Пусть игра задана платёжной матрицей Р размером m x n:

 

Матрица Р не имеет седловой точки, поэтому решение игры представлено в смешанных стратегиях.

Игрок А обладает стратегиями А1, А2,..., Аm, игрок В – стратегиями В1, В2,..., Вn. Необходимо определить оптимальные стратегии SА*=(р1*, р2*,..., рm*) и SВ*=(q1*, q2*,..., qn*), где рi*, qj* – вероятность применения соответствующих чистых стратегий Аi, Вj, причём

р1* + р2* +... + рm* = 1, q1* + q2* + qn* = 1.

Оптимальная стратегия SА* удовлетворяет следующему требованию. Она обеспечивает игроку А средний выигрыш, не меньший, чем цена игры, при любой стратегии игрока В и выигрыш, равный цене игры v, при оптимальной стратегии игрока В. Величина v (цена игры) неизвестна. Будем считать v > 0, этого можно добиться, прибавляя ко всем элементам матрицы некоторое положительное число. Если игрок А применяет смешанную стратегию SА* = (р1*, р2*,..., рm*) против любой чистой стратегии Вj игрока В, то он получат средний выигрыш, или математическое ожидание выигрыша аj = a1j p1 + a2j p2+ … + amj pm, .

Для оптимальной стратегии SА* все средние выигрыши не меньше цены игры, поэтому получаем систему неравенств:

(7.11)

Разделим каждое неравенство на v > 0. Введём новые переменные

(7.12)

Тогда система 7.11 примет вид:

(7.13)

Цель игрока А – максимизировать свой гарантированный выигрыш, т.е. цену игры v.

Разделив на v ≠ 0 равенство р1 + р2 +... + рm = 1, получаем, что переменные xi удовлетворяют условию: х1 + х2 +... + хm = 1 / v. Максимизация цены игры v эквивалентна минимизации величины , поэтому задача может быть сформулирована следующим образом: определить значения переменных xi ≥ 0 , так, чтобы они удовлетворяли ограничениям (7.13) и целевая функция

Z = x1 + x2 + … + xm (7.14)

обращалась в минимум. Это задача линейного программирования. Решая задачу (7.13) – (7.14), получаем оптимальные значения хi* и величину , затем находим рi* = v ∙ хi* и оптимальную стратегию SА* = (р1*, р2*,..., рm*).

Для определения оптимальной стратегии SВ*=(q1*, q2*,..., qn*) игрок В стремится минимизировать гарантированный выигрыш, т.е. найти max . Переменные q1, q2,..., qn удовлетворяют неравенствам

 

(7.15)

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

Если обозначить yj = qj / v, , (7.16)

то получим систему неравенств

(7.17)

Переменные yj удовлетворяют условию у1 + у2 +... + уn = 1/v.

Таким образом, получили задачу линейного программирования: определить значения переменных yj ≥ 0 , которые удовлетворяют системе неравенств (7.17) и максимизирующих линейную функцию

W = у1 + у2 +... + уn. (7.18)

Решение задачи (7.17) – (7.18) даёт оптимальные значения yj* и величину 1/v, затем находим qj* = v ∙ yj* и оптимальную стратегию SВ*=(q1*, q2*,..., qn*). При этом цена игры

v = 1/max W = 1/min Z. (7.19)

Рассмотренные задачи (7.13), (7.14), (7.17) и (7.18) являются симметричными двойственными задачами. Таким образом, для решения игры нужно решить одну из задач, требующую меньших вычислений, затем найти решение второй с помощью теорем двойственности.

Пример 7.5. Предприятие может выпускать три вида продукции (А1, А2 и А3), получая при этом прибыль, зависящую от спроса, который может быть в одном из четырёх состояний (В1, В2, В3, В4). Дана матрица (таблица 7.4), её элементы aij характеризуют прибыль, которую получит предприятие при выпуске i-й продукции с j-м состоянием спроса.

Определить оптимальные пропорции в выпускаемой продукции, гарантирующие среднюю величину прибыли при любом состоянии спроса, считая его неопределённым.

Решение. Задача сводится к игровой модели, в которой игра предприятия А против спроса В задана платёжной матрицей (таблица 7.4).

Таблица 7.4 – Платёжная матрица

  В1 В2 В3 В4
А1        
А2        
А3        

 

Определим нижнюю и верхнюю цены игры: α = max(2, 3, 1) = 3, β = min(4, 5, 6, 5) = 4. Так как α ≠ β, то матрица не имеет седловой точки и оптимальное решение следует искать в смешанных стратегиях игроков SА* = (р1, р2, р3) и SВ*=(q1, q2, q3, q4). Обозначим xi = pi/v, yj = qj/v, , . Составим симметричные двойственные задачи.

Задача 1 Задача 2

Задачу 2 приведём к канонической:

 

 

 

Решим каноническую задачу симплексным методом в симплексных таблицах (таблица 7.5).

 

 

Таблица 7.5 – Симплексная таблица

Сi Баз.                 θ
Св. члена у1 у2 у3 у4 у5 у6 у7
  у5                 1/4
  у6                 1/3
  у7                 1/2
  W   – 1 – 1 – 1 – 1        
  у1 1/4   3/4   1/2 1/4     1/4: 1/2=1/2
  у6 1/4   7/4   7/2 –3/4     1/4:7/2=1/14
  у7 1/2   7/2 – 1   –1/2     1/2: 2=1/4
  W 1/4   –1/4   –1/2 1/4      
  у1 3/14   1/2 4/7   5/14 –1/7    
  у4 1/14   1/2 6/7   –3/14 2/7    
  у7 5/14   5/2 –19/7   –1/14 –4/7    
  W 2/7     3/7   1/7 1/7    
              х1 х2 х3  

 

Из таблицы находим ; , следовательно, .

Учитывая, что qj = yj ∙ v, получим оптимальную стратегию игрока В:

Из последней строки симплексной таблицы получаем , т.к. pi*= xi* ∙ v, то получаем оптимальную стратегию игрока А: . Находим цену игры

Следовательно, предприятие должно выпускать 50% продукции А1, 50% продукции А2, а продукцию А3 не выпускать.

– оптимальная стратегия спроса означает, что оптимальный спрос в 75% находится в состоянии В1 и в 25% – в состоянии В4. Средняя величина прибыли составит при этом .

При решении произвольной конечной игры размера m x n рекомендуется придерживаться следующей схемы:

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

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

3. Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размера m x n рекомендуется симплексный метод, для игр размера 2х2, 2хn, mx2 возможно графическое решение.

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

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

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

Рассмотрим экономическую задачу, сводящуюся к игровой модели.

Пример 7.6. Предприятие выпускает скоропортящуюся продукцию, которую может сразу отправить потребителю (стратегия А1), отправить на склад для хранения (стратегия А2) или подвергнуть дополнительной обработке (стратегия А3) для длительного хранения.

Потребитель может приобрести продукцию: немедленно (стратегия В1), в течение небольшого времени (В2), после длительного периода времени (В3).

В случае стратегий А2 и А3 предприятие несёт дополнительные затраты на хранение и обработку продукции, которые не требуются для А1, однако при А2 следует учесть возможные убытки из-за порчи продукции, если потребитель выберет стратегии В2 или В3.

Определить оптимальные пропорции продукции для применения стратегий А1, А2, А3, руководствуясь «минимаксным критерием» (гарантированный средний уровень убытка) при матрице затрат (таблица 7.6).

 

Таблица 7.6 – Платёжная матрица

Bj Аi В1 В2 В3
А1      
А2      
А3      

 

Решение. Получаем игру с платёжной матрицей .

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

Игра упростилась: ,

По формулам (7.8), (7.9), (7.11) находим:

; ;

Вывод: оптимальная стратегия производителя продукции , т.е. стратегия А1 не применяется, 1/3 продукции отправляется на склад (стратегия А2), 2/3 продукции дополнительно обрабатывается (стратегия А3), при этом цена игры .

 

 

Date: 2015-10-18; view: 657; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.009 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию