Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Топ:
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Интересное:
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Дисциплины:
2017-06-04 | 434 |
5.00
из
|
Заказать работу |
|
|
Решение матричной игры можно свести к решению стандартной задачи линейного программирования.
Рассмотрим игру с m х n -матрицей выигрышей Н.
Теорема 17.9. Тройка (X*, Y*, v) является решением игры Г = <Sm, Sn, Н> тогда и только тогда, когда (X*, Y*, kv + а) является решением игры Г' = <Sm, Sn, kH + a>, где а — любое вещественное число, k>0.
Доказательство. Утверждение теоремы следует из того, что неравенства
и
эквивалентны.
В силу теоремы 17.9 всегда можно добиться того, чтобы было v>0 (в противном случае следует прибавить ко всем элементам матрицы выигрышей достаточно большую константу, что, по теореме 17.9, не меняет множества оптимальных стратегий игроков). Поэтому, не нарушая общности, будем считать, что все элементы матрицы Н положительны.
Любую матричную игру можно свести к задаче линейного программирования, вернее, к паре двойственных друг другу задач линейного программирования. Благодаря этому становится возможным применение симплекс-метода для решения матричных игр.
Пусть — произвольная стратегия игрока I в игре Н. Положим . Из положительности элементов H следует, что v(X)>0. Мы имеем
(17.34)
и равенство v(X)=v(H) является необходимым и достаточным условием оптимальности стратегии X. Следовательно, оптимальность стратегии X равносильна тому, что
. (17.35)
Так как v(X) > 0, обе части неравенства (17.34) разделим на v(X) и введем новую переменную . В результате получим
. (17.36)
То, что X — стратегия, означает
, (17.37)
где .
Из соотношений (17.35) и (17.37) следует, что стратегия X будет оптимальной тогда и только тогда, когда
.
В результате задачу определения оптимальной стратегии игрока I мы можем сформулировать так:
при условиях
Рассуждая аналогично, задачу нахождения оптимальной стратегии игрока II можно записать в следующем виде:
|
при условиях
Решив эти задачи, найдем х*, у * и v из соотношений
Пример. Решить игру
.
Чтобы гарантировать v > 0, прибавим ко всем элементам матрицы Н константу +1. Тогда получим матрицу
.
Пара двойственных задач линейного программирования будет в данном случае выглядеть следующим образом:
Минимизировать при условиях | Максимизировать при условиях |
Из этих двух задач симплексным методом удобнее решать вторую, одновременно получая из индексной строки решение первой.
Номер итерации | Базисные переменные | |||||||||
y5 | 1/7 | |||||||||
y6 | 1/6 | |||||||||
y7 | ||||||||||
L | -1 | -1 | -1 | -1 | ||||||
I | 1/7 | 6/7 | 4/7 | 1/7 | 1/7 | |||||
y6 | 1/7 | 41/7 | 67/7 | 71/7 | -6/7 | 1/71 | ||||
y7 | 6/7 | 71/7 | 38/7 | 146/7 | -1/7 | 3/73 | ||||
L | 1/7 | -1/7 | -3/7 | -6/7 | 1/7 | |||||
II | 10/71 | |||||||||
1/71 | 41/71 | 67/71 | -6/71 | 7/71 | ||||||
y7 | 40/71 | |||||||||
L | 11/71 | 25/71 | 27/71 | 5/71 | 6/71 |
После второй итерации симплексного метода получим оптимальное решение
Отсюда
Таким образом, оптимальная стратегия игрока II есть
Из индексной строки против переменных у5, уб, у7 получаем оптимальное решение первой задачи
откуда
и
Итак,
|
|
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!