В этой лекции рассматриваются матричные игры, не имеющие седловых точек.
– игры.
Рассмотрим игру с платежной матрицей
Пусть игрок A применяет набор своих оптимальных стратегий . По основной теореме теории игр это обеспечивает ему выигрыш при любых стратегиях игрока В, т.е. выполняются соотношения:
(62)
Дополняя их уравнением
(63)
получим систему линейных уравнений относительно и . Решая ее найдем
, , , (64)
где .
Повторяя те же рассуждения для игрока В, получим систему линейных уравнений
(65)
Ее решениями будут
, , , (66)
Пример.Молокозавод поставляет в магазин молочную продукцию ( ) и кисломолочную продукцию ( ). Согласно договора между ними продукция поступает в магазин два раза в день: с 10.00 до 11.00 (1-ый срок) и с 17.00 до 18.00 (2-ой срок). Если молокозавод соблюдает сроки поставок, то магазин выплачивает премии по следующей схеме: при поставке продукции в первый срок выплачивает 5 тыс. руб., во второй срок – 3 тыс. руб.; при поставке продукции в первый срок выплачивает 2 тыс. руб., во второй срок – 3 тыс. руб. Определить оптимальные стратегии поставок и получения продукции.
Решение. Примем молокозавод за игрока А, а магазин – за игрока В. Составим платежную матрицу игры:
Сроки
Продукция
1-ый срок
2-ой срок
или
Найдем
,
, седловой точки нет. Применим формулы (63) – (65) для определения оптимальных стратегий и цены игры:
, , , ,
, ,
Оптимальные стратегии: , , цена игры .
Таким образом, молокозавод поставляет молочную продукцию с вероятностью , а кисломолочную продукцию – с вероятностью , а магазин получает продукцию в 1-ый срок с вероятностью , а во 2-ой срок – с вероятностью и выплачивает 2,6 тыс. руб. премии молокозаводу ежедневно.
Матричная игра допускает простую геометрическую интерпретацию.
Нахождение цены игры и оптимальной стратегии для игрока А равносильно решению уравнения:
(66)
Для нахождения правой части (66) применим графический метод.
Пусть игрок А выбрал смешанную стратегию , , а игрок В – k-ую чистую стратегию, . Тогда средний выигрыш игрока А окажется равным
при стратегии (67)
при стратегии (68)
Очевидно, , которую называют нижней огибающей прямых I и II.
Нетрудно видеть, что
Таким образом, верхняя точка нижней огибающей – определяет оптимальную стратегию игрока А: и цену игры .
Проиллюстрируем описанный графичексий метод на рассмотренной выше игре с платежной матрицей .
На плоскости pOz построим две прямые, описываемые уравнениями: и или (I) и (II).
Решая систему уравнений
найдем , , .
Таким образом, имеем полученный выше ответ игры: и .
Теперь покажем как графическим методом найти стратегии игрока В.
(69)
Пусть игрок В выбрал смешанную стратегию , , а игрок А – i-ую чистую стратегию, . Тогда средний выигрыш игрока В окажется равным
при стратегии (70)
при стратегии (71)
Очевидно, , которую называют верхней огибающей прямых III и IV.
Нетрудно видеть, что
Таким образом, нижняя точка верхней огибающей – определяет оптимальную стратегию игрока В: и цену игры .
Для рассмотренной выше гры с матрицей H найдем стратегии игрока В.
На плоскости qOz построим две прямые, описываемые уравнениями: и или (III) и (IV).
Решая систему уравнений
найдем , , .
Таким образом, имеем и .
Замечания. На практике оптимальную стратегию игрока В, если оптимальная стратегия игрока А, следовательно, и цена игры известны, находят приравниванием любого из двух средних выйгрышей игрока В к цене игры:
или .
Для рассмотренного примера такими уравнениями будут
или
Аналогично находят оптимальную стратегию игрока А, если известна оптимальная стратегия игрока В.
и – игры.
Решают такие игры графическим способом, описанным выше. Отличие от – игр заключается в следующем.
4) Нижняя (верхняя) огибающая семейства прямых
содержит большее число отрезков.
5) Пусть в игре в верхней точке нижней огибающей пересекаются прямые и . Тогда при нахождении оптимальной смешанной стратегии игрока В полагают, что , , , , где q – решение уравнения
или
6) Пусть в игре в нижней точке верхней огибающей пересекаются прямые и . Тогда при нахождении оптимальной смешанной стратегии игрока А полагают, что , , , , где p – решение уравнения
или .
– игры.
При решении таких игр рекомендуется предварительно уменьшить размеры платежной матрицы или упростить ее в некотором смысле. С этой целью применяют следующие правила.
Правило доминировнаия.
Из платежной матрицы исключают чистые стратегии заведомо невыгодные по сравнению с другими:
а) для игрока А такими стратегиями являются те, которым соответствуют строки с элементами не большими по сравнению с элементами других строк;
б) для игрока В такими стратегиями являются те, которым соответствуют столбцы с элементами не меньшими по сравнению с элементами других столбцов.
Например, рассмотрим игру с матрицей
Сравнивая строки, убеждаемся, что элементы 2-ой строки не больше соответствующих элементов 1-ой строки, а 3-ья строка совпадает с 4-ой. Следовательно, стратегии и невыгодные и могут быть отброшены. Матрица игры преобразуется к матрице
Сравнивая столбцы полученной матрицы, убеждаемся, что элементы 2-го столбца не меньше соответствующих элементов 1-го столбца, а элементы 3-го столбца не меньше соответствующих элементов 4-го столбца, т.е. стратегии и также могут быть отброшены. Окончательно усеченная матрица игры имеет вид
.
Таким образом, оптимальными стратегиями игроков А и В игры с матрицей Н будут и , где и – оптимальные стратегии игры с матрицей .
Аффинное правило.
Пусть и – оптимальные смешанные стратегии игроков А и В в игре с платежной матрицей и ценой . Тогда и будут оптимальными стратегиями и в игре с матрицей и ценой .
Например, игру с матрицей можно заменить игрой с матрицей , т.к. элементы этих матриц связаны соотношениями : ; ; ; ; ; . При этом оптимальные стратегии игр совпадают, а цены игр связаны соотношением .
В общем случае решение игр размера в смешанных стратегиях сводят к решению двух возможно двойственных ЗЛП.
Редукция матричных игр к ЗЛП.
Пусть игра задана платежной матрицей . Через и обозначим соответственно оптимальные стратегии игроков А и В. Пусть – цена игры. Не умаляя общности, полагаем . В противном случае с помощью аффинного правила добьемся того, что все .
Оптимальная стратегия стратегия игрока А обеспечивает ему средний выигрыш, не меньший , при любой стратегии игрока В. Поэтому все средние выигрыши игрока А можно выписать в виде системы неравенств:
(72)
Введем новые переменные:
(73)
Тогда после деления каждого неравенства из (71) на получим новую систему неравенств
(73)
Из равенства
нетрудно получить соотношение для :
.
Игрок А стремится максимизировать свой гарантированный выигрыш . Максимизация равносильна минимизации . Следовательно, получили следующую задачу для нахождения оптимальной стратегии игрока А:
(74)
при условиях (73) и
(75)
Сформулированная задача (74) – (76) является ЗЛП.
Повторим с естественными изменениями предыдущие рассуждения для определения оптимальной стратегии игрока В.
Игрок В стремиться минимизировать гарантированный проигрыш . Все средние проигрыши игрока В запишем в виде системы неравенст:
, (76)
которые следуют из того, что средний проигрыш игрока В не превосходит цены игры при любой стратегии игрока А.
В обозначениях
система неравенств (76) примет вид
(77)
Применение удовлетворяют соотношению
.
Минимизация равносильна максимизации .
Получили следующую задачу для нахождения оптимальной стратегии игрока В:
(78)
при условиях (77) и
(79)
Задача (77) – (79) также является ЗЛП.
Таким образом, игра свелась к двум ЗЛП, которые запишем в матричном виде
, , ,
Очевидно, задачи I и II являются двойственными ЗЛП.
3. Конюховский П.В. Математические методы исследования операций в экономике. СПб.: Питер, 2000.
4. М. Интрилигатор. Математические методы оптимизации и экономическая теория. М.: Изд. Айрис-Пресс, 2002.
5. Ф.П. Васильев. Методы оптимизации. М. Факториал Пресс, 2005.
ОГЛАВЛЕНИЕ
Введение ……………………………………………………………………..
ЛЕКЦИЯ 1. Исследование операций. Экономико-математические модели. ……………………………………………………………………….
ЛЕКЦИЯ 2. Балансовые модели. Модель Леонтьева многоотраслевой экономики. Продуктивные модели………………………………………….
ЛЕКЦИЯ 3,4,5. Задачи математического и линейного программирования. Модели линейного программирования……………...
ЛЕКЦИЯ 6. Динамическое программирование. Принцип оптимальности и функциональности. Функциональное уравнение Беллмана…………….
ЛЕКЦИЯ 7. Модели потребительского выбора. Функция полезности. Линии безразличия. Оптимизация функции полезности. Функции спроса и предложения……………………………………………………….
ЛЕКЦИЯ 8. Элементы теории игр в задачах оптимального управления экономическими процессами……………………………………………….
ЛЕКЦИЯ 9. Методы решения матричных игр в смешанных стратегиях...
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ ……………………………
Учебное издание
Г. Н. Камышова,
Н. Н. Терехова
МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ
Краткий курс лекций
Издается в авторской редакции
Корректура авторов
АВТОМАТИЗИРОВАННЫЕ СИСТЕМЫ УПРАВЛЕНИЯ ПРОИЗВОДСТВОМ
Конспект лекций
для студентов специальности 230201 «Информационные системы и технологии» очной и очно-заочной форм обучения
СЫКТЫВКАР 2007
УДК
ББК
Рассмотрен и рекомендован к изданию кафедрой информационных систем Сыктывкарского лесного института ________________________, протокол № __.
Рассмотрен и утвержден к изданию методической комиссией технологического факультета Сыктывкарского лесного института _______________________, протокол № ___.
Истомин, П.В.
Автоматизированные системы управления производством: конспект лекций для студентов специальности 230201 «Информационные системы и технологии» очной и очно-заочной форм обучения / П.В. Истомин; Сыкт. лесн. ин-т – Сыктывкар: СЛИ, 2007. – 52 с.
УДК
ББК
Издание содержит краткий текст лекций по данной дисциплине. В сжатом виде приведены понятия по важнейшим темам курса, помещены вопросы для проверки знаний и самоконтроля. Дан список необходимой для изучения темы литературы.
Конспект лекций составлен в соответствии с дополнениями к нормам Государственного образовательного стандарта высшего профессионального образования по направлению 654700 «Информационные системы» специальности 230201 «Информационные системы и технологии».
Для студентов указанных направлений, специальностей и форм обучения.
Эффективность деятельности промышленного предприятия на в конечном счёте определяется тем, насколько успешно данное предприятие способно конкурировать в условиях современного рынка. Чтобы обойти своих конкурентов надо быть быстрее, точнее, гибче. Надо быть способным к перестройке различных сфер производственной деятельности. Одним из основных средств, обеспечивающих указанные свойства, является использование информационных технологий на различных уровнях управления предприятием. Данный курс лекция затрагивает вопросы, связанные с современным состоянием дел в области автоматизации предприятий в целом, и, в особенности, в области промышленной автоматизации и автоматики. Центральное место в курсе уделено детальному изучению автоматизированных систем оперативного диспетчерского управления технологическими процессами и производствами, которые скрываются за общепризнанной аббревиатурой SCADA (Supervisory Control And Data Acqusition). Конкретные вопросы разработки SCADA-систем рассмотрены на примере одной из наиболее популярных на российском рынке программ данного класса – TRACE MODE 6.
– игры.
. По основной теореме теории игр это обеспечивает ему выигрыш 
при любых стратегиях игрока В, т.е. выполняются соотношения:
(62)
(63)
и 
, 
, 
, (64)
.
(65)
, 
, 
) и кисломолочную продукцию ( 
). Согласно договора между ними продукция поступает в магазин два раза в день: с 10.00 до 11.00 (1-ый срок) и с 17.00 до 18.00 (2-ой срок). Если молокозавод соблюдает сроки поставок, то магазин выплачивает премии по следующей схеме: при поставке продукции 
,
, седловой точки нет. Применим формулы (63) – (65) для определения оптимальных стратегий и цены игры:
, 
, 
, 
,
, 
,
, 
, цена игры 
.
, а кисломолочную продукцию – с вероятностью 
, а магазин получает продукцию в 1-ый срок с вероятностью 
, а во 2-ой срок – с вероятностью 
и выплачивает 2,6 тыс. руб. премии молокозаводу ежедневно.
для игрока А равносильно решению уравнения:
(66)
, 
, а игрок В – k-ую чистую стратегию, 
. Тогда средний выигрыш игрока А окажется равным
при стратегии 
(67)
при стратегии 
(68)
, которую называют нижней огибающей прямых I и II.
определяет оптимальную стратегию игрока А: 
и цену игры 
и 
или 
(I) и 
(II).
, 
, 
.
(69)
, 
, а игрок А – i-ую чистую стратегию, 
. Тогда средний выигрыш игрока В окажется равным
при стратегии 
(70)
при стратегии 
(71)
, которую называют верхней огибающей прямых III и IV.
определяет оптимальную стратегию игрока В: 
и цену игры 
и 
или 
(III) и 
(IV).
, 
, 
.
или 
.
или 
и 
– игры.
и 
. Тогда при нахождении оптимальной смешанной стратегии игрока В полагают, что 
, 
, 
, 
, где q – решение уравнения
или 
и 
. Тогда при нахождении оптимальной смешанной стратегии игрока А полагают, что 
, 
, 
, 
, где p – решение уравнения
или 
.
– игры.
невыгодные и могут быть отброшены. Матрица игры преобразуется к матрице
также могут быть отброшены. Окончательно усеченная матрица игры имеет вид
.
и 
, где 
и 
– оптимальные стратегии игры с матрицей 
.
– оптимальные смешанные стратегии игроков А и В в игре с платежной матрицей 
и ценой 
и ценой 
.
можно заменить игрой с матрицей 
, т.к. элементы этих матриц связаны соотношениями 
: 
; 
; 
; 
; 
; 
. При этом оптимальные стратегии игр совпадают, а цены игр связаны соотношением 
.
. Через 
и 
обозначим соответственно оптимальные стратегии игроков А и В. Пусть 
. В противном случае с помощью аффинного правила добьемся того, что все 
.
(72)
(73)
(73)
:
.
. Следовательно, получили следующую задачу для нахождения оптимальной стратегии игрока А:
(74)
(75)
, (76)
(77)
удовлетворяют соотношению
.
(78)
(79)
, 
, 
, 