Файл: В. А.МАТВЕЕВ.pdf

Данная игра с матрицей 2 × 4. Такую игру можно решать графоаналитическим методом с позиций первого игрока (см. §6). Другой подход основан на применении линейного программирования. Одну из этих задач, именно двойственную задачу, можно решить графически (см. §8). Наконец, наиболее общий и удобный подход, основан на использовании симплекс – метода для решения пары задач линейного программирования. Используем последний подход.

Найдём нижнюю цену игры

мах{-2, -5} = -2 < 0.

Так как νН = -2 < 0, то задачи линейного программирования

запишем для преобразованной матрицы А+. Для этого добавим ко всем элементам матрицы число 3, как это сказано в начале параграфа. Итак,

Теперь нижняя цена νН = 1 > 0 и можно применять метод

линейного программирования. Запишем прямую задачу для матрицы A+. Получаем

99

f (x) = x1 + x2 + x3 + x4 → max; 6x1 + 4x2 +5x3 + x4 ≤1,

−2x1 + 2x2 + 4x4 ≤1,

xj ≥ 0, j =1,...,3.

Преобразуем её в задачу линейного программирования в канонической форме

xi ≥ 0; i =1,...,6.

Данные, представленные в канонической задаче, заносим в симплекс таблицу 11.6.

Таблица 11.6.

Заполнение таблицы стандартное, в столбце “Значения” у оценочной функции ставим 0, т.к. в функции цели постоянное слагаемое 0. Выделяем базисные переменные. Это переменные, для которых столбцы образуют единичную матрицу. Базис образуют x5, x6. Остальные переменные являются свободными.

По заполненной симплекс таблице определяем решение, соответствующее этой итерации. Свободные переменные равны 0. Базисные переменные и значение функции находим из таблицы 11.6. Они представлены в столбце “Значение”. Отметим, что значение функции цели берём с противоположным знаком. Итак, x(0) = (0, 0, 0, 0, 1, 1), f (0) =0.

В оценочной строке имеются положительные числа. Значит, решение можно улучшить. Первые столбец и строка будут

100

ведущими. Втаблице 11.6 онивыделены цветом. Наихпересечении находится ведущий элемент. В нашем случае это число 6.

Переходим к первой итерации. Её суть состоит в том, чтобы свободную переменную x1 сделать базисной, а базисную переменную x5 - свободной. В таблице выполняем преобразования аналогичные элементарным строчным преобразованиям в методе Гаусса при решении системы линейных уравнений. В результате преобразований получаем

Таблица 11.7.

Из таблицы 11.7 находим базисные переменные (свободные

переменныеравны 0) и значениефункции x(1) = (1/6, 0, 0, 0, 0, 4/3) и f

(1) =1/6. Этотрезультатможнопроверить. Полученныезначениядолжны удовлетворять функции цели в канонической (стандартной) задаче

линейногопрограммирования. Действительно1 16 +1 0 +1 0 = 16 , т.е.

получили верное равенство.

В оценочной строке таблицы 11.7 имеются положительные числа, наибольшее из них определяет ведущий столбец. Наименьшая оценка 4/13 определяет ведущую строку. В таблице 11.7 они выделены цветом. Проводим вторую итерацию. Её суть состоит в том, чтобы свободную переменную x4 преобразовать в базисную, а базисную переменную x6 сделать свободной. Результаты представлены в таблице 11.8.

Таблица 11.8.

Изтаблицынаходимбазисныепеременныеизначениефункции

101

цели, т.е. x(2) = (3/26, 0, 0, 4/13), f (1) =11/26. Этот результат можно

проверить. Действительно 1 326 +1 0 +1 0 +1 413 =1126 , т.е. получили верное равенство.

Воценочнойстрокенетположительныхчисел, значитсимплекс

–метод закончен. Обозначим через X и Y соответственно решение прямой(11.10), (11.12) идвойственной(11.5), (11.7) задачлинейного программирования. Выпишем это решение из последней симплекс – таблицы. Получаем

Перейдём к решению матричной игры. Вначале найдём цену игры. Для матрицы А+ она определяется по формуле (11.6) (или по формуле (11.11)). Получаем

x1 + x2 + x3 + x4 = 326 +0 +0 + 413 =1126 = 1ν , ν* = 2611.

Из формулы (11.4) находим оптимальную стратегию первого игрока

x* =ν *Y = 2611(313, 5 26)T = (611, 511)T .

Из формулы (11.9) получаем оптимальную стратегию второго игрока

ν * = ν −3. Значит ν * = 26/11-3 = -7/11. Окончательно проверим полученный результат для матричной игры по формуле

Действительно,

102

Задачидлясамостоятельногорешения

Задача 11.1. С помощью линейного программирования найти цену и седловую точку для игры из примера 1.1 “Камень, ножницы, бумага”. Эта матричная игра задана матрицей

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

103