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

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

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

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

на тему:

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

Оренбург – 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 .

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