Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

Динамическое программирование для начинающих

    Статьи, 7 июня 2016 в 15:04

Динамическое программирование — тема, которой в рунете посвящено довольно мало статей, поэтому мы решили ею заняться. В этой статье будут разобраны классические задачи на последовательности, одномерную и двумерную динамику, будет дано обоснование решениям и описаны разные подходы к их реализации. Весь приведённый в статье код написан на Java.

О чём вообще речь? Что такое динамическое программирование?

Динамическое программирование — метод решения задачи путём её разбиения на несколько одинаковых подзадач, рекуррентно связанных между собой. Самым простым примером будут числа Фибоначчи — чтобы вычислить некоторое число в этой последовательности, нам нужно сперва вычислить третье число, сложив первые два, затем четвёртое таким же образом на основе второго и третьего, и так далее (да, мы слышали про замкнутую формулу) .

Хорошо, как это использовать?

Решение задачи динамическим программированием должно содержать следующее:

  • Зависимость элементов динамики друг от друга. Такая зависимость может быть прямо дана в условии (так часто бывает, если это задача на числовые последовательности). В противном случае вы можете попытаться узнать какой-то известный числовой ряд (вроде тех же чисел Фибоначчи), вычислив первые несколько значений вручную. Если вам совсем не повезло – придётся думать
  • Значение начальных состояний. В результате долгого разбиения на подзадачи вам необходимо свести функцию либо к уже известным значениям (как в случае с Фибоначчи — заранее определены первые два члена), либо к задаче, решаемой элементарно.

И что, мне для решения рекурсивный метод писать надо? Я слышал, они медленные.

Конечно, не надо, есть и другие подходы к реализации динамики. Разберём их на примере следующей задачи:

Идея решения

Здесь нам даны и начальные состояния (a = a1 = 1), и зависимости. Единственная сложность, которая может возникнуть — понимание того, что 2n — условие чётности числа, а 2n+1 — нечётности. Иными словами, нам нужно проверять, чётно ли число, и считать его в зависимости от этого по разным формулам.

Рекурсивное решение

Очевидная реализация состоит в написании следующего метода:

И она отлично работает, но есть нюансы. Если мы захотим вычислить f(12) , то метод будет вычислять сумму f(6)+f(5) . В то же время, f(6)=f(3)+f(2) и f(5)=f(2)-f(1) , т.е. значение f(2) мы будем вычислять дважды. Спасение от этого есть — мемоизация (кеширование значений).

Рекурсивное решение с кэшированием значений

Идея мемоизации очень проста — единожды вычисляя значение, мы заносим его в какую-то структуру данных. Перед каждым вычислением мы проверяем, есть ли вычисляемое значение в этой структуре, и если есть, используем его. В качестве структуры данных можно использовать массив, заполненный флаговыми значениями. Если значение элемента по индексу N равно значению флага, значит, мы его ещё не вычисляли. Это создаёт определённые трудности, т.к. значение флага не должно принадлежать множеству значений функции, которое не всегда очевидно. Лично я предпочитаю использовать хэш-таблицу — все действия в ней выполняются за O(1), что очень удобно. Однако, при большом количестве значений два числа могут иметь одинаковый хэш, что, естественно, порождает проблемы. В таком случае стоит использовать, например, красно-чёрное дерево.

Для уже написанной функции f(int) кэширование значений будет выглядеть следующим образом:

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

Последовательное вычисление

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

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

LATOKEN, Москва, от 200 000 до 360 000 ₽

Суть метода в следующем: мы создаём массив на N элементов и последовательно заполняем его значениями. Вы, наверное, уже догадались, что таким образом мы можем вычислять в том числе те значения, которые для ответа не нужны. В значительной части задач на динамику этот факт можно опустить, так как для ответа часто бывают нужны как раз все значения. Например, при поиске наименьшего пути мы не можем не вычислять путь до какой-то точки, нам нужно пересмотреть все варианты. Но в нашей задаче нам нужно вычислять приблизительно log2(N) значений (на практике больше), для 922337203685477580-го элемента (MaxLong/10) нам потребуется 172 вычисления.

Ещё одним минусом такого подхода является сравнительно большой расход памяти.

Создание стека индексов

Сейчас нам предстоит, по сути, написать свою собственную рекурсию. Идея состоит в следующем — сначала мы проходим «вниз» от N до начальных состояний, запоминая аргументы, функцию от которых нам нужно будет вычислять. Затем возвращаемся «вверх», последовательно вычисляя значения от этих аргументов, в том порядке, который мы записали.

Зависимости вычисляются следующим образом:

Полученный размер стека – то, сколько вычислений нам потребуется сделать. Именно так я получил упомянутое выше число 172.

Теперь мы поочередно извлекаем индексы и вычисляем для них значения по формулам – гарантируется, что все необходимые значения уже будут вычислены. Хранить будем как раньше – в хэш-таблице.

Все необходимые значения вычислены, осталось только написать

Конечно, такое решение гораздо более трудоёмкое, однако это того стоит.

Хорошо, математика — это красиво. А что с задачами, в которых не всё дано?

Для больше ясности разберём следующую задачу на одномерную динамику:

На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных «маршрутов» мячика с вершины на землю.

Идея решения

На первую ступеньку можно попасть только одним образом — сделав прыжок с длиной равной единице. На вторую ступеньку можно попасть сделав прыжок длиной 2, или с первой ступеньки — всего 2 варианта. На третью ступеньку можно попасть сделав прыжок длиной три, с первой или со втрой ступенек. Т.е. всего 4 варианта (0->3; 0->1->3; 0->2->3; 0->1->2->3). Теперь рассмотрим четвёртую ступеньку. На неё можно попасть с первой ступеньки — по одному маршруту на каждый маршрут до неё, со второй или с третьей — аналогично. Иными словами, количество путей до 4-й ступеньки есть сумма маршрутов до 1-й, 2-й и 3-й ступенек. Математически выражаясь, F(N) = F(N-1)+F(N-2)+F(N-3). Первые три ступеньки будем считать начальными состояниями.

Реализация через рекурсию

Здесь ничего хитрого нет.

Реализация через массив значений

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

Так как каждое следующее значение зависит только от трёх предыдущих, ни одно значение под индексом меньше i-3 нам бы не пригодилось. В приведённом выше коде мы записываем новое значение на место самого старого, не нужного больше. Цикличность остатка от деления на 3 помогает нам избежать кучи условных операторов. Просто, компактно, элегантно.

Там вверху ещё было написано про какую-то двумерную динамику.

С двумерной динамикой не связано никаких особенностей, однако я, на всякий случай, рассмотрю здесь одну задачу и на неё.

В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть способов у игрока попасть в правую нижнюю клетку.

Идея решения

Логика решения полностью идентична таковой в задаче про мячик и лестницу — только теперь в клетку (x,y) можно попасть из клеток (x-1,y) или (x, y-1). Итого F(x,y) = F(x-1, y)+F(x,y-1). Дополнительно можно понять, что все клетки вида (1,y) и (x,1) имеют только один маршрут — по прямой вниз или по прямой вправо.

Реализация через рекурсию

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

Реализация через массив значений

Классическое решение динамикой, ничего необычного — проверяем, является ли клетка краем, и задаём её значение на основе соседних клеток.

Отлично, я всё понял. На чём мне проверить свои навыки?

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

Взрывоопасность

При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N определить количество возможных типов безопасных стопок.

Решение

Ответом является (N+1)-е число Фибоначчи. Догадаться можно было, просто вычислив 2-3 первых значения. Строго доказать можно было, построив дерево возможных построений.

Каждый основной элемент делится на два — основной (заканчивается на B) и побочный (заканчивается на A). Побочные элементы превращаются в основные за одну итерацию (к последовательности, заканчивающейся на A, можно дописать только B). Это характерно для чисел Фибоначчи.

Читать еще:  Crc ошибки что это
Реализация

Подъём по лестнице

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

Решение

Очевидно, что сумма, которую мальчик отдаст на N-ой ступеньке, есть сумма, которую он отдал до этого плюс стоимость самой ступеньки. «Сумма, которую он отдал до этого» зависит от того, с какой ступеньки мальчик шагает на N-ую — с (N-1)-й или с (N-2)-й. Выбирать нужно наименьшую.

Реализация

Калькулятор

Имеется калькулятор, который выполняет три операции:

  • Прибавить к числу X единицу;
  • Умножить число X на 2;
  • Умножить число X на 3.

Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N. Выведите это число, и, на следующей строке, набор исполненных операций вида «111231».

Решение

Наивное решение состоит в том, чтобы делить число на 3, пока это возможно, иначе на 2, если это возможно, иначе вычитать единицу, и так до тех пор, пока оно не обратится в единицу. Это неверное решение, т.к. оно исключает, например, возможность убавить число на единицу, а затем разделить на три, из-за чего на больших числах (например, 32718) возникают ошибки.

Правильное решение заключается в нахождении для каждого числа от 2 до N минимального количества действий на основе предыдущих элементов, иначе говоря: F(N) = min(F(N-1), F(N/2), F(N/3)) + 1. Следует помнить, что все индексы должны быть целыми.

Для воссоздания списка действий необходимо идти в обратном направлении и искать такой индекс i, что F(i)=F(N), где N — номер рассматриваемого элемента. Если i=N-1, записываем в начало строки 1, если i=N/2 — двойку, иначе — тройку.

Реализация

Самый дешёвый путь

В каждой клетке прямоугольной таблицы N*M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).

Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол.

Решение

В любую клетку таблицы мы можем попасть либо из клетки, находящейся непосредственно над ней, либо из клетки, находящейся непосредственно слева. Таким образом, F(x,y) = min(F(x-1,y), F(x,y-1)). Чтобы не обрабатывать граничные случаи, можно добавить первую строку и столбец, заполненные некоторой константой — каким-то числом, заведомо большим содержимого любой из клеток.

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

Решение находим с помощью сервиса распределение средств между предприятиями
Введём обозначения:
Х — количество средств, выделенных каждому предприятию.
Суммарная прибыль равна: Z =∑ F k (Х).
Переменные удовлетворяют ограничениям:
∑Х k =5
Х k ≥0
Требуется найти переменные Х1,Х2,Х3,Х4, удовлетворяющие системе уравнений и обращающие в максимум функцию.
Таблица

Используя уравнение Беллмана рассмотрим алгоритм решения задачи.
Если Х1=0, то S 1 =5, то прибыль, полученная от четырёх предприятий при этих условиях, будет равна: Z1 = 0+19=19.
Если Х1=1, то S 2=4, то прибыль при этих условиях равна: Z 1 = 8+16=24.
Если Х1=2, то S 2 =3, то прибыль при этих условиях равна: Z 3 = 10+13=23
Если Х1=3, то S 2 =2, то прибыль при этих условиях равна:
Z 4 = 11+10=2110+13=23
Если Х1=4, то S 2 =1, то прибыль при этих условиях равна: Z 5 = 12+16=28
Если Х1=5, то S 2 =0, то прибыль при этих условиях равна: Z 5 =18+0=18
Сравнивая полученные числа, получим: Z 1 = 24, при Х1=1.
Максимум суммарной прибыли Zmaх = 24 ус/ед. при условии, что:
— первому предприятию выделено 1 ус/ед.;
— второму предприятию 2 ус/ед.;
— третьему предприятию 1 ус/ед.;
— четвёртому предприятию 1 ус/ед.

I этап. Условная оптимизация.
1-ый шаг. k = 4.

Поясним построение таблиц и последовательность проведения расчетов.
Столбцы 1, 2 и 3 для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 4-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.
Этап II. Безусловная оптимизация.
Из таблицы 1-го шага имеем F*4(e 0 = 5) = 24. То есть максимальный доход всей системы при количестве средств e 0 = 5 равен 24.
Из этой же таблицы получаем, что 1-му предприятию следует выделить u*1(e 0 = 5) = 1
При этом остаток средств составит:
e 1 = e 0 — u 1
e 1 = 5 — 1 = 4
Из таблицы 2-го шага имеем F*3(e 1 = 4) = 16. То есть максимальный доход всей системы при количестве средств e 1 = 4 равен 16.
Из этой же таблицы получаем, что 2-му предприятию следует выделить u*2(e 1 = 4) = 2
При этом остаток средств составит:
e 2 = e 1 — u 2
e 2 = 4 — 2 = 2
Из таблицы 3-го шага имеем F*2(e 2 = 2) = 7. То есть максимальный доход всей системы при количестве средств e 2 = 2 равен 7.
Из этой же таблицы получаем, что 3-му предприятию следует выделить u*3(e 2 = 2) = 1
При этом остаток средств составит:
e 3 = e 2 — u 3
e 3 = 2 — 1 = 1
Последнему предприятию достается 1.
Итак, инвестиции в размере 5 необходимо распределить следующим образом:
1-му предприятию выделить 1,
2-му предприятию выделить 2,
3-му предприятию выделить 1,
4-му предприятию выделить 1.
Что обеспечит максимальный доход, равный 24.

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

Динамическое программирование — это вычислительный метод для решения задач определенной структуры. Возникло и сформировалось в 1950-1953 гг. благодаря работам Р. Беллмана над динамическими задачами управления запасами. В упрощенной формулировке динамическое программирование представляет собой направленный последовательный перебор вариантов, который обязательно приводит к глобальному максимуму.

Основные необходимые свойства задач, к которым возможно применить этот принцип:

  1. Задача должна допускать интерпретацию как n-шаговый процесс принятия решений.
  2. Задача должна быть определена для любого числа шагов и иметь структуру, не зависящую от их числа.

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

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

Постановку задачи динамического программирования рассмотрим на примере инвестирования, связанного с распределением средств между предприятиями. В результате управления инвестициями система последовательно переводится из начального состояния S В конечное S n . Предположим, что управление можно разбить на n шагов и решение принимается последовательно на каждом шаге, а управление представляет собой совокупность n пошаговых управлений. На каждом шаге необходимо определить два типа переменных — переменную состояния системы S k переменную управления x k . Переменная S k определяет, в каких состояниях может оказаться система на рассматриваемом k-м шаге. В зависимости от состояния S на этом шаге можно применить некоторые управления, которые характеризуются переменной xk которые удовлетворяют определенным ограничениям и называются допустимыми. Допустим. = (x 1 , x 2 , . x k , . x n ) — управление, переводящее систему на состояния S в состояние S n , a S k — есть состояние системы на k-м шаге управления. Тогда последовательность состояний системы можно представить в виде графа, представленного на рис. 2.11.

Применение управляющего воздействия x k на каждом шаге переводит систему в новое состояние S 1 (S, x k ) и приносит некоторый результат W k (S, x k ). Для каждого возможного состояния на каждом шаге среди всех возможных управлений выбирается оптимальное управление x* k , такое, чтобы результат, который достигается за шаги с k-го по последний n-й, оказался бы оптимальным. Числовая характеристика этого результата называется функцией Беллмана F k (S) и зависит от номера шага k и состояния системы S. Задача динамического программирования формулируется следующим образом: требуется определить такое управление , переводящее систему из начального состояния S в конечное состояние S n , при котором целевая функция принимает наибольшее (наименьшее) значение F(S ,) => extr.

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

  1. задача оптимизации формулируется как конечный многошаговый процесс управления;
  2. целевая функция (выигрыш) является аддитивной и равна сумме целевых функций каждого шага:

Принцип оптимальности и математическое описание динамического процесса управления.
В основе метода ДП лежит принцип оптимальности, впервые сформулированный в 1953 г. американским математиком Р.Э.Беллманом: каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая выигрыш на данном шаге. При решении задачи на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. Если считать все шаги независимыми, тогда оптимальным управлением будет то управление, которое обеспечит максимальный выигрыш именно на данном шаге. Однако, например, при покупке новой техники взамен устаревшей на ее приобретение затрачиваются определенные средства, поэтому доход от ее эксплуатации в начале может быть небольшой, а в следующие годы новая техника будет приносить больший доход. И наоборот, если принято решение оставить старую технику для получения дохода в текущем году, то в дальнейшем это приведет к значительным убыткам. Этот пример демонстрирует следующий факт: в многошаговых процессах управление на каждом конкретном шаге надо выбирать с учетом его будущих воздействий на весь процесс. Кроме того, при выборе управления на данном шаге следует учитывать возможные варианты состояния предыдущего шага. Например, при определении количества средств, вкладываемых в предприятие в i-м году, необходимо знать, сколько средств осталось в наличия к атому году и какой доход получен в предыдущем (i — 1)-м году. Таким образом, при выборе шагового управления необходимо учитывать следующие требования:

  1. возможные исходы предыдущего шага S k-1;
  2. влияние управления x k на все оставшиеся до конца процесса шаги (n-k).

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

Условная оптимизация

На первом этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м шаге оптимальное управление — х* n определяется функцией Беллмана: F(S) = max n (S, x n )>, в соответствии с которой максимум выбирается из всех возможных значений x n , причем x n € X.
Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге. В общем виде это уравнение имеет вид F n (S) = max n (S, x n ) + F k+1 (S n (S, x k )> x k € X.
Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

Безусловная оптимизация

После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый, осуществляется второй этап решения задачи, называемый безусловной оптимизацией. Пользуясь тем, что на первом шаге (k = 1) состояние системы известно — это ее начальное состояние S , можно найти оптимальный результат за все n шагов и оптимальное управление на первом шаге x 1 , которое этот результат доставляет. После применения этого управления система перейдет в другое состояние S 1 (S, x* 1 ), зная которое, можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге x* 2 , и так далее до последнего n-го шага. Вычислительную схему динамического программирования можно строить на сетевых моделях, а также по алгоритмам прямой прогонки (от начала) и обратной прогонки (от конца к началу). Рассмотрим примеры решения различных по своей природе задач, содержание которых требует выбора переменных состояния и управления.

Динамическое программирование — это вычислительный метод для решения задач определенной структуры. Возникло и сформировалось в 1950-1953 гг. благодаря работам Р. Беллмана над динамическими задачами управления запасами. В упрощенной формулировке динамическое программирование представляет собой направленный последовательный перебор вариантов, который обязательно приводит к глобальному максимуму.

Основные необходимые свойства задач, к которым возможно применить этот принцип:

  1. Задача должна допускать интерпретацию как n-шаговый процесс принятия решений.
  2. Задача должна быть определена для любого числа шагов и иметь структуру, не зависящую от их числа.

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

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

Постановку задачи динамического программирования рассмотрим на примере инвестирования, связанного с распределением средств между предприятиями. В результате управления инвестициями система последовательно переводится из начального состояния S В конечное S n . Предположим, что управление можно разбить на n шагов и решение принимается последовательно на каждом шаге, а управление представляет собой совокупность n пошаговых управлений. На каждом шаге необходимо определить два типа переменных — переменную состояния системы S k переменную управления x k . Переменная S k определяет, в каких состояниях может оказаться система на рассматриваемом k-м шаге. В зависимости от состояния S на этом шаге можно применить некоторые управления, которые характеризуются переменной xk которые удовлетворяют определенным ограничениям и называются допустимыми. Допустим. = (x 1 , x 2 , . x k , . x n ) — управление, переводящее систему на состояния S в состояние S n , a S k — есть состояние системы на k-м шаге управления. Тогда последовательность состояний системы можно представить в виде графа, представленного на рис. 2.11.

Применение управляющего воздействия x k на каждом шаге переводит систему в новое состояние S 1 (S, x k ) и приносит некоторый результат W k (S, x k ). Для каждого возможного состояния на каждом шаге среди всех возможных управлений выбирается оптимальное управление x* k , такое, чтобы результат, который достигается за шаги с k-го по последний n-й, оказался бы оптимальным. Числовая характеристика этого результата называется функцией Беллмана F k (S) и зависит от номера шага k и состояния системы S. Задача динамического программирования формулируется следующим образом: требуется определить такое управление , переводящее систему из начального состояния S в конечное состояние S n , при котором целевая функция принимает наибольшее (наименьшее) значение F(S ,) => extr.

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

  1. задача оптимизации формулируется как конечный многошаговый процесс управления;
  2. целевая функция (выигрыш) является аддитивной и равна сумме целевых функций каждого шага:

Принцип оптимальности и математическое описание динамического процесса управления.
В основе метода ДП лежит принцип оптимальности, впервые сформулированный в 1953 г. американским математиком Р.Э.Беллманом: каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая выигрыш на данном шаге. При решении задачи на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. Если считать все шаги независимыми, тогда оптимальным управлением будет то управление, которое обеспечит максимальный выигрыш именно на данном шаге. Однако, например, при покупке новой техники взамен устаревшей на ее приобретение затрачиваются определенные средства, поэтому доход от ее эксплуатации в начале может быть небольшой, а в следующие годы новая техника будет приносить больший доход. И наоборот, если принято решение оставить старую технику для получения дохода в текущем году, то в дальнейшем это приведет к значительным убыткам. Этот пример демонстрирует следующий факт: в многошаговых процессах управление на каждом конкретном шаге надо выбирать с учетом его будущих воздействий на весь процесс. Кроме того, при выборе управления на данном шаге следует учитывать возможные варианты состояния предыдущего шага. Например, при определении количества средств, вкладываемых в предприятие в i-м году, необходимо знать, сколько средств осталось в наличия к атому году и какой доход получен в предыдущем (i — 1)-м году. Таким образом, при выборе шагового управления необходимо учитывать следующие требования:

  1. возможные исходы предыдущего шага S k-1;
  2. влияние управления x k на все оставшиеся до конца процесса шаги (n-k).

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

Условная оптимизация

На первом этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м шаге оптимальное управление — х* n определяется функцией Беллмана: F(S) = max n (S, x n )>, в соответствии с которой максимум выбирается из всех возможных значений x n , причем x n € X.
Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге. В общем виде это уравнение имеет вид F n (S) = max n (S, x n ) + F k+1 (S n (S, x k )> x k € X.
Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

Безусловная оптимизация

После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый, осуществляется второй этап решения задачи, называемый безусловной оптимизацией. Пользуясь тем, что на первом шаге (k = 1) состояние системы известно — это ее начальное состояние S , можно найти оптимальный результат за все n шагов и оптимальное управление на первом шаге x 1 , которое этот результат доставляет. После применения этого управления система перейдет в другое состояниеS 1 (S, x* 1 ), зная которое, можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге x* 2 , и так далее до последнего n-го шага. Вычислительную схему динамического программирования можно строить на сетевых моделях, а также по алгоритмам прямой прогонки (от начала) и обратной прогонки (от конца к началу). Рассмотрим примеры решения различных по своей природе задач, содержание которых требует выбора переменных состояния и управления.

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

Автор работы: Пользователь скрыл имя, 11 Декабря 2012 в 19:17, курсовая работа

Описание

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

Работа состоит из 1 файл

Federalnoe_gosudarstvennoe_byudzhetnoe_obrazova.doc

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

РОССИЙСКАЯ АКАДЕМИЯ НАРОДНОГО ХОЗЯЙСТВА И ГОСУДАРСТВЕННОЙ СЛУЖБЫ

ПРИ ПРЕЗИДЕНТЕ РОССИЙСКОЙ ФЕДЕРАЦИИ

НИЖЕГОРОДСКИЙ ИНСТИТУТ УПРАВЛЕНИЯ

Факультет заочного обучения

Кафедра математики и системного анализа

ПО ДИСЦИПЛИНЕ «Разработка управленческого решения»

«Применение моделей динамического программирования для решения управленческих задач»

Выполнила: студентка 4 курса, группы ГК-641

Макаров Сергей Александрович

Введение.

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

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

— определить предмет и особенности динамического программирования;

— разъяснить принцип Беллмана, лежащий в основе метода;

— построить алгоритм решения задач методом динамического программирования;

— выявить преимущества и недостатки данного метода.

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

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

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

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

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

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

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

Выделим особенности модели ДП:

  1. Задача оптимизации интерпретируется как n-шаговый процесс управления.
  2. Критерий должен обладать свойством аддитивности, т.е. его величина есть сумма частных величин, достигаемых на отдельных этапах. Целевая функция равна сумме целевых функций каждого шага.
  3. Рассматриваемый процесс должен быть марковским, т.е. в нем предыстория не должна иметь значения для определения будущих действий. Выбор управления на k-м шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги (нет обратной связи).
  4. Состояние Sk после k-го шага управления зависит только от предшествующего состояния Sk-1 и управления Xk (отсутствие последействия).
  5. На каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние Sk — от конечного числа параметров.

Принцип оптимальности Беллмана.

Принцип оптимальности впервые был сформулирован Р. Беллманом в 1953 г. «Оптимальное поведение обладает тем свойством, что, каковы бы ни были первоначальное состояние и решение в начальный момент, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения» 1 .

Из этого следует, что планирование каждого шага должно проводиться с учетом общей выгоды, получаемой по завершении всего процесса, что и позволяет оптимизировать конечный результат по выбранному критерию. Каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая выигрыш на данном шаге. Беллманом четко были сформулированы и условия, при которых принцип верен. Основное требование — процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги. Принцип оптимальности утверждает, что для любого процесса без обратной связи оптимальное управление таково, что оно является оптимальным для любого подпроцесса по отношению к исходному состоянию этого подпроцесса. Поэтому решение на каждом шаге оказывается наилучшим с точки зрения управления в целом. Если изобразить геометрически оптимальную траекторию в виде ломаной линии, то любая часть этой ломаной будет являться оптимальной траекторией относительно начала и конца.

На первом этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м шаге, оптимальное управление х * n определяется функцией Беллмана: V(S)=maxn(S,xn)>, в соответствии с которой максимум выбирается из всех возможных значений хn, причем хn∈Х.

Дальнейшие вычисления производятся согласно соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге:

Vn * — условный максимум целевой функции показателя эффективности n-го шага при условии, что к началу последнего шага система S была в произвольном состоянии Sn-1, а на последнем шаге управление было оптимальным.

Sn-1 — состояние системы к началу n-го шага,

Хn — управление на n-м шаге,

Согласно принципу оптимальности, Хn нужно выбирать так, чтобы для любых состояний Sn-1 получить максимум целевой функции на этом шаге.

После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый, осуществляется второй этап решения задачи, называемый безусловной оптимизацией. Пользуясь тем, что на первом шаге (k = 1) состояние системы известно – это ее начальное состояние S, можно найти оптимальный результат за все n шагов.

Задачи динамического программи рования.

Алгоритм решения задач методом динамического программировани я.

Рассмотрим в общем виде алгоритм решения задач методом динамического программирования.

Будем считать, что состояние Sk рассматриваемой системы S на k-м шаге (k = 1, 2, . n) определяется совокупностью чисел Sk= (S1, S2 … Sm), которые получены в результате реализации управления Xk, обеспечивающего переход системы S из состояния Sk-1 в состояние Sk.

Пусть также выполняются два условия:

1. Условие отсутствия последействия. Состояние Sk, в которое перешла система S, зависит от исходного состояния Sk-1 и выбранного управления Xk и не зависит от того, каким образом система S перешла в состояние Sk-1.

2. Условие аддитивности. Если в результате реализации k-го шага обеспечен определенный выигрыш, также зависящий от исходного состояния системы и выбранного управления, то общий выигрыш fk(Sk-1,xk)за k шагов составит

Задача состоит в нахождении оптимальной стратегии управления, т. е. такой совокупности управлений x=(x1, x2…xn), в результате реализации которых система S за k шагов переходит из начального состояния в конечное, и при этом функция дохода F(x) принимает наибольшее значение.

Из принципа оптимальности следует, что оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на n-м шаге, затем на двух последних шагах, затем на трех последних шагах и т. д., вплоть до первого шага. Таким образом, решение рассматриваемой задачи динамического программирования целесообразно начинать с определения оптимального решения на последнем, n-м шаге. Для того чтобы найти это решение, очевидно, нужно сделать различные предположения о том, как мог окончиться предпоследний шаг, и с учетом этого выбрать управление xn 0 , обеспечивающее максимальное значение функции дохода fn(Sn-1,xn). Такое управление, выбранное при определенных предположениях о том, как окончился предыдущий шаг, называется условно оптимальным. Следовательно, принцип оптимальности требует находить на каждом шаге условно оптимальное управление для любого из возможных исходов предшествующего шага.

Чтобы решить задачу необходимо воспользоваться основным функциональным уравнением Беллмана.

Полагая k = n — 1 в уравнении Беллмана, получаем следующее функциональное уравнение:

Используя теперь это уравнение и рассматривая всевозможные допустимые состояния системы S на (n — 1)-м шаге находим условные оптимальные решения и соответствующие значения функции.

Таким образом, на n-м шаге находим условно оптимальное управление при любом допустимом состоянии системы после (n — 1)-го шага, т. е. в каком бы состоянии система не оказалась после (n — 1)-го шага, нам уже известно, какое следует принять решение на n-м шаге.

Перейдем теперь к рассмотрению функционального уравнения при

Решая это функциональное уравнение при различных состояниях на (n — 2)-м шаге, получим условно оптимальные управления x 0 n-2(Si (n-2) ), i=1,2… . Каждое из этих управлений совместно с уже выбранным управлением на последнем шаге обеспечивает максимальное значение дохода на двух последних шагах.

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

Ссылка на основную публикацию
Adblock
detector