![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Прежде, чем приводить алгоритм вычисления крайних точек множеств оптимальных стратегий, приведем два вспомогательных утверждения.
Лемма 5.5. Если векторы
,
где единица у вектора стоит на
-м, а у вектора
– на
-м месте, являются оптимальными смешанными стратегиями, то они являются крайними точками множеств
.
Доказательство. Если допустить, что не является крайней точкой множества
, то найдутся такие точки
и число
, что будет выполнено равенство
. Сравнивая координаты векторов левой и правой частей этого равенства, обнаружим, что если
, то и
. Тогда
, т.к.
– смешанные стратегии. Таким образом,
, что противоречит принципу выбора точек
. Аналогично доказывается, что и
– крайняя точка множества
. Лемма доказана.
Лемма 5.6. Для того чтобы векторы
, (5.19)
где единица у вектора стоит на
-ом, а у вектора
– на
-ом месте, были оптимальными стратегиями а
– ценой игры с
матрицей
, необходимо и достаточно, чтобы пара
была седловой точкой матрицы
.
Доказательство. Необходимость. Так как векторы (5.19) являются оптимальными стратегиями а – ценой игры, то согласно теореме 2.2.1 оптимальности выполняются неравенства
т.е. выполняются неравенства
, (5.20)
но это и означает, что пара является седловой точкой матрицы
.
Достаточность. Так как пара является седловой точкой матрицы
,
то выполняются неравенства (5.20). А так как для векторов (5.19) выполняются равенства
,
то отсюда и из (5.20) следует
Это силу следствия теоремы 2.2.1 означает, что векторы (5.19) являются оптимальными стратегиями, а число – ценой игры. Лемма доказана.
Леммы 5.5 и 5.6 показывают, что при нахождении крайних точек множеств с использованием теоремы 5.1 можно не исследовать на пригодность подматрицы, являющиеся отдельными элементами матрицы
. Вместо этого достаточно найти седловые точки матрицы
, если таковые есть, и в соответствии с леммой 5.6 определить цену игры и крайние точки вида (5.19).
Дата публикования: 2014-10-20; Прочитано: 372 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!