![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Приведение матричной игры к задаче
Линейного программирования Пусть имеем игру размерности m* n с матрицей:
Обозначим через р*=(р1, …, рm) g*=(g1, …, gn) – оптимальные смешанные стратегии игроков А и В. Стратегия р* игрока А гарантирует ему выигрыш ≥ υ независимо от выбора стратегии игроком В. Это можно записать так:
где р1 + р2 + … + рm = 1, Аналогично стратегия g* игрока В гарантирует ему проигрыш ≤ υ, независимо от выбора стратегии игроком А, т. е.
где g1 + g2 + … + gn = 1, gj ≥ 0 (j = Поскольку элементы платежной матрицы можно сделать положительными, то и цена игры υ ≥ 0. Разделим системы (9) и (10) на υ ≥ 0, получим (11) и (12).
где
где Обозначим
где х1 + х2 + … + хm=
где у1 + у2 + … + уn = Так как игрок А стремится получить max от игры (υ = max), то функция Оптимальная смешанная стратегия игрока В определяется решением задачи: найти max φ(y) = Получим двойственную задачу линейного программирования, решив ее графически (для случая двух переменных) или симплексным методом, определим
Пример 23. Два сельскохозяйственных предприятия А и В выделяют денежные средства на строительство 3-х объектов. С учетом особенностей вкладов и местных условий прибыль предприятия А в зависимости от объема финансирования выражается элементами матрицы Будем предполагать, что убыток предприятия В при этом равен прибыли предприятия А. Требуется найти оптимальные стратегии предприятий А и В. Решение. 1) Доминирующих строк и столбцов у матрицы нет, поэтому упростить ее нельзя. Обозначим чистые стратегии предприятия: А: А1, А2, А3; В: В1, В2, В3. Предположим, что предприятие А располагает общей суммой 2) Проверим игру на наличие седловой точки:
поэтому решение игры определим в смешанных стратегиях. Цена игры а ≤ υ ≤ β => 25 ≤ υ ≤ 40.
3) Составим задачу линейного программирования: а) найти для игрока А: min f =
![]() б) найти для игрока В: max φ= y1 + y2 +y3 при ограничениях
![]() Проще решить задачу для игрока В (двойственная задача): найти max φ = y1 + y2 + y3 + 0y4 + 0y5 + 0y6. Сведем ее к каноническому виду при ограничениях
Таблица 28
Оптимальный план У* = (0,0133; 0,0094; 0,0098; 0; 0;), max φ(у*) = 0,0325. Найдем решение прямой задачи: СП БП
Y1 Y2 Y3 Y4 Y5 Y6 ↕ ↕ ↕ ↕ ↕ ↕ Х4 Х5 Х6 Х1 X2 Х3
БП СП
Х*= (0,0102; 0,0180; 0,0043; 0; 0; 0), f(х*) = 0,0325,
Найдем
Итак, оптимальными смешанными стратегиями предприятий А и В являются стратегии р* = (0,314; 0,554; 0,132) и g* = (0,409; 0,289; 0,302). Это означает, что из общей суммы а тыс. руб., выделяемых предприятием А на строительство 3-х объектов, на долю 1-го объекта должно выделяться 31,4 %, 2-го – 55,4 %, 3-го – 13,2 % этой суммы. Аналогично распределяются средства b тыс. руб., предприятием В: так на долю 1-го объекта расходуется 40,9 %, 2-го – 28,9 %, 3-го – 30,2 % общей суммы. Такое распределение денежных средств предприятиями А и В по трем строящимся объектам позволит им получить max прибыль 30,77 тыс. руб. Пример 24. Найти решение игры, заданной матрицей. А= Решение. Попробуем упростить матрицу: 1) Элементы 1-го столбца не больше элементов 2 столбца (т. е. 1 столбец доминирует над 2-м); 2) Элементы 3-го столбца не больше элементов 4-го и 5-го столбцов (т. е. 3-й столбец доминирует над 4-м и 5-м столбцом)
3) Проверим игру на наличие седловой точки.
4) Составим задачу линейного программирования а) для игрока А: min f(х) = x1 + x2 при ограничениях
б) для игрока В: max φ(y) = У1 + У2 при ограничениях 5) Решим графически прямую задачу (рис. 15):
г) оптимальное решение получим в точке В. Решим систему
Тогда min f =
Точка В1 – оптимальное решение Следовательно, игрок А применяет стратегию А1 с вероятностью Аналогично делаем вывод и для игрока В.
Задание для самостоятельной работы Решить матричную игру m×n с помощью линейного программирования.
1.
3.
5.
7.
9.
11. 13.
15.
17.
19.
21.
23.
25.
27.
29.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2020-11-11; просмотров: 102; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.191.223.208 (0.034 с.) |