Экономические науки/8 математические методы в экономике

Дмитренко И.С.

Донбасская государственная машиностроительная академия, Украина

Применение методов динамического программирования на примере задачи календарного планирования трудовых ресурсов

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

Рассмотрим одну из задач календарного планирования трудовых ресурсов, предложенных в [1], стр. 455-457.

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

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

Если x_i- количество работающих на протяжении i-ой недели, то возможны затраты двух видов: 1) C₁(x_i- b_i)- затраты, связанные с необходимостью содержать избыток x_i- b_i рабочей силы и 2) C₂(x_i-x_i-1)- затраты, связанные с необходимостью дополнительного найма x_i-x_i-1 рабочих.

Элементы модели динамического программирования определяются следующим образом:

1. Этап i определяется порядковым номером недели i , i=1,2,…,n.

2. Вариантами решения на i-ом этапе являются значения x_i- количество работающих на протяжении i-ой недели.

3. Состоянием на i-ом этапе является x_{i-1 –} количество работающих на протяжении (i-1)-й недели (этапа).

Реккурентное уравнение динамического программирования имеет вид:

где f_n+1(x_n)=0. Вычисления начинаются с этапа n при x_n=b_n и заканчиваются на этапе 1.

Задача 1 Строительный подрядчик оценивает минимальные потребности в рабочей силе на каждую из последующих пяти недель следующим образом: 5,7,8,4 и 6 рабочих соответственно. Содержание избытка рабочей силы обходится подрядчику в 300 долларов за одного рабочего в неделю, а наем рабочей силы на протяжении одной недели обходится в 400 долларов плюс 200 долларов за одного рабочего в неделю.

В [1] рассмотрено подробное решение поставленной задачи, ответом на которую является следующая последовательность работ по найму-увольнению рабочих.

Номер недели	Минимум рабочей силы (bi)	Количество фактически работающих (xi)	Решение
1	5	5	Нанять 5 рабочих
2	7	8	Нанять 3 рабочих
3	8	8	Ничего не менять
4	4	6	Уволить2рабочих
5	6	6	Ничего не менять

Минимальные расходы подрядчика составляют 3300 долларов за 5 недель.

Рассмотрим усложнение предыдущей задачи на следующем примере.

Задача 2 Пусть в задаче 1 каждому уволенному рабочему выплачивается выходное пособие в размере 100 долларов. Требуется найти оптимальное решение задачи.

Выразим С₁ и С₂ в сотнях долларов, тогда имеем следующее:

b₁=5, b₂=7, b₃=8, b₄=4, b₅=6

C₁(x_i- b_i)=3(x_i- b_i), x_i>b_i; C₁(x_i- b_i)=0, x_i =b_i ; i=1,2,3,4,5

C₂(x_i-x_i-1)=4+2(x_i-x_i-1), x_i>x_i-1; C₂(x_i-x_i-1)=1(x_i-1-x_i), x_ix_i-1 i=1,2,3,4,5.

Уравнения Беллмана примут вид:

Этап 5. (b₅=6), f₆(x₅)=0

X4	C1(x5-6)+C2(x5-x4)	Оптимальное решение
	X5=6	f5(x4)	X5^*
4	0+4+2(6-4)=8	8	6
5	0+4+2(6-5)=6	6	6
6	0+1(6-6)=0	0	6

Этап 4.(b₄=4)

X3	C1(x4-4)+C2(x4-x3)+f5(x4)			Оптимальное решение
	X4=4	X4=5	X4=6	f4(x3)	X4^*
8	0+1(8-4)+8=12	3(5-4)+1(8-5)+6=12	3(6-4)+1(8-6)+0=8	8	6

Этап 3.(b₃=8)

X2	C1(x3-8)+C2(x3-x2)+f4(x3)	Оптимальное решение
	X3=8	f3(x2)	X3^*
7	0+4+2(8-7)+8=14	14	8
8	0+1(8-8)+8=8	8	8

Этап 2.(b₂=7)

X1	C1(x2-7)+C2(x2-x1)+f3(x2)		Оптимальное решение
	X2=7	X2=8	f2(x1)	X2^*
5	0+4+2(7-5)+14=22	3(8-7)+4+2(8-5)+8=21	21	8
6	0+4+2(7-6)+14=20	3(8-7)+4+2(8-6)+8=19	19	8
7	0+1(7-7)+14=14	3(8-7)+4+2(8-7)+8=17	14	7
8	0+1(8-7)+14=15	3(8-7)+1(8-8)+8=11	11	8

Этап 1.(b₁=5)

X0	C1(x1-5)+C2(x1-x0)+f2(x1)				Оптимальное решение
	X1=5	X1=6	X1=7	X1=8	f1(x0)	X1^*
0	0+4+2(5-0)+21=35	3(6-5)+4+2(6-0)+19=38	3(7-5)+4+2(7-0)+14=38	3(8-5)+4+2(8-0)+11=40	35	5

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

Полученному решению соответствует два следующих плана.

Номер недели	Минимум рабочей силы (bi)	Количество фактически работающих (xi)	Решение
1	5	5	нанять 5 рабочих
2	7	8	нанять 3 рабочих
3	8	8	ничего не менять
4	4	6	уволить2рабочих
5	6	6	ничего не менять

Минимальные расходы подрядчика составляют 3500 долларов за 5 недель.

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

Литература

1. Таха, Хэмди А. Введение в исследование операций. -М.:Изд.дом «Вильямс», 2001.-912с.