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

Страницы работы

Фрагмент текста работы

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

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

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

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

Сформулируем распределительную задачу на примере планирования деятельности предприятия на n лет. Пусть предприятие имеет ресурс в размере Y единиц, который оно может вложить в производство в течение  n лет. Функции ft(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. Будем предполагать функции  ft(x) неубывающими, что позволяет перейти от исходной задачи к равносильной задаче (2.1), (2.2′), (2.3), в которой неравенство (2.2) заменено равенством

n

                                                   ∑ xt = 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}. Пусть Sk(y) – оптимальное значение целевой функции задачи <k, y>, тогда S*= Sn(Y).

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

                                        S1(y) = f1(y), 0 ≤ y Y;(2.4)

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

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

*

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

*  *

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

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

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

*  *                  *                  * найдены оптимальные значения x n , …, x k+1 . Тогда  x k = xk(y k ),где

*  *                  *

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

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

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

xi2 fi(xi)=   , где ci > 0 и i = 1, …, n. ci

y2

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

c1

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

2                    2 x           (y x)

                     S2(y) = min {f2(x) + S1(y x)}= min {        +                }.

                                0≤ ≤x y                                              0≤ ≤x y     c2              c1

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

= 0, откуда x2(y) =   , а S2(y) =              . c2               c1               c1 +c2      c1 +c2

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

                                                 y2                             c yk

                                Sk(y) = k ,  xk(y) = k 0 ≤  y   Y.

                                              ∑ci                        ci

                                               i=1                             i=1


Таким образом, 

                             *                                               Y 2c Yn

ci

i=1

ci

i=1

                            S = Sn(Y) = n            ,  x                  = n           .

*


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

                                                                         n                                   n−1

                                                                 Y c c Yi n      Yci

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

ci ci ci i=1 i=1 i=1

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

c Yn1

x. n

ci

i=1

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

                                          x *k = c Ynk , k = 1, …, n.

ci

i=1

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

Пример 2.2. На железнодорожную станцию прибыло 8 контейнеров, которые необходимо развезти по 5 складам. Емкость i-го склада – vi контейнеров, затраты на транспортировку одного контейнера на этот  склад – gi, а стоимость хранения x контейнеров – ci(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

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

                                                 ) → min      ;

xi∈{0,1,...,vi }

i=1

5

xi = 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

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

Похожие материалы

Информация о работе

Предмет:
Математика
Тип:
Конспекты лекций
Размер файла:
383 Kb
Скачали:
0