Файл: Динамическое программирование. Сравнение с другими методами.docx
Добавлен: 04.02.2024
Просмотров: 29
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Министерство цифрового развития, связи и массовых коммуникаций Российской федерации
Ордена Трудового Красного Знамени федеральное государственное бюджетное образовательное учреждение высшего образования
«Московский технический университет связи и информатики»
Реферат
на тему:
«Динамическое программирование. Сравнение с другими методами»
Выполнил:
Проверил: Говоров П.М.
Москва 2023
ВВЕДЕНИЕ
Динамическое программирование
Динамическое программирование (ДП) в теории вычислительных систем— способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с другими методами, можно значительно сократить.
Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.
Сравнение методов
Линейное программирование объединяет методы решения задач, которые описываются линейными уравнениями. Данный метод основан на решении системы линейных уравнений, когда зависимость между изучаемыми явлениями строго функциональна. С помощью этого метода в промышленном производстве, например, исчисляется оптимальная общая производительность машин, агрегатов, поточных линий. Все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями. Решить такую задачу – значит выбрать из всех допустимых вариантов лучший, оптимальный.
Графические методы связаны прежде всего с геометрическим изображением функциональной зависимости при помощи линий на плоскости. Графики используются для наглядного изображения функциональных зависимостей. В экономическом анализе применяются почти все виды графиков – диаграммы сравнения, диаграммы временных рядов, графики зависимости.
Математические модели в задачах проектирования реальных объектов или технологических процессов должны отражать реальные протекающие в них физические и, как правило, нелинейные процессы. Переменные этих объектов или процессов связанны между собой физическими нелинейными законами, такими, как законы сохранения массы или энергии. Они ограничены предельными диапазонами, обеспечивающими физическую реализуемость данного объекта или процесса. В результате, большинство задач математического программирования, которые встречаются в научно-исследовательских проектах и в задачах проектирования - это задачи нелинейного программирования (НП).
Вместе с тем динамическое программирование не является универсальным методом решения. Практически каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения. Кроме того, большие объемы и трудоемкость решения многошаговых задач, имеющих множество состояний, приводят к необходимости отбора задач малой размерности либо использования сжатой информации.
Динамическое программирование применяется для решения таких задач, как: распределение дефицитных капитальных вложений между новыми направлениями их использования; разработка правил управления спросом и запасами; составление календарных планов текущего и капитального ремонтов оборудования и его замены; поиск кратчайших расстояний на транспортной сети и т.д.
Особенности математической модели динамического программирования заключаются в следующем:
задача оптимизации формулируется как конечный многошаговый процесс управления;
целевая функция является аддитивной и равна сумме целевых функций каждого шага
Вывод
Линейное программирование можно рассматривать как подмножество динамического программирования, оно более математически строгое.
В любом случае линейное программирование (LP) и динамическое программирование (DP) не являются исключительными друг для друга.
Ключевое различие между ними заключается в том, что в динамическом программировании мы принимаем одно решение за раз, тогда как в линейном программировании мы принимаем все решения заранее.