Метод дробления шага 2 страница

Чтобы построить алгоритм решения задач, дадим математическую формулировку принципа оптимальности. Для этого введем некоторые дополнительные обозначения. Обозначив через максимальный доход, получаемый за n шагов при переходе системы S из начального состояния х⁽⁰⁾ в конечное состояние x⁽ⁿ⁾ при реализации оптимальной стратегии управления m* = (m₁*, m₂*,..., m_k*), а через F (x^(k)) — максимальный доход, получаемый при переходе из любого состояния х^(k) в конечное состояние х⁽ⁿ⁾ при оптимальной стратегии управления на оставшихся (n - к) шагах. Тогда

(1)

(2)

при к = 0, 1,2,..., n - 1.

Выражение (2) представляет собой математическую запись принципа оптимальности Беллмана и носит название основного функционального уравнения Беллмана. Используя уравнение (2) находится решение рассматриваемой задачи динамического программирования. Рассмотрим этот процесс более подробно.

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

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

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

Перейдем теперь к рассмотрению функционального уравнения при
к = n – 2: (4)

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

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

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

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

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

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

Уравнения Беллмана. Рассмотрим последовательность задач, полагая последовательно n = 1,2,… при различных s – одношаговую, двухшаговую и т.д., - используя принцип оптимальности.

На каждом шаге любого состояния системы s_k-1 решение X_k нужно выбирать «с оглядкой», так как этот выбор влияет на последующее состояние s_k и дальнейший процесс управления, зависящий от s_k. это следует из принципа оптимальности.

Но есть один шаг, последний который можно для любого состояния s_n-1 планировать локально-оптимально, исходя только из соображений этого шага.

Рассмотрим n-й шаг: s_n-1 – состояние системы к началу n-го шага, - конечное состояние, X_n – управление на n-м шаге, а - целевая функция (выигрыш) n-го шага.

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

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

называется условным максимумом целевой функции на n-м шаге. Очевидно, что (1)

Максимизация ведется по всем допустимым управлениям X_n. Решение X_n, при котором достигается , также зависит от s_n-1 и называется оптимальным управлением на n-м шаге. Оно обозначается через .

Решив одномерную задачу локальной оптимизации (1), найдем для всех возможных состояний s_n-1 две функции и .

Рассмотрим пошаговую задачу: присоединим к n-му шагу (n-1)-й.(см. рис.).

условно оптимальный выигрыш на n-м шаге

значение целевой функции (n-1)-го шага при произвольном управлении Х_n-1 и состоянии S_n-2

Для любых состояний s_n-2, произвольных управлений и оптимальном управлении на n-м шаге значение целевой функции на двух последних шагах равно: (2).

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

(3)

Выражение, входящее в фигурных скобках (3), зависит только от s_n-2 и , так как s_n-1 можно найти при k=n-1. и подставить вместо s_n-1 в функцию .

В результате максимизации только по одной переменной согласно уравнению (3) вновь получается две функции: и .

Далее рассматривается трехшаговая задача: к двум последним шагам присоединяется (n-2)-й и т.д.

Обозначим через условный максимум целевой функции, полученный при оптимальном управлении на n-k+1 шагах, начиная с к-го до конца, при условии, что к началу к-го шага система находилась в состоянии s_к-1. Фактически эта функция равна , тогда .

Целевая функция на n-k последних шагах при произвольном управлении Х_к на к-м шаге и оптимальном управлении на последующих n-k шагах равна . Согласно принципу оптимальности, Х_к выбирается из условия максимума этой суммы, т.е. (4), k=n-1,n-2,…,2,1.

Уравнение Х_к на к-м шаге, при котором достигается максимум, обозначается через и называется условным оптимальным управлением на к-м шаге в правую часть уравнения (4) следует вместо s_k подставить выражение . Уравнения (4) называют уравнениями Беллмана. Это рекуррентные соотношения, позволяющие найти предыдущее значение функции, зная последующие.

Процесс решения уравнений (1) – (4) называется условной оптимизацией.

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

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

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

(1)

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

(2)

Поскольку логарифм функции типа (2) является аддитив­ной функцией, достаточно ограничиться рассмотрением функ­ций вида (1).

Изложим сущность вычислительного метода динамическо­го программирования на примере задачи оптимизации

(3)

при ограничениях

(4)

Отметим, что в отличие от задач, рассмотренных в преды­дущих главах, о линейности и дифференцируемости функций не делается никаких предположений, поэтому примене­ние классических методов оптимизации (например, метода Лагранжа) для решения задачи (3)-(4) либо проблематично, либо просто невозможно.

Содержательно задача (3)-(4) может быть интерпрети­рована как проблема оптимального вложения некоторых ресур­сов j, приводимых к единой размерности (например, денег) с помощью коэффициентов а_j в различные активы (инвестици­онные проекты, предприятия и т. п.), характеризующиеся фун­кциями прибыли f_j, т. е. такого распределения ограниченного объема ресурса (b), которое максимизирует суммарную прибыль. Представим ситуацию, когда она решается последова­тельно для каждого актива. Если на первом шаге принято реше­ние о вложении в п- йактив х_п единиц, то на остальных шагах мы сможем распределить b-а_пх_п единиц ресурса. Абстрагируясь от соображений, на основе которых принималось решение на первом шаге (допустим, мы по каким-либо причинам не могли на него повлиять), будет вполне естественным поступить так, чтобы на оставшихся шагах распределение текущего объе­ма ресурса произошло оптимально, что равнозначно реше­нию задачи

(5)

при ограничениях

(6)

Очевидно, что максимальное значение (5) зависит от размера распределяемого остатка, и если оставшееся количество ресур­са обозначить через , то величину (5) можно выразить как функцию от :

(7)

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

(8)

Если бы имелась возможность влиять на х_п, то мы для получе­ния максимальной прибыли должны были бы максимизировать по переменной х_п, т. е. найти и фактически решить задачу:

(9)

В результате мы получаем выражение для значения целевой функции задачи при оптимальном поэтапном процессе приня­тия решений о распределении ресурса. Оно в силу построения данного процесса равно глобальному оптимуму целевой фун­кции

(10)

т. е. значению целевой функции при одномоментном распреде­лении ресурса.

Если в выражении (5.9) заменить значения b на ,и п на k, то его можно рассматривать как рекуррентную формулу, позво­ляющую последовательно вычислять оптимальные значения це­левой функции при распределении объема ресурса за k шагов:

(11)

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

При k = 1 формула (5.11) принимает вид

(12)

т. е. допускает непосредственное вычисление функций и .

Воспользовавшись (12) как базой рекурсии, можно с помо­щью (11) последовательно вычислить и , . Положив на последнем шаге , в силу (9), найдем глобаль­ный максимум функции (3), равный , и компоненту опти­мального плана . Полученная компонента позволяет вычислить нераспределенный остаток на следующем шаге при оптимальном планировании: ,и, в свою очередь, най­ти . В результате подобных вычислений последо­вательно будут найдены все компоненты оптимального плана.

Таким образом, динамическое программирование представ­ляет собой целенаправленный перебор вариантов, который при­водит к нахождению глобального максимума. Уравнение (11), выражающее оптимальное решение на k -м шаге через решения, принятые на предыдущих шагах, называется основным рекур­рентным соотношением динамического программирова­ния. В то же время следует заметить, что описанная схема решения при столь общей постановке задачи имеет чисто тео­ретическое значение, так как замыкает вычислительный про­цесс на построение функций , т. е. сводит исход­ную задачу (5.3)-(5.4) к другой весьма сложной проблеме. Однако при определенных условиях применение рекуррентных соотношений может оказаться весьма плодотворным. В первую очередь это относится к задачам, которые допускают таблич­ное задание функций .

Задачи динамического программирования, до­пускающие табличное задание рекуррентных соотноше­ний.Рассмотрим процесс решения модифицированного вариан­та задачи (3)-(4), в котором переменные x_j и параметры a_j, b могут принимать только целочисленные значения, а ограничение (4) имеет вид равенства. В рамках предложенной ин­терпретации о вложении средств в активы данные предпосылки вполне реалистичны и, более того, могут быть даже усилены тре­бованием о кратности значений x_j, например, 1000 единицам.

Чтобы не усложнять обозначения, условимся операции це­лочисленной арифметики записывать стандартным образом, по­лагая, что промежуточные результаты подвергаются правиль­ному округлению. Так, например, будем считать, что 12/5 = 2.

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

Поскольку , x₁ принимает конечное число целых значений от 0 до b/a₁. Это позволяет, например, путем перебора значе­ний найти функцию и задать ее в форме таблицы следующей структуры (табл. 1).

Последняя колонка табл. 1 содержит значение x_l, на котором достигается оптимальное решение первого шага. Его необходимо запоминать для того, чтобы к последнему шагу иметь значения всех компонент оптимального плана.

На следующем (втором) шаге можно приступить к вычисле­нию функции , значения которой для каждого отдельно взятого находятся как

,

где значения

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

Таблица 1

…	…	…
B

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

Таблица 2

			…
…	…			…
b

На последнем п- омшаге нет необходимости табулиро­вать функцию , так как достаточно определить лишь . Одновременно определяется и оптимальное значение n -й компоненты оптимального плана . Далее, используя таблицу, сформированную на предыдущем шаге, определяем оптимальные значения остальных перемен­ных:

и т. д. или, в общем виде,

(13)

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

Выигрыш, который дает применение рассмотренного алго­ритма, может также быть оценен с помощью следующего про­стого примера. Сравним приблизительно по числу операций (состоящих, в основном, из вычислений целевой функции) опи­санный метод с прямым перебором допустимых планов задачи (3)-(4) при а₁=a₂=...а_n= 1.

Количество допустимых планов такой задачи совпадает с ко­личеством целочисленных решений уравнения

x_l+x₂+... +х_п =b,

т. е. равно числу сочетаний с повторениями из п элементов по b. Следовательно, при простом переборе число возможных вари­антов составит

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

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