К задаче линейного программирования

Сведение матричной игры

Предположим, что цена игры положительна ( γ > 0). Если это не так, то согласно свойству смешанных стратегий (теорема 3) всегда можно подобрать такое число а, прибавление которого ко всем элементам матрицы выигрышей даёт матрицу с положительными элементами, и, следовательно, с положительным значением цены игры. При этом оптимальные смешанные стратегии обоих игроков не изменяются.

Итак, пусть дана матричная игра с матрицей А порядка m х n.Согласно основной теореме матричных игр и теореме об активных стратегиях оптимальные смешанные стратегии P=(p₁, ..., p_m), Q= (q₁, ..., q_n) соответственно игроков 1 и 2 и цена игры γдолжны удовлетворять соотношениям:

Разделим все уравнения и неравенства в (1) и (2) на ν (это можно сделать, т.к. по предположению ν > 0) и введём обозначения :

, ,

Тогда (1) и (2) перепишется в виде :

, , , ,

, , , .

Поскольку первый игрок стремится найти такие значения p_i и, следовательно, u_i , чтобы цена игры была максимальной, то решение первой задачи сводится к нахождению таких неотрицательных значений u_i , при которых

, , u_i ≥ 0,

Поскольку второй игрок стремится найти такие значения q_j и, следовательно, x_j , чтобы цена игры была наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений x_j, , при которых

, , x_j ≥ 0 ,

Формулы (3) и (4) выражают двойственные друг другу задачи линейного программирования (ЛП).

Решив эти задачи, получим значения u_i , x_j .Тогда смешанные стратегии, т.е. p_i и q_j получаются по формулам :

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

1. Если в исходной платежной матрице А есть отрицательные элементы или нули, то необходимо добавить ко всем элементам матрицы одно и то же достаточно большое положительное число C, так, чтобы все элементы матрицы были положительными.

2. Составить пару двойственных задач линейного программирования, эквивалентных полученной матричной игре.

3. Определить оптимальные планы пары двойственных задач.

4. Используя соотношение между планами пары двойственных задач и оптимальными стратегиями и ценой игры, найти решение игры, заданной матрицей .

5. Перейти к оптимальным смешанным стратегиям и цене игры с матрицей А, .

Пример. Найти решение игры, определяемой матрицей.

Решение. При решении этой игры к каждому элементу матрицы А прибавим 1 и получим следующую матрицу

Составим систему уравнений (1) и (2):

(1) (2)

Разделим каждое из неравенств и уравнений, входящих в системы (1) и (2) на γ и введём новые переменные u₁, u₂, u₃; и x₁ , x₂ , x₃

W = u1+u2+u3 =1/γ → min	Z = x1+x2+x3 = 1/γ → max

Составим пару двойственных задач линейного программирования:

Задача второго игрока минимизация проигрыша γ	Задача первого игрока максимизация выигрыша γ
Целевая функция
Z = x1+x2+x3 = 1/γ → max	W = u1+u2+u3 =1/γ → min
Функциональные ограничения
Прямые ограничения
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0	u1 ≥ 0, u2 ≥ 0, u3 ≥ 0

Решение обеих задач можно найти с помощью двойственных симплекс-таблиц.

Вспомним правила метода МЖИ:

1. Разрешающий элемент заменяется обратной величиной.

2. Все элементы разрешающей строки делятся на разрешающий элемент.

3. Все элементы разрешающего столбца делятся на разрешающий элемент, и меняется знак на противоположный.

4. Все остальные элементы таблицы считаются по правилу прямоугольника и делятся на разрешающий элемент, т. е. элемент который необходимо посчитать умножается на разрешающий и вычитается произведение элементов стоящих на противоположной диагонали (см. таб. №1), затем полученное число делится на разрешающий элемент.

Определяется разрешающий элемент следующим образом:

1. Из отрицательных элементов сроки Z выбирается наибольший элемент по модулю (кроме столбца свободных членов).

2. К выбранному столбцу составляется симплексное отношение (столбец свободных членов делится на выбранный столбец).

3. Из элементов симплексного отношения выбирается положительный минимальный элемент.

4. На пересечении выбранного столбца и строки находится разрешающий элемент.

Результаты расчёта:

Zmax = 1,5 = Wmin; γ= 1/Zmax= 2/3
u1 = 0,5; p1=u1∙γ = 1/3	x1 = 0; q1=x1∙γ = 0
u2 = 1; p2= 2/3	x2 = 0,5; q2= 1/3
u3 = 0; p3 = 0	x3 = 1; q3 = 2/3
т.е , , =

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: