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

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

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

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

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

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

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

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

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

Pi — вес одного предмета /-го типа;

стоимость одного предмета типа;

число предметов /-го типа, загружаемых на имеющееся транспортное средство.

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

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

N

— стоимость груза

м

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

(2) JC, = 0, 1,... (Т. е. предметы груза неделимы).

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

1 Более сложные задачи, решаемые методами математического моделирования, требуют применения ЭВМ.

M W) = max xNVN +/N_, (W-

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

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

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

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

Пусть:

/■': Р:. : т; /'-, -■ 5 (единиц груза);

!' ~ = 20: I 13; (-'., = 6 (денежных единиц);

фузоподъемность транспортного средства W= 10 (единиц груза).

Найдем последовательно значения функций bx(W):f(W), /2W,/3W,/4WnpH различных значениях W(0< W< 10).

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

Таблица 6.7

8-10

56

2

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

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

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

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

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