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

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

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

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

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

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

Необходимо подобрать груз максимальной ценности с учетом грузоподъемности транспортного средства W. Математически формализовать данную экстремальную задачу можно следующим образом:

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

В итоге наилучший вариант загрузки транспортного средства достигается при значениях хх = 2; х2 = 0; Хт, = 1; х4 = 0 (берутся два предмета 1-го типа и один предмет 3-го типа).