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

Динамическим программированием называется метод оптимизации, в котором процесс принятия решения может быть разбит на шаги [11]. Каждый шаг переводит объект управления из состояния  в состояние  посредством управления . Если общее количество шагов равно , то можно говорить о последовательности состояний  системы, которую она принимает в результате воздействия  различных управлений  Целевая функция системы зависит от начального состояния и управления

.

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

Если считать целевую функцию аддитивной от показателя эффективности каждого шага, то на шаге  и целевая функция имеет вид

Решением задачи динамического программирования является определение такого управления , которое переводит систему из состояния  в состояние  при наибольшем (наименьшем) значении .

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

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

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

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

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

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

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

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

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

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

Задача управления запасами впервые была описана и решена в 1915 году Фордом Хариссом. В ее основе лежит проблема, связанная с рассогласованием режимов работы поставщика и потребителя. Наличие склада позволяет обеспечить независимость работы потребителя от условий поставки материальных ресурсов. Задача управления запасами имеет цель отыскания решения, минимизирующего общие затраты на приобретение и хранение запасов. Предполагается, что общая сумма затрат на хранение запасов складывается из двух основных составляющих: затраты на пополнение запасов (издержки поставок) и затраты на собственно хранение (издержки по содержанию запаса).

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

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

На рис. 26 представлен график зависимости величины запаса от времени. При управлении запасами необходимо выбирать момент заказа и объем партии. Сами запасы могут расходоваться также партиями, (например, суточная норма). Это обстоятельство отмечено на графике ступеньками. Отсутствие запаса на складе может привести к остановке производства и, как следствие, штрафным санкциям.

Рис. 26. Зависимость запаса от времени

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

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

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

откуда размер оптимальной партии

Последнее выражение в литературе получило название формулы Уилсона или формулы наиболее экономичного объема партии.

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

Рис. 27. Зависимость затрат на запасы