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

Постановка задачи

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

Исходные данные

Значения функции f_j(х_j) приведены в Таблице 1 (считаем их заданными, их определение - довольно трудоемкая экономическая задача):

Таблица 1

xj
f1(xj)
f2(xj)
f3(xj)
f4(xj)

Решение

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

Введем параметр состояния x - количество рублей, выделяемых нескольким предприятиям, и определим функцию состояния F_k(x) - максимальная прибыль на первых k предприятиях, если они вместе получат х_k рублей.

Табулируя последовательно функции F_k(x), получим решение, ход которого приведен в Таблицах 2-6.

Таблица 2

	x-х2
х2	F(x-x2) f2(x2)
		22*	42*
			57*	70*
				82*
				92*	101*
				101*

Таблица 3

x
F2(x)
x2(x)								400/500

Таблица 4

	x-х3
х3	F(x-x3) f3(x3)
		0*	22*	42*	57*
				71*	86*	99*
					99*	112*

Таблица 5

x
F2(x)
x2(x)							200/300

Таблица 6

	x-х4
х4	F(x-x4) f4(x4)
								115*

Z_max = 115 тыс. руб.,

причем четвертому предприятию должно быть выделено

х₄* = х₄(700) = 100 тыс. руб.

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

1) х₃* = х₃(700 - х₄*) = х₃(600) = 200 тыс. руб.

2) х₃* = х₃(700 - х₄*) = х₃(600) = 300 тыс. руб.

Продолжая обратный процесс, находим

1) х₂* = х₂(700 - х₄* - х₃*) = х₂(400) = 200 тыс. руб.

2) х₂* = х₂(700 - х₄* - х₃*) = х₂(300) = 200 тыс. руб.

На долю первого предприятия останется

1) х₁* = 700 - х₄* - х₃* - х₂* = 200 тыс. руб.

2) х₁* = 700 - х₄* - х₃* - х₂* = 100 тыс. руб.

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

1) х₁* = 200; х₂* = 200; х₃* = 200; х₄* = 100

2) х₁* = 100; х₂* = 200; х₃* = 300; х₄* = 100

Оно обеспечивает производственному объединению наибольший возможный прирост прибыли 115 тыс. руб.

В качестве проверки правильности решения задачи можно использовать равенство

f₁(x₁*) + f₂(x₂*) + f₃(x₃*) + f₄(x₄*) = Z_max

1) f₁(200) + f₂(200) + f₃(200) + f₄(100) = 33 + 37 + 29 + 16 = 115 = Z_max

2) f₁(100) + f₂(200) + f₃(300) + f₄(100) = 20 + 37 + 42 + 16 = 115 = Z_max

Следовательно, полученные решения верны.

Динамическая задача управления производством и запасами

Постановка задачи

Рассмотреть динамическую задачу управления производством и запасами.

Исходные данные

Спрос (заявки) потребителей на продукцию составляют: на первый этап d₁ = 5 единиц, на второй – d₂ = 1, на третий - d₃ = 2 единицы. К началу первого этапа на складе имеется только 4 единицы продукции, т.е. начальный уровень запаса равен y₁=4. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h₁ = 2, h₂ = 1, h₃ = 1. Затраты на производство x_j единиц продукции на j-м этапе определяются функцией

j_j(x_j) = 2 * x_j² + 6 (1)

т.е. а = 2; b = 0; с = 6. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а общие затраты на производство и хранение за все три этапа были наименьшими.

Решение

Воспользовавшись рекурентными соотношениями, последовательно вычисляем F₁ (x = y₂), F₂ (x = y₃), ..., F_k (x = y_k+1), ... и соответственно находим ₁ (x= y₂), ₂ (x = y₃ ), ..., ` _k (x = y_k+1), ...

Положим k = 1. Тогда имеем

F₁(x= y₂) = min{2 * x_j² + 6 + 2 * y₂} (2)

Учтем, что параметр состояния x = у₂ может принимать целые значения на отрезке

0 у₂ d₂ + d₃

0 y₂ 3

т.е.

у₂ = 0, 1, 2, 3

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

0 х₁ d₁ + у₂

0 х₁ 5 + у₂

Из балансового уравнения

х₁ + у₁ - d₁ = у₂

непосредственно следует, что объем производства связан со значением параметра состояния x= у₂ соотношением

x₁ = y₂ + d₁ - y₁ = y₂ + 5 - 4 = y₂ + 1 (3)

Каждому значению у₂ отвечает единственное значение х₁ и потому

F₁(x = y₂) = W₁ (x₁, y₂)

Придавая у₂ различные целые значения от 0 до 3 и учитывая (3), находим

y₂ = 0, x₁ = 1, W₁ (1;0) = 2 * 1² + 6 + 2 * 0 = 8

y₂ = 1, x₁ = 2, W₁ (2;1) = 2 * 2² + 6 + 2 * 1 = 16

y₂ = 2, x₁ = 3, W₁ (3;2) = 2 * 3² + 6 + 2 * 2 = 28

y₂ = 3, x₁ = 4, W₁ (4;3) = 2 * 4² + 6 + 2 * 3 = 44

Значения функции состояния F₁(x) представлены в Таблице 1.

Таблица 1

x = y2
F1 (x = y2)
x1(x=y2)

Переходим ко второму этапу. Полагаем k = 2 и табулируем функцию F₂(x = y₃):

F₂(x = y₃) = min W₁ (x₁, y₂) = min{a * x₂² + b * x₂ + c + h₂ * y₃ + F₁(y₂)} =

= min {2 * x₂² + 6 + y₃ + F₁(y₂)} (4)

Здесь минимум берется по единственной переменной х₂, которая может изменяться в пределах

0 £ x₂ £ d₂ + y₃ или 0 £ x₂ £ 1 + y₃ (5)

где верхняя граница зависит от параметра состояния x = у₃, который принимает значения на отрезке

0 £ y₃ £ d₃ , т.е. 0 £ y₃ £ 2 (6)

а аргумент у₂ в последнем слагаемом справа в соотношении (4) связан с х₂ и у₃ балансовым уравнением

x₂ + y₂ - d₂ = y₃

откуда следует

y₂ = y₃ + d₂ - x₂ = y₃ + 1 - x₂ (7)

Придавая параметру состояния различные значения от 0 до 2, будем последовательно вычислять W₂ (x₂, x), а затем определять F₂(x ) и ₂(x ).

Положим x = у₃ = 0. Тогда, согласно (5),

0 £ x₂ £ 1,

т.е. переменная х₂ может принимать значения 0, 1, которым отвечает значение у₂, вычисляемое по формуле (7):

у₂ = 1 - х₂

Последовательно находим:

x₂ = 0, y₂ = 1 - 0 = 1, W₂ (0,0) = 2 * 0² + 6 + 0 + F₁(1) = 6 + 16 = 22

x₂ = 1, y₂ = 1 - 1 = 0, W₂ (1,0) = 2 * 1² + 6 + 0 + F₁(0) = 8 + 8 = 16*

Наименьшее из полученных значений W₂ есть F₂ (0), т.е.

F₂ (x = y₃ = 0) = min W₂ (x₂,0) = min (22, 16) = 16,

x₂

причем минимум достигается при значении х₂, равном

` ₂ (x = y₃ = 0) = 1

Положим x = у₃ = 1. Тогда, согласно (5),

0 £ x₂ £ 2,

т.е. переменная х₂ может принимать значения: 0, 1, 2, а каждому значению х₂ отвечает определенное значение у₂, вычисляемое по формуле (7):

у₂ = 2 - х₂

Последовательно находим:

x₂ = 0, y₂ = 2 - 0 = 2, W₂ (0,1) = 2 * 0² + 6 + 1 + F₁(2) = 7 + 28 = 35

x₂ = 1, y₂ = 2 - 1 = 1, W₂ (1,1) = 2 * 1² + 6 + 1 + F₁(1) = 9 + 16 = 25

x₂ = 2, y₂ = 2 - 2 = 0, W₂ (2,1) = 2 * 2² + 6 + 1 + F₁(0) = 15 + 8 = 23*

Наименьшее из полученных значений W₂ есть F₂ (1), т.е.

F₂ (x = y₃ = 1) = min W₂ (x₂,1) = min (35, 25, 23) = 23,

x₂

причем минимум достигается при значении х₂, равном

` ₂ (x = y₃ = 1) = 2

Положим x = у₃ = 2. Тогда, согласно (5),

0 £ x₂ £ 3,

т.е. переменная х₂ может принимать значения: 0, 1, 2, 3, а каждому значению х₂ отвечает определенное значение у₂, вычисляемое по формуле (7):

у₂ = 3 - х₂

Последовательно находим:

x₂ = 0, y₂ = 3 - 0 = 3, W₂ (0,2) = 2 * 0² + 6 + 2 + F₁(3) = 8 + 44 = 52

x₂ = 1, y₂ = 3 - 1 = 2, W₂ (1,2) = 2 * 1² + 6 + 2 + F₁(2) = 10 + 28 = 38

x₂ = 2, y₂ = 3 - 2 = 1, W₂ (2,2) = 2 * 2² + 6 + 2 + F₁(1) = 16 + 16 = 32*

x₂ = 3, y₂ = 3 - 3 = 0, W₂ (3,2) = 2 * 3² + 6 + 2 + F₁(0) = 26 + 8 = 34

Наименьшее из полученных значений W₂ есть F₂ (2), т.е.

F₂ (x = y₃ = 2) = min W₂ (x₂,2) = min (52, 38, 32, 34) = 32,

x₂

причем минимум достигается при значении х₂, равном

₂ (x = y₃ = 2) = 2

Результаты табулирования функции F₂(x = y₃) сведены в Таблице 2.

Таблица 2

x= у3
F2 (x= y3)
(x= y3)

Переходим к следующему этапу. Полагаем k=3 и табулируем функцию F₃ (x = y₄):

F₃ (x = y₄) = min{a * x₃² + b * x₃ + c + h₃ * y₄ + F₂(y₃)} =

= min{2 * x₃² + 6 + y₄ + F₂(y₃)}

Вычисляем значение функции состояния только для одного значения аргумента x = у₄ = 0, так как не имеет смысла оставлять продукцию в запас в конце исследуемого периода.

Тогда, согласно (5),

0 £ x₃ £ 2,

т.е. переменная х₃ может принимать значения: 0, 1, 2, а каждому значению х₃ отвечает определенное значение у₃, вычисляемое по формуле (7):

у₃ = 2 - х₃

Последовательно находим:

x₃ = 0, y₃ = 2 - 0 = 2, W₂ (0,0) = 2 * 0² + 6 + 0 + F₂(2) = 6 + 32 = 38

x₃ = 1, y₃ = 2 - 1 = 1, W₂ (1,0) = 2 * 1² + 6 + 0 + F₂(1) = 8 + 23 = 31

x₃ = 2, y₃ = 2 - 2 = 0, W₂ (2,0) = 2 * 2² + 6 + 0 + F₂(0) = 14 + 16 = 30*

Получаем

F₃ (x = y₄) = min W₃ (x₃,0) = min (38, 31, 30) = 30,

x₃

причем минимум достигается в двух значениях переменной х₃

` ₃ (x = y₄ = 0) = 2

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

x₃* = 2

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

х₃ + у₃ - d₃ = y₄

2 + у₃ - 2 = 0,

у₃ = 0,

Из таблицы 2 значений находим

x₂*= ₂ (x = y₃ = 0) = 1

Аналогично, продолжая двигаться в обратном направлении и учитывая, что

х₂ + у₂ - d₂ = y₃

1 + у₂ - 1 = 0,

у₂ = 0

из таблицы (1) значений х₁(x) находим

x₁*= ₁ (x = y₂ = 0) = 1

Итак, оптимальный план производства имеет вид

х₁ = 1

х₂ = 1

х₃ = 2

а минимальные общие затраты составляют 30 единиц.