104529 (Теория принятия решений), страница 4
Описание файла
Документ из архива "Теория принятия решений", который расположен в категории "". Всё это находится в предмете "менеджмент" из 2 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "менеджмент" в общих файлах.
Онлайн просмотр документа "104529"
Текст 4 страницы из документа "104529"
Как же искать смешанные стратегии? Их можно найти точно – алгебраическим способом (в частности, с помощью симплекс-метода) или графическим способом (для игры размерности 2 х n или m х 2 ).
Для того чтобы точно найти решение матричной игры в смешанных стратегиях, нужно представить заданную матричную игру в виде задачи линейного программирования и решить её симплекс-методом.
Рассмотрим матричную игру, не разрешимую в чистых стратегиях, в общем виде:
Заметим, что в матричной игре, разрешимой в чистых стратегиях, элементы платежной матрицы могут быть как положительными, так и отрицательными. Для симплекс-метода, которым будем решать игру, не разрешимую в чистых стратегиях, необходимо, чтобы элементы платежной матрицы были неотрицательными. Для этого, если в платежной матрице будут отрицательные элементы, нужно ко всем элементам платежной матрицы прибавить достаточно большое число с . При этом решение задачи не изменится, а цена игры увеличится на с.#
PA = (p1, p2, …, pm)– это оптимальная смешанная стратегия первого игрока. Её применение гарантирует первому игроку выигрыш не меньший, чем цена игры . Если при этом второй игрок выберет стратегию В1, математически все вышесказанное будет иметь вид:
а11р1 + а21р2 + … + am1pm ≥
Таких неравенств будет столько, сколько есть возможных альтернатив у второго игрока, т.е. столбцов платежной матрицы – n штук:
а11р1 + а21р2 + … + am1pm ≥
а12р1 + а22р2 + … + am2pm ≥
а1nр1 + а2nр2 + … + amnpm ≥
Разделив все неравенства на , получим (в общем виде):
а1j + а2j + … + amj ≥ 1
Обозначим: = xi, . С помощью таких новых переменных вышеуказанные неравенства запишутся в виде:
а11 x1 + а21 x2 + … + am1 xm ≥ 1
а12 x1 + а22 x2 + … + am2 xm ≥ 1
а1n x1 + а2n x2 + … + amn xm ≥ 1
Просуммируем новые переменные:
= x1 + x2 + … + xm = + + … + = =
PA = (p1, p2, …, pm)– это оптимальная смешанная стратегия первого игрока. То есть нужно так подобрать (p1, p2, …, pm) , чтобы была как можно большей. Или же, что то же самое, чтобы была как можно меньшей.
Таким образом, используя новые переменные и учитывая всё вышесказанное, исходную матричную игру можно представить в виде задачи линейного программирования:
найти вектор переменных Х = {x1, x2, … , xm}, такой что:
целевая функция f = min
при множестве ограничений:
АТХ ≥ Е
гдеА – матрица коэффициентов (платежная матрица), заданная в условии;
Е – единичный вектор
Х – вектор неизвестных переменных, такой что xi = ;
– это цена игры: = = ;
рi – это коэффициенты вектора смешанной стратегии первого игрока.
-
4.2.2 Решение задачи симплекс-методом
Рассмотрим числовой пример.
Пусть имеем игру с платежной матрицей:
Проверим, имеет ли наша матричная игра седловую точку? Для этого используем принцип максимина.
Выигрыш игрока А: = = 2 он достигается в первой строке.
Выигрыш игрока В:в = = 3 он достигается в четвертом столбце.
Как видим, выигрыши игроков не совпадают, значит у матрицы нет седловой точки. Значит, нужно искать смешанные стратегии.
В данном конкретном случае в множестве ограничений будет четыре неравенства (т.к. в условии задачи четыре столбца). Пересчитывать симплекс- таблицы с четырьмя строками не очень сильно хочется, поэтому удобнее решить двойственную задачу (для коэффициентов вектора смешанной стратегии второго игрока), в которой будет всего две строки (т.к. в условии задачи две строки):
найти вектор двойственных переменных Y = {y1, y2, … yn}, такой что:
целевая функция g = max
при множестве ограничений:АY ≤ Е
Для нашего примера задача линейного программирования будет такой:
найти вектор Y = {y1, y2, y3, y4}, такой что:
целевая функция g = max
при множестве ограничений:
Далее нужно вспомнить методику применения симплекс-метода и использовать её для нашей задачи.
Однако, как показывает многолетняя практика, студенты обладают так называемой "краткосрочной памятью", которая работает только до сдачи необходимого экзамена. Поэтому вспомнить сейчас методику применения симплекс-метода вряд ли кто-то сможет. Для этого нужно сходить в библиотеку, найти специальную литературу и умело ей воспользоваться. Осмелимся заметить, что и этого половина студентов сделать поленится и благополучно завалит данную тему . #
Поэтому для всеобщего блага приведем здесь методику применения симплекс-метода (пройденного и успешно сданного в математическом программировании) для нашей конкретной задачи.
1 этап – приведение задачи линейного программирования к каноническому виду.
Неравенства во множестве ограничений нужно превратить в равенства с помощью добавления искусственных переменных. Для того чтобы неравенства превратить в равенства, надо в каждое неравенство добавить (или отнять – в зависимости от знака неравенства) искусственную переменную:
Целевая функция при этом будет выглядеть так:g = y1 + y2 + y3 + y4 + 0y5 + 0y6
2 этап – определение начального опорного плана.
В полученном случае начальный опорный план будут составлять искусственные переменные, входящие в ограничения с коэффициентами +1 :{ y5 ; y6 }. Новых искусственных переменных для данной задачи вводить не требуется.
3 этап – заполнение исходной симплекс-таблицы.
Исходная симплекс-таблица для нашей двойственной задачи будет иметь вид:
В столбец "текущий базис" ставим переменные, начального опорного плана : { y5 ; y6 }.
В столбец "сi" ставим их коэффициенты в целевой функции.
В столбец "А0" ставим вектор ограничений Е : а10 = 1 ;а20 = 1 .
В самую верхнюю строку таблицы ставим коэффициенты cj при соответствующих переменных в целевой функции:c1 = 1 ; c2 = 1 ; c3 = 1 ; c4 = 1 ; c5 = 0 ; c6 = 0 .
В столбцы "А1", ...., "А6" ставим соответствующие коэффициенты матрицы ограничений А.
Вычисляем оценки по формулам
D0 = ; .Dj = – cj
и ставим их в самую нижнюю строку симплекс-таблицы (строку оценок) :
D0 = = 0 * 1 + 0 * 1 = 0D1 = – c1 = 0 * 4 + 0 * 3 – 1 = – 1
D2 = – c2 = 0 * 3 + 0 * 7 – 1 = – 1D3 = – c3 = 0 * 8 + 0 * 1 – 1 = – 1
D4 = – c4 = 0 * 2 + 0 * 3 – 1 = – 1D5 = – c5 = 0 * 1 + 0 * 0 – 0 = 0
D6 = – c6 = 0 * 0 + 0 * 1 – 0 = 0
4 этап – пересчет симплекс-таблицы.
-
Если j 0 для всех j = 1, 2, .... , n , то данный план (в столбце "текущий базис") – оптимален. В нашем случае это условие не выполняется, значит, текущий базис можно улучшить.
-
Если имеются k < 0 и в столбце Аk все элементы aik 0 , то целевая функция не ограничена сверху на допустимом множестве и данная задача не имеет смысла. В нашем случае видим, что целевая функция сверху ограничена.
-
Если имеются j 0, то возможен переход к новому лучшему плану, связанному с большим значением целевой функции. У нас так и есть.
-
Переменная хk, которую необходимо ввести в базис, для улучшения плана соответствует наименьшей отрицательной оценке j. Столбец Ak, содержащий эту оценку называется ведущим. В нашем случае все оценки одинаковы. Поэтому в качестве ведущего столбца выберем любую оценку, например, третью: k = 3.
-
Ищем min{ ai0 / ai1 } = min{ 1/8 ; 1/1 } = 1/8– этот минимум достигается при i = 1. Значит, r = 1первая строка – ведущая. (на рисунке помечена стрелкой)
Ведущий элементark = a13 = 8 (на рисунке выделен)
-
Заполняем новую симплекс-таблицу.
В столбец "текущий базис" вместо переменной у5 ставим переменную у3 .
В столбец "сi" ставим коэффициент переменной у3 в целевой функции.
Самая верхняя строка таблицы всегда остаётся неизменной.
Пересчитываем ведущую строку по формуле :
После этого пересчитываем остальные строки по формуле
:
вторая строка (i = 2)
Пересчитываем и заполняем строку оценок:
D0 = = 1 * + 0 * = D1 = – c1 = 1 * + 0 * – 1 = –
D2 = – c2 = 1 * + 0 * – 1 = – D3 = – c3 = 1 * 1 + 0 * 0 – 1 = 0
D4 = – c4 = 1 * + 0 * – 1 = –
D5 = – c5 = 1 * + 0 * – 0 = D6 = – c6 = 1 * 0 + 0 * 1 – 0 = 0
После этого повторяем 4 этап до тех пор, пока не будет выполнен п.1 (все j 0).
В нашем случае имеются j < 0 и наименьшая среди них 4 . Значит ведущим столбцом на данном шаге будет A4 (пометим его стрелкой).
Ищем min{ ai0 / ai4 } = min{ : ; : } = min{ ; } = – этот минимум достигается при i = 2. Значит, r = 2вторая строка – ведущая (на рисунке помечена стрелкой).
Таким образом, в новый текущий базис вместо переменной у6 надо ввести переменную у4 .