рефераты конспекты курсовые дипломные лекции шпоры

Раздел Философия
/
Геометрический метод решения задач теории игр

Реферат Курсовая Конспект

Выберите учебное заведение

Геометрический метод решения задач теории игр

Геометрический метод решения задач теории игр - раздел Философия, Конспект лекций По дисциплине Методы принятия управленческих решений Геометрический Метод Решения Игр С Нулевой Суммой Применяется...

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

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

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

Рассмотрим платежную матрицу


5	4	3	2	3
5	6	6
2	3	3	2	4

Упростим матрицу, вычеркивая заведомо невыгодные стратегии игроков, начиная с игрока А, а затем игрока В.

Путем упрощения, ее можно свести к матрице (2 * 2)

В_J А_J	В1	В2
A₁
A₂

р₁ - вероятность применения игроком А стратегии A₁;

р₂ - вероятность применения игроком А стратегии A₂.

Так как р₁+ р₂=1, то р₂=1- р₁. Тогда получим:

Чистые стратегии игрока В	Ожидаемые выигрыши игрока А
В1	4 р₁+3 р₂= (4-3)р₁+3=р₁+3
В2	2 р₁+5 р₂=(2-5)р₁+5=-3р₁+5

На оси Ох разместим точки р₁=0 и р₁=1, через которые проведем прямые, перпендикулярны оси Ох. Подставляя р₁=0 и р₁=1 в выражение р₁+3, найдем значения, которые отложим на соответствующих перпендикулярных прямых. Соединив эти точки, получим прямую.

Аналогично рассмотрим выражение -3р₁+5.

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

р₁+3 и -3р₁+5: р₁= р₂=0,5. S_A = (0,5; 0; 0,5; 0), при этом цена игры равна 3,5.

Для второго игрока оптимальная стратегия ищется аналогично.

Если же игра не сводится путем упрощения к 2 x n или m x 2, то составляется математическая модель и задача решается симплекс-методом.

8.3 Игры с « природой».

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

1. Критерий Вальда. Рекомендуется применять максиминную стратегию. Она достигается из условия max min α_ijи совпадает с нижней ценой игры.

j i

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

Рассмотрим задачу.

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

Если булочка не продана днем, то она м.б. реализована за 15 центов к концу дня. Свежие булочки продаются по 49 центов за штуку. Затраты магазина на одну булочку 25 центов.

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

Составим платежную матрицу. Сначала вычислим прибыль (49-25=24) и убыток (15-25=-10).


100*24	100*24	100*24	100*24	100*24
10024-5010	150*24	150*24	150*24	150*24
10024-10010	15024-5010	200*24	200*24	200*24
10024-15010	15024-10010	20024-5010	250*24	250*24
10024-20010	15024-15010	20024-10010	25024-5010	300*24

Платежная матрица примет вид

Вычислим критерий Вальда - максиминный. Он отражает принцип гарантированного результата:

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

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

Н = max min α_ij

j i

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

А₁
А₂
А₃
А₄
А₅

Критерий Вальда рекомендует выбирать стратегию А_1.

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

H = Max {γmin a_ij + (1- γ)max a_ij}

j i i

где γ - степень оптимизма - изменяется в диапазоне [0, 1].

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

Рассмотрим платежную матрицу.

Параметр Гурвица возьмем равным 0,6.

	min	max	γmin a_ij + (1- γ)max a_ij
А₁			24000.6+0.42400=2400
А₂			19000.6+36000.4=2580
А₃			14000.6+48000.4=2760
А₄			9000.6+60000.4=2940
А₅			4000.6+72000.4=3120

Критерий Гурвица рекомендует стратегию А₅.

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

Элементы матрицы рисков находится по формуле (r_ij):

r_ij = maxa_ij - a_ij

где maxa_ij - максимальный элемент в столбце исходной матрицы.

Оптимальная стратегия находится из выражения

H = Min {max(max a_ij - a_ij)}

Составим матрицу риска, (max a_ij - a_ij).

Выберем максимальный элемент в столбце и вычитаем из него остальные элементы столбца, получим max(max a_ij - a_ij).

						Мax
А₁
А₂
А₃
А₄
А₅

Из максимальных значений последнего столбца выбираем минимальную величину, получим Min {max(max a_ij - a_ij)}.

Критерий Сэвиджа рекомендует стратегию А₄.

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

H = Max {1/n·∑ a_ij}

где 1/n вероятность реализации одного из состояний р = 1/n.

А₁	(2400+2400+2400+2400+2400)/5=2400
А₂	(1900+3600+3600+3600+3600)/5=3260
А₃	(1400+3100+4800+4800+4800)/5=3780
А₄	(900+2600+4300+6000+6000)/5=3960
А₅	(400+2100+3800+5500+7200)/5=3800

Критерий Лапласа рекомендует нам стратегию А₄.

Таким образом, рассмотрев одну платежную матрицу, мы получили, что критерии Лапласа и Сэвиджа рекомендует стратегию А₄.То есть необходимый заказ булочек составит 250 единиц ежедневно.

5. Критерий Байеса. Принятие решения в условиях риска.

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

Выбор стратегии осуществляется по формуле

H = Max {∑p_i a_ij}

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



0,2	0,25	0,3	0,15	0,1

Подставив значение a_ij и p_i в формулу, получим:

А₁	24000,2+24000,25+24000,3+24000,15+2400*0,1=2400
А₂	19000,2+36000,25+36000,3+36000,15+3600*0,1=3260
А₃	14000,2+31000,25+48000,3+48000,15+4800*0,1=3695
А₄	9000,2+26000,25+43000,3+60000,15+6000*0,1=3620
А₅	4000,2+21000,25+38000,3+55000,15+7200*0,1=3290

Критерий Байеса рекомендует стратегию А₃

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

Оптимальные стратегии, выбранные по различным критериям, различны.

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

ПРИМЕР №1

Найти оптимальные стратегии 1-го игрока, исходя из различных критериев, в игре с полной неопределенностью относительно второго игрока, заданной платежной матрицей:

а₁₁ а₁₂ а₁₃ а₁₄5 10 18 25

а₂₁ а₂₂ а₂₃ а₂₄8 7 8 23

А = а₃₁ а₃₂ а₃₃ а₃₄; А = 21 18 12 21

а₄₁ а₄₂ а₄₃ а₄₄20 22 19 15

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Конспект лекций По дисциплине Методы принятия управленческих решений

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ... МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ...

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Линейного программирования
4.1.Постановка задачи.............................................................................. . 40 4.2.Алгоритм решения транспортных задач………………………….…... 42 4.2.1.Метод наим

Общие положения
Человек наделён сознанием, существо свободное и обречено на выбор решений, стараясь сделать всё наилучшим образом. Теория принятия

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

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

Общая постановка задачи
Линейное программирование — наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения.

Виды математических моделей ЛП
Математическая модель задачи ЛП может быть канонической и неканонической. Определение.Если все ограничения системы заданы уравнениями и п

Алгоритм геометрического метода решения задач ЛП.
Решение задач ЛП геометрическим методом осуществляется по следующему алгоритму: 1.Строим координатные оси Х1ОХ2 и с учетом коэффициентов математическо

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

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

Алгоритм симплексного метода
1.Математическую модель задачи привести к каноническому (стандартному) виду. 2. Построить начальную симплекс-таблицу исходя из стандартного вида. &

Стандартный вид
min (Z= -6x1-5x2-4x3-3x4) 2x1+3x2+2x3+x4+S1=25 4x1+x2+3x3+2x4+S2=30 3x1+5x2+2x3+2x4+S3=42 x1, x2, x3, x4, S1, S2, S3 > 0

Анализ решения
Продукции 1 вида производим 6,5 ед., второго вида 4 единицы, третьего и четвертого вообще не производим. Прибыль при этом составит 59 ден. единиц. Ресурс 1

Транспортной задачи.
Постановка задачи: Однородный груз сосредоточен у m поставщиков в объемах а1, а2, …, аm

Математическая модель транспортной задачи
Математическая модель транспортной задачи в общем виде имеет вид:

Метод наименьшего элемента.
1.Сбалансировать задачу (убедиться, что задача сбалансирована). 2.Определить свободную клетку с наименьшей стоимостью перевозки. Если таких клеток несколько, то выбрать кле

Метод потенциалов.
1.Для всех базисных клеток создать систему уравнений вида . Выбрать переменную

Решаем задачу по методу максимального элемента.
Составляем опорный план (табл. 2) Табл.2 Bj Ai П1 П2

Переходим к следующему плану.
Для клетки (1,5) с наименьшей оценкой (-5) строим цикл. Ставим в эту клетку коэффициент W со знаком «+» и применяя метод наибольшего элемента находим цикл, (табл. 2). Опреде

Математическая модель прямой задачи
при условии что,

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

Целочисленного программирования.
1.Построить систему координат x10х2 и выбрать масштаб. 2.Найти область допустимых решений (ОДР) системы ограничений задачи. 3.Построить целевую функцию, явля

Условие задачи.
Решить методом ветвей и границ задачу, имеющую следующую математическую модель.

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

Принцип оптимальности Беллмана.
Основным методом динамического программирования является метод рекуррентных соотношений; который основывается на использовании принципа оптимальности, разработанного американским математиком Р.Белл

Рассмотрим 2-й шаг.
Вклад Проект Остаток Прибыль из матрицы Прибыль за шаг Прибыль на шаге

Рассмотрим 1-й шаг.
Вклад Проект Остаток Прибыль из матрицы Прибыль за шаг Прибыль на шаге

Лекция . Управление производством . Управление запасами.
С течением времени любое оборудование изнашивается физически и морально, поэтому на каком-то этапе его эксплуатация становится менее выгодной, нежели приобретение

Второй месяц
S1 x2 S2 y2 φ(x2) ψ(y

Первый месяц
S0 x1 S1 y1 φ(x1) ψ(y1)

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

Решение.
1. Максиминный критерий Вальда. max min аij j i Вычислим минимальные знач

Критерий Гурвица.
Параметр Гурвица возьмем равным γ=0,6: H= max[γ min аij+(1- γ) max аij] j i i

Выбор стратегии в условиях риска (при наличии вероятностной информации).
В1 В2 В3 В4 n

I. Формулировка задачи и характеристики СМО
Часто приходится сталкиваться с такими ситуациями: очередь покупателей в кассах магазинов; колонна автомобилей, движение которых остановлено светофором; ряд станков, вышедших из строя и ожидающих р

СМО с отказами.
9.2.1 Основные понятия Заявка, поступившая в систему с отказами и нашедшая все каналы занятыми, получает отказ и покидает систему необслуженной. Показателем качества обслуживания выступает

Формулы для установившегося режима
1. Вероятность простоя каналов, когда нет заявок (k=0): P0=1 : {Σ ρк/к!+ρn+1/n!(n-ρ)[1-(ρ/n)m]}

Условный экстремум
Задача на минимум. Определить матрицы L и все ее главные миноры порядка больше чем m+1 должны иметь знак (-1)m, где m – число ог

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

СКЛАДСКАЯ ЗАДАЧА
Складская задача относится к динамическим детерминированным задачам управления запасами. Следовательно, для решения этой задачи можно применить принцип Беллмана. ЗАДАЧА 5.2

АНТАГОНИСТИЧЕСКИЕ ИГРЫ
ЗАДАЧА 6.1 Из платежной матрицы найти нижнюю и верхнюю цену игры. Упростить матрицу, решить графически. Данные в таблице 6.1

ТЕМА . СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ
ЗАДАЧА 7.1 Вариант 1. Дежурный по администрации города имеет 8 телефонов. Телефонные звонки поступают с интенсивностью 120 заявок в

Голосование - один из методов экспертных оценок
Голосование - один из методов принятия решения комиссией экспертов. Организация голосования, в частности, на собрании акционеров, имеет свои подводные камни. Многое зависит от регламента (т.е. прав

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

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

Принятие решений в условиях инфляции
Под инфляцией понимаем рост (изменение) цен [6]. При анализе экономических процессов, протяженных во времени, необходимо переходить к сопоставимым ценам. Это невозможно сделать без расчета индекса

В экономических расчетах при принятии решений
.Хорошо известно, что стоимость денежных единиц со временем меняется. Например, на один доллар США полвека назад можно было купить примерно в восемь раз больше материальных ценност

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