русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Лекция 12. Сведение матричной игры к задаче линейного программирования


Дата добавления: 2013-12-23; просмотров: 1596; Нарушение авторских прав


 

Предположим, что цена игры положительна (u > 0). Если это не так, то согласно свойству 6 всегда можно подобрать такое число с, прибавление которого ко всем элементам матрицы выигрышей даёт матрицу с положительными элементами, и следовательно, с положительным значением цены игры. При этом оптимальные смешанные стратегии обоих игроков не изменяются.

Итак,пусть дана матричная игра с матрицей А порядка mх n. Согласно свойству 7 оптимальные смешанные стратегии х = (х1, ..., хm), y = (y1,..., yn) соответственно игроков 1 и 2 и цена игры u должны удовлетворять соотношениям.

(46)

(47)

Разделим все уравнения и неравенства в (46) и (47) на u (это можно сделать, т.к. по предположению u > 0) и введём обозначения:

, ,

Тогда (46) и (47) перепишется в виде :

, , , ,

, , , .

Поскольку первый игрок стремится найти такие значения хi и, следовательно, pi , чтобы цена игрыu была максимальной, то решение первой задачи сводится к нахождению таких неотрицательных значений pi , при которых

, . (48)

Поскольку второй игрок стремится найти такие значения yj и ,следовательно, qj, чтобы цена игры u была наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений qj, , при которых

, . (49)

 

Формулы (48) и (49) выражают двойственные друг другу задачи линейного программирования (ЛП).

Решив эти задачи, получим значения pi , qj и u. Тогда смешанные стратегии, т.е. xi и yjполучаются по формулам :

(50)

 

Пример. Найти решение игры, определяемой матрицей.

Решение. При решении этой игры к каждому элементу матрицы А прибавим 1 и получим следующую матрицу

Составим теперь пару взаимно-двойственных задач :

 

Решим вторую из них

 

Б.п. q1 q2 q3 q4 q5 q6 Решение å Отношение
  -1 -1 -1 -3  
q4
q5
q6

 



Б.п. q1 q2 q3 q4 q5 q6 Решение å Отношение
-1  
q4
q3
q6

 

Б.п. q1 q2 q3 q4 q5 q6 Решение å Отношение
 
q2  
q3  
q6  

 

Из оптимальной симплекс-таблицы следует, что

(q1, q2, q3) = (0;; 1),

а из соотношений двойственности следует, что

( p1, p2, p3) = (; 1; 0).

Следовательно, цена игры с платёжной матрицей А1 равна

. ,

а игры с платёжной матрицей А :

.

При этом оптимальные стратегии игроков имеют вид:

Х = (х1, х2, х3) = (1; uр2; uр3) = =

Y = (y1, y2, y3) = (uq1; uq2; uq3) = = .

 

 



<== предыдущая лекция | следующая лекция ==>
Решение. | Лекция 13. Основы теории систем массового обслуживания. Предмет теории массового обслуживания.


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.007 сек.