📄Работа №105702
Тема: Решение оптимизационных задач методом динамического программирования
Характеристики работы
Тип работы
Бакалаврская работа
Предмет
Информатика и вычислительная техника
Объем:
55 листов
Год:
2018
Просмотров:
280
4700
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ
ГЛАВА 1 ОСНОВНЫЕ ВИДЫ ОПТИМИЗАЦИОННЫХ ЗАДАЧ И МЕТОД ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
1.1Оптимизационные задачи
1.2Метод динамического программирования
1.3Анализ основных видов оптимизационных задач и применение
метода динамического программирования
1.3.1Задача коммивояжера.
1.3.2Задача о ранце
1.3.3Задача отыскания кратчайших путей на графе
1.3.4Задача о назначениях
1.3.5Задача о порядке произведения матриц
1.3.6Задача распределения ресурсов
ГЛАВА 2 НЕКОТОРЫЕ ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ И ИХ РЕШЕНИЕ
2.1Решение задачи коммивояжера
2.2Решение задачи о ранце
2.3Решение задачи отыскания кратчайших путей на графе
2.4Решение задачи о порядке произведения матриц
2.5Решение задачи распределения ресурсов
ГЛАВА 3 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ОТЫСКАНИЯ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФЕ
3.1Алгоритм решения задачи отыскания кратчайших путей на графе
3.2Описание интерфейса
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ А Листинг кода программной реализации задачи отыскания кратчайших путей на графе методом динамического программирования
ГЛАВА 1 ОСНОВНЫЕ ВИДЫ ОПТИМИЗАЦИОННЫХ ЗАДАЧ И МЕТОД ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
1.1Оптимизационные задачи
1.2Метод динамического программирования
1.3Анализ основных видов оптимизационных задач и применение
метода динамического программирования
1.3.1Задача коммивояжера.
1.3.2Задача о ранце
1.3.3Задача отыскания кратчайших путей на графе
1.3.4Задача о назначениях
1.3.5Задача о порядке произведения матриц
1.3.6Задача распределения ресурсов
ГЛАВА 2 НЕКОТОРЫЕ ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ И ИХ РЕШЕНИЕ
2.1Решение задачи коммивояжера
2.2Решение задачи о ранце
2.3Решение задачи отыскания кратчайших путей на графе
2.4Решение задачи о порядке произведения матриц
2.5Решение задачи распределения ресурсов
ГЛАВА 3 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ОТЫСКАНИЯ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФЕ
3.1Алгоритм решения задачи отыскания кратчайших путей на графе
3.2Описание интерфейса
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ А Листинг кода программной реализации задачи отыскания кратчайших путей на графе методом динамического программирования
📖 Введение
При управлении сложными дорогостоящими экономическими системами возникшие ошибки могут иметь крайне высокую цену. Чтобы исключить или, по крайней мере, снизить риск появления подобных ошибок, необходимо использовать математические модели. Математические модели могут выражать полный спектр существенных соотношений между параметрами систем управления и различными количественными характеристиками. Другими словами, математическая модель описывает в математической форме исследуемую систему, процессы или явления.
Оптимизационными называются экономико-математические задачи, цель которых заключается в нахождении оптимального (наилучшего) с точки зрения некоторого критерия или критериев варианта использования имеющихся ресурсов (труда, капитала и пр.).
Опирающиеся на хорошо построенные математические модели задачи управления приводят к качественным и пригодным для применения на практике результатам. Однако, такие задачи управления являются сложными, и простых формул для их решения не существует. Поэтому возникает объективная потребность в разработке специальных математических методов решения поставленных задач.
Таким методом решения задач управления многошаговыми процессами является рассматриваемый в данной работе метод динамического программирования.
Динамическое программирование — это один из математических методов нахождения оптимальных решений по управлению многошаговыми процессами. Состояние исследуемых систем изменяется поэтапно или во времени. В реальном мире подобные процессы и системы имеют широкое распространение. Важность и актуальность применения математических методов для решения соответствующих управленческих задач определяется необходимостью эффективного управления. Для метода динамического программирования теоретической основой является принцип оптимальности, который получил широкую сферу приложений в технике, естествознании, экономике и военном деле.
Объект исследования: математические модели оптимизационных задач.
Предмет исследования: оптимизация задач методом динамического программирования.
Цель данной работы заключается в разработке алгоритмов решения оптимизационных задач методом динамического программирования и программной реализации одного из полученных алгоритмов.
Для достижения поставленной цели потребуется:
•Изучить виды оптимизационных задач.
•Проанализировать метод динамического программирования.
•Построить математические и оптимизационные модели для выбранных задач.
•Описать алгоритмы решения оптимизационных задач.
•Разработать программную реализацию одного из полученных алгоритмов для решения выбранной задачи.
•Протестировать программное обеспечение на реальных задачах.
Оптимизационными называются экономико-математические задачи, цель которых заключается в нахождении оптимального (наилучшего) с точки зрения некоторого критерия или критериев варианта использования имеющихся ресурсов (труда, капитала и пр.).
Опирающиеся на хорошо построенные математические модели задачи управления приводят к качественным и пригодным для применения на практике результатам. Однако, такие задачи управления являются сложными, и простых формул для их решения не существует. Поэтому возникает объективная потребность в разработке специальных математических методов решения поставленных задач.
Таким методом решения задач управления многошаговыми процессами является рассматриваемый в данной работе метод динамического программирования.
Динамическое программирование — это один из математических методов нахождения оптимальных решений по управлению многошаговыми процессами. Состояние исследуемых систем изменяется поэтапно или во времени. В реальном мире подобные процессы и системы имеют широкое распространение. Важность и актуальность применения математических методов для решения соответствующих управленческих задач определяется необходимостью эффективного управления. Для метода динамического программирования теоретической основой является принцип оптимальности, который получил широкую сферу приложений в технике, естествознании, экономике и военном деле.
Объект исследования: математические модели оптимизационных задач.
Предмет исследования: оптимизация задач методом динамического программирования.
Цель данной работы заключается в разработке алгоритмов решения оптимизационных задач методом динамического программирования и программной реализации одного из полученных алгоритмов.
Для достижения поставленной цели потребуется:
•Изучить виды оптимизационных задач.
•Проанализировать метод динамического программирования.
•Построить математические и оптимизационные модели для выбранных задач.
•Описать алгоритмы решения оптимизационных задач.
•Разработать программную реализацию одного из полученных алгоритмов для решения выбранной задачи.
•Протестировать программное обеспечение на реальных задачах.
✅ Заключение
В результате изучения и анализа метода динамического программирования показан широкий спектр задач, к которым данный метод применим. Представлены подходы использования метода динамического программирования.
В работе были подробно рассмотрены разные виды оптимизационных задач и особенности применения к ним метода динамического программирования для решения в общем виде.
В рамках данной работы описаны алгоритмы решения оптимизационных задач, полученные методом динамического программирования. Работа алгоритмов продемонстрирована на конкретных примерах оптимизационных задач.
Применение метода динамического программирования к оптимизационным задачам малой размерности позволило получить эффективные алгоритмы решения, в редких случаях уступающих альтернативным алгоритмам. Однако при увеличении размерности задачи сильно увеличивается трудоемкость решения и объём памяти, требуемый для хранения результатов решения большого количество подзадач.
Задача отыскания кратчайших путей является удачным примером применения метода динамического программирования. На основе полученного алгоритма решения этой задачи была реализована программа на языке программирования Java. Алгоритм дополнен определением совокупностей вершин, через которые проходят вычисленные кратчайшие пути.
В работе были подробно рассмотрены разные виды оптимизационных задач и особенности применения к ним метода динамического программирования для решения в общем виде.
В рамках данной работы описаны алгоритмы решения оптимизационных задач, полученные методом динамического программирования. Работа алгоритмов продемонстрирована на конкретных примерах оптимизационных задач.
Применение метода динамического программирования к оптимизационным задачам малой размерности позволило получить эффективные алгоритмы решения, в редких случаях уступающих альтернативным алгоритмам. Однако при увеличении размерности задачи сильно увеличивается трудоемкость решения и объём памяти, требуемый для хранения результатов решения большого количество подзадач.
Задача отыскания кратчайших путей является удачным примером применения метода динамического программирования. На основе полученного алгоритма решения этой задачи была реализована программа на языке программирования Java. Алгоритм дополнен определением совокупностей вершин, через которые проходят вычисленные кратчайшие пути.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.