Теория игр. Динамическое программирование

Динамическое программирование

Нелинейное программирование

Линейное программирование

Основные виды моделей и методов принятия решений

Общий вид моделей линейного программирования:

F(X) = c1*x1 + c2*x2 + … + cN*xN => max/min – линейная целевая функция

a11*x1 + a12*x2 + … + a1N*xN <= b1 – система линейных ограничений

a21*x1 + a22*x2 + … + a2N*xN >= b2

aN1*x1 + aN2*x2 + … + aNN*xN = bN

x1, x2, …, xN >= 0

Пример 1. Задача об использовании ресурсов (задача планирования производства). Для изготовления 2 видов продукции используют 4 вида ресурсов. Известны затраты ресурсов на изготовление единиц продукции каждого вида и прибыль, получаемая от единицы продукции. Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

Пример 2. Транспортная задача. Имеется несколько поставщиков и потребителей с известными объемами предложения / спроса. Известна стоимость перевозки единицы продукции от каждого из поставщиков к каждому из потребителей. Необходимо найти такой план перевозок, чтобы перевезти все произведенные товары от поставщиков к потребителям и при этом минимизировать транспортные расходы.

При решении данных задач используется симплекс-метод и его модификации, а также специализированные методы решения транспортных задач. Симплекс-метод разработан независимо американцем Дж. Данцигом (1949) и советским математиком Леонидом Витальевичем Канторовичем (1939).

Одной из разновидностей моделей линейного программирования являются целочисленные модели: одна или несколько переменных по смыслу задачи могут быть только целыми числами и округление неправомерно (рабочие, станки и т.п.). Используется метод отсечения (Гомори) и метод ветвей и границ.

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

Решение проблемы состоит из нескольких этапов (элементов), и решение на каждом последующем этапе зависит от ранее принятых решений.

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

Для простоты будем рассматривать парные (участвуют 2 игрока) антагонистические (выигрыш одного игрока равен проигрышу другого) игры. Игра проходит следующим образом. На каждом этапе игроки делает по одному ходу. Личный ход – сознательный выбор игроком одного из возможных действий. Случайный ход – случайно выбранное действие. Стратегия игрока – совокупность правил, определяющих выбор его действия при каждом личном ходе в зависимости от сложившейся ситуации. Цель игроков – найти оптимальные стратегии (дающие максимальный выигрыш / минимальный проигрыш). Если игра состоит из нескольких этапов, то максимизируют средний выигрыш / минимизируют средний проигрыш.

Для каждого игрока можно составить платежную матрицу (матрицу игры). Пусть игру ведут игроки A и B. Построим платежную матрицу для игрока A. Ход игрока A соответствует выбору строки матрицы, ход игрока B – выбору столбца. На пересечении выбранной строки – столбца находится выигрыш игрока A (равный проигрышу игрока B). Например:

	B1	B2	B3	B4
A1
A2
A3

Игрок A стремится максимизировать свой выигрыш, а игрок B – уменьшить его (навредить). Для любой строки, выбранной игроком A, игрок B будет выбирать столбец, дающий наименьший выигрыш игроку A. Для строки 1 – столбец 1 или 2 (выигрыш 3), для строки 2 – столбец 4 (2), для строки 3 – столбец 4 (4). Игрок A выберет в итоге строку 3, которая дает ему наибольший выигрыш при вреде со стороны игрока B (4). Это гарантированный выигрыш игрока A при любой стратегии игрока B. Он называется также нижней ценой игры или максимином.

Если поменять теперь роли игроков, то можно определить по аналогии гарантированный проигрыш игрока B – верхнюю цену игры или минимакс. Для любой столбца, выбранного игроком B, игрок A будет выбирать строку, дающую наибольший проигрыш игроку B. Для столбца 1 – строку 2 (проигрыш 9), для столбца 2 – строку 2 (10), для столбца 3 – строку 1 (6), для столбца 4 – строку 1 (8). Игрок B выберет в итоге столбец 3, который дает ему наименьший проигрыш при вреде со стороны игрока A (6).

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

Задачи теории игр решаются с использованием методов линейного программирования.

Дата добавления: 2014-01-04