37. Решение матричных игр методами линейного программирования

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

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

Определение. Общей задачей линейного программирования называется задача максимизации (или минимизации) линейной формы

(3.48)

При ограничениях

, ;

, ; (3.49)

, ,

Где – вектор неизвестных величин, изменяя который можно улучшать описываемую систему или объект; он имеет ряд названий: план задачи, вектор решения, вектор управления, стратегия, поведение и т. д.; (3.48) – целевая функция (показатель эффективности, критерий оптимальности, функционал задачи, функция цели и т. д.), она позволяет выбрать наилучший вариант, при котором выражение (3.48) достигает экстремального значения. Совокупность ограничений (3.49) определяет область допустимых решений для вектора X.

Словесно общую задачу линейного программирования можно сформулировать так: требуется найти максимум (или минимум) линейной формы от N переменных при M ограничениях в виде неравенств или равенств.

В приложениях часто используется симметричная форма задач линейного программирования:

Максимизировать линейную форму

(3.50)

При ограничениях

, ; (3.51)

, . (3.52)

Или минимизировать линейную форму

(3.53)

При ограничениях

, ; (3.54)

, . (3.55)

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

Пусть задана матричная игра A порядка N ´ M

.

При этом полагаем, что чистая нижняя и верхняя цены игры положительны, т. е. a > 0 и b > 0, или отрицательны. Если a < 0, а b > 0, то не исключается возможность того, что цена игры V равна нулю, что недопустимо в последующих преобразованиях. В таком случае к каждому элементу матрицы необходимо добавить такую положительную константу K, чтобы a и b стали одного знака. При таком добавлении константы K компоненты смешанных стратегий обоих игроков не изменятся, а цена игры возрастет на K единиц.

Согласно теореме 3.3 оптимальные смешанные стратегии игроков X0, Y0 удовлетворяют соотношениям (3.15) – (3.18):

, ;

(3.56)

 
;

, ;

.

Разделим обе части каждого из соотношений (3.56) на цену игры V и, введя обозначения , , , , получим:

, ;

;

, ;

.

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

При ограничениях

, .

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

Второй игрок с помощью своей смешанной стратегии или стратегии стремится уменьшить цену игры V или максимизировать ее обратную величину . Это равносильно максимизации линейной формы

При ограничениях

, .

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

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

Определение. Две задачи линейного программирования называются двойственными симметричными задачами, если они могут быть сформулированы следующим образом

Задача 1 (прямая задача).

Найти при ограничениях

, ;

, .

Задача 2 (двойственная задача).

Найти при ограничениях

, ,

, .

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

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

– если прямая задача на минимум, то двойственная – на максимум, и наоборот;

– коэффициенты и целевых функций прямой и двойственной задач являются свободными членами ограничений соответственно двойственной и прямой задач;

– в прямой задаче число переменных N и число ограничений M равно соответственно числу ограничений N и числу переменных M двойственной задачи;

– если прямая задача на минимум, то ее ограничения описываются системой неравенств вида "≥"; в двойственной задаче на максимум ограничения описываются системой неравенств "£";

– в обеих задачах линейного программирования все переменные неотрицательны.

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

Теорема 3.6 (теорема двойственности) [6]. Если одна из двойственных задач имеет оптимальное решение, то и другая задача имеет оптимальное решение, причем экстремальные значения целевых функций равны: . Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений второй задачи противоречива.

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

© 2011-2024 Контрольные работы по математике и другим предметам!