Анализ матричной игры
Теория игр – это математическая теория конфликтных ситуаций. Игра – конфликтная ситуация, регламентированная определенными правилами:
§ порядок выполнения ходов;
§ порядок выполнения каждого хода;
§ количественный результат игры.
Наиболее изучены матричные игры. Например,
В этой игре два участника – сторона и сторона , у каждого участника по 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 тыс. единиц. Распределение выполним способом наименьших тарифов
Поставщики | Мощность | |||||
- | - | - | ||||
- | ||||||
- | - | -2 | ||||
- | - | - | ||||
-1 | - |
Полученный план не оптимален, следует перейти к лучшему. Это можно сделать на основе изложенного алгоритма.
Дата добавления: 2022-07-20; просмотров: 75;