Стохастическое программирование

Содержание

Цель работы……………………………………………………………………….3

1. Теоретические вопросы………………………………….………………….…4

1.1 Теория игр………………………………………………………………..……4

1.2 Теория массового  обслуживания……………………………………….……7

1.3 Динамическое программирование………………………….………………10

1.4 Сетевое планирование и управление………………………….……………13

1.5 Стохастическое программирование……………………………...…………16

2. Практическое применение стохастического программирования…….……21

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

Список использованной литературы……………………………...……………28

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Цель работы

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

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

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

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

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

1.1 Теория игр

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

В матрице x1 обозначают ходы игрока Р1, а yj - ходы игрока Р2.

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

для игрока Р1

x1+x2+…+xm=1(2)

x1>=0, x2>=0, …, xm>=0

для игрока Р2

y1+y2+…+yn=1(3)

y1>=0, y2 >=0, …, yn >=0

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

 

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

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

Одна из особенностей метода динамического программирования состоит в том, что принятие решения  по отношению к многошаговым процессам  рассматривается не как единичный  акт, а как целый комплекс взаимосвязанных решений. Эту последовательность взаимосвязанных решений называют стратегией. Цель оптимального планирования - выбрать стратегию, обеспечивающую получение наилучшего результата с точки зрения заранее выбранного критерия. Такую стратегию называют оптимальной.

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

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

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

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

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

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