Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Prikl_mat_4_kurs / лекции исслед операц

.docx
Скачиваний:
54
Добавлен:
04.06.2015
Размер:
4.23 Mб
Скачать

ИГРЫ С ПРИРОДОЙ

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

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

Максиминный критерий Вальда (пессимистичный критерий).

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

Критерий максимакса.

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

Критерий Гурвица.

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

Критерий Сэвиджа (оптимистичный критерий).

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

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

, где

Математически критерий записывается так: .

Критерий Лапласа.

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

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

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

.

Максиминный критерий Вальда

, следовательно для выбора первому игроку рекомендуется вторая (т.к. полученная 3 стоит во второй строке) стратегия.

Критерий максимакса.

, следовательно для выбора первому игроку рекомендуется четвертая (т.к. полученная 10 стоит на 4 месте) стратегия.

Критерий Гурвица.

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

Критерий Сэвиджа

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

Тогда , следовательно для выбора первому игроку рекомендуется либо первая, либо четвертая (т.к. полученные 4 стоят на 1 и 4 месте) стратегии.

Критерий Лапласа.

, следовательно для выбора первому игроку рекомендуется либо вторая, либо четвертая (т.к. полученные стоят на 2 и 4 месте) стратегии.

  1. На предприятии имеется три группы станков, каждая из которых может выполнять пять операций по обработке деталей (операции могут выполняться в любом порядке). Максимальное время работы каждой группы станков равно 100, 250 и 180 часов соответственно. Время выполнения каждой операции составляет 100, 120, 70, 110 и 130 часов соответственно. Определить, сколько времени и на какой операции нужно использовать каждую группу станков, чтобы обработать максимальное количество деталей. Производительность каждой группы станков на каждой операции задана матрицей .

  2. Некоторая фирма решила выделить часть производственных мощностей своего завода для производства сезонных изделий в течение 4 месяцев. В течение первого месяца завод может произвести 50 изделий при спросе 100 изделий, оговоренном в контракте. В течение второго, третьего и четвертого месяцев эти цифры соответственно составят 180 и 200, 280 и 180, 270 и 300. В течение каждого месяца спрос можно удовлетворить за счет: а) избытка изделий, произведенных в предыдущие месяцы и хранящиеся на складе для реализации в будущем; б) за счет производства изделий в течение текущего месяца; в) избытка производства изделий в более поздние месяцы в счет невыполненных заказов. Затраты, связанные с производством одного изделия, составляют 4 единицы. Хранение одного изделия на складе в течение одного месяца обходятся в 0,5 единиц, а недопоставка одного изделия обходится предприятию в 2 единицы. Необходимо разработать план поставок готовой продукции покупателю, обеспечивающий минимальные затраты, связанные с реализацией проекта выпуска сезонных изделий в течение 4 месяцев.

  3. Сельхозпредприятие имеет возможность выращивать две культуры. Прибыль с/х предприятия при посеве первой культуры в засушливое лето 8 единиц, в нормальное лето 5 единиц, в дождливое лето 3 единицы; при посеве второй культуры в засушливое лето 2 единицы, в нормальное лето 3 единицы, в дождливое лето 6 единиц. Необходимо определить, как сеять эти культуры, если при прочих равных условиях их урожаи зависят от погоды, а план посева должен обеспечить наибольший доход. В зоне рискованного земледелия (а таковой явл-ся большая часть России) планирование посева должно осуществляться с учетом наименее благоприятного состояния погоды. Решение задачи написано от руки далее.

  4. Предположим, что сторона А посылает в расположение противника В 2 бомбардировщика. Один из них, заранее не известно какой, несет в расположение противника бомбу, а второй выполняет функцию сопровождения. Бомбардировщики подвергаются атаке истребителя стороны В. Если истребитель атакует второй бомбардировщик, то по нему ведут огонь пушки только этого бомбардировщика и поражают его с вероятностью 0,3. Если истребитель атакует первый бомбардировщик, то по нему ведут огонь пушки обоих бомбардировщиков и поражают его с вероятностью 0,51. Если истребитель не сбит огнем бомбардировщиков, то он поражает наземную цель с вероятностью 0,8. Задача бомбардировщиков – донести бомбу до цели, а задача истребителя – воспрепятствовать этому. Необходимо найти оптимальные стратегии игроков. . Решение задачи написано от руки далее.

  5. Ежедневный спрос на булочки в некотором магазине представляет собой дискретную случайную величину, принимающую значения 100, 120 и 130. Владелец магазина ограничен в выборе величины запаса булочек. Если он закупает больше, чем может продать, то должен реализовать излишек со скидкой в 0,55 единиц за каждую булочку. Сколько булочек ему следует закупать, если закупочная цена булочки 0,6 единиц, а отпускная 1,05 единиц?

Решенеие: Покупательский спрос на булочки выступает в качестве второго игрока.

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

спрос 100 булочек

Спрос 120 булочек

Спрос 130 булочек

Далее предлагается решить задачу самостоятельно.

  1. Руководство универмага заказывает товар. Известно, что спрос на данный вид товара лежит в пределах от 6 до 9 единиц. Если заказанного товара окажется недостаточно для удовлетворения спроса, то руководство может срочно заказать и завезти недостающее количество. Если же спрос будет меньше наличного количества товара, то нереализованный товар хранится на складе универмага. Требуется определить такой объем заказа на товар, при котором дополнительные затраты, связанные с хранением и срочным завозом, были бы минимальными, если расходы на хранение единицы товара составляют 1 млн руб, а по срочному заказу и завозу – 2 млн руб.

Решенеие: Покупательский спрос выступает здесь в качестве второго игрока, стратегиями которого является спрос. Поэтому у второго игрока будет по 4 стратегии: спрос на товар равен 6 единицам, равен 7 ед., равен 8 ед., равен 9ед. Но тогда у первого будет также 4 стратегии: заказать 6 ед. товара, 7 ед. товара, 8 ед. товара, 9 ед. товара.

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

справа указаны стратегии универмага

Спрос 6 ед. товара

Спрос 7 ед. товара

Спрос 8 ед. товара

Спрос 9 ед. товара

Итак, если, например, заказано 6 ед.товара, спрос 8 ед. товара, то универмагу срочно необходимо дозаказать 2 ед. товара, за каждую из которых надо доплатить по 2 млн. руб. Поэтому универмаг оказывается в убытке на 4 млн.руб, чему в матрице соответствует -4.

Применим к матрице критерии:

Максиминный критерий Вальда

, следовательно оптимальной для универмага является 3 стратегия – заказать 8 ед. товара.

Критерий Гурвица.

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

Критерий Сэвиджа

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

Тогда , следовательно для универмага оптимальной является 3 стратегия .

Критерий Лапласа.

, следовательно ля универмага снова оптимальной будет 3 стратегия.

  1. Предприятие производит 2 вида скоропортящейся продукции А и Б, которая должна реализовываться в день выпуска. Если же произведенная продукция в день выпуска не реализуется, то она продается на следующий день в 2 раза дешевле из-за снижения качества. Предыдущий опыт показал, что объемы реализации продукции зависят от состояния погоды. В хорошую погоду реализуется 500 единиц А и 300 единиц Б, а в плохую 2000 единиц А и 600 единиц Б. Себестоимость и отпускная цена А составляет 0,4 и 0,6ден.ед. соответственно, а Б – 0,25 и 0,4 ден.ед. Расходы на реализацию всей произведенной за день продукции составляют 100 ден.ед. Требуется найти оптимальное сочетание производства продукции, то есть определить ежедневный объем производства продукции каждого вида с целью получения наибольшей прибыли.

  2. С/х предприятие – поставщик скоропортящейся продукции на рынок – имеет 3 возможных варианта ее реализации: 1-ый – подвергать переработке для длительного хранения и последующей реализации; 2-й – отправить до реализации на временное хранение в холодильник; 3-й – сразу реализовать потребителю. Потребитель со своей стороны может: 1) затребовать продукцию в переработанном виде; 2) приобрести ее через некоторый небольшой промежуток времени; 3) приобрести всю продукцию сразу в свежем виде. Требуется найти оптимальное соотношение поставки продукции потребителю в свежем виде, после непродолжительного хранения, после переработки. Прибыль от реализации продукции в зависимости от поведения потребителя представлена в таблице:

Стратеги с/х предприятия

Стратегии потребителя

1

2

3

1

12

14

16

2

14

10

11

3

12

9

6

  1. Обувная фабрика планирует выпуск двух моделей обуви А и Б. Спрос на эти модели не определен, однако можно предположить, что он может принимать одно из двух состояний. В зависимости от этих состояний прибыль предприятия различна. Прибыль от производства модели А 52 и 22 ден.ед. соответственно, а от модели Б – 22 и 49 ден.ед. Найти оптимальное соотношение между объемами выпуска каждой из моделей, при котором предприятию гарантируется средняя величина прибыли при любом состоянии спроса.

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

Определим седловую точку ,

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

.

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

  1. Швейное предприятие планирует к массовому выпуску новую модель одежды. Спрос на эту модель не может быть точно определен. Однако можно предположить, что его величина характеризуется тремя возможными состояниями. С учетом этих состояний анализируются три возможных варианта выпуска данной модели. Каждый из этих вариантов требует своих затрат и обеспечивает в конечном счете различный эффект. Прибыль, которую получает предприятие при данном объеме выпуска модели и соответствующем состоянии спроса, определяется матрицей . Требуется найти объем выпуска модели одежды, обеспечивающий среднюю величину прибыли при любом состоянии спроса.

Решение: Определим седловую точку ,

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

  1. Для отопления помещения необходимо приобрести топливо. Однако расход топлива и цены на него зависят от погоды в зимнее время (мягкая, нормальная и суровая зима) см.таблицу. В настоящее время уголь может быть приобретен по минимальной цене 10ден.ед./т и излишекнеиспользованного угля можно реализовать весной по цене 5 ден.ед./т. Можно изб рать одну из трех стратегий в закупке угля: 5т, 10 т, 18 т. Определить оптимальную стратегию в образовании запасов угля; определить оптимальную стратегию в образовании запасов угля, если имеется 100 помещений для отапливания.

  2. Двое полицейских охраняют ювелирный магазин, в котором 2 отдела. Полицейские дежурят по одному в каждом отделе, причем один из них более опытный. Последнее означает, что для вора, забравшегося в тот отдел, где дежурит опытный, шанс уйти с добычей 1:4. От второго же он убежит с вероятностью 1:2. Допустим, что средний улов вора в первом отделе равен 20000 ден.ед., а во втором – 30000 ден.ед. Найти платежную матрицу с точки зрения вора и найти оптимальные стратегии обеих сторон.

СВЕДЕНИЕ ИГРЫ К ЗАДАЧЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Теория игр находится в тесной связи с линейным программированием. Так, каждая игра двух лиц с нулевой суммой может быть представлена как ЗЛП и решена СМ, и наоборот, каждая ЗЛП может быть сведена к игре.

Рассмотрим игру 2 лиц с нулевой суммой, заданную платежной матрицей:.

Будем считать, что матрица не имеет седловой точки. Тогда ищем решение игры в смешанных стратегиях. Пусть 1 игрок выбрал свою оптимальную смешанную стратегию. Она обладает тем свойством, что обеспечивает ему выигрыш, не меньший , при любом поведении противника. Если 2 игрок выбрал свою 1-ю стратегию, то выигрыш 1 игрока это 1 строка следующей системы, если 2 игрок выбрал свою 2-ю стратегию, то выигрыш 1 игрока – это 2 строка и т.д.

Разделим левые и правые части на . Введем обозначение . (*)

Тогда система примет вид:

Таким образом, получилась ЗЛП на min.

Аналогично можно получить и ЗЛП на max, проведя все рассуждения для 2 игрока. Можно найти решение одной из этих задач СМ, а решение другой задачи получить на основе теорем двойственности. Очевидно, что СМ удобнее решать ЗЛП на max.

Пример: Найти решение и цену игры, заданной матрицей .

Задача разрешима и в чистых стратегиях, но мы продемонстрируем, как ее решить как ЗЛП и сравним полученные рез-ты.

Запишем ЗЛП на max:

1

1

1

0

0

0

1

1

1

6

4

5

2

3

5

5

7

6

1

0

0

0

1

0

0

0

1

-1

-1

-1

3/5

2/5

1/5

4

1

1

1

13/5

17/5

6/5

-2/5

-3/5

1/5

1/5

1/5

1/5

Итак, получили оптимальное решение , . Но теперь необходимо вернуться к переменным p и q (вероятностям выбора игроками своих стратегий, см. (*)).

, .

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

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

Эквивалентная игра будет иметь матрицу .

Пример: Построить игру для ЗЛП .

Здесь , , . Тогда матрица игры имеет вид:

Пример: Построить игру для ЗЛП .

Здесь , , . Тогда матрица игры имеет вид: