Основная идея и особенности вычислительного метода динамического программирования. Общая постановка и алгоритм решения задач. Определение функциональных уравнений, свойства. Интегрированные системы для автоматизации математических расчетов класса MathCAD.
Аннотация к работе
Курсовая работа на тему: Решение задач динамического программированияВ настоящее время выделяется большое вниманием вопросам организации и управления, это приводит к необходимости анализа сложных целенаправленных процессов под углом зрения их структуры и организации. Предприятия пересматривают существующие системы управления, внедряют новые информационные системы управления, проводят реорганизацию бизнеса на основе современных методов реинжиниринга. К разряду "вечных" проблем предприятий относится проблема распределения ресурсов: ресурсы, в отличие от потребностей, всегда ограничены. Динамическое программирование является одним из наиболее эффективных методов решения подобных задач, чем и объясняется актуальность данной работы. динамический программирование алгоритм Для построения математической модели необходимо иметь строгое представление о цели функционирования исследуемой системы и располагать информацией об ограничениях, которые определяют область допустимых значений.Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана , центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме. Слово «программирование» в словосочетании «динамическое программирование» в действительности к традиционному программированию (написанию кода) почти никакого отношения не имеет и происходит от словосочетания «математическое программирование », которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. Метод динамического программирования можно использовать для решения весьма широкого круга задач, включая задачи распределения ресурсов, замены и управления запасами, задачи о загрузке.Отыскание оптимальной стратегии принятия набора последовательных решений, в большинстве случаях, производится следующим образом: сначала осуществляется выбор последнего во времени решения, затем при движении в направлении, обратном течению времени, выбираются все остальные решения вплоть до исходного. Обычно условия, в которых принимается решение, называют «состоянием» системы. Нет необходимости выяснять, как возникло то ил иное состояние или каковы были предшествующие решения. Независимо от того, отыскивают оптимальные решения с помощью табличного метода и последующего поиска или аналитическим путем, обычно быстрее и выгоднее производить выбор по одному решению в один момент времени, переходя затем к следующему моменту и т.д.Идею вычислительного метода динамического программирования рассмотрим на следующем примере: максимизировать (2) при условиях Таким образом, если бы была известна функция , то вся задача свелась бы к задаче с одной переменной. В конце концов на-м шаге мы используем "основное рекуррентное соотношение (ОРС) динамического программирования" На первом шаге, зафиксировав начало интервала 0 и изменяя его правый конец , вычисляем Оптимальное решение первого шага обозначим через .Состояние в которое перешла система S, зависит от исходного состояния и выбранного управления и не зависит от того, каким образом система S перешла в состояние Задача состоит в нахождении оптимальной стратегии управления, т. е. такой совокупности управлений в результате реализации которых система S за п шагов переходит из начального состояния в конечное и при этом функция дохода G(m) принимает наибольшее значение. Каково бы ни было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы доход на данном шаге плюс оптимальный доход на всех последующих шагах был максимальный. Из принципа оптимальности следует, что оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на n-м шаге, затем на двух последних шагах, затем на трех последних шагах и т. д., вплоть до первого шага. Обозначив через максимальный доход, получаемый за п шагов при переходе системы S из начального состояния в конечное состояние при реализации оптимальной стратегии управления , а через - максимальный доход, получаемый при переходе из любого состояния в конечное состояние при оптимальной стратегии управления на оставшихся (n - k) шагах.Позиция File (Файл) главного меню служит для работы с файлами документов. Файлы документов MATHCAD содержат полный текст программы, выводящей документ в окно редактирования, с указаниями координат расположения блоков, фактического содержания и характера выполняемых операций, форматов предоставления информации и т. д..
План
Содержание
Введение
1. Динамическое программирование
1.1 Задача динамического программирования
1.2 Общая структура динамического программирования
2. Решение задач в динамическом программировании
2.1 Основная идея и особенности вычислительного метода динамического программирования
2.2 Общая постановка и алгоритм решения задач методом динамического программирования
3. Программа MATHCAD в задачах динамического программирования