Подбор кадров для служб железной дороги

Матричные игры и линейное программирование. Итеративный метод решения матричных игр. Игры на выживание, игры-погони. Критерии принятия решений. Персонал, набранный с помощью резерва в результате решения статистической игры по различным критериям.
Краткое сожержание материала:

Размещено на

Тема: Подбор кадров для служб железной дороги



Задание: на основе предложенных примеров разработать собственную систему поддержки принятия решений



1. Введение

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

Как утверждал Г.Лейбниц, "...и игры заслуживают изучения; и если какой-нибудь проницательный математик посвятит себя их изучению, то получит много важных результатов, ибо нигде человек не показывает столько изобретательности, как в игре ".

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

Остановимся на классификации игр.

Интересы участников игры (игроков) могут оказаться несовпадающими и даже противоположными. В последнем случае игра называется антагонистической.

В игре могут участвовать два или более игроков. Случай игры с одним участником (пасьянс, управление физическим объектом и т.д.) в сущности является игрой двух лиц, где вторым участником выступает природа (судьба, рок, провидение).

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

Игры, в которых игроки осведомлены о состоянии своем и партнеров, а также о прошлом поведении участников игры, относятся к категории игр с полной информацией (типичные примеры - шахматы, "крестики-нолики" и т.п.). Большинство же игр протекает в условиях неполной информации, где сведения о состоянии партнеров исчерпываются лишь вероятностными характеристиками (домино, карточные игры, игры против "природы").

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

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

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

Простейшими являются игры 2 лиц с нулевой суммой.

Пусть в такой игре игрок 1 имеет m выборов и игрок 2 - n выборов. Если игрок 1 делает свой i-й выбор, а игрок 2 - свой j-й выбор, то выигрыш игрока 1 (проигрыш игрока 2) равен Rij. Такая игра называется матричной и матрица R = [ Rij / i=1..m , j=1..n ] называется матрицей выигрышей (пла-тежной матрицей).

При ведении игры игрок должен ориентироваться на оптимальную политику партнера и наказывать его за отступления от таковой.

Проведем рассуждения за игрока 1. Если Я воспользуюсь i-м выбором, мой противник для минимизации моего выигрыша сделает тот из своих выборов, который даст min Rij. Соответственно, Я должен использовать тот выбор, который гарантирует мне выигрыш, не меньший

Противник, рассуждая аналогично, приходит к выводу о гарантированном проигрыше, не превышающем

Если в матрице выигрышей существует элемент Rkl = V1 = V2, то говорят о наличии оптимальной политики "в пространстве чистых стратегий" и оптимальными выборами для игроков соответственно являются выборы k и l. Пару (k, l) называют седловой точкой.

Пример 1. Пусть игра определяется матрицей

Седловые точки - (4, 1) и (4, 2). Цена игры = 6; оптимальный выбор для игрока 1 - четвертый, для игрока 2 равнозначны первый и второй (под ценой игры понимают гарантированный выигрыш-проигрыш при оптимальной политике обоих игроков).

Пример 2. Пусть игра определяется матрицей

Здесь равенство V1 = V2 не выполняется; оптимальной чистой стратегии для игроков нет.

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

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

При отсутствии седловой точки среди чистых стратегий приходится искать таковую среди смешанных.

Если игрок 1 прибегает к своему выбору i с вероятностью Pi, а игрок 2 - к своему j-му выбору с вероятностью Qj, то ожидаемый выигрыш игрока 1 (проигрыш игрока 2) равен

Основная теорема теории игр (теорема Джона фон Неймана) утверждает, что любая матричная игра с нулевой суммой всегда имеет седловую точку, т.е. существуют векторы P и Q такие, что

(V - цена игры).



2. Матричные игры и линейное программирование

Очевидно, что если игрок 1 отступит от оптимальной политики, а игрок 2 будет действовать оптимально, то выигрыш игрока 1 будет меньше цены игры, и если игрок 2 отступит от оптимальной политики при сохранении оптимального поведения игроком 1, то его проигрыш превысит цену игры:

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

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

Отсюда возникают две задачи:

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

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

Обратим внимание на то, что при увеличении элементов матрицы R на любую константу С цена игры увеличится на С и это изменение не окажет влияния на искомые вероятности выборов. Таким образом, можно добиться, например, положительности элементов матрицы и, следовательно, цены игры. Поэтому можно допустить, что цена игры V положительна.

В предположении V > 0 проведем замену переменных

Хi = Pi / V, Yj = Qj / V.

Отсюда видно, что

Соответственно, поставленные задачи можно преобразовать к задачам с меньшим числом переменных:

Например, для игры с матрицей

возникают задачи:

максимизировать минимизировать

Y1 + Y2 + Y3 X1 + X2 + X3



при

Y1 + 2 Y2 + 3 Y3 Ј 1 X1 + 4 X2 + 2 X3 і 1

4 Y1 + Y3 Ј 1 2 X1 + 3 X3 і 1

2 Y1 + 3 Y2 Ј 1 3 X1 + X2 і 1

Y1, Y2, Y3 і 0 X1, X2, X3 і 0

Решение этих задач симплексным методом дает оптимальные значения

X = {11/37, 4/37, 5/37}, Y = {8/37, 7/37, 5/37}

и экстремумы целевых функций, равные 20/37.

Отсюда V = 37/20, P = {11/20, 4/20, 5/20}, Q = {8/20, 7/20, 5/20}.



3. Итеративный метод решения матричных игр

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

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

Для примера возьмем задачу, которую мы только что решили.

Пусть игрок 1 сделал выбор 1 с ожидаемыми выигрышами 1, 2, 3. Противник, стремясь минимизировать свой проигрыш, прибегнет к выбору 1 с ожиданием проигрыша 1, 4, 2. Игрок 1 в стремлении максимизировать свой выигрыш прибегнет к выбору 2, что даст ему надежду на суммарный выигрыш (1+4, 2+0, 3+1). Но тогда его противник найдет среди этих значений меньшее и прибегнет к выбору 2 с ожидаемым суммарным проигрышем (1+2, 4+0, 2+3) и т.д.

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

В результате 10 выборов для 1-го игрока частоты составили 0.6, 0.2, 0.2; для игрока 2 - 0.4, 0.3, 0.3; оценка цены игры в диапазоне от 1.7 до 1.9.



4. Многошаговые игры. Игры на выживание

Предыдущее рассмотрение игр проводилось в предположении, что реализация игры может осуществляться любое число раз. Например, для игры "орел-решка", где в случае совпадения предъявляемых сторон монеты выигрывает игрок 1 и при несовпадении - игрок 2, оптимальная политика игроков состоит в равновероятностном выборе "орла" и "решки" и цена игры равна 0.

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

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

где Fk(A,B) - ожидаемый выигрыш игрока 1 в k последовательных реализациях при начальных ресурсах A и B и использовании оптимальной политики.

Пусть общий начальный ресурс игроков A + B = C и игра продолжается до разорения одного из игроков. Обозначим через F(A) ожидаемую вероятность выживания (шансы не разориться) игрока 1 при его начальном ресурсе А и оптимальной политике обоих игроков.

Тогда