ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

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

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

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

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

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