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

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

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

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

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

Использование в экономическом анализе метода динамического программирования покажем на простейшем примере.

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

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

Рi—вес одного предмета i-го типа; Vi — стоимость одного предмета i-го типа; xi —число предметов i-го типа, загружаемых на имеющееся транспортное средство.

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

Математически формализовать данную экстремальную задачу можно следующим образом:

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

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

— максимальная ст-ть груза, состоящего из предметов N-го типов;

—стоимость взятых предметов N-гo типа;

—максимальная стоимость груза, состоящего из предметов (N— 1) типа с общим весом не более

—наибольшее целое число, не превосходящее .

Будем считать, f0(W) = 0 для любого W. Последовательно найдя значение функций f1,(W), f2(W),..., fn(W), можно получить полное решение сформулированной задачи.

Пусть:

Р1, = 4; Р2 = 3; Р3 = 2; Р4 = 1 (единиц груза); V1, = 28; V2 = 20; V3 = 13; V4 = 6 (денежных единиц); грузоподъемность транспортного средства W = 10 (единиц груза).

Найдем последовательно значения функций b1(W): f1(W), f2(W), f2(W), f3(W), при различных значениях W(0< W<10).

Таким образом, максимальная стоимость груза f4(10) равна 69 денежным единицам, при этом предметы 4-го типа загружать не следует, так как f4(10) = 69 достигается при х4= О (табл. 6.7).

Таблица 6.7

Таблица 6.8

Таблица 6.9

Таблица 6.10

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

х3 = 1, так как f3(10) = 69 достигается при х3 = 1 (табл. 6.9), следовательно, вес этого предмета равен 2 единицам груза, поэтому остальные предметы можно загрузить лишь в пределах веса, равного 8(10 2) единицам груза;

f2(8) = 56 достигается при x= 0 (табл. 7.8), следовательно, предметы 2-го типа брать не следует.

И наконец, f1(8)= 56 достигается при x1 = 2 (табл. 6.7), следовательно, предметов 1-го типа следует взять два.

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