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

Пусть игра задана платежной матрицей (таблица 5.1). Оптимальные смешанные стратегии игроков A и B могут быть найдены в результате решения пары двойственных задач линейного программирования.

Для игрока A:

(2.1)

В результате решения задачи (2.1) находят оптимальный вектор а затем

Для игрока B:

(2.3)

Решая задачу (2.3), находят оптимальный вектор

Поскольку задачи (2.1) и (2.3) образуют пару симметричных двойственных задач линейного программирования, нет необходимости решать обе задачи. Получив решение одной из них, достаточно воспользоваться соответствием между переменными в канонических записях задач

И из строки целевой функции последней симплекс-таблицы, содержащей компоненты оптимального вектора, выписать значение компонент оптимального вектора двойственной задачи.

2.3. Решение матричных игр в смешанных стратегиях. Решение матричных игр в смешанных стратегиях графическим методом

При поиске оптимальных стратегий в матричных играх размерностей

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

Пример 1. Произвести возможные упрощения следующей платежной матрицы

и найти решения игр, используя графический метод решения.

Сделаем несколько упрощений. Так как четвертая и вторая строка являются одинаковыми, то можно вычеркнуть любую из них, например, четвертую, третий столбец доминирует над остальными, значит, он является не выгодным для игрока, поэтому его вычеркиваем. В результате получим:

Откуда а поэтому для определения оптимальных смешанных стратегий игроков составляем задачи:

Поскольку первая задача содержит две переменные, то ее будем решать графическим методом. В результате получим, что Используя формулы (5.2), получаем:

Определим оптимальную смешанную стратегию В

оптимальном плане исходной задачи поэтому первое и второе ограничение двойственной задачи обращаются в равенства. Кроме того, третье ограничение исходной задачи при подстановке значения обращается в строгое неравенство. Следовательно, в двойственной задаче соответствующая ему третья переменная равна нулю, т.е. Для определения остальных двух переменных необходимо решить уравнение:

Откуда находим Используя формулу (5.4), определяем

Тема № 3.Транспортные экономико-математические модели

3.1. Постановка транспортной задачи и методы ее решения

Постановка транспортной задачи. В m пунктах производства A1,A2………..Am; находится однородный продукт (уголь, картофель и т.д.)

в количествах соответственно a1, a2…….am единиц, который должен быть

доставлен n потребителям B1,B2……..Bn в количествах b1, b2…….bn единиц. Известны транспортные издержки Aij (расходы), связанные с перевозкой единицы продукта из пункта в пункт Bj Требуется составить такой план перевозок, который обеспечивал бы при минимальных транспортных издержках удовлетворение спроса всех пунктов потребления за счет распределения всего продукта, произведенного всеми пунктами поставки.

Для разрешимости поставленной задачи необходимо и достаточно,

чтобы сумма запасов продукта равнялась сумме спроса на него, т.е.

(3.1.)

Такую транспортную задачу называют закрытой или задачей c правильным балансом, если же условие (6.1) нарушается, – открытой.

На практике условие (6.1), как правило, не выполняется. Однако при использовании рассматриваемых ниже методов решения предполагается, что задача закрытая. Поэтому надо знать, как открытую задачу формально преобразовать в закрытую. Если суммарный запас продукта превышает общий спрос, т.е.

то в рассмотрение вводится фиктивный пункт потребления со спросом, равным небалансу, т.е.

и одинаковыми тарифами, полагаемыми обычно равными нулю. Теперь условие разрешимости выполняется, а величина целевой функции остается прежней, поскольку цены на дополнительные перевозки равны нулю. При этом грузы, которые должны быть перевезены в пункт Bn+1, фактически останутся в пункте отправления.

Если же общий спрос потребителей больше суммарного запаса продукта, то вводится фиктивный (m + 1)-й пункт отправления Am+1 с

запасом продукта

Тарифы на доставку продукта фиктивным поставщиком полагают, как и в предыдущем случае, равными нулю, что не отразится на целевой функции.

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

Таблица 3.1.

Составим математическую модель задачи. Целевая функция f, выражающая суммарные транспортные затраты, связанные с реализацией плана X перевозок, запишется в виде

(3.2)

Переменные xij должны удовлетворять ограничениям по запасам

(3.3)

и ограничениям по потребностям

(3.4)

Поскольку обратные перевозки не предполагаются, то

(3.5)

Таким образом, математически транспортная задача (3.2) – (3.5) ставится следующим образом. Среди множества решений системы линейных уравнений 3.3), (3.4) и неравенств (3.5) найти такое решение которое доставляет минимум линейной функции (3.2). Отсюда видно, что транспортная задача является задачей линейного программирования и ее можно решать симплекс-методом. Однако специфические особенности системы ограничительных уравнений (3.3), (3.4) позволили разработать для транспортной задачи более простые методы решения.

Эти особенности состоят в следующем:

1) коэффициенты при переменных во всех уравнениях равны либо единице, либо нулю;

2) каждая переменная встречается в двух и только двух уравнениях: один раз в системе ограничений по запасам и один раз в системе ограничений по потребностям;

3) система уравнений симметрична относительно всех переменных xij .

При решении транспортной задачи будем использовать прием последовательного улучшения плана, предусматривающий следующие этапы:

1) построение начального опорного плана;

2) оценка этого плана;

3) переход от имеющегося опорного плана к новому опорному плану с меньшими транспортными затратами. Ранг системы ограничений транспортной задачи (3.2) – (3.5) равен m+n- 1. (на единицу меньше m+n за счет связующего условия баланса). Поэтому количество базисных переменных также равно m + n-1, а свободных mn-( m+n- 1).

Циклом, или замкнутым контуром, называется последовательность клеток (i; j) таблицы 3.1 транспортной задачи, в которой каждые две рядом стоящие клетки находятся в одной строке или одном столбце, при этом первая и последняя клетки совпадают. Циклы могут быть самой разнообразной конфигурации, однако количество вершин в них всегда четно, и повороты линий цикла производятся под прямым углом. Решение транспортной задачи будет ацикличным, если в таблице с этим решением невозможно построить ни одного цикла, в вершинах которого были бы все занятые клетки, или если для любой свободной клетки таблицы можно построить только один цикл, содержащий эту свободную клетку, а остальные вершины будут в занятых клетках.