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



7

 

 

 

Контрольная работа

по дисциплине  «Математические методы в экономике»

 

на тему

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Москва – 2010

 

 

Содержание:

1. Уравнение Беллмана.

2. Задача управления запасами.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.  Уравнение Беллмана

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

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

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

В основу метода динамического программирования положен принцип оптимальности, сформулированный в 1957 г. американским математиком Ричардом Беллманом: «Оптимальное поведение обладает тем свойством, что каковы бы ни были первоначальные состояние и решение в начальный момент времени, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения».

Оптимизация управления n-шагового процесса состоит в том, чтобы найти такую последовательность управлений ui, при которой критерий качества Jn(u) принимает минимальное значение. Это минимальное значение критерия качества управления n-шагового процесса будет зависеть только от начального состояния x0 и его можно обозначать fn(x0). По определению имеем:

 

fn(x0)=min min … min [Q(x0,u0)+ Q(x1,u1)+…+ Q(xn-1,un-1)].

 

Заметим, что первое слагаемое этого выражения Q(x0,u0) зависит только от управления u0, тогда как остальные слагаемые зависят как от u0, так и от управлений на других шагах. Так, Q(x1,u1) зависит от u1, но оно зависит и от u0, так как x1 =T(x0,u0). Аналогично обстоит дело и с остальными слагаемыми. Поэтому выражение можно записать в виде

 

fn(x0)=min {Q(x0,u0)+ min … min [Q(x1,u1)+…+ Q(xn-1,un-1)]}.

 

Заметим далее, что выражение min … min [Q(x1,u1)+…+ Q(xn-1,un-1)] представляет собой минимальное значение критерия качествa управления   (n-1)-шагового процесса, имеющего начальное состояние х1. В соответствии с определением эту величину можем обозначить через fn-1(x1). Таким образом, получаем: fn(x0)=min {Q(x0,u0)+ fn-1(x1)}.

Эти рассуждения можно повторить, если рассмотреть (n-1)-шаговый процесс, начинающийся с начального состояния x1. Минимальное значение критерия качества управления для этого случая

fn-1(x1)=min {Q(x1,u1)+ fn-2(x2)}.

Продолжая эти рассуждения, получаем аналогичное выражение для    (n -k) -шагового процесса, начинающегося с состояния xk:

fn-k(xk)=min {Q(xk,uk)+ fn-(k+1)(xk+1)}.

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

Рекуррентная формула — формула вида выражающая каждый член последовательности an () через предыдущих членов.

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

Рассматривается следующая общая задача. Имеется некоторая физическая система, в которой происходит какой-то процесс, состоящий из n шагов. Эффективность процесса характеризуется некоторым показателем W, который называют выигрышем. Пусть общий выигрыш W за все n шагов процесса складывается из выигрышей на отдельных шагах

                                            2.1

где wi — выигрыш на i-м шаге. Если W обладает таким свойством, то его называют аддитивным критерием.

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

Шаговые управления в общем случае не числа, а, как правило, векторы, функции и т.п.

В модели динамического программирования процесс на каждом шаге находится в одном из состояний s множества состояний S. Считается, что всякому состоянию сопоставлены некоторые шаговые управления. Эти управления таковы, что управление, выбранное в данном состоянии при любой предыстории процесса, определяет полностью следующее состояние процесса. Обычно выделены два особых состояния: s0 — начальное и sw — конечное.

Итак, пусть каждому состоянию поставлено множество допустимых шаговых управлений и каждому шаговому управлению соответствует — состояние, в которое процесс попадает из si в результате использования шагового управления u. Пусть процесс находится в начальном состоянии s0. Выбор переводит процесс в состояние s1 = σ(s0,u1), выбор — в состояние s2 = σ(s1,u2) и т.д. В результате получается траектория процесса, которая состоит из последовательности пар

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

  2.2

   2.3

конечны и Us для различных s не пересекаются.

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

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

 

              2.4

 

Тот максимальный выигрыш, который достигается при этом управлении обозначим Wmax:

 

Wmax = maxU{W(u)}.             (2.5)

 

Рассмотрим на примере задачи о рюкзаке, что понимается под шагом, состоянием, управлением и выигрышем.

Загрузку рюкзака можно представить себе как процесс, состоящий из n шагов. На каждом шаге требуется ответить на вопрос: взять данный предмет в рюкзак, или нет? Таким образом, шаг процесса — присваивание переменной xi значения 1 или 0.

Теперь определим состояния. Очевидно, что текущее состояние процесса характеризует остаточная грузоподъёмность рюкзака — вес, который остался в нашем распоряжении до конца (до полной укладки рюкзака).

 

 

Следовательно, под состоянием перед i-м шагом понимается величина

 

        2.6

при этом s0 является начальным состоянием, которому соответствует величина b — исходная грузоподъемность рюкзака.

Управление на i-м шаге означает присваивание двоичной переменной xi значения 0 или 1. Значит, на каждом шаге имеем всего два управления. Причем допустимость управления ui, устанавливающего xi = 1, определяется условием

             (2.7)

 

Далее везде вместо переменных будем использовать соответствующие управления

 

Тогда формулы (2.6), (2.7) примут следующий вид:

                           (2.8)

         (2.9)

 

Шаговый выигрыш можно определить как Поэтому

             (2.10)

 

Требуется найти оптимальное управление при котором величина выигрыша (2.10) обращается в максимум.

 

Уравнение Беллмана для задачи о рюкзаке:

 

Пусть к началу -шага остаточная грузоподъемность равна s. Оптимальное управление определяется следующим образом:

- если то последний предмет можно положить в рюкзак, что соответствует оптимальному управлению ;

-  иначе 

Ясно, что оптимальный условный выигрыш на -ом шаге составит

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

 

Нужно найти такое при котором этот выигрыш максимален

где максимум берется по всем допустимым управлениям — управлениям, для которых верно ограничение (2.9). Напомним, что может принимать лишь два значения: 0 или 1.

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

   (2.11)

которое позволяет для любого -го шага вычислить условный оптимальный выигрыш и найти соответствующее ему условное оптимальное управление Здесь — значение, при котором достигается максимум в (2.11).

 

К достоинствам метода динамического программирования следует отнести

                 сравнительную простоту расчетов, удобство их алгоритмизации;

                 независимость от вида исходных данных (целевая функция и функции ограничений могут быть линейными и нелинейными, целочисленными и нецелочисленными, заданными аналитически и таблично).

 

Недостатки метода

                 большой объём промежуточной информации;

                 большой объём вычислительной работы.

 

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

             

 

 

 

 

 

 

 

 

 

 

1.                 Задача управления запасами

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

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

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

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

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

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

 

1) длительность одного этапа планового периода;

2) выпуск продукции в течение этапа;

3) спрос на продукцию в конце этапа;

4) уровень запасов изделий на конец этапа;

5) максимально возможный выпуск изделий на одном этапе;

6) максимально возможный уровень запасов на одном этапе;

 

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

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

 

 

 

 

Введем следующие обозначения:

 

N – число календарных этапов из которых состоит плановый период;

При этом каждый n-й этап (n=1,N) характеризуется параметрами:

in-1 – запас, оставшийся после окончания n-1-го этапа;

хn – объем производства предприятия на n-м этапе;

dn – величина спроса на продукцию предприятия на n-м этапе;

xmax – максимальный объем производства на одном этапе;

imax – максимальный объем запасов на одном этапе;

Сn(xn,in-1) – затраты на n-м этапе функционирования, связанные с выпуском хn деталей и хранением in-1 запасов деталей.

 

Тогда критерий оптимизации имеет вид:

                                       N

 

F=∑ Сn(xn,in-1) ® min                      (12.1)  

 

                                     n=1

при ограничениях:

 

1)    ограничение на удовлетворение спроса на каждом этапе:

 

dn £ in-1 + xn , n=1,N ;                      (12.2)

 

2)    установление объема запаса в конце n-го периода:

 

in = in-1 + xn – dn , n=1,N ,  xn =  0,xmax , in =  0,imax ;           (12.3)

 

 

Выбор метода решения

 

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

 

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

 

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

Показатель эффективности задачи в целом обозначим через W, а показатели эффективности на отдельных шагах—через φi, i=1..m. Если W обладает свойством аддитивности, т.е.

 

                                                W=∑ φi ,                                             (22.1)

 

Переменная Xi, от которой зависят выигрыши на i-м шаге и, следовательно, выигрыш в целом, называется шаговым управлением, i=1..m.

Управлением процесса в целом (x) называется последовательность шаговых управлений (вектор управлений) x=(x1, x2,…, xi,…, xm).

Оптимальное управление x—это значение управления x, при котором значение W(x*) является максимальным (или минимальным, если требуется уменьшить проигрыш).  

 

W*=W(x*)=max{W(x)}, x € X,                          (22.2)

 

  где X—область допустимых управлений.

 

Оптимальное управление x* определяется последовательностью оптимальных шаговых управлений x*=(x2*, x2*,…, xi*,…, xm*).  

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

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

 

1)      возможные исходы предыдущего шага;

2)      влияние управления на все оставшиеся до конца процесса шаги.

 

В задачах динамического программирования первый пункт учитывают, делая на каждом шаге условные предположения о возможных вариантах окончания предыдущего шага и приводя для каждого из вариантов условную оптимизацию. Выполнение второго пункта обеспечивается тем, что в задачах динамического программирования условная оптимизация проводится от конца процесса к началу. Сперва оптимизируется последний m-й шаг, на котором не надо учитывать возможные воздействия выбранного управления xm на все последующие шаги, так как эти шаги просто отсутствуют. Делая предположения об условиях окончания (m-1)- го шага, делая предположения об исходах окончания (m-2)-го шага и определяя условное оптимальное управление на (m-1)-м шаге, приносящее оптимальный выигрыш на двух последних шагах—(m-1)-м и m-м. Так же действуют на всех остальных шагах до первого. На первом шаге, как правило, не надо делать условных предположений, так как состояние системы перед первым шагом обычно известно. Для этого состояния выбирают оптимальное шаговое управление, обеспечивающее оптимальный выигрыш на первом и всех последующих шагах. Это управление является безусловным оптимальным управлением на первом шаге и, зная его, определяются оптимальное значение выигрыша и безусловные оптимальные управления на всех шагах.

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

1)    этап – некий календарный интервал (месяц, квартал, год и т.д.);

2)    состояние – наличие финансовых/производственных средств, свободной продукции и т. п.;

3)    управление – возможные варианты использования имеющихся средств;

4)    локальный доход – прибыль (или затраты) получаемая на отдельном этапе;

5)    суммарный доход – прибыль (или затраты) получаемая по окончании планового периода.

 

Дополнительно введем следующие условные обозначения:

s—состояние процесса;

Si—множество возможных состояний процесса перед i-м шагом;

Wi—выигрыш с i-го шага до конца процесса, i=1..m.

 

Можно определить следующие основные этапы составления математической модели задачи динамического программирования.

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

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

3)  Определение множества шаговых управлений xi, i=1..m и налагаемых на них ограничений, т.е. области допустимых управлений X.

4) Определение выигрыша  φ(s, xi), который принесет на i-м шаге управление xi, если система перед этим находилась в состоянии s.

5) Определение состояния s’, в которое переходит система из состояния s под влиянием управления xi :   s’=fi(s, xi,), где fi—функция перехода на i-м шаге из состояния s в состояние s’.

6) Составление уравнения, определяющего условный оптимальный выигрыш                                                                                                              на последнем шаге, для состояния s моделируемого процесса

 

                        Wm(S)=max{φm(s,xm)}.       (2.2.3)

                                                     xm€X

 

7)   Составление основного функционального уравнения динамического                           программирования, определяющего условный оптимальный выигрыш для                             данного состояния s с i-го шага и до конца процесса через уже известный                           оптимальный выигрыш с (i+1)-го шага и до конца:

 

Wi(S)=max{φi(s,xi)+Wi=1(fi(s,xi))}. (2.2.4)                                                                                                                    xm€X  

 

В уравнении (22.4) в уже известную функцию Wi+1(s), характеризующую условный оптимальный выигрыш с (i+1)-го шага до конца процесса, вместо состояния s подставлено новое состояние s’=fi(s, xi), в которое система переходит на i-м шаге под влиянием управления xi.

После того как выполнены пункты 1—7, и математическая модель составлена, приступают к ее расчету.

 

 

 

Укажем основные этапы решения задачи динамического программирования.

1)  Определение множества возможных состояний Sm для последнего шага.

2) Проведение условной оптимизации для каждого состояния s, принадлежащей Sm на последнем m-м шаге по формуле (22.3) и определение условного оптимального управления x(s), s принадлежит Sm.

3) Определение множества возможных состояний Si для i-го шага, i=2, 3,…m-1.

4) Проведение условной оптимизации для i-го шага, i=2, 3,…m-1 для каждого состояния  s, принадлежащей Si,, по формуле (22.4) и определение условного оптимального управления xi(s), s принадлежит Si, i=2, 3,…m-1.

5)  Определение начального состояния системы s1, оптимального выигрыша W1(S1) и оптимального управления x1(S1) по формуле (22.4) при i=1. Это есть оптимальный выигрыш для всей задачи W*=W1(x1*).

6) Проведение безусловной оптимизации управления. Для проведения безусловной оптимизации необходимо найденное на первом шаге оптимальное управление x1*=x1(s1) подставить в формулу (22.2) и определить следующее состояние системы s2=f2(s1, x1). Для измененного состояния найти оптимальное управление x2*=x2(s2), подставить в формулу (22.21) и т.д. Для i-го состояния si найти si+1=fi+1(si,xi*) и x*i+1(si+1) и т.д.

 

Применение метода динамического программирования к задаче оптимального управления запасами

 

Определим основные компоненты:

1)    этап - календарный период деятельности предприятия, n=1,N;

2)    состояние – объем запасов in в конце n периода;

3)    управление – планируемый объем производства xn на n-м периоде;

4)    локальный доход – затраты на n-м этапе, связанные с хранением запасов и производством новой продукции Сn(xn,in-1);

5)    оператор перехода – устанавливает связь между объемом запасов в конце n – 1-го и n-го этапов: in = in-1 + xn – dn .

 

Введем функцию:

fn(in) = min∑ Сn(xn,in-1)                            (2.3.1)   .

 

Функциональное уравнение Беллмана для такой задачи:

fn(in) = min(fn(in-1) + Сn(xn,in-1)).              (2.3.2)

 

Если

Сn(xn,in-1) = cn(xn) + h*in-1                        (2.3.4),

 

где cn(xn) – затраты на производство продукции на n-ном этапе в xn объеме;

h*in-1 – затраты на хранение продукции на n-ном этапе в объеме i0.

Известно c0(x0)  - затраты на формирование начального запаса.

Тогда на шаге 1 принятия решения уравнение Беллмана (2.3.2) примет вид:

f1(i1) = min(f1(i0) + С1(x1,i0)) =  min(f1(i0) + c0(x0) + h*i0)  (2.3.5)

 

все переменные в уравнении известны, а значит его можно решить.

На шаге n уравнение (23.2) имеет вид:

fn(in) = min(fn(in-1) + cn(x) + h*in-1)            (2.3.6)

 

 

Алгоритм решения задачи

 

Для получения оптимального решения нам необходимо разработать алгоритм решения уравнения Беллмана (2.3.6) на произвольном шаге принятия решения n.