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

ФГОУ ВПО «Оренбургский государственный аграрный университет»

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

 

 

 

 

 

 

 

 

 

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

Тема: «Динамическое программирование»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Оренбург 2005

 

Содержание

 

I Цель работы

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

2.1 Теория игр

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

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

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

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

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

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

 

 

I Цель работы

 

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

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

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

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

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

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

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

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

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

 

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

 

2.1 Теория игр

 

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

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

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

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

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

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

 

v₁ + v₂ + ... + v_i + … + v_n = 0 (1)

 

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

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

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

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

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

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

 

P1 P2	y1	y2	….	yj	…..	yn
x1	a11	a12	…..	a1j	…..	a1n
x2	a21	a22	….	a2j	…..	a2n
….	….	…	…	…	…	…
xi	ai1	ai2	….	a1j	…	a1n
…	…	…	…	…	…	…
xm	am1	am2	…	amj	…	amn

 

В матрице x₁ обозначают ходы игрока Р₁, а y_j - ходы игрока Р₂.

 В любой игре важное значение имеет стратегия, под которой понимается совокупность правил, определяющих выбор при каждом личном ходе игрока, в зависимости от ситуации, сложившейся в процессе игры. В матричных играх применяются чистые и смешанные стратегии. Стратегии с компонентом, равным единице, называются чистыми стратегиями. Они обозначаются для игрока Р₁ через = (0,..., 0,1,0, …, 0), где единица стоит на i-м месте (i= 1,2, …, m), и аналогично для игрока Р₂ = (0, …,0,1,0, …,0), где единица стоит на j-м месте (j=1,2, …,n). Стратегии с отличными от единицы компонентами, представляющими вероятные её доли, называются смешанными. Если игра ведется в смешанных стратегиях, то игрок Р₁ из своих m чистых стратегий может их выбирать с частотами x₁, x₂, …,x_m, а игрок Р₂ имеющий n чистых стратегий, может их выбрать с частотами y₁, y₂, …, y_n. Набор смешанных стратегий, используемых в игре, должен отвечать требованиям (2) и (3) :

для игрока Р₁

 

x₁+x₂+…+x_m=1(2)

x₁>=0, x₂>=0, …, x_m>=0

 

для игрока Р₂

 

y₁+y₂+…+y_n=1(3)

y₁>=0, y₂ >=0, …, y_n >=0

 

Как видно, чистая стратегия является частным случаем смешанной стратегии, в которой все стратегии, кроме одной, применяются с нулевыми частотами, а одна применяется с частотой 1. (2)

 

 

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

 

Теория массового обслуживания впервые применялась в телефонии, а затем и в других областях хозяйственной деятельности.

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

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

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

Задача теории массового обслуживания состоит в выработке рекомендаций по рациональному построению СМО, рациональной организации их работы и регулированию потока заявок с целью обеспечить более высокую эффективность обслуживания при малых затратах на создание и функционирование системы. Для этого теория массового обслуживания устанавливает зависимости между характеристиками потока заявок, числом и производительностью каналов обслуживания и «выходными» характеристиками СМО, описывающими результаты ее работы. Системы массового обслуживания делятся на две группы: СМО с отказами в обслуживании и СМО с ожиданием, или очередью. В СМО с отказами заявка, поступившая в момент, когда все каналы обслуживания заняты, получает «отказ» и сразу покидает систему, а не становится в очередь. Примерами системы с отказами могут служить система телефонной связи города, пошивочная мастерская, если нет «записи на очередь».

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