Решение матричной игры в excel
Покажем на рассмотренном ниже примере, как можно решить антагонистическую игру в смешанных стратегиях средствами MS Excel 1 . Подробно пройдем все этапы решения.
Проверьте, установлена ли надстройка «Поиск решения» в вашей программе MS Excel. Для этого в меню «Данные > Анализ» найдите надстройку «Поиск решения». Если она не установлена, то ее несложно установить (рис. 2.13).
Рис. 2.13
1 Рассматривается версия MS Excel 2007.
Пусть матрица игры размерности 3x3 имеет следующий вид:
Как отмечалось выше, такая игра сводится к задаче линейного программирования
Сначала вводим в таблицу матрицу игры и выделим ячейки для значений векторов р и q, а также для цены игры V. Заполним эти ячейки (А7 — А9; D4 — F4, В1) произвольными числами (начальные значения) вероятностей и зарезервируем под переменную v ячейку В2. Кроме того, поместим в ячейки А10 и G4 формулы сумм: А10: =СУММ (А7: А9), G4: =СУММ (D4: F4). В ячейку Е1 поместим целевую функцию Е1: =В2 (рис. 2.14).
Далее введем в ячейку D11 формулу =СУММПРОИЗВ ($А$7:$А$9; D7: D9) — $В$ 1 и скопируем ее в соседние ячейки Е11 и F11. Эти ячейки мы готовим для последующего ввода неравенств (1) — (3) в задачу оптимизации (рис. 2.15).
Мы все подготовили для решения задачи. Запускаем надстройку «Поиск решения» в меню «Данные» (рис. 2.16).
Установим в качестве целевой ячейку Е1 и выбираем опцию «Равной максимальному значению». В окне «Изменяя ячейки» выбираем ячейки А 7 — А9, зарезервированные под вероятности ра,рЬурс и ячейку В1 (для цены игры).
Далее вводим несколько ограничений:
- 1) сумма вероятностей равна 1;
- 2) ограничения на неотрицательность вероятностей;
- 3) система неравенств (1) — (3).
Для запуска программы осталось нажать кнопку «Выполнить». Все изменения видны в таблице (рис. 2.17).
Программа вычислила вектор и цену игры v = 0.
Для нахождения вектора вероятностей q добавим в таблицу еще несколько элементов. Ранее было показано, что решение антагонистической игры в смешанных стратегиях приводит к системе неравенств для второго игрока вида (2.5).
Применительно к нашей задаче получим
Добавим в ячейку Н7 формулу для ограничения (4): и скопируем формулу в ячейки Н8 и Н9 (рис. 2.18).
Снова запускаем программу «Поиск решения» и перенастраиваем ее (рис. 2.19).
Обратите внимание, что мы поменяли задачу на максимум на задачу на минимум. Кроме того, изменились переменные в окне «Изменяя ячейки» и ограничения на переменные. После нажатия на клавишу «Выполнить» получим результат (рис. 2.20).
Ответ: цена игры v = 0.
2. Получить навык решения матричных игр с помощью линейного программирования в среде EXCEL.
Решение матричной игры сведением к задаче линейного программирования в среде Excel
| -3 | |
| -1 |
 |
 |
Среди элементов матрицы есть отрицательные
.
Введем переменные для игрока , для игрока .
ПЗЛП для игрока 1:
ДЗЛП для игрока 2:
Таблица - Решение ПЗЛП в среде Excel
 |  |  |
| 0,176471 | 1,235294 | |
| 1,31E-17 | 1,705882 | |
| 0,058824 | ||
| 0,117647 | ||
| 1,31E-17 | ||
| 0,058824 | ||
| 0,117647 |
 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Таблица – Решение ДЗЛП в среде Excel
Переход к решению исходной игры.
Проверка: Произведение двух векторов и матрицы, взятое в заданном порядке, равно цене игры:
Ответ: Обоснование распределения финансовых ресурсов между проектами. На инвестирование трех проектов выделено В млн. руб. Известна эффективность капитальных вложений xi в каждый j-й проект, заданная таблично значением нелинейной функции fj(xi), где , , n – количество проектов, m – количество возможных сумм капитальных вложений. Необходимо распределить выделенные средства между проектами таким образом, чтобы получить максимальный суммарный доход. Исходные данные варианта 0:
Математическая модель задачи. Определить х * = ( , , …, , …, ), обеспечивающий максимум целевой функции
и удовлетворяющий условиям
,
Математическая модель задачи варианта 0:
,
. Максимально возможный доход, который может быть получен с проектов (с k-го по n-й), определяется с помощью функции Беллмана:
, Для упрощения расчетов предполагаем, что распределение средств осуществляется в целых числах xi = тыс. руб. Решение. I этап. Условная оптимизация. 1-й шаг: k = 3.
В шапке таблицы отражены варианты значений капиталовложений х3, которые могут быть предоставлены третьему проекту. В столбце C3 отражены варианты значений капиталовложений, которые могут быть выделены всем трем проектам в совокупности. Предположим, что все средства в количестве x3 = 700 тыс. руб. отданы третьему проекту. В этом случае максимальный доход составит f3(x3) = 700 тыс. руб., следовательно: F3(C3) = f3(x3) и x3= C3. 2-й шаг: k = 2. Определяем оптимальную стратегию при распределении денежных средств между вторым и третьим проектами. При этом рекуррентное соотношение Беллмана имеет вид:
. Представим в таблице расчет функции Беллмана.
В шапке таблицы отражены варианты значений капиталовложений х2, которые могут быть предоставлены второму проекту при условии, что часть средств выделяется третьему проекту. В клетках таблицы первое слагаемое – это возможный прирост выпуска продукции при втором проекте f2(х2) в результате освоения капиталовложений х2; второе слагаемое – значение функции Беллмана, полученной на предыдущем шаге F3(C2 – х2), т.е. возможный прирост выпуска продукции при третьем проекте, если ему будет выделена оставшаяся часть капиталовложений, определяемая как C2 – х2. Например, рассуждая формально, если при общей величине капиталовложений C2 = 0 второму проекту выделяется х2 = 0, то прирост продукции составляет f2(0) = 0, а значение функции Беллмана из табл.1 составит: F3(0 – 0) = 0. Поэтому в клетке табл. 2 (0, 0) отражается сумма 0+0. При общей величине капиталовложений C2 = 100 тыс. руб. возможны уже два варианта распределения средств между вторым и третьим проектами: 1) второму проекту ничего не выделяется, т.е. х2 = 0 и прирост продукции составляет f2(0) = 0. В этом случае значение функции Беллмана из табл. 1 составит F3(100 – 0) = F3(100) = 40 тыс. руб., т.е. вся сумма C2 = 100 тыс. руб. выделена третьему проекту, поэтому суммарный прирост продукции составит 0+40, отражаемый в клетке (100, 0). 2) второму проекту может быть выделено х2 = 100 тыс. руб., прирост продукции при втором проекте составляет f2(100) = 50 тыс. руб. В этом случае значение функции Беллмана из табл. 1 составит F3(100 – 100) = F3(0) = 0, т.е. вся сумма C2 = 100 тыс. руб. выделена второму проекту, поэтому суммарный прирост продукции составит 50+0, отражаемый в клетке (100, 100). Рассуждая аналогично, заполняются все строки табл. 2.
Максимальная сумма по каждой строке вносится в колонку F2(C2), одновременно в колонку вносят соответствующие максимальным суммам значения х2 из шапки табл. 2. Например, в строке C2 = 100 максимальная сумма 160 не единственная, следовательно, F2(100) = 50, ему соответствует значение х2 = 100, следовательно, =100. В строке C2 = 500 максимальная сумма единственная 50, следовательно, F2(500) = 160, ему соответствуют значения х2 = 100, х2 = 400, х2 = 500, следовательно, =100/400/500. 3-й шаг: k = 1. Определяем оптимальную стратегию при распределении денежных средств между первым и двумя другими проектами, используя следующую формулу для расчета суммарного дохода:
, на ее основе составлена табл. 3. В шапке таблицы отражены варианты значений капиталовложений х1, которые могут быть предоставлены первому проекту при условии, что часть средств выделяется второму и третьему проекту. В клетках таблицы первое слагаемое – это возможный прирост выпуска продукции при первом проекте f1(х1) в результате освоения капиталовложений х1; второе слагаемое – значение функции Беллмана, полученной на предыдущем шаге F2(C1–х1), т.е. возможный прирост выпуска продукции при втором и третьем проектам, если им будет выделена оставшаяся часть капиталовложений, определяемая как C1 – х1.
Значение функции Беллмана F1(С1) представляет собой максимально возможный доход при всех проектах, а значение , на котором достигается максимум дохода, является оптимальным количеством средств, вложенных в первый проект. Значение целевой функции равно максимальному значению функции Беллмана F1(С1) из табл. 3. Следовательно, значение целевой функции равно Fmax(x * ) = 240 тыс. руб. II этап. Безусловная оптимизация. Далее на этапе безусловной оптимизации для всех последующих шагов вычисляется величина Сk = (Сk-1 – хk-1) оптимальным управлением на k-м шаге является то значение хk, которое обеспечивает максимум дохода при соответствующем состоянии системы Sk. Определяем компоненты оптимальной стратегии. Для этого значения функций Беллмана и соответствующие им оптимальные значения х вносим в итоговую табл. 4.
1-й шаг. По данным из табл. 4 максимальный доход при распределении 700 тыс. руб. между тремя проектами составляет: C1 = 700, F1(700) = 240 тыс. руб. При этом возможны следующие варианты. Первому проекту нужно выделить:
1) = 500 тыс. руб.;
2) = 600 тыс. руб. 2-й шаг. Определяем величину оставшихся денежных средств, приходящуюся на долю второго и третьего проектов:
1) С2 = C1 – = 700 – 500 = 200 тыс. руб.;
2) С2 = C1 – = 700 – 600 = 100 тыс. руб. По данным табл. 4 находим, что оптимальный вариант распределения между вторым и третьим проектами денежных средств размером:
1) 200 тыс. руб. составляет: F2(200) = 90 тыс. руб. при выделении второму проекту = 100 тыс. руб.;
2) 100 тыс. руб. составляет: F2(100) = 50 тыс. руб. при выделении второму проекту = 100 тыс. руб. 3-й шаг. Определяем величину оставшихся денежных средств, приходящуюся на долю третьего проекта:
1) С3 = C2 – = 200 – 100 = 100 тыс. руб.;
2) С3 = C2 – = 200 – 200 = 0. По данным табл. 4 находим:
1) F3(100) = 40 и = 100 тыс. руб.;
2) F3(0) = 0 и = 0. Таким образом, возможны два альтернативных варианта оптимального плана инвестирования проектов: 1) х * = (500, 100, 100), который обеспечит максимальный доход, равный F(700) = f1(500) + f2(100) + f3(100) = 150 + 50 + 40 = 240 тыс. руб.; 2) х ** = (600, 100, 0), который обеспечит максимальный доход, равный F(700) = f1(600) + f2(100) + f3(0) = 190 + 50 + 0 = 240 тыс. руб. Заключение.Подвести итог о том, что в работе исследовано и что получено. Как уже отмечалось, любая парная игра с нулевой суммой может быть сведена к решению задачи линейной оптимизации. Используя значение функции и неизвестных взаимно двойственных задач линейной оптимизации, легко найти цену игры и вероятности применения стратегий каждым из игроков. Пример 1. В качестве примера применения информационных технологий Excel найдем решение парной игры с платежной матрицей
Для данной задачи (седловая точка отсутствует). Запишем пару двойственных задач линейной оптимизации для решения игры.
Решим исходную и двойственную задачи с помощью Excel. Рекомендуемые файлыЧасть 3. Математический анализ - кратные и криволинейные интегралы. Часть 5. Дифференциальные уравнения в примерах и задачах. Высшая математика (Криволинейные и кратные интегралы) 2021г Вариант 2 - ДЗ №2 - Криволинейные и поверхностные интегралы Высшая математика (Криволинейные и кратные интегралы) Высшая математика (Криволинейные и кратные интегралы)Внесем данные на рабочий лист в соответствии с Рис. 4.1.
Рис. 4.1. Данные для решения исходной задачи примера 1. В ячейки E3:E6 введем формулы для расчета функций – ограничений, ячейки B9:D9 отведем для переменных , ячейку B15 – для расчетного значения цены игры , диапазон ячеек F12:H12 – для расчетных значений вероятностей применения стратегий игроком I, и, наконец, ячейку F9 – для расчета целевой функции. Введем все необходимые формулы в соответствующие ячейки. Установим все необходимые ограничения исходной задачи перед запуском Поиска решения. С помощью Поиска решения получим следующий результат:
В EXCEL задача составляется на двух листах. На первом отражены интересы второго игрока, а на втором- первого. На первом листе в ячейки B4:F4 заносятся значения, равные 1. Следующая строка- это нижняя граница, равная 0, а следующая строка- верхняя граница, равная 1. В ячейки B8:F10 заносятся ограничения модели. В левую часть заносится формула сумма произведений. В правую часть в первом ограничении заносится 1, в остальные два- 0. Знак в первом ограничении =, а в остальных- <=. Целевая функция на минимум. На втором листе в ячейки B4:D4 заносятся 1. Также пишется верхняя и нижняя граница. В ячейки B8:C12 заносятся 5 ограничений модели. Левая и правая части аналогичны первому листу. Знак первого ограничения- =, а остальные- >=. Целевая функция на максимум. Для составления компьютерного аналога математической модели используется надстройка «поиск решений». Для вызова окна надстройки необходимо обратиться в меню сервис/поиск решений. Для запуска вычислительного процесса необходимо нажать кнопку ВЫПОЛНИТЬ, после чего в случае верного решения появляется окно «Результаты поиска решения». При этом на рабочем листе происходят соответствующие изменения найдены оптимальные значения переменных, в целевой ячейке – минимальное значение целевой функции, а на втором листе- максимальное. Внизу экрана появился корешок – отчет по результатом. 3.Анализ результатов расчетов, и их экономическая интерпретация. Графический анализ матричной игры Это означает, что первый игрок должен делать 1-й ход с вероятностью 0,6, а 2-й с вероятностью 0,4. V=-1,4 - это означает, что первый игрок проиграет второму 1,4 ед. , и это будет его минимальный проигрыш. Это означает, что второй игрок должен делать 2-й ход с вероятностью 0,533, 3-й ход с вероятностью 0,467, а первым и четвертым он не должен пользоваться V=-1,4 – это означает, что второй игрок выиграет 1,4 ед. , и это будет его минимальный выигрыш. Задача оптовой закупки при неопределенности розничной продажи Это означает, что фирма будет рассчитывать на дождь с вероятностью 0,5547, а на солнце с вероятностью 0,4353. V= -697 – это означает, что фирма потерпит убытки в размере 697 рублей, и это будит ее минимальный проигрыш. Это означает, что дождь будит с вероятностью 0,5547, а солнце с вероятностью 0,4353. Читайте также:
|
