Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

3.5. Динамическое программирование и вариационные задачи. Дискретная форма условий

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

Обычно требуется найти экстремум функционала 3


при ограничениях типа уравнений связи


и т. д. Иногда дополнительные условия налагаются на η1, η2 и соответствующие им значения xj1), xj2), x'j1), x'j2).

Классическим примером вариационной задачи является так называемая задача о брахистохроне в следующей формулировке: дана материальная точка с массой га, занимающая в пространстве определенное положение (его удобно принять за начало координат); в момент t = 0 эта точка начинает двигаться под действием силы тяжести Р, чтобы достичь некоторого заданного конечного положения К; требуется найти такую траекторию движения, которая обеспечила бы минимальное время перехода из нуля в К (рис. 3.4). В силу закона сохранения энергии работа, произведенная силой Р на расстоянии х1 (t), пройденном точкой вдоль направления действия Р к моменту t>0, равна кинетической энергии mv2(t)/2, где v (t) - полная скорость точки в тот же момент; таким образом, v2(t) = 2Px1(t)/m или v = √2gx1 (g - ускорение силы тяжести).

Рис. 3.4
Рис. 3.4

Рассматривая элемент ds дуги ОК, можно утверждать: vdt = ds или dt = ds/v, откуда следует


или


(здесь Т - время перемещения точки из О в К). Используя соотношения


и


получаем окончательно


Минимизация Т, как указывалось, составляет основу нашей задачи.

Классический метод решения вариационных задач предусматривает анализ системы дифференциальных уравнений (уравнения Эйлера), позволяющих найти х*j (j = 1, ...,n) и J*. Такой подход предъявляет определенные требования к xj(η) и подынтегральной функции F[xj(η), x'j(η), η] в выражении У (в частности,

необходимо существование производных xj и F). Нарушение подобных требований приводит к затруднениям, которые либо совершенно исключают возможность использования классического вариационного исчисления, .либо делают эту возможность сомнительной из-за больших затрат усилий и времени на поиск x*j(η) (j = 1,...,n). Эти затруднения возникают, например, тогда, когда в задаче есть ограничения-неравенства, функции xj(η)m среди которых отыскиваются **j(r]), заведомо негладкие и т. д. В этих случаях метод динамического программирования оказывается не только применимым, но и часто дает более простую схему решения. Чтобы конкретизировать эти замечания, обратимся к уже знакомой задаче о брахистохроне и рассмотрим последовательность шагов, приводящих к отысканию оптимальной в смысле min Т траектории движения точки из нуля в К.

Прежде всего полезно заметить, что брахистохрона является кривой, лежащей целиком в плоскости I, проходящей через ось х1 и точку К (рис. 3.4), поэтому s дальнейшем достаточно рассматривать систему координат х, y; здесь


(3.4)

Первое, на что следует обратить внимание при анализе выражения (3.4), - это возможность дискретизации задачи, позволяющая построить процедуру поиска решения, сходную с той, которая была рассмотрена в п. 3.3. Пусть интервал изменения х разбит на N равных частей так, что xk = NΔx. Координата каждой точки деления с номером r (1≤r≤N-1) есть хr = r×Δх; соответствующие величины y=yr позволяют оценить производные функции y = y(х) в точках xr: y'r ≈ (yr+1-yr)/Δх, r = 1,....., N - 1.

Учитывая это, можно преобразовать интеграл (3.4) следующим образом:


(в основе приближенного равенства здесь лежит предположение о постоянстве величины √(1+(y'r)2) на интервале [хr, хr+1]).

Очевидно, исходная задача свелась к задаче с сепарабельной целевой функцией (относительно переменных Δyr = yr+1-yr), что делает возможным применение метода динамического программирования.

Обозначив, как и ранее, величину


через Ψq, приходим к функциональному уравнению


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

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

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"