Для решения данной динамической задачи дискретной оптимизации можно использовать метод динамического программирования. [c.311]
Решение этой задачи в принципе не так уж сложно — алгоритм дискретного динамического программирования, подробно описанный в 44, приводит к цели с затратой числа операций в общем случае порядка О (Nh 2n). Последовательность точек (6) и объявляется оптимальной траекторией задачи (1) — (5) разумеется, речь идет о приближенно оптимальной траектории, точность зависит от шагов сетки т и А. Если элементарная операция реализована точным решением задачи типа (1) — (5) на малом интервале [t(, tt+1], то мы имеем дело с точной траекторией управляемой системы (2), проходящей через узлы ж/, в моменты tf обычно элементарная операция реализуется не абсолютно точно, и узлы (6), соединенные, например, отрезками прямых, представляют некоторую аппроксимацию решения системы ж=/. Если нас интересует не только оптимальная траектория (6), но и реализующее ее управление и (t), то его можно восстановить по узлам (6) с помощью той же элементарной операции. Следует прежде всего подчеркнуть ту легкость, с которой данный метод справляется со всеми ограничениями на фазовую часть траектории, будь то ограничения на правом конце траектории (х (Т)=Х1) или еще более сложные ограничения типа х (t) G при всех t. В известной монографии [57] отражена история развития методов приближенного решения задач оптимального управления группой ВЦ АН СССР под руководством Н. Н. Моисеева. Работа начиналась с естественной попытки строить минимизирующие последовательности управляющих функций. После первых успехов в решении простейших неклассических задач (это — задачи, содержащие только ограничение типа u U без условий на правом конце траектории в [40] опубликовано решение задачи о максимальной дальности планирования) встретились определенные трудности, связанные с огра- [c.122]
Дискретное динамическое программирование [c.386]
Основным содержанием настоящего параграфа является алгоритм динамического программирования, позволяющий эффективно решать специальные дискретные задачи оптимального управления. Такие задачи могут появляться при оптимизации дискретных систем и при аппроксимации задач оптимального управления (см., например, 15). [c.386]
I 44] ДИСКРЕТНОЕ ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 387 [c.387]
ОПТИМАЛЬНОЕ ПРОГРАММИРОВАНИЕ — общий термин, которым объединяются различные математические методы и дисциплины линейное программирование, нелинейное программирование, дискретное программирование, целочисленное программирование, динамическое программирование, выпуклое программирование и другие. [c.23]
Решение многошаговых стохастических задач представляет более высокий порядок трудности. Часть из них удается свести к задачам линейного программирования, если переменные принять дискретными величинами. Простейшие из многошаговых стохастических задач (например, задачи о запасах) можно решить методами динамического программирования. Однако для большинства многошаговых стохастических задач требуется применение эвристических программ, обеспечивающих сокращение перебора возможных вариантов посредством адаптации алгоритма решения. [c.252]
Рассмотрим вопросы применения модели динамического программирования в обобщенном виде. Пусть стоит задача управления некоторым абстрактным объектом, который может пребывать в различных состояниях,. Текущее состояние объекта отождествляется с некоторым набором параметров, обозначаемым в дальнейшем и именуемый вектором состояния. Предполагается, что задано множество Н всех возможных состояний. Для объекта определено также множество допустимых, управлений (управляющих воздействий) X, которое, не умаляя общности, можно считать числовым множеством. Управляющие воздействия могут осуществляться в дискретные моменты времени k ( el n), причем управленческое решение заключается в выборе одного из управлений xk e X. Планом задачи или стратегией управления называется вектор = (, , j 2,..., j ), компонентами которого служат управления, выбранные на каждом шаге процесса. Ввиду предполагаемого отсут- [c.166]
Методы исследования операций Системный анализ, имитационное моделирование, управление запасами, теория расписаний, сетевое планирование и управление, методы теории массового обслуживания, математическое (линейное, нелинейное, динамическое, дискретное, стохастическое) программирование, метод ветвей и границ и др. [c.430]
Математическая трактовка этого круга вопросов сводится к разного рода экстремальным задачам, классическим, как, например, решаемые в дифференциальном или вариационном исчислениях, или современным, которые составляют предмет различных отраслей оптимального программирования (линейное, дискретное, динамическое, стохастическое и т.д.). [c.432]
С помощью ППП методов дискретного программирования решаются задачи линейного, динамического, стохастического, нелинейного программирования и др. [c.126]
В свою очередь, в зависимости от вида решаемых задач, в математическом программировании выделяют такие области, как линейное, нелинейное, дискретное, динамическое, геометрическое, стохастическое программирование. Первые четыре раздела, а также их применение для решения экономических задач составили содержание последующих глав. [c.16]
Отфильтрованную информацию об изменениях и отклонениях технологических параметров классифицируют на возмущения и оправданные улучшения условий производства. Для этого ее передают на дискретные ЭВМ ИВЦ с указанием причин, виновников (инициаторов) изменений условий производства. Подобная классификация предполагает обязательное сравнение отфильтрованной информации с нормами безопасного ведения технологических процессов и допусков на работу очистных сооружений. При автоматизированном решении указанных задач особое программное обеспечение, разрабатываемое, как правило, методами динамического программирования. Возможно также получение соответствующих форм выходных табуляграмм (машинограмм) с проставлением в них вручную кодов причин, виновников (инициаторов) допущенных изменений и отклонений с последующим возвратом одного экземпляра каждой выходной формы в ИВЦ предприятия. Возвращенные экземпляры используют для перезаписи выходной информации с последующей ее фильтрацией по техническим и экономическим допускам. [c.141]
Цель работы состоит в использовании методов теории управления для решения динамических стохастических задач в дискретном времени, для исследования стратегий управления портфелем активов и пассивов и вообще финансовых инструментов в динамическом случае. Основные результаты относятся к динамической задаче при наличии неопределенных факторов в виде марковского процесса и двухкритериальнои задаче при учете риска в виде критерия допустимых потерь и ожидаемом доходе как математическом ожидании. В такой постановке для решения задачи по выбору одной из паретовских точек применим формализм динамического программирования. Удается установить принцип линейного разложения оптимального результата текущей оптимальной оценки конечного результата и как следствие установить оптимальность простых стратегий для задачи максимизации математического ожидания конечного результата. [c.4]
Динамическое программирование непосредственно ориентировано на решение дискретных задач однако его можно использовать и для задач, в которых все переменные непрерывны. В этих случаях непрерывная область пространства решений дискретизуется и отыскивается оптимальное управление. Затем в его окрестности используется более мелкая сетка, и т.п. Непрерывные функции заменяются аппроксимациями по ряду дискретных точек. Доказанная вогнутость или выпуклость функций дохода (затрат) существенно ограничивают перебор. [c.149]
ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ (shortest route problem) — задача о нахождении на ориентированном графе пути наименьшей длины между двумя заданными его вершинами Длиной пути такого графа называется сумма длин дуг, составляющих этот путь 3 о к п возникает чаще всего при решении транспортных задач, дискретных задач программирования динамического и др В сетевых методах планирования и управления алгоритмы решения 3 о к п используют для нахождения критического пути Известно несколько эффективных методов ее решения Так, для анализа трансп сетей применяют алгоритм, основанный на методе последовательного анализа вариантов [c.69]