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

Содержание

I Цель работы

II Теоретические вопросы

2.1 Теория игр

2.2 Теория массового обслуживания

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

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

III Практическое применение динамического программирования

IV Выводы по результатам работы

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

I Цель работы

В сельском хозяйстве непрерывно проте

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

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

Основная цель написания реферативно-прикладного исследования – ознакомиться с основами методов математического программирования, необходимого для решения теоретических и практических задач экономики. Для достижения поставленной цели необходимо решить ряд задач:

- рассмотреть понятие «динамическое программирование»;

- показать механизм решения экономической задачи при помощи динамического программирования;

- ознакомиться с элементами теории игр;

- показать методы сетевого планирования и управления;

- ознакомиться с моделированием систем массового обслуживания;

- сделать выводы по результатам работы.

II Теоретические вопросы

2.1Теория игр

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

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

Математический аппарат теории игр, особенно антагонистических, разработан весьма подробно. Создана важная и содержательная теория построения модели и её анализа.

Конфликтные ситуации, встречающиеся в реальной жизни, обуславливаются многочисленными факторами и являются весьма сложными. Чтобы можно было их изучать, необходимо отвлечься от всего второстепенного и сосредоточить внимание на анализе главных факторов, иначе говоря, надо формализовать реальную ситуацию и построить её модель. Такую модель называют игрой.

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

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

v1 + v2 + . + vi + … + vn = 0 (1)

Число v1 может быть положительным, отрицательным и равным нулю. При v1> 0 – выигрыш, v1< 0 – проигрыш и v1= 0 – ничейный исход.

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

Развитие игры во времени сводится к ряду последовательных действий или вариантов принятия решений. Выбор одного из предусмотренных правилами игры вариантов называется ходом. Ходы делятся на личные и случайные. Личным ходом называется сознательный выбор одним из игроков из возможных в данной ситуации ходов и его осуществление. Случайным ходом называется выбор из ряда возможностей, осуществляемый не игроком, а каким-либо механизмов случайного выбора. Игры могут состоять из личных, случайных и смешанных ходом.

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

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

В общем виде постановка задачи парной игры с нулевой суммой сводится к следующему: если два игрока P1 и P2 играют в какую-либо игру, то как должен вести партию каждый из этих игроков, чтобы достигнуть наиболее благоприятного исхода для себя. При случайных ходах (действиях) этих игроков естественной оценкой благоприятного исхода (выигрыша) является его среднее значение, которое обозначается символом aij. Если известны значения aij выигрыша, то парную игру можно записать в виде прямоугольной таблицы, которая называется матрицей выигрышей или платежной матрицей. Она имеет такой вид:

 Скачать реферат