Оренбургский государственный аграрный университет

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

Реферативно-прикладное исследование

на тему:

"Практическое применение теории игр"

Оренбург – 2006г.

Содержание

Введение

I. Теоретические основы методов программирования

1. Динамическое программирование

2. Теория игр

3. Сетевое планирование и управление

4. Моделирование систем массового обслуживания

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

Заключение

Список литературы

Введение

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

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

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

I. Теоретические основы методов программирования

1. Динамическое программирование

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

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

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

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

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

Процесс длится определенное число шагов N. На каждом шаге осуществляется выбор одного управления uⁿ, под воздействием, которого система переходит из одного состояния Sⁿ в другое Sⁿ⁺¹: Sⁿ Sⁿ⁺¹. Поскольку процесс марковский, то Sⁿ = uⁿ (Sⁿ) зависит только от текущего состояния.

Каждый шаг (выбор очередного решения) связан с определенным эффектом, который зависит от текущего со стояния и принятого решения: (Sⁿ , Sⁿ ).

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

Требуется найти такое решение uⁿ для каждого шага (n = 1, 2, 3, ..., N), т.е. последовательность (u¹, ..., u^N), чтобы получить максимальный эффект (доход) за N шагов.

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

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

Любая возможная допустимая последовательность решений (u¹, ..., u^N) называется стратегией управления. Стратегия управления, доставляющая максимум критерию оптимальности, называется оптимальной.

В основе общей концепции метода ДП лежит принцип оптимальности Беллмана:

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

,

где — все допустимые управления при условии, что система находится в состоянии Sⁿ;

(Sⁿ , Sⁿ ) — эффект от принятия решения uⁿ;

— эффект за оставшиеся n шагов.

Благодаря принципу оптимальности удается при последующих переходах испытывать не все возможные варианты, лишь оптимальные выходы. РДП позволяют заменить трудоёмкое вычисление оптимума по N переменным в исходной задаче решением N задач, в каждой из которых оптимум годится лишь по одной переменной.

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

В качестве примера построения РДП рассмотрим использование принципа оптимальности для реализации математической модели задачи оптимального распределения некоторого ресурса в объеме х:

где x_j — количество ресурса, используемое j-м способом;

— доход от применения способа j, j = 1, N .

Рекуррентные соотношения, с помощью которых находится решение этой задачи, имеют вид:

2. Теория игр

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

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

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

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

Важными являются понятия оптимальной стратегии, цены игры, среднего выигрыша. Эти понятия находят отражение в определении решения игры: стратегии Р* и Q* первого и второго игрока соответственно называются их оптимальными стратегиями, а число V — ценой игры, если для любых стратегий Р первого игрока и любых стратегий Q выполняются неравенства: где М (Р,Q) означает математическое ожидание выигрыши (средней выигрыш) первого игрока, если первым и вторым игроками избраны соответственно стратегии Р и Q.

Из неравенств следует, в частности, что V = M (P^*,Q^*),т.е. цена игры равна математическому ожиданию выигрыша первого игрока, если оба игрока изберут оптимальные для себя стратегии.

Одним из основных видов игр являются матричные игры, которыми называются парные игры с нулевой суммой (один игрок выигрывает столько, сколько проигрывает другой) при условии, что каждый игрок имеет конечное число стратегий. В этом случае парная игра формально задается матрицей А = (а_ij), элементы которой а_ij определяют выигрыш первого игрока (и соответственно проигрыш второго), если первый игрок выберет i-ю стратегию (i = ), а второй —j-ю стратегию (j = ). Матрица А называется матрицей игры, или платежной матрицей.