Динамическое программирование. Задача о ранце. Задача о ближайшем соседе

2. Динамическое программирование

В основе метода лежит идея рассмотрения исходной задачи как представителя семейства сходных с ней задач. Динамическое программирование (ДП) связано с многошаговым (многоэтапным) процессом принятия решений. При этом под многошаговым процессом принятия решений понимается деятельность, при которой принимаются последовательные решения, направленные на достижение одной цели. Методу ДП посвящено множество публикаций, в частности работы [1, 2, 5], в которых достаточно подробно рассмотрена техника решения задач методом динамического программирования.

В данном разделе мы будем изучать метод постепенно по принципу «от простого к сложному». Начнем с распределительной задачи.

      2.1. Распределительная задача

Сформулируем распределительную задачу на примере планирования деятельности предприятия на n лет. Пусть предприятие имеет ресурс в размере Y единиц, который оно может вложить в производство в течение  n лет. Функции f_t(x) отражают эффективность использования x единиц ресурса в год t. Требуется определить план расхода имеющегося ресурса по годам, чтобы максимизировать суммарную эффективность.

Обозначим через х_t искомую величину ресурса, вкладываемого в развитие производства в год t = 1, …, n. Тогда математическая модель может быть записана в виде

n

ft(xt) →max ; {x } t=1       t	(2.1)
n ∑ xt ≤ Y; t=1	(2.2)
xt ≥ 0, t = 1, ..., n.	(2.3)

Решение задачи (2.1)−(2.3) будем строить шаг за шагом, оптимизируя на текущем шаге размер инвестиций в год t. Будем предполагать функции  f_t(x) неубывающими, что позволяет перейти от исходной задачи к равносильной задаче (2.1), (2.2′), (2.3), в которой неравенство (2.2) заменено равенством

n

                                                   ∑ x_t = Y.(2.2′)

t=1

Для задачи (2.1), (2.2′), (2.3) используем обозначение <n, Y>. Кроме того, обозначим:

− S^* – оптимальное значение целевой функции (2.1);

 , …, x^*_n ) – оптимальное решение рассматриваемой задачи, т. е.

n

S^* ));

k=1 k

 оптимальное вложение ресурса за k первых лет, 

i=1

k = 1, …, n.

Далее воспользуемся терминологией и обозначениями из [2]. Наряду с

исходной        задачей        <n,        Y>       рассмотрим       семейство       задач 

π = {<k, y>: k = 1, …, n; 0 ≤ y ≤ Y}. Пусть S_k(y) – оптимальное значение целевой функции задачи <k, y>, тогда S^*= S_n(Y).

Теорема 2.1. Для задачи (2.1), (2.2′), (2.3) справедливы следующие рекуррентные соотношения ДП:

                                        S₁(y) = f₁(y), 0 ≤ y ≤ Y;(2.4)

            S_k, k = 2, …, n; 0 ≤ y ≤ Y.(2.5)

Значение переменной x, при котором достигается максимум в (2.5), обозначим через x_k(y) и назовем условно-оптимальным решением.

*

Следствие 2.1. Условно-оптимальное решение x_k(y _k ) является оптимальным значением k-й компоненты вектора x^* исходной задачи <n, Y>, 

*  *

т. е.  x _k = x_k(y _k ), k = 1, …, n.

Алгоритм ДП состоит из прямого хода (процесса последовательного вычисления величин S_k(y), k = 1, …, n; 0 ≤ y ≤ Y) и обратного хода (восстановления оптимального решения). На последнем шаге прямого хода полу-

*  чаем оптимальное значение последней переменной x _n = x_n(Y). Пусть уже

*  *                  *                  * найдены оптимальные значения ^x _n ^{, …, x} _k+1 . Тогда  ^x _k = x_k(^y _k ),где

*  *                  *

y k = y k+1− x k+1.

Схема (2.4), (2.5), как правило, требует численного расчета, но иногда удается получить выражение функций S_k(y) в аналитическом виде.

Пример 2.1. Рассмотрим метод ДП для задачи (2.1)−(2.3) с функциями

xi2 f_i(x_i)=   , где c_i > 0 и i = 1, …, n. c_i

y2

Прямой ход. На первом шаге получаем S₁(y) =                          и условно-

c1

оптимальное решение x₁(y) = y. Далее

2                    2 x           (y − x)

                     S₂(y) = min {f₂(x) + S₁(y − x)}= min {        +                }.

                                0≤ ≤x y                                              0≤ ≤x y     ^c₂              ^c₁

Выражение в фигурных скобках представляет выпуклую функцию, минимум которой можно найти, приравняв нулю ее производную. Получим x y x− c y₂ y²

− = 0, откуда x₂(y) =   , а S₂(y) =              . c2               c1               c1 +c2      c1 +c2

С помощью математической индукции нетрудно доказать, что 

                                                 y2                             c yk

                                S_k(y) = _k ,  x_k(y) = _k ,  0 ≤  y ≤  Y.

                                              ∑c_i                        ∑c_i

                                               i=1                             i=1

Обратный ход. Зная оптимальное значение последней переменной ^x_n , находим 

                                                                         n                                   n−1

                                                                 Y c c Y∑ i − n      Y∑ci

                      y*n−1=Y− x*n =Y− c Ynn  =     i=1 n                     =    ni=1      .

∑c_i ∑c_i ∑c_i i=1 i=1 i=1

Следовательно,

c Yn−1

x. n

∑c_i

i=1

Воспользовавшись математической индукцией, получим 

                                          x ^*_k = ^{c Y}_n^k , k = 1, …, n.

∑c_i

i=1

В общем случае для реализации алгоритма ДП нужна дискретность значений x_k. Пусть переменные x_k целые. Тогда величины y также целые. Следовательно, параметру y достаточно принимать значения из конечного множества {0, 1, …, Y}. Трудоемкость алгоритма в этом случае равна O(nY²), а требуемая память – O(nY).

Пример 2.2. На железнодорожную станцию прибыло 8 контейнеров, которые необходимо развезти по 5 складам. Емкость i-го склада – v_i контейнеров, затраты на транспортировку одного контейнера на этот  склад – g_i, а стоимость хранения x контейнеров – c_i(x). Требуется развезти все прибывшие контейнеры по складам, чтобы суммарные затраты на транспортировку и хранение были минимальны. 

Исходные данные задачи приведены в табл. 2.1 и 2.2.

Таблица 2.1

			Склады
	1	2	3	4	5
gi	0,5	1	1,2	1,5	2
vi	2	3	3	5	5

Таблица 2.2

x	c1(x)	c2(x)	c3(x)	c4(x)	c5(x)
1	2	1,5	1	0,5	0,3
2	4	2	2	1	0,5
3	−	3	3	1,5	1
4	−	−	−	2	1,5
5	−	−	−	2,5	2

Решение. Для записи математической постановки задачи введем функции h_i(x) = g_ix + c_i(x), i = 1, …, 5, которые задаются табл. 2.3. Тогда математическая модель имеет следующий вид:

                                                 ) → min      ;

x_i∈{0,1,...,^v_i }

i=1

5

∑ x_i = 8.

i=1

Таблица 2.3

x	h1(x)	h2(x)	h3(x)	h4(x)	h5(x)
1	2,5	2,5	2,2	2	2,3
2	5	4	4,4	4	4,5
3	−	6	6,6	6	7
4	−	−	−	8	9,5
5	−	−	−	10	12

Это распределительная задача, и для нее справедливы рекуррентные