📄Работа №38339
Тема: Экспериментальное исследование приближенного алгоритма решения задачи минимизации максимального временного смещения
Тип работы
Бакалаврская работа
Предмет
Информатика и вычислительная техника
Объем:
41 листов
Год:
2019
Просмотров:
436
7300
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 3
1. Теоретические аспекты исследования задачи 5
1.1. Математическая постановка задачи 5
1.2. Метод решения задачи 6
2. Реализация программы 9
2.1. Описания работы программы 9
2.2. Реализация программной части 16
3. Экспериментальное исследование 20
3.1. Описание экспериментов 20
3.2. Анализ эксперимента 21
Заключение 23
Список литературы 25
Приложение
1. Теоретические аспекты исследования задачи 5
1.1. Математическая постановка задачи 5
1.2. Метод решения задачи 6
2. Реализация программы 9
2.1. Описания работы программы 9
2.2. Реализация программной части 16
3. Экспериментальное исследование 20
3.1. Описание экспериментов 20
3.2. Анализ эксперимента 21
Заключение 23
Список литературы 25
Приложение
📖 Введение
Теория расписаний - одна из самых популярных разделов исследования операций. В задачи теории расписаний входит упорядочивание некоторых требований (работ) по времени и/или приборам (исполнителям). При этом требуется учитывать ограничения, связанные с временем поступления и временем выполнения требований, а также ограничения, связанные с приборами, например, время начала их работы. Целью решения таких задач является построение допустимых расписаний с соблюдением всех ограничений. Более сложным является нахождение оптимального допустимого расписания по тому или иному критерию оптимальности (например, по быстродействию).
В рамках данной работы изучался метод решения задачи минимизации максимального временного смещения. При нахождении оптимального расписания по данному критерию важную роль играют директивные сроки требований. Директивным сроком называется момент времени, к которому необходимо или, во всяком случае, желательно завершить обслуживание требования. В общем случае не удается построить такого расписания, при котором обслуживание каждого требования завершается не позднее заданного директивного срока. Появляется объективная необходимость в нарушении отдельных директивных сроков, что связано с определенными потерями. Эти потери, как правило, зависят от того, какие именно требования и на сколько задерживаются с обслуживанием [2, с.73].
Большинство задач теории расписаний являются NP-трудными. В настоящее время поиск точных алгоритмов для их решения представляется бесперспективным, так как время их работы ограничено полиномом от размера входа задачи. Алгоритмы переборного типа, даже при решении примеров средней размерности, требуют больших вычислительных затрат. Именно поэтому построение и анализ приближенных алгоритмов является одной из важных направлений исследования. Более того, для многих оптимизационных задач теории расписаний необязательно находить точные ответы. Достаточно построить разумное приблизительное решение за короткое время, с чем успешно справляются приближенные алгоритмы.
Цели данной работы:
1) Программная реализация приближенного метода решения задачи минимизации максимального временного смещения. Программа должна помогать в исследовании данной задачи, а также обладать удобным и понятным для пользователя интерфейсом.
2) Исследование задачи минимизации максимального временного смещения и сравнение результатов приближенных алгоритмов для их решения.
Для разработки программы использовался язык программирования C# и технология WPF (Windows Presentation Foundation). Программа рассчитывает приближенное оптимальное расписание для введенных начальных данных и ограничений. Данные могут быть введены с экрана, а также получены из файла.
В рамках данной работы изучался метод решения задачи минимизации максимального временного смещения. При нахождении оптимального расписания по данному критерию важную роль играют директивные сроки требований. Директивным сроком называется момент времени, к которому необходимо или, во всяком случае, желательно завершить обслуживание требования. В общем случае не удается построить такого расписания, при котором обслуживание каждого требования завершается не позднее заданного директивного срока. Появляется объективная необходимость в нарушении отдельных директивных сроков, что связано с определенными потерями. Эти потери, как правило, зависят от того, какие именно требования и на сколько задерживаются с обслуживанием [2, с.73].
Большинство задач теории расписаний являются NP-трудными. В настоящее время поиск точных алгоритмов для их решения представляется бесперспективным, так как время их работы ограничено полиномом от размера входа задачи. Алгоритмы переборного типа, даже при решении примеров средней размерности, требуют больших вычислительных затрат. Именно поэтому построение и анализ приближенных алгоритмов является одной из важных направлений исследования. Более того, для многих оптимизационных задач теории расписаний необязательно находить точные ответы. Достаточно построить разумное приблизительное решение за короткое время, с чем успешно справляются приближенные алгоритмы.
Цели данной работы:
1) Программная реализация приближенного метода решения задачи минимизации максимального временного смещения. Программа должна помогать в исследовании данной задачи, а также обладать удобным и понятным для пользователя интерфейсом.
2) Исследование задачи минимизации максимального временного смещения и сравнение результатов приближенных алгоритмов для их решения.
Для разработки программы использовался язык программирования C# и технология WPF (Windows Presentation Foundation). Программа рассчитывает приближенное оптимальное расписание для введенных начальных данных и ограничений. Данные могут быть введены с экрана, а также получены из файла.
✅ Заключение
В ходе написания дипломного проекта была проделана следующая работа:
1) Были изучены теоретически аспекты задачи минимизации максимального временного смещения.
2) Был реализован приближенный алгоритм решения задачи на языке программирования C#, а также был реализован интерфейс для работы с программой с помощью технологии WPF.
3) Было проведено экспериментальное исследование, полученные результаты были проанализированы.
Программа способна работать с задачами разной размерности, может принимать данные как с экрана, так и считывать их из файла, проверяет данные на корректность и выдает правильный результат согласно Алгоритму 1.
Исходя из результатов исследования и анализа экспериментов можно сделать вывод, что Алгоритм 2 выдает более хорошее значение целевой функции при небольших размерностях требований и диапазонах значений параметров. При больших размерностях следует отдать предпочтение Алгоритму 1. Также при выборе алгоритма нужно также учитывать следующие факторы.
Во-первых, для работы Алгоритма 2 необходимо выполнение неравенств ri > Г2 > ... > Гд и di < d2 < ... < dn, а это значит, что не все примеры подойдут для решения задачи с помощью этого алгоритма. В свою очередь Алгоритм 1 может работать с любыми значениями параметров требований.
Во-вторых, алгоритмы имеют разную трудоемкость. Трудоемкость Алгоритма 1 составляет O(n4) операций, а трудоемкость Алгоритма 2 составляет 0(п2 • EJEN VJ)- ЕСЛИ значения pj не столь большие, второй алгоритм будет работать быстрее. Однако при больших значениях pj предпочтение стоит отдать Алгоритму 1.
Таким образом, можно сделать вывод, что оба алгоритма имеют свои достоинства и недостатки, и при выборе алгоритма нужно исходить из своих потребностей и учитывать их особенности.
1) Были изучены теоретически аспекты задачи минимизации максимального временного смещения.
2) Был реализован приближенный алгоритм решения задачи на языке программирования C#, а также был реализован интерфейс для работы с программой с помощью технологии WPF.
3) Было проведено экспериментальное исследование, полученные результаты были проанализированы.
Программа способна работать с задачами разной размерности, может принимать данные как с экрана, так и считывать их из файла, проверяет данные на корректность и выдает правильный результат согласно Алгоритму 1.
Исходя из результатов исследования и анализа экспериментов можно сделать вывод, что Алгоритм 2 выдает более хорошее значение целевой функции при небольших размерностях требований и диапазонах значений параметров. При больших размерностях следует отдать предпочтение Алгоритму 1. Также при выборе алгоритма нужно также учитывать следующие факторы.
Во-первых, для работы Алгоритма 2 необходимо выполнение неравенств ri > Г2 > ... > Гд и di < d2 < ... < dn, а это значит, что не все примеры подойдут для решения задачи с помощью этого алгоритма. В свою очередь Алгоритм 1 может работать с любыми значениями параметров требований.
Во-вторых, алгоритмы имеют разную трудоемкость. Трудоемкость Алгоритма 1 составляет O(n4) операций, а трудоемкость Алгоритма 2 составляет 0(п2 • EJEN VJ)- ЕСЛИ значения pj не столь большие, второй алгоритм будет работать быстрее. Однако при больших значениях pj предпочтение стоит отдать Алгоритму 1.
Таким образом, можно сделать вывод, что оба алгоритма имеют свои достоинства и недостатки, и при выборе алгоритма нужно исходить из своих потребностей и учитывать их особенности.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.