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

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.