Анализ матричной игры

<2 3 456 7 8 >

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

§ порядок выполнения ходов;

§ порядок выполнения каждого хода;

§ количественный результат игры.

Наиболее изучены матричные игры. Например,

В этой игре два участника – сторона и сторона , у каждого участника по 3 стратегии. Будем полагать, что матрица характеризует выигрыш стороны (и соответственно проигрыш стороны ).

Решить игру – значит, дать рекомендации каждом из сторон относительно использования их стратегий. Предварительно игру анализируют по “принципу мини-макса”. Он состоит в выборе наиболее осторожной стратегии, исходя из наихудшего образа действия другой стороны.

а) Анализируем игру с позиций стороны . Если игрок выбирает стратегию , то его гарантированный выигрыш (или самое худшее, что его ожидает) равен 3. Если он выбирает вторую стратегию, то гарантированная величина выигрыша равна 2. Наконец, если он использует стратегию , то гарантирует себе выигрыш 2. Эти величины являются минимальными в строках. Очевидно, что из этих гарантированных выигрышей сторона постарается выбрать наибольшее значение – это 3. Данную величину называют нижней ценой игры или максимином и обозначают: .

б) Анализируем игру с позиции стороны . Если игрок выбирает стратегию , то самое худшее для него – проигрыш 5. Если он остановится на стратегии , то худший исход – проигрыш 6. Если же он выберет стратегию , то наихудший для него результат – проигрыш 5. Эти величины являются максимальными в столбцах. Конечно, игрок выберет стратегию или , чтобы уменьшить гарантированный проигрыш – это число 5. Эту величину называют верхней ценой игры или минимаксом и обозначают: .

в) Цена игры – это величина, отражающая объективное соотношение сил, она всегда удовлетворяет условию: . В данном примере: .

Если , то игра имеет решение в конкретных стратегиях, называемых оптимальными. Эти оптимальные стратегии являются устойчивыми, обеспечивают равновесие в игре, а цена игры называется “седловой точкой”. Если такой ситуации нет, то оптимальные стратегии будут выглядеть так:

; .

где – вероятности стратегий стороны ;

– вероятности стратегий стороны .

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

Анализ матричной игры проводится в два этапа:

§ формируются двойственные задачи, решают одну из них симплекс-методом и записывают решение обеих двойственных задач;

§ определяют решение игры.

1. Запишем две двойственные задачи на основе приведенной платежной матрицы:

а) для участника	б) для участника

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

Данная задача приобретет вид:

В результате использования симплекс-алгоритма получим:

Базис			– 1	– 1	– 1




-строка
		2/5		11/5	19/5			–3/5
		3/5		24/5	16/5			–2/5
	– 1	1/5		3/5	2/5			1/5
-строка	–1/5		2/5	3/5			–1/5
	– 1	2/19		11/19		5/19		–3/19
		5/19		56/19		–16/19		2/19
	– 1	3/19		7/19		–2/19		5/19
-строка	–5/19		1/19		–3/19		–2/19
	– 1	3/56				24/56	–11/56	–10/56
	– 1	5/56				–16/56	19/56	2/56
	– 1	7/56					–7/56	14/56
-строка	–15/19				–8/56	–1/56	–6/56

Решение будет иметь вид:

а)

б)

2. Найдем решение игры:

а) определим цену игры, – эта величина характеризует количественный результат игры:

б) найдем вероятности стратегий:

; .

; ; .

в) составим оптимальные стратегии для участников

; .

Как видим, для достижения оптимального результата стороне рекомендуется из 15 раз стратегию использовать 3 раза, стратегию – 5 раз, стратегию – чаще всего, а именно 7 раз. Для стороны стратегию – рекомендуется использовать реже всего – 1 раз из 15, гораздо чаще нужно применять стратегию – 6 раз из 15, и более всего – стратегию . Если кто-то из участников отклонится от этих рекомендаций, то он ухудшит только свое собственное положение.

Метод потенциалов

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

§ необходимым и достаточным условием существования решения является баланс между спросом и предложением;

§ по загруженным клеткам определяют систему потенциалов:

где – потенциал строки;

– потенциал столбца;

– тариф соответствующей клетки.

§ в оптимальном распределении сумма потенциалов строки и столбца не должна превосходить тариф соответствующей незагруженной клетки;

§ количество поставок должно быть равно величине , где - число поставщиков, - число потребителей.

Метод потенциалов осуществляется в три этапа:

1. Построение первоначального опорного плана (начальное распределение грузов).

2. 0ценка оптимальности распределения грузов с помощью системы потенциалов.

3. Улучшение плана перевозок, если оно возможно.

Второй и третий этапы повторяются до тех пор, пока решение не станет оптимальным.

I этап. Построение начального опорного плана

Начальное распределение можно выполнять различными способами: способом северо-западного угла, способом наименьших тарифов, двойного предпочтения, способом Фогеля, способом Лебедева-Тихомирова и др. Наиболее простым и легко реализуемым на ЭВМ является способ северо-западного угла. Он заключается в том, что от каждого поставщика, начиная с первого, вывозят весь груз с учетом запросов потребителей. Распределение завершено, если весь груз от поставщиков вывезен, а каждый потребитель получил требуемый объем.

Рассмотрим пример: имеется три поставщика и три потребителя , указаны мощности поставщиков, спрос потребителей и тарифы на перевоз груза (табл. 1).

Таблица 1

Поставщики	Мощность

			50 –	⁺(4)
		(3)		(1)	– 1
		(2)	50 +	– 200	– 2
					–

Установим, прежде всего, наличие баланса между спросом и предложением

250 + 150 + 250 = 650

200 + 250 + 200 = 650

Баланс есть. Теперь распределим груз, начиная с первой верхней клетки, отсюда и название способа - северо-западный угол. Распределение завершено, необходимо определить затраты (величину ) и оценить оптимальность решения.

II этап. Оценка оптимальности решения

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

; ;

; ; .

Имеем систему из 5 уравнений с 6 неизвестными, поэтому один из потенциалов примем равным 0. Обычно берут и находят все остальные потенциалы:

; ; ; ; .

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

; ;

; .

Условие оптимальности ни для одной из пустых клеток не выполняется. Следует улучшить решение.

III этап. Построение нового распределения

Из всех клеток, для которых условие оптимальности не выполняется, выбирают ту, в которой расхождение наибольшее. Если таких клеток несколько, то выбирают клетку с меньшим тарифом. Ее отмечают знаком “+”. Начиная от выбранной клетки, строят прямоугольную фигуру, все остальные вершины которой располагаются в заполненных клетках. Знаки вершин чередуют.

Прямоугольные фигуры могут быть следующих видов:

Реже встречаются фигуры такого вида:

Вид фигуры предопределен распределением поставок.

Из всех клеток, отмеченных знаком минус, выбирают наименьший груз. Его перемещают вдоль прямоугольной фигуры, прибавляя, если стоит знак “+”, и, вычитая, если стоит знак “–”. Все изменения отражают в новой таблице. Величины, не участвующие в перераспределении, в новую таблицу переносят без изменения. Обратимся к примеру: в таблице 1 знаком “–” отмечены две клетки, выбирают наименьший груз 50 и перемещают его вдоль прямоугольной фигуры. Все изменения отражают в табл. 2. Получено новое распределение: необходимо оценить его, поэтому возвращаемся ко II этапу алгоритма.

Таблица 2

Поставщики	Мощность

		200 –	.	+ 50
		(7) +	– 150	(1)
		(6)	+ 100	– 150
					–

Проверим число заполненных клеток, их по-прежнему 5. Вновь находим потенциалы, причем можно не составлять систему, а использовать правила:

1. В 1 строке берем 0.

2. Неизвестный потенциал столбца равен разности между издержками заполненной клетки и известным потенциалом строки.

3. Неизвестный потенциал строки равен разности между издержками заполненной клетки и известным потенциалом столбца.

Чередуя эти правила, найдем потенциалы.

Проверку оптимальности также можно проводить непосредственно в таблице, ставя “точку”, если условие выполняется, и, указывая в круглых скобках величину расхождения в случае невыполнения условия.

В нашем примере самое большое расхождение между суммой потенциалов и тарифами – в клетке (2;1). Строим прямоугольную фигуру и замечаем, что две клетки, отмеченные знаком “–”, имеют одинаковую наименьшую величину 150, – этот факт ведет к вырожденному распределению. И действительно, после перемещения получим таблицу 3, в которой число загруженных клеток равно 4.

Таблица 3

Поставщики	Мощность

		50 –	+ (2)
			l	l	– 4
		0 +	– 250	l	– 4
				–

Вырожденность может появиться и исчезнуть при переходе от таблицы к таблице. Чтобы продолжить решение в случае вырожденной задачи, вводят нулевые поставки, соответствующие клетки считают условно заполненными. Нулей будет столько, сколько недостает поставок. Их вписывают в клетки, имеющие малые издержки, и при этом следят, чтобы не получался замкнутый цикл (прямоугольная фигура, во всех вершинах которой - заполненные клетки). В данном примере следует вписать один ноль и лучше всего в клетку (3; 1). В остальном решение обычное: находят потенциалы, проверяют условие оптимальности. После очередного перераспределения получим таблицу 4.

Таблица 4

Поставщики	Мощность

		l
			l	l	– 2
				l	– 2
				–

Задача вновь стала невырожденной - число загруженных клеток равно 5. Условие оптимальности выполняется. Размещение грузов видно из таблицы. Найденные суммы издержек на каждом этапе решения: , , , . На каждом этапе получали решение лучше предыдущего.

Замечание 1. Если мы имеем дело с открытой транспортной задачей, то для ее решения необходимо первоначально обеспечить баланс между спросом и предложением. Для этого вводят дополнительного поставщика, если спрос превышает предложение, в противном случае вводят дополнительного потребителя. Если добавляют поставщика, то его “мощностью” будет величина, недостающая до баланса, транспортные тарифы берут равными нулю. Аналогично поступают, если добавляют потребителя. В дальнейшем решение проводят по изложенному выше алгоритму. Введение дополнительного поставщика или потребителя имеет вполне определенное экономическое объяснение. В первом случае мы определяем, какому потребителю выгоднее недопоставить груз, исходя из интересов всех участников, во втором случае – у какого поставщика целесообразнее всего оставить часть груза.

Замечание 2. Ранее был подробно рассмотрен способ северо-западного угла для начального распределения грузов. Число итераций (таблиц) можно уменьшить, если воспользоваться способом наименьших тарифов. Он заключается в анализе всей матрицы тарифов, выборе наименьших значений и максимальном заполнении соответствующих клеток таблицы. Эти действия выполняются до тех пор, пока не будет распределен весь груз и удовлетворен спрос всех потребителей. В результате заполнения одной из клеток исключается из рассмотрения какой-то поставщик или потребитель. При этом условные участники транспортной задачи принимаются во внимание в последнюю очередь.

Рассмотрим пример транспортной задачи.

Поставщики	Мощность

Баланса между спросом и предложением нет, необходимо ввести условного поставщика с мощностью 150 тыс. единиц. Распределение выполним способом наименьших тарифов