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

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

1. Многошаговые процессы в динамических задачах. Некоторые задачи математического программирования обладают специфическими особенностями, которые позволяют свести их решение к рассмотрению некоторого множества более простых “подзадач”. В результате вопрос о глобальной оптимизации целевой функции сводится к поэтапной оптимизации некоторых промежуточных целевых функций.

Пусть, например, на некоторый период времени Т, состоящий из m лет, планируется деятельность группы промышленных предприятий. В начале планируемого периода на развитие предприятий выделяются основные средства Q ₀, которые необходимо распределить между предприятиями. В процессе функционирования предприятий выделенные им средства частично расходуются. Однако каждое из этих предприятий за определенный период времени (хозяйственный год) получает прибыль, зависящую от объема вложенных средств. В начале каждого года имеющиеся средства могут перераспределяться между предприятиями. Требуется определить, сколько средств надо выделить каждому предприятию в начале каждого года, чтобы суммарный доход от всей группы предприятий за весь период времени Т был максимальным.

Эта задача является естественно многошаговой. Шагом управления здесь будет хозяйственный год. Управление процессом состоит в перераспределении средств в начале каждого хозяйственного года.

Обычно методами динамического программирования оптимизируют работу некоторых управляемых систем, эффект которой оценивается аддитивной целевой функцией. Аддитивной называется функция многих переменных f (x ₁, x ₂, …, x_n) вида

где каждая функция f_j зависит только от одной переменной х_j. Слагаемые аддитивной целевой функции соответствуют эффекту решений, принимаемых на отдельных этапах управляемого процесса.

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

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

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

Этот принцип можно сформулировать и по-другому: оптимальное поведение в многошаговом процессе обладает тем свойством, что, какими бы ни были решение, принятое на последнем шаге, и состояние процесса перед последним шагом, предыдущие решения должны составлять оптимальное относительно этого состояния поведение.

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

(4.4)

l = 0, 1, …, n -1, где U_l = (u_l ⁽¹⁾; …; u_l ^{( m )}) - решение (управление), выбранное на l -м шаге; S_l = (s_l ⁽¹⁾; …; s_l ^{( m )}) - состояние системы на l -м шаге; R_l - непосредственный эффект, достигаемый на l -м шаге; f_n-l - оптимальное значение эффекта, достигаемого за n-l шагов; n - количество шагов (этапов). “Optimum” в выражении (4.4) означает максимум или минимум в зависимости от условия задачи. Формула (4.4) носит название уравнения Беллмана или рекурентного соотношения. Процесс вычисления f_n-l, l = 0, …, n -1, осуществляется при естественном начальном условии f ₀(S_n) = 0, которое означает, что за пределами конечного состояния системы эффект равен нулю.

Сформулированный принцип и уравнение Беллмана носят общий характер и применяются не только в задачах дискретной оптимизации. Метод динамического программирования широко используется для решения многих экономических задач, связанных с планированием производственных программ, оптимальным распределением ресурсов (денежных средств, рабочей силы, сырья и т. д.). Алгоритмы решения таких задач можно найти, например, в [3, 6].

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

3. Задача о кратчайшем маршруте. Требуется перевезти груз из города А в город В. Сеть дорог, связывающих эти города, изображена в виде графа на рис 4.1. Вершинам графа поставлены в соответствие города, а дугам - транспортные магистрали. Стоимость перевозки груза из города s (s = 1, …, 6) в город j (j = 2, …, 7) проставлена над соответствующими дугами графа. Необходимо найти маршрут, связывающий города А и В, для которого суммарные затраты на перевозку груза были бы наименьшими.

Для решения задачи разобьем все множество вершин (городов) на подмножества. В первое подмножество включим исходную вершину 1. Во второе - вершины, в которые входят дуги, выходящие из вершины 1. В третье - вершины, в которые входят дуги, выходящие из вершин второго подмножества. Таким образом, продолжая разбиение дальше, получим четыре подмножества: {1}, {2, 3, 4}, {5, 6}, {7}.Очевидно, что любой маршрут из города 1 в город 7 содержит ровно три дуги, каждая из которых связывает вершины, принадлежащие соответствующим подмножествам. Следовательно, процесс решения задачи (нахождения оптимального маршрута) разбивается на три этапа. На первом этапе принимается решение, через какой город, принадлежащий второму подмножеству, везти груз из города 1. На втором этапе необходимо определить, через какой город третьего подмножества везти груз из некоторого города, принадлежащего второму подмножеству. На последнем третьем этапе формируется оптимальный маршрут.

Перенумеруем этапы от конечной вершины графа к начальной и введем обозначения: n - номер шага (n = 1, 2, 3); f_n (s) - минимальные затраты на перевозку груза от города s до конечного города В, если до конечного города осталось n шагов; j_n (s) - номер города, через который надо ехать из города s, чтобы достичь затрат f_n (s); c_{s, j} -стоимость перевозки груза из города s в город j.

Здесь все обозначения несут важную смысловую нагрузку: f означает целевую функцию, s - состояние системы (номер города), индекс n несет динамическую информацию о том, что из города s до конечного города осталось n шагов.

Предположим, что груз доставлен в город 7, следовательно, число оставшихся шагов равно нулю (n = 0) и f_n (s) = f ₀(7) = 0, так как из города 7 груз вести не надо.

Рассмотрим последний шаг (n = 1) и вычислим для него значение функции. Очевидно, что в город 7 груз может быть доставлен из города 5 или из города 6. Вычислим затраты на перевозку для этих двух состояний:

Чтобы произвести расчет для n = 2 выдвинем гипотезы о месте нахождения груза: 1-я гипотеза - груз находится в городе 2; 2-я гипотеза - груз находится в городе 3; 3-я гипотеза - груз находится в городе 4.

Из города 2 в город 7 можно перевезти груз или через город 5, или через город 6. Поэтому оптимальный маршрут из города 2 найдется из выражения

Здесь s = 2 и j ₂(2) = 6, т. е. условно-оптимальный маршрут проходит через город 6. Аналогично для s = 3 и s = 4:

Вычисления для третьего шага (n =3) показывают, что

j ₃(1) = 2, т. е. минимальные затраты на перевозку груза f ₃(1)=11 и оптимальный маршрут проходит через город 2. Далее из вычислений f ₂(2) следует, что оптимальный маршрут проходит через город 6, так как j ₂(2) = 6. Наконец, из города 6 груз доставляется в конечный город 7 (место назначения). Таким образом, мы определили оптимальный маршрут х * = (1-2-6-7), затраты на перевозку груза по которому составляют f ₃(1) = 4 + + 4 + 3 = 11.

Следует отметить, что метод динамического программирования применим только для нахождения кратчайшего пути на связных графах, где любой маршрут состоит из одного и того же числа дуг, как, например, на рис 4.1. Для графов более общей структуры используются соответствующие алгоритмы теории графов (см. [10]).

Контрольные вопросы и задания

4.1. Сформулируйте задачу целочисленного линейного программирования.

4.2. Сформулируйте задачу о рюкзаке. К какому классу задач целочисленного программирования она относится?

4.3. Сформулируйте задачу о комивояжере. К какому классу задач целочисленного программирования она относится?

4.4. В чем состоит суть задачи раскроя?

4.5. Какова основная идея методов ветвей и границ?

4.6. Объясните значения понятий “ветвление” и “граница”, используемых в методе ветвей и границ?

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

4.8. Каковы правила выбора переменной ветвления?

4.9. Для каких оптимизационных задач применяется метод динамического программирования?

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

4.11. Сформулируйте принцип оптимальности Беллмана.

4.12. Что является целевой функцией в задаче о кратчайшем маршруте? Какой параметр определяет состояние системы на каждом шаге?

4.13. При помощи метода ветвей и границ решите следующие задачи ЦЛП:

а) ¦ = 10 х ₁ - 9 х ₂ ® min б) ¦ = -4 х ₁ - 3 х ₂ ® min

Х: х ₁ £ 8, х ₂ £ 10, Х: -8 х ₁ - 2 х ₂ ³ 88,

5 х ₁ + 3 х ₂ ³ 45, х ₁ £ 22, х ₂ £ 45,

х_j = 0, 1, 2, …; j =1, 2. х_j = 0, 1, 2, …; j =1, 2.

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

ЛИТЕРАТУРА

1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986. 328 с.

2. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике: В 2 кн.: Пер. с англ. М.: Мир, 1986. Кн.1 - 352 с. Кн.2 - 320 с.

3. Конюховский П.В. Математические методы исследования операций в экономике. СПб.: Издательство “Питер”, 2000. - 208 с.

4. Банди Б. Методы оптимизации. Вводный курс: Пер. с англ. М.: Радио и связь, 1988. - 128 с.: ил.

5. Ракитин В.И., Первушин В.Е. Практическое руководство по методам вычислений с приложением программ для персональных компьютеров. М.: Высшая школа, 1988. - 383с.

6. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию. Минск: Вышэйшая школа, 1978. 256 с.

7. Бугров Я.С., Никольский С.М. Высшая математика. Дифференциальное и интегральное исчисление. М.: 1984

8. Кудрявцев Л.Д. Курс математического анализа. В 3 т. М.: 1988, 1989, т.1 - 540 с., т.2 - 576 с.

9. Сборник задач по математике для ВТУЗов: В 3 кн. Кн. 3: Специальные курсы / Под ред. Ефимова А.В. М.: Наука, 1984. - 608 с.

10. Новиков Ф.А. Дискретная математика для прораммистов. СПб.: Питер, 2000. -304 с.: ил.

ОГЛАВЛЕНИЕ

Глава 1.Введение в оптимизацию.............. 3

§1. Постановка и классификация задач оптимизации.......5

§ 2. Общие сведения о численных методах оптимизации. Условия оптимальности.......................... 9

Контрольные вопросы и задания....................15

Глава 2. Методы безусловной оптимизации.... 16

§ 1. Постановка задачи безусловной оптимизации..........16

§ 2. Методы одномерной минимизации.................. 18

§ 3. Методы многомерной безусловной оптимизации........29

Контрольные вопросы и задания....................43

Глава 3. ЛиНЕЙНОЕ ПРОГРАММИРОВАНИЕ..........45

§ 1. Задачи линейного программирования и их свойства......45

§ 2. Симплекс-метод.................................54

§ 3. Теория двойственности в линейном программировании..65

§ 4. Разработка моделей линейного программирования...... 70

§ 5. Транспортная задача............................. 74

Контрольные вопросы и задания.................. 76

Глава 4. МЕТОДЫ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ..... 80

§ 1. Постановка и примеры дискретных оптимизационных задач..........................................80

§ 2. Методы решения задач целочисленного

программирования...............................86

§ 3. Динамическое программирование...................91

Контрольные вопросы и задания.................. 97

Литература........................................99

Учебное издание