Оренбургский государственный аграрный университет
Кафедра организации производства и моделирования экономических систем
Реферативно-прикладное исследование
на тему:
"Практическое применение теории игр"
Оренбург – 2006г.
Содержание
Введение
I.Теоретические основы методов программирования
1. Динамическое программирование
2. Теория игр
3. Сетевое планирование и управление
4. Моделирование систем массового обслуживания
II. Практическое применение теории игр в задачах моделирования экономических процессах
Заключение
Список литературы
Введение
Целью данного реферативного исследования является рассмотрение решения задач с помощью методов: динамического программирования, теории игр, сетевого планирования и управления и моделирование систем массового обслуживания. Актуальность данной работы заключается в том, что с помощью этих методов можно облегчить условия труда современному человеку. В приведенной ниже работе можно найти способы решения задач, которые часто встречаются в нашем обиходе: например, для менеджера предприятия, для бухгалтеров, для отдела потребления и т.д.
Особое внимание в данной работе уделено фактору сезонности в экономических процессах, приведения формул и примеров расчетов. Некоторые модели посвящены рассмотрению ряда прикладных задач маркетинга, менеджмента и других областей управления в экономике: моделирование спроса и потребления, научное управление запасами, аналитическое моделирование систем массового обслуживании, принятие решений на основе теории игр.
На моделях связанных с теорией игр я решила остановиться более подробно, так как там представлены, на мой взгляд, более актуальные задачи: как сделать так, чтобы природа работала на тебя, а не ты на неё, как получить набольшую выгоду или учет твоих интересов конкурентом, или поставщиком, какой товар лучше производить и т.д.
I
. Теоретические основы методов программирования
1. Динамическое программирование
Динамическое программирование — один из разделов оптимального программирования, в котором процесс принятия решения и управления может быть разбит на отдельные этапы (шаги).
Экономический процесс является управляемым, если можно влиять на ход его развития. Под управлением понимается совокупность решений, принимаемых на каждом этапе для решений, принимаемых на каждом этапе для влияния на ход развития процесса. Например, выпуск продукции предприятием – управленческий процесс. Совокупность решений принимаемых в начале года (квартала и т.д.) по обеспечению предприятия сырьем, замене оборудования, финансированию и т.д., является управлением. Необходимо организовать выпуск продукции так, чтобы принятые решения на отдельных этапах способствовали получению максимально возможного объема продукции или прибыли.
Динамическое программирование позволяет свести одну сложную задачу со многими переменными ко многим задачам с малым числом переменных. Это значительно сокращает объем вычислений и ускоряет процесс принятия управленческого решения.
При решении задачи этим методом процесс решения расчленяется на этапы, решаемые последовательно во времени и приводящие, в конечном счете, к искомому решению. Типичные особенности многоэтапных (многошаговых) задач, решаемых методом динамического программирования, состоят в следующем:
Процесс перехода производственно-экономической системы из одного состояния в другое должен быть марковским (процессом с отсутствием последействия). Это значит, что если система находится в некотором состоянии Sn
Sn
, то дальнейшее развитие процесса зависит только от данного состояния и не зависит от того, каким путем система приведена в это состояние.
Процесс длится определенное число шагов N. На каждом шаге осуществляется выбор одного управления un
, под воздействием, которого система переходит из одного состояния Sn
в другое Sn
+1
:Sn
Sn
+1
. Поскольку процесс марковский, то Sn
= un
(Sn
) зависит только от текущего состояния.
Каждый шаг (выбор очередного решения) связан с определенным эффектом, который зависит от текущего со стояния и принятого решения: (Sn
, Sn
).
Общий эффект (доход) за N шагов слагается из доходов на отдельных шагах, т.е. критерий оптимальности дол жен быть аддитивным (или приводящимся к нему).
Требуется найти такое решение un
для каждого шага (n = 1, 2, 3, ..., N), т.е. последовательность (u1
, ..., uN
), чтобы получить максимальный эффект (доход) за N шагов.
В отличие от линейного программирования, в котором симплексный метод является универсальным методом решения, в динамическом программировании такого универсального метода не существует. Одним из основных методов динамического программирования является метод рекуррентных соотношений, который основывается на использовании принципа оптимальности, разработанного американским математиком Р. Беллманом. Принцип состоит в том, что, каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому придет система в конце данного шага. Использование данного принципа гарантирует, что управление, выбранное на любом шаге; не локально лучше, а лучше с точки зрения процесса в целом.
В некоторых задачах, решаемых методом динамического программирования, процесс управления разбивается на шаги. При распределении на несколько лет ресурсов деятельности предприятия шагом целесообразно считать временной период; при распределении средств между предприятиями — номер очередного предприятия. В других задачах разбиение на шаги вводится искусственно. Например, непрерывный управляемый процесс можно рассматривать как дискретный, условно разбив, его на временные отрезки (шаги). Исходя из условий каждой конкретной задачи, длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений.
Любая возможная допустимая последовательность решений (u1
, ..., uN
) называется стратегией управления
. Стратегия управления, доставляющая максимум критерию оптимальности, называется оптимальной
.
В основе общей концепции метода ДП лежит принцип оптимальности
Беллмана
:
Оптимальная стратегия обладает таким свойством, что независимо от того, каким образом система оказалась в рассматриваемом конкретном состоянии, последующие решения должны составлять оптимальную стратегию, привязывающуюся к этому состоянию. Математически этот принцип записывается в виде рекуррентного соотношения ДП (РДП):
,
где — все допустимые управления при условии, что система находится в состоянии Sn
;
(Sn
, Sn
) — эффект от принятия решения un
;
— эффект за оставшиеся n шагов.
Благодаря принципу оптимальности удается при последующих переходах испытывать не все возможные варианты, лишь оптимальные выходы. РДП позволяют заменить трудоёмкое вычисление оптимума по N переменным в исходной задаче решением N задач, в каждой из которых оптимум годится лишь по одной переменной.
Имеется очень много практически важных задач, которые ставятся и решаются как задачи ДП (задачи о замене оборудования, о ранце, распределения ресурсов и т.д.)
В качестве примера построения РДП рассмотрим использование принципа оптимальности для реализации математической модели задачи оптимального распределения некоторого ресурса в объеме х:
где xj
— количество ресурса, используемое j-м способом;
— доход от применения способа j, j = 1, N .
Рекуррентные соотношения, с помощью которых находится решение этой задачи, имеют вид:
2.
Теория игр
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные цели; это особенно характерно в условиях рыночной экономики. Такого рода ситуации называются конфликтными.
Математической теорией конфликтных ситуаций является теория игр
. В игре могут сталкиваться интересы двух (игра парная
) или нескольких (игра множественная
) противников; существуют игры с бесконечным множеством игроков. Если во множественной игре игроки образуют коалицию, то игра называется коалиционной
; если таких коалиций две, то игра сводится к парной.
На промышленных предприятиях теория игр может применяться для выбора оптимальных решений, например, при создании рациональных запасов сырья, материалов, полуфабрикатов, когда противоборствуют две тенденции: увеличение запасов, гарантирующих бесперебойную работу производства, сокращения запасов в целях минимизации затрат на их хранение. В сельском хозяйстве теория игр может применяться при решении таких экономических задач, как посева одной из возможных культур, урожай которой зависит от погоды, если известны цена единицы той или иной культуры и средняя урожайность каждой культуры в зависимости от погоды (например, будет ли лето засушливы, нормальным или дождливым); в этом случае одним выступает сельскохозяйственное предприятие, стремящееся обеспечить наибольший доход, а другим — природа.
Решение подобных задач требует полной определенности формулировании их условий (правил игры
); установления количества игроков, выявления возможных стратегий игроков, возможных выигрышей (проигрыш понимается как отрицательный выигрыш). Важным элементом в условии игровых задач является стратегия
, т.е. совокупность правил, которые в зависимости от ситуации в игре определяют однозначный выбор действий данного игрока. Если в процессе игры игрок применяет попеременно несколько стратегий, то такая стратегия называется смешанной
, а ее элементы — чистыми
стратегиями. Количество стратегий у каждого игрока может быть конечным и бесконечным, в зависимости от этого игры подразделяются на конечные
и бесконечные
.
Важными являются понятия оптимальной стратегии
, цены игры, среднего выигрыша
. Эти понятия находят отражение в определении решения
игры: стратегии Р* и Q* первого и второго игрока соответственно называются их оптимальными стратегиями
, а число V — ценой игры
, если для любых стратегий Р первого игрока и любых стратегий Q выполняются неравенства: где М (Р,Q) означает математическое ожидание выигрыши (средней выигрыш) первого игрока, если первым и вторым игроками избраны соответственно стратегии Р и Q.
Из неравенств следует, в частности, что V = M (P*
,Q*
),т.е. цена игры равна математическому ожиданию выигрыша первого игрока, если оба игрока изберут оптимальные для себя стратегии.
Одним из основных видов игр являются матричные игры
, которыми называются парные игры с нулевой суммой
(один игрок выигрывает столько, сколько проигрывает другой) при условии, что каждый игрок имеет конечное число стратегий. В этом случае парная игра формально задается матрицей А = (аij
), элементы которой аij
определяют выигрыш первого игрока (и соответственно проигрыш второго), если первый игрок выберет i-ю стратегию (i = ), а второй —j-ю стратегию (j = ). Матрица А называется матрицей игры
, или платежной матрицей
.
Существует ряд методов решения матричных игр. Если матрица игры имеет одну из размерностей, равную двум (у одного из игроков имеется только две стратегии), то решение игры может быть получено графически. Известно несколько методов приближенного решения матричной игры, например, метод Брауна. Во многих игровых задачах в сфере экономики неопределенность вызвана не сознательным противодействием противника, а недостаточной осведомленностью об условиях, в которых действуют стороны.
Когда одной из сторон выступает природа, когда неизвестно заранее погода, игры называются – играми с природой
. В этих случаях строки матрицы игры соответствуют стратегии игрока, а столбцы — состояниям «природы». В ряде случаев при решении такой игры рассматривают матрицу рисков
.
При решении игр с природой используется так же ряд критериев: критерий Сэвиджа, критерий Вальда, критерий Гурвица и др.
При максимальном критерии Вальда
оптимальным считается та стратегия лица, принимающего решение, которая обеспечивает максимум минимального выигрыша; применяя этот критерий, ЛПР в большей степени ориентируется на наихудшие условия (этот критерий иногда называют критерием «крайнего пессимизма»).
Критерий минимаксного риска Сэвиджа
предполагает,
что оптимальной является та стратегия, при которой величина риска в наихудшем случае минимальна.
При использовании критерия «пессимизм — оптимизма” Гурвица
ЛПР выбирает некоторый так называемый “коэффициент пессимизма» q; при q = 1 критерий Гурвица приводится к критерию Вальда («крайнего пессимизма»), а при критерию q=0 «крайнего оптимизма».
3.
Модели сетевого планирования и управления
Сетевой моделью (другие названия: сетевой график, сеть
) называется экономико-математическая модель, отражающая комплекс работ (операций) и событий, связанных с реализацией некоторого проекта (научно-исследовательского, производственного и др.), в их логической и технологической последовательности и связи. Анализ сетевой модели, представленной в графической или табличной (матричной) форме, позволяет, во-первых, более четко выявить взаимосвязи этапов реализации проекта и, во-вторых, определить наиболее оптимальный порядок выполнения этих этапов в целях, например, сокращения сроков выполнения всего комплекса работ. Таким образом, методы сетевого моделирования относятся к методам принятия оптимальных решений.
Математический аппарат сетевых моделей базируется на теории графов.
Графом
называется совокупность двух конечных множеств: множества точек, которые называются вершинами, и множества пар вершин, которые называются ребрами. Если рассматриваемые пары вершин являются упорядоченными, т. е. на каждом ребре задается направление, то граф называется ориентированным
; в противном случае — неориентированным.
Последовательность неповторяющихся ребер, ведущая от некоторой вершины к другой, образует путь
. Граф называется связным
, если для любых двух его вершин существует путь, их соединяющий; в противном случае граф называется несвязным
. В экономике чаще всего используются два вида графов: дерево и сеть. Дерево
представляет собой связный граф без циклов, имеющий исходную вершину (корень) и крайние вершины; пути от исходной вершины к крайним вершинам называются ветвями
. Сеть
— это ориентированный конечный связный граф, имеющий начальную вершину (источник
) и конечную вершину (сток
). Таким образом, сетевая модель представляет собой граф вида «сеть».
В экономических исследованиях сетевые модели возникают при моделировании экономических процессов методам сетевого планирования и управления (СПУ).
Объектом управления в системах сетевого планирования и управления являются коллективы исполнителей, располагающих определенными ресурсами и выполняющих определенный комплекс операций, который призван обеспечить достижение намеченной цели, например, разработку нового изделия, строительства объекта и т.п.
Основой СПУ является сетевая модель (СМ), в которой моделируется совокупность взаимосвязанных работ и событий отображающих процесс достижения определенной цели. Она может быть представлена в виде графика или таблицы.
Основные понятия СМ: событие, работа и путь. На рисунке графически представлена СМ, состоящая из 11 событий и 16 работ, продолжительность выполнения которых указана над работами.
Работа характеризует материальное действие, требующее использования ресурсов, или логическое, требующее взаимосвязи событий. При графическом представлении работа изображается стрелкой, которая соединяет два события. Она обозначается парой заключенных в скобки чисел (i, j), где i - номер события, из которого работа выходит, а j – номер события, в которое она входит. Работа не может начаться раньше, чем свершится событие, из которого она выходит. Каждая работа имеет определенную продолжительность t (i, j). Например, запись t (2,5) = 4 означает, что работа имеет продолжительность 5 единиц. К работам относятся такие процессы, которые не требуют ни ресурсов, ни времени выполнения. Они заключаются в установлении логической взаимосвязи работ и показывают, что одна из них непосредственно зависит от другой; такие работы называются фиктивными и на графике изображаются пунктирными стрелками.
Рис. Сетевая модель
Событиями называются результаты выполнения одной или нескольких работ. Они не имеют протяженности во времени. Событие свершается в тот момент, когда оканчивается последняя из работ, входящая в него. События обозначаются одним числом и при графическом представлении СМ изображаются кружком (или иной геометрической фигурой), внутри которого проставляется его порядковый номер (i = 1, 2, ..., N). В СМ имеется начальное событие (с номером 1), из которого работы только выходят, и конечное событие (с номером N), в которое работы только входят.
Путь — это цепочка следующих друг за другом работ, соединяющих начальную и конечную вершины, например, в приведенной выше модели путями являются L1
= (1, 2, 3, 7, 10, 11), L2
= (1, 2, 4, 6, 11) и др. Продолжительность пути определяется суммой продолжительностей составляющих его работ. Путь, имеющий максимальную длину, называют критическим
и обозначают Lкр
, а его продолжительность — tкр
. Работы, принадлежащие критическому пути, называются критическими. Их несвоевременное выполнение ведет к срыву сроков всего комплекса работ.
СМ имеют ряд характеристик, которые позволяют определить степень напряженности выполнения отдельных работ, а также всего их комплекса и принять решение о перераспределении ресурсов. Однако перед расчетом СМ следует убедиться, что она удовлетворяет следующим основным требованиям:
1. События правильно пронумерованы, т. е. для каждой работы (i,j) i <j (см. на рис. работы (4,3) и (3,2)). При невыполнении этого требования необходимо использовать алгоритм перенумерации событий, который заключается в следующем:
нумерация событий начинается с исходного события, которому присваивается № 1;
из исходного события вычеркивают все исходящие из него работы (стрелки), и на оставшейся сети находят событие, в которое не входит ни одна работа, ему и присваивают № 2;
затем вычеркивают работы, выходящие из события № 2, и вновь находят событие, в которое не входит ни одна работа, и ему присваивают № 3, и так продолжается до завершающего события, номер которого должен быть равен количеству событий в сетевом графике;
если при очередном вычеркивании работ одновременно несколько событий не имеют входящих в них работ, то их нумеруют очередными номерами в произвольном порядке.
2. Отсутствуют тупиковые события (кроме завершающего), т. е. такие, за которыми не следует хотя бы одна работа (событие 5);
3. Отсутствуют события (за исключением исходного), которым не предшествует хотя бы одна работа (событие 7);
4. Отсутствуют циклы, т. е. замкнутые пути, соединяющие событие с ним же самим (см. путь (2,4,3)).
При невыполнении указанных требований бессмысленно приступать к вычислениям характеристик событий, работ и критического пути. Для событий рассчитывают три характеристики: ранний и поздний срок совершения события, а также его резерв.
Ранний срок
свершения события определяется величиной наиболее длительного отрезка пути от исходного до рассматриваемого события, причем tp
(N)= tкр
(L):
Поздний срок
свершения события характеризует самый поздний допустимый срок, к которому должно совершиться событие, не вызывая при этом срыва срока свершения конечного события:
Этот показатель определяется «обратным ходом», начиная с завершающего события, с учетом соотношения t.п
(N) = tp
(N). Все события, за исключением событий, принадлежащих критическому пути, имеют резерв R(i):
Полный резерв времени показывает, на сколько можно увеличить время выполнения конкретной работы при условии, что срок выполнения всего комплекса работ не изменится.
Независимый резерв времени соответствует случаю, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие — начинаются в ранние сроки. Использование этого резерва не влияет на величину резервов времени других работ.
Путь характеризуется двумя показателями — п
4.
Моделирование систем массового обслуживания
Многие экономические задачи связаны с системами массового обслуживания (СМО), т. е. такими системами, в которых, с одной стороны, возникают массовые запросы (требования) на выполнение каких-либо услуг, с другой — происходит удовлетворение этих запросов. СМО включает в себя следующие элементы: источник требований, входящий поток требований, очередь, обслуживающие устройства (каналы обслуживания), выходящий поток требований. Исследованием таких систем занимается теория массового обслуживания.
Методами теории массового обслуживания могут быть решены многие задачи исследования процессов, происходящих в экономике. Так, в организации торговли эти методы позволяют определить оптимальное количество торговых точек данного профиля, численность продавцов, частоту завоза товаров и другие параметры. Другим характерным примером систем массового обслуживания могут служить склады или базы снабженческо-сбытовых организаций, и задача теории массового обслуживания в данном случае сводится тому, чтобы установить оптимальное соотношение между числом поступающих на базу требований на обслуживание и числом обслуживающих устройств, при котором суммарные расходы на обслуживание и убытки от простоя транспорта были бы минимальными. Теория массового обслуживания может найти применение и при расчете площади складских помещений, при этом складская площадь рассматривается как обслуживающее устройство, а прибытие транспортных средств под выгрузку — как требования. Модели теории массового обслуживания применяются также при решении ряда задач организации и нормирования труда, других социально-экономических проблем.
Системы массового обслуживания могут быть классифицированы по ряду признаков.
1. В зависимости от условий ожидания начала обслуживания различают:
• СМО с потерями (отказами),
• СМО с ожиданием.
В СМО с отказами требования, поступающие в момент, когда все каналы обслуживания заняты, получают отказ и теряются. Классическим примером системы с отказами является телефонная станция. Если вызываемый абонент занят, то требование на соединение с ним получает отказ и теряется.
В СМО с ожиданием требование, застав все обслуживающие каналы занятыми, становится в очередь и ожидает, пока не освободится один из обслуживающих каналов.
СМО, допускающие очередь, но с ограниченным числом требований в ней, называются системами с ограниченной длинной очереди.
СМО, допускающие очередь, но с ограниченным сроком пребывания каждого требования в ней, называются системами с ограниченным временем ожидания.
2. По числу каналов обслуживания СМО делятся на:
одноканальные;
многоканальные.
3. По месту нахождения источника требований МО делятся на:
- разомкнутые, когда источник требования находится вне системы;
- замкнутые, когда источник находится в самой системе.
Примером разомкнутой системы может служить ателье по ремонту телевизоров. Здесь неисправные телевизоры — это источник требований на их обслуживание, находятся вне самой системы, число требований можно считать неограниченным. К замкнутым СМО относится, например, станочный участок, в котором станки являются источником неисправностей, а следовательно, источником требований на их обслуживание, например, бригадой наладчиков
Возможны и другие признаки классификации СМО, например, по дисциплине обслуживания, однофазные и многофазные СМО и др.
Методы и модели, применяющиеся в теории массового обслуживания, можно условно разделить на аналитические имитационные.
Аналитические методы теории массового обслуживания позволяют получить характеристики системы как некоторые функции параметров её функционирования. Благодаря этому появляется возможность проводить качественный анализ влияния отдельных факторов на эффективность работы СМО. Имитационные методы основаны на моделировании процессов массового обслуживания на ЭВМ и применяются, если, невозможно применение аналитических моделей. Далее будем рассматривать аналитические метод моделирования СМО.
В настоящее время теоретически наиболее разработаны и удобны в практических приложениях методы решения таких задач массового обслуживания, в которых входящий поток требований является простейшим (пуассоновским).
Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона, т.е. вероятность поступления за время t ровно k требований задается формулой:
Простейший поток обладает тремя основными свойств ординарности, стационарности и отсутствием последствия.
Ординарность потока означает практическую невозможность одновременного поступления двух и более требований. Например, достаточно малой является вероятность того, что из группы станков, обслуживаемых бригадой ремонтников, одновременно выйдут из строя сразу несколько станков.
Стационарным называется поток, для которого математическое ожидание числа требований, поступающих в систему в единицу времени (обозначим ), не меняется во времени. Таким образом, вероятность поступления в систему определенного количества требований в течение заданного промежутка времени t зависит от его величины и не зависит от начала его отсчета на оси времени.
Отсутствие последействия означает, что число требований, поступивших в систему до момента t, не определяет того сколько требований поступит в систему за промежуток времени от t до t+t.
Важная характеристика СМО — время обслуживания требований в системе. Время обслуживания одного требования является, как правило, случайной величиной и, следовательно, может быть описано законом распределения. Наибольшее распространение в теории и особенно в практических приложениях получил экспоненциальный закон распределения
времени обслуживания. Функция распределения для этого она имеет вид:
т.е. вероятность того, что время обслуживания не превосходит некоторой величины t, определяется формулой, где — параметр экспоненциального закона распределения времени обслуживания требований в системе, т.е. величина, обратная среднему времени обслуживания :
Рассмотрим аналитические модели наиболее распространенных СМО с ожиданием, т.е. таких СМО, в которых требования, поступившие в момент, когда все обслуживающие каналы заняты, ставятся в очередь и обслуживаются по мере освобождения каналов.
Общая постановка задачи состоит в следующем. Система имеет n обслуживающих каналов, каждый из которых может одновременно обслуживать только одно требование.
В систему поступает простейший (пуассоновский) поток лини с параметром . Если в момент поступления очередного требования в системе на обслуживании уже находится не меньше n требований (т.е. все каналы заняты), то это требование становится в очередь и ждет начала обслуживания.
Время обслуживания каждого требования — случайная величина, которая подчиняется экспоненциальному закону распределения с параметром .
СМО с ожиданием можно разбить на две большие группы: замкнутые и разомкнутые. К замкнутым относятся системы, в которых поступающий поток требований возникает в самой системе и ограничен.
Если питающий источник обладает бесконечным числом требований, то системы называются разомкнутыми. Отмеченные особенности функционирования этой системы. Расчет характеристик работы СМО различного вида может быть проведен на основе расчета вероятностей состояний СМО (так называемы формулы Эрланга).
Рассмотрим алгоритмы расчета показателей качества функционирования разомкнутой системы массового обслужит с ожиданием.
При изучении таких систем рассчитывают различны показатели эффективности обслуживающей системы. В качестве основных показателей могут быть вероятность того, что все каналы свободны или заняты, математическое ожидание длины очереди (средняя длина очереди), коэффициент занятости и простоя каналов обслуживания и др.
Введем в рассмотрение параметр . Заметим, что если , то очередь не может расти безгранично. Это условие имеет следующий смысл: — среднее число требований, поступающих за единицу времени, -время обслуживания одним каналом одного требования. Тогда — среднее число каналов, которое необходимо иметь, чтобы обслуживать в единицу времени все поступившие требования. Поэтому условие < 1 означает, что число обслуживающих каналов должно быть больше числа каналов, необходимых для того, чтобы за единицу времени обслужить все поступившие требования. Важнейшие характеристики работы СМО:
1. Вероятность того, что все обслуживающие каналы свободны
2. Вероятность того, что занято ровно k обслуживающих каналов при условии, что общее число требований, находятся на обслуживании, не превосходит числа обслуживающих аппаратов:
Po
где
3. Вероятность того, что в системе находится k требований в случаи, когда их число больше числа обслуживающих каналов:
где
4. Вероятность того, что все обслуживающие каналы заняты:
5.Среднее время ожидания требованием начала обслуживания в системе:
6.Средняя длина очереди:
7.Среднее число свободных от обслуживания каналов:
8.Коэффициент простоя каналов:
.
9.Среднее число занятых обслуживанием каналов:
10.Коэффициент загрузки каналов:
Перейдем к рассмотрению алгоритмов расчета характеристик функционирования замкнутых СМО. Поскольку система замкнутая, то к постановке задачи следует добавить условие: поток поступающих требований ограничен, т.е. в системе обслуживания одновременно не может находиться больше m требований (m — число обслуживаемых объектов).
За критерий, характеризующий качество функционирования рассматриваемой системы, выберем отношение средней длины очереди к наибольшему числу требований, находящихся одновременно в обслуживающей системе — коэффициент простоя обслуживаемого объекта. В качестве другого критерия возьмем отношение среднего числа незанятых обслуживающих каналов к их общему числу — коэффициент простоя обслуживаемого канала.
Первый из названных критериев характеризует потери времени из-за ожидания начала обслуживания; второй показывает полноту загрузки обслуживающей системы.
Очевидно, что очередь может возникнуть, лишь когда число каналов меньше наибольшего числа требований, находящихся одновременно в обслуживающей системе (n < m).
Приведем последовательность расчетов характерней замкнутых СМО и необходимые формулы.
1. Определим параметр — показатель загрузки системы, т.е. математическое ожидание числа требований поступающих в систему за время, равное средней длительности обслуживания ( ).
2. Вероятность того, что занято k обслуживающих каналов при условии, что число требований, находящихся в системе не превосходит числа обслуживающих каналов системы:
3. Вероятность того, что в системе находится k требований для случая, когда их число больше числа обслуживающих каналов:
4. Вероятность того, что все обслуживающие каналы свободны, определим, используя очевидное условие:
, откуда .
Величину Ро
можно получить также путем подстановки в равенство значения , в которых Ро
вводит сомножителем. Подставляя их, получаем следующее уравнение для определения Ро
:
,
откуда
5.Среднее число требований, ожидающих начала обслуживания (средняя длина очереди),
или
.
6.Коэффициент простоя обслуживаемого требования ( объекта)
.
7. Среднее число требований, находящихся в обслуживающей системе, обслуживаемых и ожидающих обслуживания:
или
8.Среднее число свободных обслуживающих каналов
.
9.Коэффициент простоя обслуживающего канала:
II
. Практическое применение теории игр в задачах моделирования экономических процессах
Пример №1
На базе торговой фирмы имеется n типов товара ассортиментного минимума. В магазин фирмы должен быть завезен только один из этих типов товара. Если товар типа j будет пользоваться спросом, то магазин от его реализации получит прибыль . Если же этот товар не будет пользоваться спросом, то издержки на его хранение принесут магазину убыток .Требуется выбрать тип товара, который целесообразно завезти в магазин.
В условиях неопределенного покупательского спроса конфликтная ситуация товароснабжения формализуется матричной игрой. Пусть первый игрок — магазин, второй игрок — покупательский спрос. Каждый из игроков имеет по n стратегий. Завоз i-го товара — i-я. стратегия первого игрока, спрос на j-й товар — j-я стратегия второго игрока. Тогда матрица выигрышей первого игрока имеет вид квадратной матрицы n-го порядка:
Пример №2
Матрица игры имеет вид:
Минимальный элемент первой строки (первой стратегии первого игрока) равен 2, второй — 5, третьей — 4; максимальное значение из этих величин равно 5. Максимальный элемент первого столбца (первой стратегии второго игрока) равен 10, второго — 10; третьего — 5, четвертого — 14, пятого — 12; минимальное значение из них равно 5. Следовательно, данная игра имеет седловую точку (2, 3) и задача разрешима в чистых стратегиях. Придерживаясь чисто второй стратегии, первый игрок обеспечивает себе выигрыш, не меньший 5; второй игрок, применяя чистую третью стратегию, проигрывает не более 5. Обе стратегии j = 2 и j = 3 являются оптимальными для первого и второго игроков, при этом цена игры V = 5.
Пример №3
Диспетчер автобусного парка (ЛПР) в месяцы в конце каждой недели должен принять решение о целесообразности выделения дополнительных автобусов на загородный маршрут. ЛПР имеет три варианта решений: увеличить количество автобусов на 10 (стратегия ) увеличить это количество на 5 (стратегия Р2
) или оставить без изменения обычное число автобусов на линии (стратегия Р3
). Возможны два состояния погоды: —Q1
плохая погода,Q2
- хорошая погода, причем в момент принятия решения нет возможности определить ожидаемое состояние погоды. Если в выходные дни будет хорошая погода и много желающих выехать за город, а выделено мало автобусов, то парк понесет убытки, связанные с недополученной прибылью. Если же выделены дополнительные автобусы, а погода окажется плохой, то возникнут потери вследствие эксплуатации незаполненных автобусов.
Пусть, на основе анализа статистических данных за определенный период установлена функция потерь для возможных комбинаций состояний природы и решений ЛПР в виде матрицы игры А (Рi
,Qi
), в которой отрицательные значения показывают дополнительную прибыль, а положительные – потери:
Q1
Q2
Если нет сведений о вероятностях различных состояний погоды, то по критерию Вальда и по критерию Сэвиджа оптимальной является стратегия Р2
. По критерию Гурвица при “коэффициенте пессимизма” q=1 оптимальной окажется стратегия Р2
, а при q=0 — стратегия Р1
.
Пример №4
Швейное предприятие, выпускающее детские платья и костюмы, реализует свою продукцию через фирменный магазин. Сбыт продукции зависит от состояния погоды. Но данным прошлых наблюдений предприятие в течении апреля — мая в условиях теплой погоды может реализовать 600 костюмов и 1975 платьев, а при прохладной погоде 1000 костюмов и 625 платьев. Известно, что затраты на единицу продукции в течение указанных месяцев составили для костюмов 27 руб., для платьев 8 руб., а цена реализации равна соответственно 48 руб. и 16 руб. (цифры условные).
Задача заключается в максимизации средней величины прибыли от реализации выпущенной продукции с учетом неопределенности погоды в рассматриваемые месяцы. Таким образом, служба маркетинга предприятия должна в этих условиях определить оптимальную стратегию предприятия, обеспечивающую при любой погоде определенный средний доход. Решим эту задачу методами теории игр, игра в этом случае будет относиться к типу игр с природой.
Предприятие располагает в этих условиях двумя чистыми стратегиями: стратегия А — в расчете на теплую погоду и стратегия Б — в расчете на холодную погоду. Природу будим рассматривать как второго игрока также с двумя стратегиями: прохладная погода (стратегия В) и теплая погода (стратегия Г). Если предприятие выберет стратегию А, то в случае прохладной погоды (стратегия природы В) доход составит
600(48 - 27) + 625(16 - 8) - (1975 - 625)8 = 6 800 руб.,
а в случае теплой погоды (стратегия природы Г) доход равен
600(48 - 27) + 1 975(16 - 8) = 28 400 руб.
Если предприятие выберет стратегию Б, то реализация продукции в условиях прохладной погоды даст доход
1 000(48 - 27) + 625(16 - 8) = 26 000 руб.,
а в условиях теплой погоды
600(48 - 27) + 625(16 - 8) - (1 000 - 600)27 = 6 800
Следовательно, матрица данной игры (платежная матица) имеет вид:
Первая и вторая строки этой матрицы соответствуют стратегиям А и Б предприятия, а первый и второй стратегиям В и Г природы.
По платежной матрице видно, что первый игрок (предприятие) никогда не получит доход меньше 6800. Но если погодные условия совпадают с выбранной стратегией, то выручка (выигрыш) составит 26 000 или 28 400. Отсюда можно сделать вывод, что в условиях неопределенности погоды наибольший гарантированный доход предприятие обеспечит, если будет попеременно применять то А, то стратегию Б. Такая стратегия называется смешанной. Оптимизация смешанной стратегии позволит первому игроку всегда получать выигрыша независимо от стратегии второго игрока.
Пусть х означает частоту применения первым игроком стратегии А, тогда частота применения им стратегии Б равна (1 - х). В случае оптимальной смешанной стратегии первый игрок (предприятие) получит и при стратегии В (холодная погода), и при стратегии Г (теплая погода) второго игрока одинаковый средний доход:
6800х + 26 000(1 - х) = 28 400х + 6800(1 - х).
Отсюда можно найти, что х — 8/17; 1 - х = 9/17.
Следовательно, первый игрок, применяя чистые стратеги А и Б в соотношении 8:9, будет иметь оптимальную смешанную стратегию, обеспечивающую ему в любом случае средний доход в сумме
6800-8/17 + 26000-9/17 16965 руб.; эта величина и будет в данном случае ценой игры.
Легко рассчитать, какое количество костюмов и платьев должно выпускать предприятие при оптимальной стратегии:
(600 костюмов + 1975 платьев)*8/17 + (1000 костюмов + 625 платьев)*9/17 = 812 костюмов + 1260 платьев.
Следовательно, оптимальная стратегия предприятия заключи в выпуске 812 костюмов и 1260 платьев, что обеспечит три любой погоде средний доход в сумме 16 965 руб.
Заключение
На основании выше изложенного материала можно сделать вывод о том, что особое внимание при исследовании экономико-математических методов необходимо уделять следующим моментам:
- фактору сезонности в экономических процессах;
- приведению формул и примеров расчетов;
- рассмотрению ряда прикладных задач маркетинга, менеджмента и других областей управления в экономике;
- моделированию спроса и потребления;
- научному управлению запасами;
- анализу сетевого планирования и управления;
- анализу динамического программирования;
- аналитическому моделированию систем массового обслуживания;
- принятию решений на основе теории игр.
Так как я в своей работе особое внимание уделила теории игр, то, после рассмотрения ее более подробно, и в этой конкретной области можно сделать определенные выводы. Здесь представлены, на мой взгляд, более актуальные задачи:
- как сделать так, чтобы природа работала на тебя, а не ты на неё;
- как получить набольшую выгоду или учет твоих интересов конкурентом, или поставщиком;
- какой товар лучше производить и т.д.
Список используемой литературы
1. Экономико-математические методы и прикладное моделирование / В.В. Федосеев. – М.: ЮНИТИ, 2002. - 391 с.
2. Математическое моделирование макроэкономических процессов / А.Н. Котов. – Л.: ЛГУ, 1980
3. Основы экономико-математического моделирования / Ю.Г. Семенов.1976
4. Экономико-математические методы / Л.Л. Терехов.– М.: Статистика–1972