Главная страница
Навигация по странице:

  • Игроки B

  • Базис B x

  • 2870538 МОР, В-25. Решение Для запрета перемещения в x 12 устанавливаем для этой ячейки более высокое значение M


    Скачать 58.02 Kb.
    НазваниеРешение Для запрета перемещения в x 12 устанавливаем для этой ячейки более высокое значение M
    Дата31.10.2022
    Размер58.02 Kb.
    Формат файлаdocx
    Имя файла2870538 МОР, В-25.docx
    ТипРешение
    #764146
    страница2 из 5
    1   2   3   4   5

    Решение


    Предполагаем, что игрок I выбирает такую стратегию, при которой полученный выигрыш будет максимальным. Игрок II выбирает такую стратегию, чтобы минимизировать выигрыш игрока I.

    Определим минимальные значения для каждого А и максимальные – для каждого В.

    Получим:


    Игроки

    B1

    B2

    B3

    B4

    B5

    B6

    min(Ai)

    A1

    6

    2

    5

    7

    3

    8

    2

    A2

    7

    3

    8

    9

    2

    8

    2

    A3

    6

    4

    6

    5

    4

    4

    4

    A4

    5

    4

    5

    6

    4

    6

    4

    A5

    7

    2

    6

    3

    3

    5

    2

    max(Bi)

    7

    4

    8

    9

    4

    8




    Гарантированный выигрыш определяется нижней ценой игры. Согласно методу минимакса, нижней ценой игры является максимальное значение из минимальных a, то есть: max(Ai)=4.

    Верхней ценой игры является минимальное значение из максимальных значений B: min(bj) = 4.

    Так как max(Ai)= min(bj)=4, седловая точка существует и указывает решение на пару альтернатив (A3, B2). Таким образом, цена игры равна 4.
    3. Определить оптимальные стратегии игроков и найти среднюю цену игры, применив графический и аналитический методы решения:



    Решение

    Проверим, имеет ли матрица седловую точку.

    Игроки

    B1

    B2

    a = min(Ai)

    A1

    6

    5

    5

    A2

    -3

    7

    -3

    b = max(Bi)

    6

    7




    Гарантированный выигрыш, определяемый нижней ценой игры равен максимальному значению a, то есть 5, которая указывает на максимальную чистую стратегию A1.

    Верхняя цена игры – минимальное значение из b - составляет 6.

    седловая точка отсутствует.

    Цена игры находится в пределах 5 ≤ y ≤ 6. 

    Это значит, что решение игры ищем в смешанных стратегиях: игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш, а игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.

    Решим задачу графическим методом.

    Для этого на осях отложим единичный отрезок. Левый конец отрезка (точка х = 0) соответствует стратегии A1, правый - стратегии A2 (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S1 = (p1,p2).

    На левой оси ординат откладываются выигрыши стратегии A1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A2.

    Решение игры (2 x 2) проводим с позиции игрока A, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.

    Выделяем нижнюю границу выигрыша B1NB2. Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B1B1 и B2B2, для которых можно записать следующую систему уравнений:

    y = 6 + (-3 - 6)p2

    y = 5 + (7 - 5)p2

    Откуда

    p1 = 10/11

    p2 = 1/11

    Цена игры, y = 57/11

    Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений

    6q1+5q2 = y

    -3q1+7q2 = y

    q1+q2 = 1

    или

    6q1+5q2 = 57/11

    -3q1+7q2 = 57/11

    q1+q2 = 1

    Решая эту систему, находим:

    q1 = 2/11; q2 = 9/11.

    Таким образом, цена игры равна y = 57/11, векторы стратегии игроков:

    Q(2/11, 9/11), P(10/11, 1/11)


    4. Найти решение игры путем сведения ее к задаче линейного программирования:



    Решение

    Для начала проверим, имеет ли платежная матрица седловую точку.

    Игроки

    B1

    B2

    B3

    a = min(Ai)

    A1

    4

    2

    0

    0

    A2

    3

    1

    4

    1

    A3

    0

    2

    2

    0

    b = max(Bi)

    4

    2

    4




    Нижняя цена игры, характеризующая гарантированный выигрыш, составит: a = max(ai) = 1

    Верхняя цена игры: b = min(bj) = 2

    Получим: a ≠ b – седловая точка отсутствует, решение найдем в смешанных стратегиях.

    Цена игры будет заключена в интервале 1 ≤ y ≤ 2.

    Запишем математические модели пары двойственных задач линейного программирования.

    Минимум функции F(x) при ограничениях (для игрока II):

    4x1+3x2 ≥ 1

    2x1+x2+2x3 ≥ 1

    4x2+2x3 ≥ 1

    F(x) = x1+x2+x3 → min

    Максимум функции Z(y) при ограничениях (для игрока I):

    4y1+2y2 ≤ 1

    3y1+y2+4y3 ≤ 1

    2y2+2y3 ≤ 1

    Z(y) = y1+y2+y3 → max

    Решим прямую задачу линейного программирования двойственным симплексным методом, с использованием симплексной таблицы.

    Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).

    Определим минимальное значение целевой функции F(X) = x1+x2+x3 при следующих условиях-ограничений.

    -4x1-3x2≤-1

    -2x1-x2-2x3≤-1

    -4x2-2x3≤-1

    Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

    -4x1-3x2+x4 = -1

    -2x1-x2-2x3+x5 = -1

    -4x2-2x3+x6 = -1

    Решим систему уравнений относительно базисных переменных: x4, x5, x6
    Полагая, что свободные переменные равны 0, получим первый опорный план:

    X0 = (0,0,0,-1,-1,-1)

    Базис

    B

    x1

    x2

    x3

    x4

    x5

    x6

    x4

    -1

    -4

    -3

    0

    1

    0

    0

    x5

    -1

    -2

    -1

    -2

    0

    1

    0

    x6

    -1

    0

    -4

    -2

    0

    0

    1

    F(X0)

    0

    -1

    -1

    -1

    0

    0

    0

    План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

    Среди отрицательных значений базисных переменных выбираем наибольший по модулю.

    Ведущей будет 1-ая строка, а переменную x4 следует вывести из базиса.
    Минимальное значение θ соответствует 1-му столбцу, т.е. переменную x1 необходимо ввести в базис.

    На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-4).

    Базис

    B

    x1

    x2

    x3

    x4

    x5

    x6

    x4

    -1

    -4

    -3

    0

    1

    0

    0

    x5

    -1

    -2

    -1

    -2

    0

    1

    0

    x6

    -1

    0

    -4

    -2

    0

    0

    1

    F(X0)

    0

    -1

    -1

    -1

    0

    0

    0

    θ




    -1 : (-4) = 1/4

    -1 : (-3) = 1/3

    -

    -

    -

    -

    Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

    Базис

    B

    x1

    x2

    x3

    x4

    x5

    x6

    x1

    1/4

    1

    3/4

    0

    -1/4

    0

    0

    x5

    -1/2

    0

    1/2

    -2

    -1/2

    1

    0

    x6

    -1

    0

    -4

    -2

    0

    0

    1

    F(X0)

    1/4

    0

    -1/4

    -1

    -1/4

    0

    0
    1   2   3   4   5


    написать администратору сайта