минимакс и максимин что это

ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ МАКСИМИННОГО И МИНИМАКСНОГО ПРИНЦИПОВ ИГРЫ

Введение

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

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

Таким образом, проблема применения теории игр на практике в сфере экономике является на сегодняшний день важной и актуальной. Целью данной работы является рассмотрение решения задач в экономике с помощью метода теории игр. Предмет работы – принципы максимина и минимакса, объект исследования – теория игр в экономике. Задачи:

Исследование принципов максимина и минимакса

Наблюдение динамики решения задач: упрощается или усложняется экономическое решение с применением теории игр

Применение методов теории игр в экономике: рассмотреть конкретные примеры

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

Понятие игры. Максиминные и минимаксные решения.

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

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

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

Если игра содержит ограниченное количество стратегий, то такая игра называется конечной. В противном случае – бесконечной.

α = max(mina_ij), где α – гарантированный выигрыш (максимин).

Очевидно, что аналогично распределения можно провести и для конкурента В, который должен рассмотреть все свои стратегии, выделяя для каждой из них максимальные значения выигрыша:

β = min(maxaij), дает минимаксный выигрыш, или минимакс.

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

Если α = β = С, то число С называют чистой ценой игры или седловой точкой. Для игры с седловой точкой нахождение решения состоит в выборе пары максиминной и минимаксной стратегий, которые являются оптимальными, так как любое отклонение от этих стратегий приводит к уменьшению выигрыша первого игрока и увеличению проигрыша второго игрока по сравнению с ценой игры С.

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

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

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

Практическое применение теории игр в задачах моделирования экономических процессах

В условиях неопределенного покупательского спроса конфликтная ситуация товароснабжения формализуется матричной игрой. Пусть первый игрок — магазин, второй игрок — покупательский спрос. Каждый из игроков имеет по n стратегий. Завоз i-го товара — i-я. стратегия первого игрока, спрос на j-й товар — j-я стратегия второго игрока. Тогда матрица выигрышей первого игрока имеет вид квадратной матрицы n-го порядка:

Матрица игры имеет вид:

Составим платежную матрицу и найдем в ней максимин и минимакс

Следовательно, данная игра имеет седловую точку (2, 3) и задача разрешима в чистых стратегиях. Придерживаясь чисто второй стратегии, первый игрок обеспечивает себе выигрыш, не меньший 5; второй игрок, применяя чистую третью стратегию, проигрывает не более 5. Обе стратегии j = 2 и j = 3 являются оптимальными для первого и второго игроков, при этом цена игры V = 5.

Пусть, на основе анализа статистических данных за определенный период установлена функция потерь для возможных комбинаций состояний природы и решений ЛПР в виде матрицы игры А (Р_i,Q_i), в которой отрицательные значения показывают дополнительную прибыль, а положительные – потери: Q₁ Q₂

Если нет сведений о вероятностях различных состояний погоды, то по критерию Вальда и по критерию Сэвиджа оптимальной является стратегия Р₂. По критерию Гурвица при “коэффициенте пессимизма” q=1 оптимальной окажется стратегия Р₂, а при q=0 — стратегия Р₁.

Швейное предприятие, выпускающее детские платья и костюмы, реализует свою продукцию через фирменный магазин. Сбыт продукции зависит от состояния погоды. Но данным прошлых наблюдений предприятие в течении апреля — мая в условиях теплой погоды может реализовать 600 костюмов и 1975 платьев, а при прохладной погоде 1000 костюмов и 625 платьев. Известно, что затраты на единицу продукции в течение указанных месяцев составили для костюмов 27 руб., для платьев 8 руб., а цена реализации равна соответственно 48 руб. и 16 руб. (цифры условные).

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

Предприятие располагает в этих условиях двумя чистыми стратегиями: стратегия А — в расчете на теплую погоду и стратегия Б — в расчете на холодную погоду. Природу будим рассматривать как второго игрока также с двумя стратегиями: прохладная погода (стратегия В) и теплая погода (стратегия Г).

Следовательно, матрица данной игры (платежная матица) имеет вид:

Первая и вторая строки этой матрицы соответствуют стратегиям А и Б предприятия, а первый и второй стратегиям В и Г природы.

По платежной матрице видно, что первый игрок (предприятие) никогда не получит доход меньше 6800. Но если погодные условия совпадают с выбранной стратегией, то выручка (выигрыш) составит 26 000 или 28 400. Отсюда можно сделать вывод, что в условиях неопределенности погоды наибольший гарантированный доход предприятие обеспечит, если будет попеременно применять то А, то стратегию Б. Такая стратегия называется смешанной. Оптимизация смешанной стратегии позволит первому игроку всегда получать выигрыша независимо от стратегии второго игрока.

Следовательно, первый игрок, применяя чистые стратеги А и Б в соотношении 8:9, будет иметь оптимальную смешанную стратегию, обеспечивающую ему в любом случае средний доход в сумме: 6800-8/17 + 26000-9/17 16965 руб.; эта величина и будет в данном случае ценой игры.

Легко рассчитать, какое количество костюмов и платьев должно выпускать предприятие при оптимальной стратегии: (600 костюмов + 1975 платьев)*8/17 + (1000 костюмов + 625 платьев)*9/17 = 812 костюмов + 1260 платьев.

Следовательно, оптимальная стратегия предприятия заключи в выпуске 812 костюмов и 1260 платьев, что обеспечит три любой погоде средний доход в сумме 16 965 руб.

Заключение

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

снизить фактор сезонности в экономических процессах;

приведению формул и примеров расчетов;

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

моделированию спроса и потребления;

научному управлению запасами;

анализу сетевого планирования и управления;

аналитическому моделированию систем массового обслуживания;

принятию решений на основе теории игр.

Так как я в своей работе особое внимание уделила теории игр, то, после рассмотрения ее более подробно, и в этой конкретной области можно сделать определенные выводы. Здесь представлены, на мой взгляд, более актуальные задачи:

как получить набольшую выгоду или учет твоих интересов конкурентом, или поставщиком;

какой товар лучше производить и т.д.

Список используемой литературы

Математическое моделирование макроэкономических процессов / А.Н. Котов. – Л.: ЛГУ, 1980

Основы экономико-математического моделирования / Ю.Г. Семенов.1976

Экономико-математические методы / Л.Л. Терехов.– М.: Статистика–1972

Зенкевич Н.А., Петросян Л. А., Янг Д.В.К. Динамические игры и их приложения в менеджменте: учеб. Пособие / Н.А. Зенкевич, Л.А. Петросян, Д.В.К. Янг; Высшая школа менеджмента СпбГУ. — Спб.: Изд-во «Высшая школа менеджмента», 2009. — 415 с.

Лефевр Владимир Александрович, Смолян Георгий Львович Алгебра конфликта / Предисл. В.Н. Цыгичко. Изд. 5-е. М.: Книжный дом «ЛИБРОКОМ», 2013. — 72 с.

Источник

Минимакс

СОДЕРЖАНИЕ

Теория игр [ править ]

В целом игры [ править ]

Для каждого игрока i максимин не превышает минимакс:

В играх с нулевой суммой [ править ]

В контексте игр с нулевой суммой теорема о минимаксе эквивалентна: [4] [ неудачная проверка ]

Для каждой игры двух лиц с нулевой суммой и конечным числом стратегий существует значение V и смешанная стратегия для каждого игрока, такие что

(a) Учитывая стратегию игрока 2, наилучший возможный выигрыш для игрока 1 равен V, и (b) Учитывая стратегию игрока 1, наилучший возможный выигрыш для игрока 2 равен −V.

Пример [ править ]

Матрица выплат для игрока А

B выбирает B1	B выбирает B2	B выбирает B3
A выбирает A1	+3	−2	+2
A выбирает A2	−1	+ 0	+4
A выбирает A3	−4	−3	+1

Некоторые варианты выбора преобладают над другими и могут быть исключены: A не выберет A3, поскольку либо A1, либо A2 дадут лучший результат, независимо от того, что выберет B ; B не выберет B3, поскольку некоторые смеси B1 и B2 дадут лучший результат, независимо от того, что выберет A.

Максимин [ править ]

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

В повторяющихся играх [ править ]

Комбинаторная теория игр [ править ]

В комбинаторной теории игр существует минимаксный алгоритм игровых решений.

Алгоритм минимакс с альтернативными ходами [ править ]

Это можно расширить, если мы сможем предоставить функцию эвристической оценки, которая дает значения незавершенным игровым состояниям без учета всех возможных следующих полных последовательностей. Затем мы можем ограничить алгоритм минимакса, чтобы он смотрел только на определенное количество ходов вперед. Это число называется «упреждающим» и измеряется в « слоях ». Например, шахматный компьютер Deep Blue (который первым обошел действующего чемпиона мира Гарри Каспарова на тот момент) смотрел вперед как минимум на 12 уровней, а затем применил функцию эвристической оценки. [6]

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

Псевдокод [ править ]

Псевдокод для глубины ограничена минимаксного алгоритма приведен ниже.

Источник

МИНИМАКС

Полезное

Смотреть что такое «МИНИМАКС» в других словарях:

Минимакс — Минимакс правило принятия решений, используемое в теории игр, теории принятия решений, исследовании операций, статистике и философии для минимизации возможных потерь из тех, которые лицу, принимающему решение, нельзя предотвратить при… … Википедия

МИНИМАКС — (minimax) Наиболее низкое значение среди ряда цифр, каждая из которых найдена путем нахождения максимума среди некоторого дальнейшего ряда. Это понятие активно используется в теории игр. Предположим, что i возможных стратегий фирмы А, которая… … Экономический словарь

МИНИМАКС — (Fire extinguisher) см. Огнетушитель. Самойлов К. И. Морской словарь. М. Л.: Государственное Военно морское Издательство НКВМФ Союза ССР, 1941 … Морской словарь

Минимакс — Минимакс [minimax] в теории решений, теории игр (матричных) наименьший из всех максимальных элементов строк платежной матрицы. Критерий минимакса в игре двух лиц с нулевой суммой симметричен критерию максимина и также означает осторожный подход… … Экономико-математический словарь

минимакс — В теории решений, теории игр (матричных) наименьший из всех максимальных элементов строк платежной матрицы. Критерий минимакса в игре двух лиц с нулевой суммой симметричен критерию максимина и также означает осторожный подход игрока, выбирающего… … Справочник технического переводчика

минимакс — минимум максимума например: принцип минимакса … Словарь сокращений и аббревиатур

Минимакс — в математике, значение вещественной функции двух переменных f(x, у). С понятием М. связано понятие максимина, равного В теории антагонистических игр (См. Антагонистические игры) основным принципом… … Большая советская энциклопедия

МИНИМАКС — смешанный экстремум и т. п. (см. также Максимин);может интерпретироваться (напр., в теории принятия решений, исследовании операций или статистике) как наименьшие потери из тех, к рые нельзя предотвратить принимающему решения субъекту в наихудших… … Математическая энциклопедия

МИНИМАКС — смешанный экстремум ф ции f(x, у) двух переменных: Значение М. не меньше значения соответствующего максимина. Условия их равенства весьма важны в. игр теории … Большой энциклопедический политехнический словарь

минимакс — миним акс, а (матем.) … Русский орфографический словарь

Источник

Минимакс и максимакс

Найти минимакс и максимакс (определить нижнюю и верхнюю границы игры).

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

Игроки	B₁	B₂	B₃	B₄	a = min(Ai)
A₁	5	0	6	8	0
A₂	1	0	5	4	0
A₃	7	9	6	5	5
A₄	6	5	2	1	1
b = max(Bi )	7	9	6	8	0

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = 5, которая указывает на максимальную чистую стратегию A₃.
Верхняя цена игры b = min(b_j) = 6.
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 5 ≤ y ≤ 6. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).

2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.
Иногда на основании простого рассмотрения матрицы игры можно сказать, что некоторые чистые стратегии могут войти в оптимальную смешанную стратегию лишь с нулевой вероятностью.
Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если a_ij ≥ a_kj для всех jЭ N и хотя бы для одного j a_ij > a_kj. В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.
Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M a_ij ≤ a_il и хотя бы для одного i a_ij

Источник

Минимакс

СОДЕРЖАНИЕ

Теория игр [ править ]

В целом игры [ править ]

Для каждого игрока i максимин не превышает минимакс:

В играх с нулевой суммой [ править ]

В контексте игр с нулевой суммой теорема о минимаксе эквивалентна: [4] [ неудачная проверка ]

Для каждой игры двух лиц с нулевой суммой и конечным числом стратегий существует значение V и смешанная стратегия для каждого игрока, такие что

Пример [ править ]

Матрица выплат для игрока А

B выбирает B1	B выбирает B2	B выбирает B3
A выбирает A1	+3	−2	+2
A выбирает A2	−1	+ 0	+4
A выбирает A3	−4	−3	+1

Максимин [ править ]

В повторяющихся играх [ править ]

Комбинаторная теория игр [ править ]

В комбинаторной теории игр существует минимаксный алгоритм игровых решений.

Алгоритм минимакс с альтернативными ходами [ править ]

Псевдокод [ править ]

Псевдокод для глубины ограничена минимаксного алгоритма приведен ниже.

Источник