К задаче линейного программирования

Приведение матричной игры

Игра m×n в общем случае не имеет наглядной геометрической интерпретации. Решение достаточно трудоемко при больших m и n, но может быть сведено к задаче линейного программирования.

Пример решения задачи. Предприятие может выпускать 3 вида продукции А₁, А₂ и А₃, получая при этом прибыль, зависящую от спроса, который может быть в одном из 4-х состояний (В₁, В₂, В₃, В₄). Элементы платежной матрицы характеризуют прибыль, которую получат при выпуске i-й продукции при j-м состоянии спроса. Определить оптимальные пропорции в выпускаемой продукции, гарантирующие максимизацию средней величины прибыли при любом состоянии спроса, считая его определенным. Задача сводится к игровой модели, в которой игра предприятия А против спроса В задана платежной матрицей.

Таблица 2.5

Платежная матрица игры

	В1	В2	В3	В4	α
А1
А2
А3
β

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

Для игрока В невыгодна вторая стратегия (столбец В₂), так как все элементы этого столбца больше или равны элементам столбца В₁, то есть при любой стратегии, выбранной игроком А, игрок В проигрывает больше в случае выбора второй стратегии вместо первой.

Поскольку a ¹ b, следовательно седловая точка отсутствует, решение будем искать в смешанных стратегиях.

Чтобы привести игру к задаче линейного программирования, обозначим:

.

Получим две взаимно двойственные задачи линейного программирования:

Для первого игрока:

(так как , то .

Поскольку .

И для второго игрока:

Вторую задачу на максимум решать легче. Решаем ее симплексным методом. Получаем следующий результат:

.

Последняя запись целевой функции имеет вид:

.

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

Цена игры

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

,

То есть .

Данный результат означает, что предприятие должно выпустить 40 % продукции А₁ и 60 % продукции А₃, а продукцию А₂ выпускать не надо. Тогда максимально гарантированное из минимально возможных значений средней величины прибыли составит 5,4 ден. ед., независимо от спроса покупателей.

Задание для самостоятельной работы.

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

При решении произвольной конечной игры размера m×n рекомендуется придерживаться следующей схемы:

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

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

3) Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размера m×n рекомендуется симплексный метод, для игр размера 2×2, 2×n, n×2 возможно геометрическое решение.

На практике реализация решения в смешанных стратегиях может происходить несколькими путями. Первый состоит в физическом смешении чистых стратегий в пропорциях, заданных вероятностями p_i. Другой путь – при многократном повторении игры предполагает применение в каждой партии чистых стратегий в виде случайной последовательности, причем каждая из них – с частотой, равной ее вероятности в оптимальном решении.

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

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

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

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

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

Ø Важно помнить. Теория игр является очень сложной областью знания. При обращении к ней надо соблюдать известную осторожность и четко знать границы применения. Слишком простые толкования, принимаемые фирмой самостоятельно или с помощью консультантов, таят в себе скрытую опасность. Анализ и консультации на основе теории игр из-за их сложности рекомендуются лишь для особо важных проблемных областей. Опыт фирм показывает, что использование соответствующего инструментария предпочтительно при принятии однократных, принципиально важных плановых стратегических решений, в том числе при подготовке крупных кооперационных договоров.

Пример решения задачи.

Швейная фабрика выпускает брюки и шорты, сбыт которых зависит от состояния погоды. Затраты фабрики на единицу продукции составили: брюки – 15 ден. ед., шорты – 10 ден. ед. Цена реализации: брюки – 21 ден. ед., шорты – 14 ден. ед. Фабрика может реализовать при теплой погоде 120 брюк и 300 шорт, а при прохладной погоде: 370 брюк и 100 шорт.

Составим платежную матрицу игры.

Таблица 2.6

Матрица выигрыша фабрики

Погода

		Теплая	Холодная
Фабрика	Теплая
	Холодная

Вычислим значения элементов матрицы:

= 120*(21 – 15) + 300*(14 – 10) = 1920 – прибыль фабрики, если продукция выпущена по плану теплой погоды и погода оказалась теплой;

= 370*(21 – 15) + 100*(14 – 10) = 2620 – прибыль фабрики, если продукция выпущена по плану холодной погоды и погода оказалась холодной;

= 120*(21 – 15) + 100*(14 – 10) – 200*10 = –880 – прибыль фабрики, если продукция выпущена по плану теплой погоды, а погода оказалась холодной;

= 120*(21 – 15) + 100*(14 – 10) – 250*15 = –2630 – прибыль фабрики, если продукция выпущена по плану холодной погоды, а погода оказалась теплой.

Таким образом, платежная матрица данной игры имеет вид:

Таблица 2.7

Платежная матрица игры

Погода

		Теплая	Холодная
Фабрика	Теплая		-880
	Холодная	-2630

Обозначим: р₁ – вероятность выбора фабрикой первой стратегии (то есть производства продукции по плану теплой погоды), р₂ – вероятность выбора фабрикой второй стратегии (то есть производства продукции по плану холодной погоды). Тогда:

(1920* р₁ – 2630* р₂) – прибыль фабрики, если погода будет теплой;

(–880* р₁ + 2620* р₂) – прибыль фабрики, если погода будет холодной.

Чтобы прибыль фабрики не зависела от погоды, надо найти такие р₁ и р₂, что (1920* р₁ – 2630* р₂) = (–880* р₁ + 2620* р₂). Учитывая свойство вероятностей: р₁ + р₂ = 1, решаем уравнение.

1920* р₁ – 2630*(1 – р₁) = –880* р₁ + 2620*(1 – р₁)

Раскрывая скобки и приводя подобные, получаем:

р₁ *(1920 + 2630 + 880 + 2620) = (2620 + 2630)

. Тогда р₂ = 1–0,652 = 0,348.

Тогда план выпуска продукции для фабрики должен составить:

количество брюк = 120*0,652 + 370*0,348 = 207 шт.;

количество шорт = 300*0,652 + 100*0,348 = 230 шт.

При таком плане производства фабрика гарантирует себе прибыль в размере 1920*0,652 – 2630*0,348 = 337 ден.ед.

Задание для самостоятельной работы.

Применив методы теории игр, решить следующие экономические задачи.

1. Предприятие выпускает скоропортящуюся продукцию, которую можно сразу отправить к потребителю (А₁), отправить на склад для хранения (А₂) или подвергнуть дополнительной обработке для длительного хранения (А₃). Потребитель может приобрести продукцию немедленно (В₁), в течение небольшого времени (В₂) или после длительного периода времени (В₃).

В случае стратегии А₂ и А₃ предприятие несет дополнительные затраты на хранение и обработку продукции, которая не требуется для А₁, однако при А₂ следует учесть возможные убытки из-за порчи продукции, если потребители выберут стратегии В₂ и В₃. Определить оптимальные пропорции выпуска продукции, руководствуясь минимаксным критерием, при следующей матрице затрат.

Таблица 2.8

Платежная матрица игры

	В1	В2	В3	α
А1
А2
А3
β

2. Швейная фабрика выпускает платья и костюмы, сбыт которых зависит от состояния погоды. Затраты фабрики на единицу продукции составили: платья – 8 ден. ед., костюмы – 27 ден. ед. Цена реализации: платья – 17 ден. ед., костюмы – 48 ден. ед. Фабрика может реализовать при теплой погоде 1975 платьев и 600 костюмов, а при прохладной погоде: 625 платьев и 1000 костюмов.

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

Что означают следующие термины и понятия?

Игра	Комбинаторная игра
Игроки	Стратегическая игра
Стратегия	Непрерывная игра
Ход	Матричная игра
Личный ход	Платежная матрица
Случайный ход	Решение игры
Функция выигрыша	Оптимальные стратегии
Парная игра	Максиминная стратегия
Множественная игра	Минимаксная стратегия
Игра с нулевой суммой	Устойчивость решения
Игра с постоянной разностью	Цена игры
Конечная игра	Верхняя цена игры
Бесконечная игра	Нижняя цена игры
Кооперативная игра	Чистая стратегия
Коалиционная игра	Смешанная стратегия
Бескоалиционная игра	Седловая точка

Теперь вы должны уметь:

o составлять экономико-математические модели задач, применяя методы теории игр;

o решать матричные игры графическим методом;

o приводить задачи теории игр к задачам линейного программирования;

o определять, разрешима ли игра в чистых стратегиях;

o определять оптимальные смешанные стратегии для игроков, то есть находить вероятности применения чистых стратегий;

o классифицировать игру;

o анализировать результаты решения игры;

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

Контрольные вопросы:

1. Понятие игры.

2. Какие проблемы решает теория игр (теория конфликтных ситуаций)?

3. Классификация игр.

4. Что значит решить игру?

5. Что такое платежная матрица?

6. Что называется чистой ценой игры?

7. Когда в игре существует седловая точка?

8. Геометрическая интерпретация игры.

9. Схема решения игры.

10. Понятие смешанных стратегий, когда они необходимы, как применить их на практике.

11. Какие типы экономических задач сводятся к игровой модели?

Дата добавления: 2015-05-09