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

Динамическое программирование – это метод оптимизации, приспособленный к поэтапным операциям нахождения решения. Задача разбивается на ряд последовательных шагов или этапов.

Условием применимости метода является аддитивность целевой функции, т.е. возможность представления функции от переменных в виде суммы функции, каждая из которых зависит только от одной переменной:

.

К числу задач динамического программирования относятся задачи: о замене и загрузке оборудования; оптимального распределения ресурсов по этапам планирования; оптимального управления запасами; оптимального распределения капиталовложений и многие другие.

Рассмотрим модель нелинейного программирования

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

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

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

,

где – варианты условий начала-го шага.

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

Уравнение Беллмана для шагов, начиная с предпоследнего до начала процесса, имеет вид:

,

где – варианты условий начала-го шага;

–функция Беллмана, найденная на предыдущем шаге.

При динамическом программировании многошаговый процесс проходят два раза:

1) от конца к началу – находят условные оптимальные решения на каждом шаге с учетом выигрыша на всех шагах, начиная с данного до конца;

2) от начала к концу – находят оптимальные шаговые решения на всех шагах.

5.4 Применение динамического программирования для решения задач о замене оборудования и эффективного использования

ресурсов

Задача эффективного использования ресурсов. Имеется некоторое количество ресурса , которое можно использовать различными способами. Пусть–количестворесурса,используемое -м способом,– доход от использования ресурса-м способом ().

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

Модель оптимального использования ресурса имеет вид:

(5.13)

(5.14)

. (5.15)

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

На последнем шаге определяется функция

.

Для всех остальных шагов используется рекуррентное соотношение

, ,

здесь – количество ресурса, оставшееся для распределения к началу-го шага.

Очевидно,

.

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

Задача 5.3 Необходимо составить план вложений денежных средств в три отделения предприятия, исходя из общей суммы средств, которая равна 250 денежным единицам.

Известны функции прибыли f_i(x_i) по каждому отделению, где x_i - средства, вкладываемые в i-е отделение (таблица 5.1). Размеры вложений ограничены: для первого отделения суммой 250 ден. ед., для второго отделения – 100 ден. ед.; для третьего - 250 ден. ед.

Найти оптимальное распределение денежных средств по отделениям, соответствующее максимуму суммарной но трем отделениям прибыли.

Таблица 5.1 – Функции прибыли по трем отделениям

xi
fi	0	50	100	150	200	250
f1	0	7	9	10	11	12
f2	0	5	8	-	-	-
f3	0	3	5	9	13	15

решение.

Введем обозначения:

x₁ - количество вложенных денежных средств в первое отделение; x₂ - количество вложенных денежных средств во второе отделение; x₃ - количество вложенных денежных средств в третье отделение.

Целевая функция имеет смысл суммарной но трем отделениям прибыли.

Математическая модель задачи

.

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

,

x₃250.

Поскольку функции прибыли f_i(x_i) заданы таблично, метод динамического программирования будем применять в табличном виде.

Так как с ростом x₃ функция f₃(x₃) возрастает, то на последнем этапе все оставшиеся средства нужно отдать третьему отделению, таким образом, x₃ = z_3.

Таблица 5.2 – Условно-оптимальные планы для третьего отделения

z3	0	50	100	150	200	250
x3	0	50	100	150	200	250
F1(z3 )	0	3	5	9	13	15

Запишем уравнение Беллмана для второго шага распределения средств:

(5.16)

x₂ 100,

здесь – средства, оставшиеся для вложений во второе и третье отделение, следовательно,

. (5.17)

В таблицу 5.3 внесем все элементы формулы (5.16). В графы 2 и 4 записываем все возможные сочетания значений и, которые в сумме составят величинусогласно выражению (5.17). При этом учитываем, что

не должен превышать 100.

Таблица 5.3 – Условно-оптимальные планы для второго отделения

z2	x2	f2(x2)	z3	F1(z3 )	f2(x2)+F1(z3)	F2(z2)
1	2	3	4	5	6	7
250	0	0	250	15	15
	50	5	200	13	18	18
	100	8	150	9	17
200	0	0	200	13	13
	50	5	150	9	14	14
	100	8	100	5	13
150	0	0	150	9	9
	50	5	100	5	10
	100	8	50	3	11	11
100	0	0	100	5	5
	50	5	50	3	8	8
	100	8	0	0	8	8
50	0	0	50	3	3
	50	5	0	0	5	5

Уравнение Беллмана для первого шага:

.

Переменная имеет смысл денежных средств для вложений во все три отделения предприятия и, следовательно, имеет единственное значение, равное общей сумме вложений 250 ден. ед. Значения функцииF₂(z₂ ) будем брать из последнего столбца таблицы 5.3.

Таблица 5.4 – Условно-оптимальные планы для первого отделения.

z1	x1	f1(x1)	z2	F2(z2 )	f1(x1)+F1(z3)	F1(z1)
250	0	0	250	18	18
	50	7	200	14	21	21
	100	9	150	11	20
	150	10	100	8	18
	200	11	50	5	16
	250	12	0	0	12

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

.

Теперь в ходе движения от первого шага к концу определим оптимальные величины вложений. Из таблицы 5.4 видим, что максимальная прибыль достигается при x₁, равном 50, и z₂, равном 200. Рассмотрим второй шаг (таблица 5.3). При z₂, равном 200, функция Беллмана F₂(z₂) = 14. Это значение соответствует строке, в которой x₂ равно 50, следовательно, на долю третьего отделения остается 150 денежных единиц.

Таким образом, максимум прибыли от вложения денежных средств составляет

.

Оптимальный план вложений:

– в первое отделение ден. ед.;

– во второе отделение ден. ед.;

– в третье отделение ден. ед..

Задача о замене оборудования.

Задача 5.4 К началу пятилетнего периода на предприятии установлено новое оборудование. Зависимость производительности этого оборудования от времени его использования предприятием, а также зависимость затрат на содержание и ремонт оборудования при различном времени его использования приведены в таблице 5.5.

Таблица 5.5 – Зависимость выпуска и эксплуатационных затрат от времени использования оборудования

Показатель	Время , в течение которого используется оборудование, год
	0	1	2	3	4	5
Выпуск продукции в стоимостном выражении, ден. ед.	95	88	81	74	57	50
Эксплуатационные затраты оборудования , ден. ед.	22	31	40	49	58	67

Зная, что затраты, связанные с приобретением и установкой нового оборудования, идентичного с установленным, составляют 35 ден. ед., а заменяемое оборудование списывается, составить такой план замены оборудования в течение пятилетки, при котором общая прибыль за данный период максимальна.

решение.

Обозначим:

– время службы оборудования;

– принятие решения в начале -го года об использовании имеющегося оборудования;

– принятие решения в начале -го года о замене оборудования;

– стоимость нового оборудования.

Целевая функция имеет смысл суммарной за пятилетний период прибыли.

Математическая модель задачи

, (5.18)

где – прибыль предприятия за-й год.

,

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

Уравнения Беллмана для последнего шага имеет вид:

, (5.19)

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

Уравнения Беллмана для -го шага

; (5.20)

–максимальная прибыль, начиная с -го года и до конца периода в зависимости от возраста оборудования в начале-го года.

Планируем замену оборудования в начале пятого года. Предполагаем варианты условий начала данного шага, т.е. последовательно перебираем возможные значения возраста оборудования к началу пятого года. Расчеты проводим по уравнению (5.19). принимает значения: 1, 2, 3, 4. В результате получаем функцию максимальной прибыли за последний год в зависимости от возраста оборудования:

(5.21)

Планируем начало четвертого года. Расчеты проводим по уравнению (5.20). принимает значения: 1, 2, 3. Получаем функцию максимальной прибыли за последние два года в зависимости от возраста оборудования:

(5.22)

Планируем начало третьего года. Расчеты проводим по уравнению (5.20). принимает значения: 1, 2. Получаем функцию максимальной прибыли за последние три года в зависимости от возраста оборудования:

(5.23)

Планируем начало второго года. Расчеты проводим по уравнению (5.20). Получаем функцию максимальной прибыли за период со второго по пятый год:

(5.24)

Планируем начало первого года.

(5.25)

Значение функции Беллмана представляет собой максимальную прибыль предприятия за пятилетний период.

Мы выполнили расчет шагов динамического программирования от конца к началу периода. В результате определили

.

Теперь в направлении от начала периода до его конца найдем оптимальный план замены оборудования.

По условию задачи в начале первого года оборудование было обновлено, т.е. .

В выражение (5.25) входит значение . Оно было вычислено по формуле (5.24) и соответствует .

В свою очередь это выражение содержит значение , вычисленное по (5.23) при .

В (5.23) входит , вычисленное по (5.22) при .

И, наконец, из выражения (5.21) ясно, что .