Задачи последовательного принятия решений

Структура рассмотренной задачи распределения ресурсов такова, что переменные , по мере построения процесса можно было определять в произвольном порядке (то есть их можно было менять местами). Однако существует много задач, в которых решения должны определяться в строгой временной последовательности, и потому переменные , нельзя менять местами. Такие задачи называют задачами последовательного принятия решений. Для этих задач существует выбор между двумя разными схемами решения [18; 49]:

решение в прямом направлении, когда первый шаг схемы динамического программирования соответствует первому по времени принимаемому решению;

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

Для объяснения этих двух схем рассмотрим такую задачу.

Задача об использовании трудовых ресурсов

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

-й месяц идеальное число рабочих равно . Если б предприятию можно было увольнять и набирать новых рабочих без дополнительных затрат, то оно в -й месяц наняло бы ровно рабочих .

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

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

,

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

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

,

где .

Тогда основное рекуррентное соотношение будет иметь вид:

,    (7.1.13)

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

Используя (7.1.13), последовательно вычисляем , , …, для всех возможных значений .

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

Для этого находим

. (7.1.14)

Определив из (7.1.14) и положив = , из таблицы предыдущего шага находим , дальше и т.д.

В рассматриваемом случае решение в обратном направлении целесообразно, так как неизвестно число рабочих в конце работ, то есть на ()-й месяц.

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

.     (7.1.15)

Здесь можно записать

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

Определим последовательность функций состояния

Тогда

Основное рекуррентное соотношение ДП для этого случая будет иметь вид:

(7.1.16)

Функция есть минимальные затраты за первые () месяцев при условии, что численность работников в ()-й месяц равна .

Используя ОРС (7.1.16), последовательно вычисляем , для всех возможных значений .

Наконец, на последнем шаге при , положив , получим соотношение

.         (7.1.17)

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

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

Пример 7.2.Пусть задана задача об использовании трудовых ресурсов с такими данными: = 4 месяца; = 2, = 5, = 3, = 1, = 2.

Пусть функции и имеют следующий вид:

Поскольку зафиксировано начало (= = 2), то будем решать задачу в обратном направлении. Для этого используем основное рекуррентное соотношение

Первый шаг.

Для отыскания составляем таблицу значений (табл. 7.3). Значение для всех выбираем из табл. 7.3 и записываем в основную таблицу – табл. 7.4. Поскольку все функции и выпуклы по , то и функция выпукла по для всех значений . Поэтому для нахождения достаточно найти первый минимум функции , который и будет глобальным. Соответственно этому выводу значения функции вычисляем лишь для области значений , содержащей этот минимум (табл. 7.3).

Вычисления выполняем следующим образом.

ξ = 0 , x4= 0; Ω4= 0 + 11(1 – 0) = 11; ξ = 0 , x4= 1; Ω4= 10(1 – 0) + 0 = 10; ξ = 0 , x4= 2; Ω4= 10(2 – 0) + 8(2 – 1) = 28.		ξ = 1 , x4= 0; Ω4= 7(1 – 0) + 11(1 – 0) = 18; ξ = 1 , x4= 1; Ω4= 0 + 0 = 0; ξ = 1 , x4= 2; Ω4= 10(1 – 0) + 8(2 – 1) = 18.
ξ = 2 , x4= 0; Ω4= 7(2 – 0) + 11(1 – 0) = 25; ξ = 2 , x4= 1; Ω4= 7(2 – 1) + 0 = 7; ξ = 2 , x4= 2; Ω4= 7·0 + 8(2 – 1) = 8.		ξ = 3 , x4= 0; Ω4= 7(3 – 0) + 11(1 – 0) = 32; ξ = 3 , x4= 1; Ω4= 7(3 – 1) + 0 = 14; ξ = 3 , x4= 2; Ω4= 7(3 – 2) + 8(2 – 1) = 15.
ξ = 4 , x4= 0; Ω4= 7(4 – 0) + 11(1 – 0) = 39; ξ = 4 , x4= 1; Ω4= 7(4 – 1) + 0 = 21; ξ = 4 , x4= 2; Ω4= 7(4 – 2) + 8(2 – 1) = 22.		ξ = 5 , x4= 0; Ω4= 7(5 – 0) + 11(1 – 0) = 46; ξ = 5 , x4= 1; Ω4= 7(5 – 1) + 0 = 28; ξ = 5 , x4= 2; Ω4= 7(5 – 2) + 8(2 – 1) = 29.

Нужно определить диапазон изменения параметра . Очевидно, , а . В рассматриваемом примере = 5.

Таблица 7.3				Таблица 7.4
	0	11		0	10	1
0	1	10		1	0	1
	2	28		2	7	1
	0	18		3	14	1
1	1	0		4	21	1
	2	18		5	28	1
	0	25
2	1	7
	2	8
	0	32
3	1	14
	2	15
	0	39
4	1	21
	2	22
	0	46
5	1	28
	2	29

Второй шаг.Используем ОРС при k = 3:

и выполним второй шаг аналогично первому. Вспомогательные результаты вычисления приведем в табл. 7.5, а итоговые – в табл. 7.6.

Таблица 7.5				Таблица 7.6
	0	40		0	32	1	1
0	1	32		1	22	1	1
	2	38		2	18	2	1
	0	50		3	14	3	1
1	1	22		4	21	3	1
	2	28		5	28	3	1
	0	57
2	1	29
	2	18
	3	24
	1	36
3	2	25
	3	14
	4	39
	2	32
4	3	21
	4	29
	2	39
5	3	28
	4	36

Третий шаг.Используем соотношения (1) и вычислим для всех

,

где . Результаты вычисления заносим в табл. 7.7, а значение и в основную таблицу 7.8.

Таблица 7.7				Таблица 7.8
	1	76		0	66	3	3	1
0	2	71		1	56	3	3	1
	3	66		2	46	3	3	1
	4	72		3	36	3	3	1
	2	61		4	32	4	3	1
1	3	56		5	28	5	3	1
	4	62

Продолжение таблицы 7.7
	2	51
2	3	46
	4	52
	2	58
3	3	36
	4	42
	2	65
4	3	43
	4	32				Таблица 7.9
	5	38
	4	39					1	74
5	5	28				2	2	46
	6	46					3	54

Четвертый шаг.Используя начальное условие и подставляя его в соотношение , находим и оптимальное значение переменной . Они приведены в табл. 7.9. Дальше из табл. 7.8 по значению вычисляем оптимальные значения всех остальных переменных: . При этом суммарные затраты составляют = 46 условн.ед., что является минимумом.