Лямбда оптимизация в задачах динамического программирования
Обновлено: 08.07.2024
Решение задач высокой размерности методами классического анализа сопряжено с определенными трудностями, вызванными необходимостью решения систем обычно нелинейных уравнений высокого порядка. В то же время существуют многостадийные процессы с управлением на каждой стадии, широко распространенные в химической технологии, где принцип последовательной переработки сырья является по существу основным. Для решения задач оптимизации многостадийных процессов, а также процессов, которые могут быть математически описаны как многостадийные, разработан и успешно применяется метод динамического программирования.
В качестве стадии принимается один из элементов, на совокупность которых можно разбить процесс, как во времени, так и изменения его в пространстве. При этом в первом случае под стадией понимается некоторый заранее выбранный отрезок времени, а во втором — отдельный аппарат (элемент аппарата) в технологической цепи производства или один из этапов проектирования в общем комплексе проектных работ.
Стадии в процессе могут быть однородными и неоднородными. Процесс с однородными стадиям (например, каскад реакторов) представляет собой последовательность однотипных аппаратов, в которой поток сырья проходит последовательную переработку.
Примером процесса с неоднородными стадиями является технологический участок химического производства, на котором исходное сырье последовательно перерабатывается в аппаратах различных типов (например, химический реактор — адсорбер — ректификационная колонна).
Состояние отдельной стадии процесса можно охарактеризовать совокупностью входных и выходных параметров хг Если выход стадии служит входом для следующей стадии, то для последней совокупность выходных параметров предыдущей стадии определяет состояние входа.
Кроме входных и выходных переменных на каждой стадии необходимо выделять группу управляющих воздействий uj (рис. 6.5).
Рис. 6.5. Схема многостадийного процесса
Динамическое программирование, как и все другие рассматриваемые в этой главе методы, применяется для оптимизации математически описанных процессов. То есть предполагается известным математическое описание каждой стадии процесса, которое представляется в общем виде системой уравнений связывающей выходные и управляющие параметры /-й стадии с входными (выходными) параметрами предыдущей стадии.
Если каждая из N стадий характеризуется набором к оптимизируемых параметров, то одновременное определение Nk параметров может вызвать затруднения при применении любого поискового метода. Следует отметить, что прямой поиск по всем параметрам дает только один оптимум. Изменение другого состояния системы, например, производительности или температуры, потребует нового поиска. Метод динамического программирования позволяет осуществлять поиск оптимума последовательно для каждой стадии. Проведение N поисков, в каждом из которых подбирается к величин, гораздо легче осуществить, чем одновременный поиск Nk величин. Кроме того, динамическое программирование позволяет установить набор оптимальных режимов для различных стадий и заданных начальных условий процесса.
Пусть поток на выходе из /'-й стадии характеризуется величинами хи. хтР которые можно рассматривать как составляющие вектора хг Вектор регулируемых переменных обозначим = | ии, . ukj |. Каждая стадия преобразует состояние хм (вход) Bxf (выход) в зависимости от регулируемых переменных и:.
Пусть целевая функция для /-й стадии gi = g;(x). Тогда для всей
системы целевая функция G = ?gf.
Оптимальное решение обладает следующим свойством: каковы бы ни были характеристики системы из N -р звеньев, последующие решения для р звеньев должны быть оптимальными относительно исходного состояния (на выходе из N - р звеньев). Этот принцип сформулирован Веллманом. Пусть максимум берется по всем наборам управляющих величин иг . , uN. При любом выборе режима и, на первой стадии состояние потока на выходе этой стадии задается уравнением
где jCj — начальное состояние для последующих N - 1 стадий.
По принципу оптимальности х должно быть оптимально для всех оставшихся стадий
где оптимум берется по и. иN.
Понятно, что для последней стадии принцип оптимальности дает:
Здесь оптимум берется уже только по uN. Таким образом, принцип оптимальности позволяет проводить оптимизацию, начиная с последней стадии, путем подбора управляющих параметров для этой стадии; затем рассматривают две последние стадии и т.д.
Следует отметить, что динамическое программирование позволяет заменить сложную задачу рядом более простых задач, но не дает конкретного метода их решения. Этот метод сложен также при применении к процессам с рециклами на стадиях.
Следует отметить, что динамическое программирование позволяет заменить сложную задачу рядом более простых задач, но не дает конкретного метода решения этих задач. Этот метод сложен также при применении к процессам с рециклами на стадиях.
Задача 6.5. Применить метод динамического программирования для определения минимального объема трех последовательно расположенных реакторов идеального перемешивания, в которых проводится изотермическая реакция первого порядка. Целью является получение при минимальном общем объеме системы реакторов конечной концентрации исходного вещества х3, равной 10% от начальной, х0 = 1. Задана также константа скорости реакции к.
При стационарном режиме по уравнению материального баланса для /-го аппарата идеального перемешивания (3.9) имеем
а если учесть скорость реакции для исходного реагента
где v — объемный расход; Vj — объем /-го аппарата; к — константа скорости реакции; хм и х. — концентрации исходного вещества на входе в аппарат и выходе из него соответственно.
Обозначив т. = V./v, получим для каждого из реакторов согласно (3.13):
Начнем оптимизацию с последнего реактора. Для него с учетом (6.60) время пребывания
Для минимизации т3 необходимо подобрать концентрацию хт Зависимость т3 от х2 согласно (6.61) линейна.
Переходим к двум последним реакторам. Для второго реактора получим с учетом (6.60) время пребывания
Зависимость (6.62) можно построить в координатах т2 - хт Она представляет собой гиперболу. Эти зависимости для различных значений Xj (прияты значения 0,9; 0,7; 0,5; 0,3 и 0,1) приведены ниже:
Переходя к двум последним реакторам, выражаем суммарное время (т2 + т3) согласно зависимостям (6.61) и (6.62)
Далее строим график для суммарного времени (т2 + т3) как функцию от х2 для указанных выше значений х.
Для оптимизации каскада необходимо найти минимум суммы (Т2 + Т3) и оптимальные величины х2 для принятых значений х. Для этого находим производную функции (6.63) пох2 и приравниваем ее к нулю. В результате этого получим соотношение
Подставим найденное значение х2 в уравнение (6.63). В результате получим минимальное значение суммы (т2 + т3) > как функцию от концентрации х,:
Выражение (т2 + x3)mjn является степенной зависимостью. В виде графика оно представлено ниже, здесь же показаны точечные значения, принятые выше для х,:
Далее дополним (6.65) зависимостью для первого реактора В результате получим
Построим аналогично графику, приведенному выше, график зависимости (Tj + Т2 + Т3) OTXj!
Затем находим минимум функции (т2 + т3+ ij) mjn. Для этого определяем производную этой функции и приравниваем ее к нулю. Найдено оптимальное значение = 0,4642. Оно показано на графике пунктиром.
Далее по уравнению (6.67) при оптимальном значении х] находим (xt + т2 + x3)min = 3,464Д, а по уравнению (6.65) - (х, + x2)min = = 2,309Д. Подставляя это значение в (6.63), находим соответствующее время Xj = 1,154/к.
Далее при оптимальном значении х по зависимости (6.67) находим значение (х, + х2 + x3)min = 3,463/к, а по уравнению (6.65) значение (х? + x3)min = 2,3091 /к. По соотношению (6.64) находим оптимальное значение^ = 0,2155. Затем находим, что соотношения входных и выходных концентраций для всех реакторов равны и составляют
Оптимальное время пребывания во всех реакторах также одинаково и составляет
Так как оптимальные значения времени пребывания для всех реакторов равны и соответственно равны все соотношения входных и выходных концентраций, равны и все объемы реакторов.
Из рассмотренного примера ясно: аналогично моделирование N последовательно соединенных изотермических реакторов при необходимости минимизации их объемов. А это приводит к равенству объемов аппаратов и времени пребывания реакционной смеси в каждом реакторе.
Методы динамического программирования применяются при решении оптимизационных задач, в которых целевая функция или ограничения, или же и первое, и второе одновременно характеризуются нелинейными зависимостями.
Задача распределения инвестиций
В задачах данного типа заданы сумма инвестиций (или сумма для распределения) и таблица планируемой прибыли. Если сумма для распределения явно не задана, то ее можно найти из таблицы - она равна максимальному значению xi (последняя строчка таблицы).
Таблицы могут иметь разный вид.
Таблица 1 - Первый вариант таблицы исходных данных
| x | f1(x) | f2(x) | f3(x) |
| 1 | 6.3 | 4 | 5 |
| 2 | 5.2 | 6 | 7 |
| 3 | 4.3 | 4.6 | 7.8 |
| 4 | 5 | 6 | 3 |
| 5* | 7 | 6.3 | 8.2 |
Таблица 2 - Второй вариант таблицы исходных данных
| x | 0 | 10 | 20 | 30 | 40 |
| f1(x) | 0 | 4 | 5 | 7 | 8 |
| f2(x) | 0 | 3 | 3 | 4 | 6 |
| f3(x) | 0 | 4 | 4 | 5 | 6 |
Пример задачи.
Для двух предприятий выделено A единиц средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от x единиц средств, вложенных в первое предприятие, равен f1(х), а доход от y единиц средств, вложенных во второе предприятие, равен f2(y). Остаток средств к концу года составляет g1(x) для первого предприятия и g2(y) для второго предприятия. Задачу решить методом динамического программирования.
При вводе данных первую нулевую строку можно не заполнять.
В сервисе Задача распределения инвестиций используется метод обратной прогонки.
Метод прогонки
Данная задача соответствует задаче распределения инвестиций. Разница состоит в оформлении результатов полученного решения и применения метода прямой прогонки.
В сервисе Метод прогонки необходимо также выбрать метод решения: процедура прямой или обратной прогонки.
Задача замены оборудования
Цель решения - определить на каких шагах алгоритма (в какие годы) необходимо заменить оборудование. Для этого вводятся Период эксплуатации (в годах) и Стоимость нового оборудования. После этого необходимо заполнить таблицу дохода r(t) и остаточной стоимости S(t).
Задача замены оборудования
Планирование производственной линии
Задача последовательной обработки на двух машинах N различных деталей, если известно время Ai и Bi обработки i -й детали на соответствующих машинах. Требуется найти порядок обработки, минимизирующий время простоя второй машины и тем самым сокращающий общее время обработки деталей.
Задача Джонсона
Динамическое программирование — тема, которой в рунете посвящено довольно мало статей, поэтому мы решили ею заняться. В этой статье будут разобраны классические задачи на последовательности, одномерную и двумерную динамику, будет дано обоснование решениям и описаны разные подходы к их реализации. Весь приведённый в статье код написан на Java.
О чём вообще речь? Что такое динамическое программирование?
Динамическое программирование — метод решения задачи путём её разбиения на несколько одинаковых подзадач, рекуррентно связанных между собой. Самым простым примером будут числа Фибоначчи — чтобы вычислить некоторое число в этой последовательности, нам нужно сперва вычислить третье число, сложив первые два, затем четвёртое таким же образом на основе второго и третьего, и так далее (да, мы слышали про замкнутую формулу) .
Хорошо, как это использовать?
Решение задачи динамическим программированием должно содержать следующее:
- Зависимость элементов динамики друг от друга. Такая зависимость может быть прямо дана в условии (так часто бывает, если это задача на числовые последовательности). В противном случае вы можете попытаться узнать какой-то известный числовой ряд (вроде тех же чисел Фибоначчи), вычислив первые несколько значений вручную. Если вам совсем не повезло — придётся думать
- Значение начальных состояний. В результате долгого разбиения на подзадачи вам необходимо свести функцию либо к уже известным значениям (как в случае с Фибоначчи — заранее определены первые два члена), либо к задаче, решаемой элементарно.
И что, мне для решения рекурсивный метод писать надо? Я слышал, они медленные.
Конечно, не надо, есть и другие подходы к реализации динамики. Разберём их на примере следующей задачи:
Идея решения
Здесь нам даны и начальные состояния (a0 = 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) кэширование значений будет выглядеть следующим образом:
Не слишком сложно, согласитесь? Зато это избавляет от огромного числа операций. Платите вы за это лишним расходом памяти.
Последовательное вычисление
Теперь вернёмся к тому, с чего начали — рекурсия работает медленно. Не слишком медленно, чтобы это приносило действительные неприятности в настоящей жизни, но на соревнованиях по спортивному программированию каждая миллисекунда на счету.
Метод последовательного вычисления подходит, только если функция ссылается исключительно на элементы перед ней — это его основной, но не единственный минус. Наша задача этому условию удовлетворяет.
10–12 января, Онлайн, Беcплатно
Суть метода в следующем: мы создаём массив на N элементов и последовательно заполняем его значениями. Вы, наверное, уже догадались, что таким образом мы можем вычислять в том числе те значения, которые для ответа не нужны. В значительной части задач на динамику этот факт можно опустить, так как для ответа часто бывают нужны как раз все значения. Например, при поиске наименьшего пути мы не можем не вычислять путь до какой-то точки, нам нужно пересмотреть все варианты. Но в нашей задаче нам нужно вычислять приблизительно log2(N) значений (на практике больше), для 922337203685477580-го элемента (MaxLong/10) нам потребуется 172 вычисления.
Ещё одним минусом такого подхода является сравнительно большой расход памяти.
Создание стека индексов
Зависимости вычисляются следующим образом:
Полученный размер стека — то, сколько вычислений нам потребуется сделать. Именно так я получил упомянутое выше число 172.
Теперь мы поочередно извлекаем индексы и вычисляем для них значения по формулам — гарантируется, что все необходимые значения уже будут вычислены. Хранить будем как раньше — в хэш-таблице.
Все необходимые значения вычислены, осталось только написать
Конечно, такое решение гораздо более трудоёмкое, однако это того стоит.
Хорошо, математика — это красиво. А что с задачами, в которых не всё дано?
Для большей ясности разберём следующую задачу на одномерную динамику:
Идея решения
На первую ступеньку можно попасть только одним образом — сделав прыжок с длиной равной единице. На вторую ступеньку можно попасть сделав прыжок длиной 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). Это характерно для чисел Фибоначчи.
Реализация
Подъём по лестнице
Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.
Решение
Реализация
Калькулятор
- Прибавить к числу X единицу;
- Умножить число X на 2;
- Умножить число X на 3.
Решение
Наивное решение состоит в том, чтобы делить число на 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)). Чтобы не обрабатывать граничные случаи, можно добавить первую строку и столбец, заполненные некоторой константой — каким-то числом, заведомо большим содержимого любой из клеток.
Методы динамического программирования применяются при решении оптимизационных задач, в которых целевая функция или ограничения, или же и первое, и второе одновременно характеризуются нелинейными зависимостями.
Задача распределения инвестиций
В задачах данного типа заданы сумма инвестиций (или сумма для распределения) и таблица планируемой прибыли. Если сумма для распределения явно не задана, то ее можно найти из таблицы - она равна максимальному значению xi (последняя строчка таблицы).
Таблицы могут иметь разный вид.
Таблица 1 - Первый вариант таблицы исходных данных
| x | f1(x) | f2(x) | f3(x) |
| 1 | 6.3 | 4 | 5 |
| 2 | 5.2 | 6 | 7 |
| 3 | 4.3 | 4.6 | 7.8 |
| 4 | 5 | 6 | 3 |
| 5* | 7 | 6.3 | 8.2 |
Таблица 2 - Второй вариант таблицы исходных данных
| x | 0 | 10 | 20 | 30 | 40 |
| f1(x) | 0 | 4 | 5 | 7 | 8 |
| f2(x) | 0 | 3 | 3 | 4 | 6 |
| f3(x) | 0 | 4 | 4 | 5 | 6 |
Пример задачи.
Для двух предприятий выделено A единиц средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от x единиц средств, вложенных в первое предприятие, равен f1(х), а доход от y единиц средств, вложенных во второе предприятие, равен f2(y). Остаток средств к концу года составляет g1(x) для первого предприятия и g2(y) для второго предприятия. Задачу решить методом динамического программирования.
При вводе данных первую нулевую строку можно не заполнять.
В сервисе Задача распределения инвестиций используется метод обратной прогонки.
Метод прогонки
Данная задача соответствует задаче распределения инвестиций. Разница состоит в оформлении результатов полученного решения и применения метода прямой прогонки.
В сервисе Метод прогонки необходимо также выбрать метод решения: процедура прямой или обратной прогонки.
Задача замены оборудования
Цель решения - определить на каких шагах алгоритма (в какие годы) необходимо заменить оборудование. Для этого вводятся Период эксплуатации (в годах) и Стоимость нового оборудования. После этого необходимо заполнить таблицу дохода r(t) и остаточной стоимости S(t).
Задача замены оборудования
Планирование производственной линии
Задача последовательной обработки на двух машинах N различных деталей, если известно время Ai и Bi обработки i -й детали на соответствующих машинах. Требуется найти порядок обработки, минимизирующий время простоя второй машины и тем самым сокращающий общее время обработки деталей.
Задача Джонсона
Читайте также: