Метод динамического программирования
Динамическое программирование как математический аппарат, разработанный для повышения эффективности вычислений при решении некоторого класса задач математического программирования путем их декомпозиции. Соотношения Беллмана, задачи максимизации функции.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 18.08.2017 |
| Размер файла | 32,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Лекция № 10. Метод динамического программирования
ДП представляет собой математический аппарат, разработанный с целью повышения эффективности вычислений при решении некоторого класса задач мат. программирования путем их декомпозиции на относительно небольшие и, следовательно, менее сложные задачи. Характерным для ДП является подход к решению задачи по этапам, с каждым из которых ассоциирована одна управляемая переменная. Набор рекуррентных вычислительных процедур, связывающий различные этапы, обеспечивает получение решения задачи при достижении последнего этапа.
Рассмотрим функционирование некоторого объекта в течение промежутка времени Т. Пусть в момент времени tj состояние объекта характеризуется вектором , причем в начальный момент времени t1 состояние объекта задано, т.е. вектор известен. Объект меняет свое состояние под воздействием управления в моменты времени . При этом управляющее воздействие выбирается из заданной области , т.е.
динамический программирование декомпозиция беллман
(1)
Рассматривается случай, когда будущее состояние объекта зависит только от состояния объекта в данный момент времени и управляющего воздействия в этот момент времени, т.е.
.(2)
Здесь - заданная функция своих аргументов. Уравнение (2) является уравнением движения объекта, т.е. описывает динамику объекта во времени.
Обозначим -выигрыш, получаемый от функционирования объекта на j-м участке времени, т.е. в полуинтервале . Если в момент времени , когда объект находился в состоянии выбрать управление , то объект перейдет в состояние . Далее последовательно можно выбирать в соответствии с (1) , в из (2) определять . Этим значениям и будет соответствовать вполне определенное значение дохода:
(3)
Если выбирать другие значения управляющих воздействий, то им будут соответствовать другие состояния объекта, а следовательно, и другое значение общего дохода (3). Поэтому естественно поставить следующую оптимизационную задачу:
(4)
.(5)
(6)
- задан.(7)
Здесь необходимо найти неизвестные и , которые удовлетворяли бы ограничениям (5)-(7) и максимизировали бы целевую функцию (4).
Эта задача является в общем случае задачей нелинейного программирования и обладает следующими особенностями:
1. Искомые переменные разбиты на N групп, в каждую j-тую из которых входят только и .
2. Целевая функция (4) является суммой функций , каждая из которых зависит лишь от переменных соответствующей группы. В этом случае говорят, что целевая функция сепарабельна, или аддитивна.
3. Уравнение (5) является рекуррентным, т.е. через значения и однозначно определяется .
Многие реальные задачи ИСО сводятся к ММ вида (4)-(7), которая допускает различные интерпретации.
Решение задачи вида (4)-(7) обычными методами оказывается либо невозможным, либо неэффективным из-за большой размерности. Поэтому ее решение сводится к последовательному решению N связанных между собой задач меньшей размерности. Для выявления этих задач и связей между ними рассмотрим задачу вида (4)-(7), соответствующую последним этапам . Она запишется в виде:
(8)
.(9)
(10)
- фиксирован.(11)
В этой задаче мы не знаем, чему равно конкретное значение , но если его зафиксировать, то получим соответствующее максимальное значение (8). Если зафиксировать другое значение , то естественно максимальное значение целевой функции (8) будет другим. Обозначим максимальное значение целевой функции (8)при некотором зафиксированном через :
Запишем это равенство в виде:
(12)
Здесь первое слагаемое не зависит от , а вторая сумма функций зависит от . Поэтому выражение (12) можно переписать в виде:
Таким образом окончательно запишем:
(13)
Данное соотношение справедливо для всех , а для имеем:
(14)
Полученные рекуррентные соотношения являются основными соотношениями МДП. Это так называемые соотношения Беллмана. Они позволяют свести решение ЗНП (4)-(7) к последовательному решению N задач максимизации меньшей размерности.
Соотношение (13) позволяет вычислить , если известно , а (14) позволяет вычислить максимальное значение целевой функции на последнем этапе. Тогда рекуррентный процесс решения задачи (13)-(14) должен проводиться в порядке . Действительно, зная из (13) можно найти значения и т.д.
Рассмотрим алгоритм решения такой задачи.
1 шаг. Решается задача (14):
.
Решается столько однотипных задач, сколько существует возможных значений фиксированных . Здесь максимизируется функция по переменной для каждого возможного фиксированного значения . Решается столько однотипных задач, сколько существует возможных значений фиксированных . Поэтому для каждого в результате получаются условные точки максимума и максимальное значение функции в этих точках.
2 шаг. На этом шаге решается задача (13) при :
Здесь решаются задачи максимизации функции по переменной при каждом возможном фиксированном значении . В результате находятся условные точки максимума и значения суммы двух функций в этих точках .
Далее, зная , решается задача (13) для . Наконец, при переходим к шагу N:
N шаг. , . На этом шаге решается только одна задача оптимизации, т.к. - задан. В результате получим точку максимума и значение .
Для окончательного решение проводим обратное движение алгоритма:
1 шаг: ; .
2 шаг: ; .
3 шаг: ; .
…
N шаг: ; .
.
Таким образом, определяется решение исходной ЗНП (4)-(7) как , при этом максимальное значение целевой функции (4) будет равно значению .
Достоинства метода динамического программирования.
1. На каждом этапе решается задача поиска экстремума лишь по части переменных, следовательно, размерность этих задач по сравнению с исходной значительно ниже. Это позволяет упростить поиск оптимальных значений искомых переменных.
2. Метод ДП дает возможность решать задачи, которые не могут быть решены другими методами.
3. Алгоритм метода ДП легко реализуется на ЭВМ.
Недостатки метода ДП.
1. Отсутствие универсального алгоритма, который был бы пригоден для решения всех задач рассматриваемого класса. Алгоритмы ДП объединены лишь общей идеей, и в каждом конкретном случае должны формироваться применительно к специфике прикладной задачи.
2. При большой размерности исходной задачи эти алгоритмы требуют значительных ресурсов ЭВМ.
Размещено на Allbest.ru
...Подобные документы
Класс задач, к которым применяются методы динамического программирования. Решения задачи распределения капитальных вложений между предприятиями путем построения математической модели. Программа "Максимизации капиталовложений" на базе Microsoft Excel.
курсовая работа [1,4 M], добавлен 28.10.2014Постановка задачи динамического программирования. Поведение динамической системы как функция начального состояния. Математическая формулировка задачи оптимального управления. Метод динамического программирования. Дискретная форма вариационной задачи.
реферат [59,9 K], добавлен 29.09.2008Общая характеристика динамического программирования: задачи о коммивояжере, о назначении, о теории расписаний. Численные методы ветвей и границ, методы отсечения. Задачи целостного программирования с булевыми переменными. Аддиктивный метод Балаша.
учебное пособие [534,1 K], добавлен 11.07.2010Формулировка общей задачи математического программирования. Классификация задач нелинейного программирования. Понятие о функции Лагранжа. Задача теоремы Куна-Таккера. Экономическая интерпретация множителей Лагранжа, формулирование условий оптимальности.
презентация [669,1 K], добавлен 25.07.2014Основные понятия и принципы динамического программирования, реккурентность природы задач данного типа и функциональные уравнения Беллмана. Разработка структуры блок-схемы и реализация на ЭВМ построенного алгоритма на выбранном языке программирования.
курсовая работа [30,2 K], добавлен 26.11.2010Восстановление математической модели задачи нелинейного программирования. Решение уравнений прямых. Метод линеаризации: понятие, особенности применения при решении задач. Нахождение точки максимума заданной функции. Решение задачи графическим методом.
задача [472,9 K], добавлен 01.06.2013Обзор задач, решаемых методом динамического программирования. Составление маршрута оптимальной длины. Перемножение цепочки матриц. Задача "Лестницы". Анализ необходимости использования специальных методов вероятностного динамического программирования.
курсовая работа [503,3 K], добавлен 28.06.2015Модель динамического программирования для решения задач оптимального распределения ресурсов. Принцип оптимальности, уравнение Беллмана. Двумерная и дискретная динамическая модель. Значение метода в решении прикладных задач различных областей науки.
курсовая работа [400,2 K], добавлен 01.10.2009Постановка задачи динамического программирования. Составление основного функционального управления динамического программирования, определяющего условный оптимальный выигрыш для данного состояния. Выбор оптимальной стратегии замены оборудования.
курсовая работа [873,9 K], добавлен 02.07.2014Постановка задачи линейного программирования и формы ее записи. Понятие и методика нахождения оптимального решения. Порядок приведения задач к каноническому виду. Механизмы решения задач линейного программирования аналитическим и графическим способами.
методичка [366,8 K], добавлен 16.01.2010Понятие математического программирования. Класс как тип структуры, позволяющий включать в описание типа не только элементы данных, но и функции. Рассмотрение основных особенности языка программирования C++. Характеристика среды MS Visual Studio 2008.
контрольная работа [318,0 K], добавлен 13.01.2013Постановка задачи синтеза системы управления. Применение принципа Максимума Понтрягина. Метод аналитического конструирования оптимальных регуляторов. Метод динамического программирования Беллмана. Генетическое программирование и грамматическая эволюция.
дипломная работа [1,0 M], добавлен 17.09.2013Основные понятия математического линейного программирования. Постановка и методы решения заданий целочисленного и параметрического составления программ. Примеры вычисления задач с параметрами в целевой функции и в свободных членах системных ограничений.
дипломная работа [432,0 K], добавлен 25.10.2010Определение совокупности шаговых управлений. Решение задач динамического программирования двухэтапным способом. Решение последовательности задач условной оптимизации. Оптимальное распределение памяти, политика замены оборудования, замена форвардера.
презентация [674,9 K], добавлен 30.10.2013Классификация задач математического программирования. Сущность графического метода решения задач линейного программирования, алгоритм табличного симплекс-метода. Описание логической структуры и текст программы по решению задачи графическим методом.
курсовая работа [263,5 K], добавлен 27.03.2011Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
курсовая работа [581,5 K], добавлен 13.10.2008Особенности задач линейного программирования. Симплексный метод решения задач линейного программирования. Обоснование выбора языка, инструментария программирования, перечень идентификаторов и блок-схема алгоритма. Логическая схема работы программы.
дипломная работа [2,4 M], добавлен 13.08.2011Решение задач нелинейного программирования различными методами для проведения анализа поведения этих методов на выбранных математических моделях. Компьютерная реализация выбранных задач нелинейного программирования в среде пакетов Excel и Matlab.
дипломная работа [2,9 M], добавлен 25.01.2013Достижения математики в теории полумарковских процессов. Связь управляемых полумарковских процессов и динамического программирования. Разработка программы модели управляемого полумарковского процесса, реализованной на языке программирования СИ++.
курсовая работа [356,7 K], добавлен 10.09.2017Решение задачи нелинейного программирования с определением экстремумов функции. Этапы процесса нахождения решения задачи нелинейного программирования с использованием ее геометрической интерпретации. Определение гиперповерхности уровней функции.
курсовая работа [1,5 M], добавлен 25.09.2010
