§ 8. Расширенная a – игра и задача линейного программирования

Для любой расширенной А–игры с матрицей А размера n ´ m можно построить пару двойственных задач линейного программирования, эквивалентных А – игре.

Пусть даны: матрица   Ā размера        ,  вектор-строка b длины     . Условимся для двух векторов a = (a₁, ¼, a_k), b = (b₁, ¼, b_k) длины k писать a ³ b, если a_i ³ b_i для i = 1, ¼, k.

Сформулируем пару задач линейного программирования и расширенную А-игру в матричной форме.

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

Найти вектор                        ,   удовлетворяющий  следующим условиям:

при ограничениях:

где 

Рекомендуемые материалы

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

Найти вектор                         , удовлетворяющий   следуюшим условиям:

при ограничениях:

Расширенная А – игра

Найти векторы x = (x₁, ¼, x_n), y = (y₁, ¼, y_m) и число ã, удовлетворяющие условиям:

Где  e_k = (1, ¼, 1) и A – матрица размера n ´ m.

Предположим, что матрица A расширенной A–игры имеет только положительные элементы (a_ij ³ 0) и x, y – оптимальные стратегии игры с положительной ценой ã. 

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

Решением этих задач будет:

Прямая задача будет выглядеть:

при ограничениях:

Двойственная задача:

при ограничениях:

Действительно ли             являются решениями задач?

Проверяем условия:

   удовлетворяют необходимым условиям.

Предположим, что есть еще один, претендующий на решение, вектор    , удовлетворяющий условиям:

и такой, что

Обозначим

Очевидно, что вектор z удовлетворяет соотношениям

В силу лемм (§4) строгое неравенство здесь невозможно, поэтому вектор     не является решением.

Аналогично доказывается и  для     .

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

Рассмотрим обратную связь.

Предположим, что имеется матрица А с положительными элементами и           являются решением пары задач линейного программирования.

Тогда оптимальные стратегии имеют вид:

где

Если матрица А имеет неположительные элементы, то прибавляем к каждому элементу этой матрицы положительное число d такое, чтобы новая матрица

была положительной, где

Для матрицы A^/ c положительными элементами можно построить пару задач линейного программирования. Для такой матрицы оптимальные стратегии x^/, y^/ совпадают с оптимальными стратегиями x, y, а цена игры

Если Вам понравилась эта лекция, то понравится и эта - 7 Объединения адвокатских коллективов.

Задачи к § 8

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

8.2. Рассмотрите игру, в которой два противника А и В ведут борьбу за два стратегических пункта. Под командованием А находятся два полка, под командованием В – три. Обе стороны должны распределить свои силы между двумя пунктами. Пусть n₁ и n₂ – количество полков, посланных со стороны А на пункты 1 и 2 соответственно. Аналогично пусть m₁ и m₂ – количество полков, посланных В на пункты 1 и 2. Выигрыш В подсчитывается следующим образом. Если m₁ > n₁, он получает на первой позиции 2n₁+1 очков, если m₁ < n₁, он теряет на первой позиции 2m₁+1 очков. Аналогично осуществляется подсчет на второй позиции. И наконец, если число полков на какой-нибудь позиции с каждой стороны одно и то же, то каждая сторона на этой позиции получает ноль очков. Сформулируйте задачу как расширенную А-игру и решите ее методом линейного программирования.