Функциональное уравнение ДП

Рассмотрим общую многошаговую задачу, к которой применим метод ДП. Пронумеруем шаги в порядке проведения условной оптимизации, в данной задаче с конца к началу. Эффективность i -го шага описывается функцией Z_i ( S_i,U_i ), где S_i - состояние к i -му шагу (вектор параметров состояния), U_i - управление на i -м шаге (вектор управляемых переменных или решение). Структура задачи на рис.

Модель задачи ДП включает целевую функцию

описание допустимой области управлений D, а также уравнение состояния , связывающее между собой два последовательных состояния - выводится из условий задачи. Формализация вычислительной процедуры метода ДП базируется на принципе оптимальности. Для описания этого свойства введем после­довательность функций { f_k ( S_k )}, так, что каждая из них есть зависимость экстремального значения критерия за k оставшихся шагов от состояния на начало k -го шага: . Эф-ть k шагов: -

основное функциональное уравнение ДП/ рекуррентное соотношение. Для k =1:

. Алгоритм:

1. Имея описание и модель задачи, выделяем шаги и производим их нумерацию с конца.

2. Определяем параметры состояния и вводим последовательность функций { f_k (S_k)}, , в которой каждая функция f_k (S_k) есть наилучшее значение критерия за k оставшихся шагов относительно состояния S_k.

3. На основе принципа оптимальности составляем функциональное уравнение ДП и отдельно выражение для f ₁.

9. Проводим условную оптимизацию, последовательно вычисляя f ₁, f ₂,..., f_N. При этом на каждом шаге для всех возможных значений состояния S_k запоминаются значения U_k ^* и f_k (в таблице или файле).

5.Исходя из заданного состояния S_N ^{^}, проводим безусловную оптимизацию по схеме:

S_N ^{^}®табл. N ® U_N ^*®у.с.® S_{N -1}^{^}®табл. N -1® U_{N -1}^*®у.с.®...® S ₁^{^}®табл.1® U ₁^*,

где у.с. - уравнение состояния. Значение f_N (S_N) из N -й таблицы есть оптимальное значение критерия задачи.

48. ДП: задача распределения ресурсов, достоинства ДП.

Необходимо распределить ресурс в количестве X между N предприятиями, если известно, что при выделении i -му предприятию ресурса x_i оно дает прибыль r_i (x_i). К функциям r_i не предъявляется каких-либо требований (например, дифференцируемости). Модель задачи: . Условия применимости ДП выполняются: и критерий, и ограничение задачи являются составными. Представим задачу как многошаговую. В качестве шага будем рассматривать выделение ресурса одному предприятию. Расположим предприятия в виде последовательности и пронумеруем их справа налево. Порядок предприятий в последовательности:

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

2. Если нет уверенности, что некоторое предприятие останется в рассматриваемой системе распределения, его следует поставить последним (на самое левое место); тогда в случае его удаления не придется решать задачу заново.

Состояние определяется количеством распределяемого ресурса, которое обозначим через V. Оно может относиться к разному числу предприятий, поэтому VЈX. В соответствии с процедурой ДП введем последовательность функций { f_k (V_k)} так, что

есть максимальная прибыль k предприятий при распределении между ними ресурса в количестве V_k. Рекуррентное со отношение: Допустим, что осталось распределить ресурс V_k между k предприятиями. Выделим из них две части: k -е предприятие и все остальные k -1.

Примем решение по k -му предприятию: из всего имеющегося ресурса V_k выделим ему X_k. Тогда оно даст прибыль r_k (x_k), а система перейдет в состояние V_{k -1}, относительно которого следует искать решения на k -1 оставшихся шагах. По принципу оптимальности эти решения должны составлять оптимальное поведение независимо от того, как система попала в состояние V_{k -1}, то есть f_{k -1}(V_{k -1}). В результате, прибыль k предприятий составит r_k (x_k) + f_{k -1}(V_{k -1}). Уравнение состояния: V_{k -1}= V_k - x_k -> r_k (x_k) + f_k (V_k - x_k), рекуррентное соотношение: . (1)

Допустимая область D_k, задаваемая диапазоном x_k, явно зависит от состояния V_k. Формула применима для k і2. Для первой функции последовательности: f ₁(V ₁)= r ₁(V ₁), x ₁^*= V ₁, так как весь имеющийся ресурс распределяется полностью.

Остановимся на вычислительной стороне формулы (1). В отдельных случаях при простых функциях r_k (V_k) максимум может быть найден аналитически, однако в общем случае максимум находится одним из численных методов, в том числе полным перебором допустимых значений x_k. Тогда, если x_k и V_k - непрерывные величины, для вычислений по рекуррентному соотношению их необходимо дискретизировать. Шаг дискретности D выбирается по точности, с которой следует провести распределение ресурса. Шаг дискретности должен быть одинаковым для x_k и V_k. Рекуррентная формула: где = 1,2,…, m; m D = X, D = V_k, m D = x_k. Один из способов вычислений по формуле состоит в том, что сначала фиксируется , а затем ищется максимум правой части, и так для всех значений . Результаты заносятся в таблицу вида:

где x_k ^*( D ) - значение x_k, доставляющее максимум при V_k = D. Все N таблиц, получаемых при последовательном расчете функций f_k, имеют одинаковую структуру. Решение исходной задачи находится на этапе безусловной оптимизации: По значению V_N = X входим в таблицу N, из которой берем f_N (X) - максимальную прибыль от N предприятий при распределении между ними ресурса в количестве X и x_N ^*= x_N ^*(X) - количество ресурса, выделяемое N -му предприятию при оптимальном распределении ресурса X. По уравнению состояния находим V_{N -1}= X - x_N ^*, входим по этому значению состояния в таблицу N -1 и из нее извлекаем f_{N -1}(X - x_N ^*) и x_{N -1} ^* - максимальную прибыль от N -1 предприятий и количество ресурса, выделяемое (N -1)-му предприятию при оптимальном распределении, соответственно. Пересчитываем состояние V_{N -2}= V_{N -1}- x_{N -1}^*= X - x_N ^*- x_{N -1}^* и по нему входим в таблицу N -2, в которой найдем x_{N -2} ^*, и так вплоть до таблицы 1, из которой получим x ₁^*. В результате имеем оптимальное решение задачи распределения ресурса в количестве X.

На примере этой задачи отметим ряд достоинств метода ДП.

1. Задача содержит N переменных, которые после дискретизации могут принимать m значений. Поэтому порядок числа вариантов распределения определяется величиной m^N. При расчете по рекуррентной формуле - Nm ²/2.

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

3. При использовании любого метода оптимизации, кроме ДП, исключение одного из предприятий из системы распределения приведет к необходимости решать изменившуюся задачу как новую. В динамическом программировании, если этому предприятию был присвоен номер N, то есть оно было последним по ходу условной оптимизации, решение измененной задачи находится сразу: по заданному количеству распределяемого ресурса входим не в N -ю, а в (N -1)-ю таблицу и далее действуем в соответствии со схемой безусловной оптимизации, которая была рассмотрена выше.

4. Метод ДП не накладывает каких-либо специальных требований на вид и форму представления функций, составляющих критерий. Так функции r (V) могут быть недифференцируемыми, могут быть заданы даже в виде таблицы или графика, или задаваться алгоритмически.

5. ДП снижает размерность решаемых задач в N раз (по числу переменных), что значительно облегчает нахождение глобального экстремума. Так в рассмотренной задаче на каждом шаге находится максимум функции одной переменной. Из свойства рекуррентного соотношения следует, что отыскание глобального оптимума на каждом шаге гарантирует достижение глобального оптимума исходной задачи.

6. Наложение специфических условий на переменные не «утяжеляет» решение задачи методом ДП (в отличие от многих других). Например, ограничения сверху и снизу или/и дискретность (в частности, целочисленность) переменных не затрудняют, а, наоборот, облегчают решение на каждом шаге.

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

 

49. ДП: задача о кратчайшем пути и с мультипликативным критерием.