📄Работа №62422
Тема: ПРИБЛИЖЕННЫЙ АЛГОРИТМ ДЛЯ РЕШЕНИЯ ЗАДАЧИ МИНИМИЗАЦИИ МАКСИМАЛЬНОГО ШТРАФА
Характеристики работы
Тип работы
Бакалаврская работа
Предмет
Информатика и вычислительная техника
Объем:
41 листов
Год:
2017
Просмотров:
379
4750
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 3
1. Цель работы 5
2. Постановка задачи 6
3. Описание алгоритма 8
4. Описание работы проекта 9
4.1 Результаты работы проекта 9
5. Примеры 13
6. Эксперименты 16
Заключение 23
Список использованной литературы 25
Приложение 26
1. Цель работы 5
2. Постановка задачи 6
3. Описание алгоритма 8
4. Описание работы проекта 9
4.1 Результаты работы проекта 9
5. Примеры 13
6. Эксперименты 16
Заключение 23
Список использованной литературы 25
Приложение 26
📖 Введение
Люди на протяжении всей своей жизни сталкиваются с необходимостью составления расписаний. Каждый из нас занимается планированием личного времени. Мы знаем что и к какому сроку нужно выполнить, а также имеем представление, сколько времени потребуется на каждое дело. Исходя из этих данных мы составляем расписание, согласуя наши дела по времени. Чаще всего составление личного расписания не вызывает сложности. Практически все люди при этом руководствуются “похожими алгоритмами”, стремясь сделать все дела вовремя.
Часто мы планируем наши действия в порядке возрастания крайних сроков исполнения работ. Например, студенты во время экзаменационной сессии учат предмет с наименьшим директивным сроком (ближайший по дате сдачи экзамен), тем самым они минимизируют максимальное временное смещение.
Но перед обществом стоят и более трудные задачи. Развивающаяся стремительными темпами автоматизация производства и неуклонно увеличивающиеся его масштабы требуют разработки алгоритмов составления расписаний, в которых учтены разнообразные ограничения.
Теория расписаний - одна из самых популярных с теоретической и практической точек зрения области исследования операций. Задачи теории расписаний, разумеется, связаны с построением расписаний, т.е. с упорядочиванием некоторых работ (операций) по времени и/или по исполнителям (приборам). При этом необходимо учитывать ограничения на последовательность выполнения работ, ограничения, связанные с исполнителями, и т.п. Цель решения таких задач - построение допустимых расписаний, при котором все ограничения соблюдены, или, что является более сложным, - нахождение оптимального допустимого расписания потому или иному критерию оптимальности. Например, построение оптимального
Задачи составления расписаний возникают в частности:
• на транспорте при составлении расписания движения поездов, самолетов, общественного городского транспорта;
• при планировании занятий в учебных заведениях;
• при планировании занятости персонала, например, дежурства врачей;
• при выполнении сложных продолжительных проектов строительства зданий, кораблей и т.п.;
• при планировании проведения спортивных мероприятий;
• в компьютерных сетях при планировании очередности передачи пакетов информации и т.д.
Из выше изложенного можно сделать вывод, что подобные задачи актуальны. В дипломной работе рассматривается известная NP - полная в сильном смысле задача теории расписаний для одного прибора: задача минимизации
максимального временного смещения. [1]
Часто мы планируем наши действия в порядке возрастания крайних сроков исполнения работ. Например, студенты во время экзаменационной сессии учат предмет с наименьшим директивным сроком (ближайший по дате сдачи экзамен), тем самым они минимизируют максимальное временное смещение.
Но перед обществом стоят и более трудные задачи. Развивающаяся стремительными темпами автоматизация производства и неуклонно увеличивающиеся его масштабы требуют разработки алгоритмов составления расписаний, в которых учтены разнообразные ограничения.
Теория расписаний - одна из самых популярных с теоретической и практической точек зрения области исследования операций. Задачи теории расписаний, разумеется, связаны с построением расписаний, т.е. с упорядочиванием некоторых работ (операций) по времени и/или по исполнителям (приборам). При этом необходимо учитывать ограничения на последовательность выполнения работ, ограничения, связанные с исполнителями, и т.п. Цель решения таких задач - построение допустимых расписаний, при котором все ограничения соблюдены, или, что является более сложным, - нахождение оптимального допустимого расписания потому или иному критерию оптимальности. Например, построение оптимального
Задачи составления расписаний возникают в частности:
• на транспорте при составлении расписания движения поездов, самолетов, общественного городского транспорта;
• при планировании занятий в учебных заведениях;
• при планировании занятости персонала, например, дежурства врачей;
• при выполнении сложных продолжительных проектов строительства зданий, кораблей и т.п.;
• при планировании проведения спортивных мероприятий;
• в компьютерных сетях при планировании очередности передачи пакетов информации и т.д.
Из выше изложенного можно сделать вывод, что подобные задачи актуальны. В дипломной работе рассматривается известная NP - полная в сильном смысле задача теории расписаний для одного прибора: задача минимизации
максимального временного смещения. [1]
✅ Заключение
В ходе данной работы были изучены постановки и методы решения известной NP-полной задачи теории расписаний - минимизации максимального временного смещения для одного прибора. Был разработан программный проект, включающий приближенные алгоритмы решения этой задачи. Один из алгоритмов представляет собой реализацию общей схемы решения задачи, второй - обобщенное правило Джексона (из всех поступивших требований на текущий момент выбирать с минимальным директивным сроком).
Разработанный программный проект достаточно универсален. Интерфейс удобен для тестирования алгоритмов и для их экспериментального исследования. В проекте предусмотрены различные способы ввода данных и вывода результатов.
Также был проведен численный эксперимент сравнения решений найденных предложенными алгоритмами. Эксперименты проводились с размерностями от 5 до 1000, для определенной размерности было сгенерировано и решено по 100 примеров. Из проведенных экспериментов было выявлено:
при размерности задачи = 5, в 38% примеров значения целевой функции совпали, в 2% примеров F1/F2 < 1, в 26% примеров F1/F2 < 1.1, в оставшихся 34% примеров F1/F2 < 1.7;
при размерности задачи = 10, в 15% примеров значения целевой функции совпали, в 8% примеров F1/F2 < 1.02, в 42% случаях F1/F2 < 1.05, в оставшихся 35% примеров F1/F2 < 1.16;
при размерности задачи = 20, в 13% примеров значения целевой функции совпали, в 22% примеров F1/F2 < 1.01, в 34% примеров F1/F2 < 1.05, в 30% примеров F1/F2 < 1.12;
при размерности задачи = 30, в 8% примеров значения целевой функции совпали, в 17% примеров F1/F2 < 1.01, в 31% примеров F1/F2 < 1.03, в 44% примеров F1/F2 < 1.09;
при размерности задачи = 50, в 7% примеров значения совпали, в 28% примеров F1/F2 < 1.01, в 24% примеров F1/F2 < 1.02, в 41% примеров значение F1/F2 < 1.05;
при размерности задачи = 100, в 4% примеров значения совпали, в 24% примеров F1/F2 < 1.005, в 53% примеров F1/F2 < 1.015, в 19% примеров F1/F2 < 1.02;
при размерности задачи = 500, в 3% примеров значения совпали, в 43% примеров F1/F2 < 1.002, в 28% примеров F1/F2 < 1.003, в 26% примеров F1/F2 < 1.004;
при размерности задачи = 1000, в 1% примеров значения совпали, в 40% примеров F1/F2 < 1.001, в 59% примерах F1/F2 < 1.002.
Из этого можно сделать вывод, что при увеличении размерности задачи процент совпадения решений уменьшается. Было определено, что в 88% примеров расписания с меньшим значением целевой функции были построены вторым приближенным алгоритмом (обобщенное правило Джексона), в 12% примеров значения целевой функции совпадают.
Разработанный программный проект достаточно универсален. Интерфейс удобен для тестирования алгоритмов и для их экспериментального исследования. В проекте предусмотрены различные способы ввода данных и вывода результатов.
Также был проведен численный эксперимент сравнения решений найденных предложенными алгоритмами. Эксперименты проводились с размерностями от 5 до 1000, для определенной размерности было сгенерировано и решено по 100 примеров. Из проведенных экспериментов было выявлено:
при размерности задачи = 5, в 38% примеров значения целевой функции совпали, в 2% примеров F1/F2 < 1, в 26% примеров F1/F2 < 1.1, в оставшихся 34% примеров F1/F2 < 1.7;
при размерности задачи = 10, в 15% примеров значения целевой функции совпали, в 8% примеров F1/F2 < 1.02, в 42% случаях F1/F2 < 1.05, в оставшихся 35% примеров F1/F2 < 1.16;
при размерности задачи = 20, в 13% примеров значения целевой функции совпали, в 22% примеров F1/F2 < 1.01, в 34% примеров F1/F2 < 1.05, в 30% примеров F1/F2 < 1.12;
при размерности задачи = 30, в 8% примеров значения целевой функции совпали, в 17% примеров F1/F2 < 1.01, в 31% примеров F1/F2 < 1.03, в 44% примеров F1/F2 < 1.09;
при размерности задачи = 50, в 7% примеров значения совпали, в 28% примеров F1/F2 < 1.01, в 24% примеров F1/F2 < 1.02, в 41% примеров значение F1/F2 < 1.05;
при размерности задачи = 100, в 4% примеров значения совпали, в 24% примеров F1/F2 < 1.005, в 53% примеров F1/F2 < 1.015, в 19% примеров F1/F2 < 1.02;
при размерности задачи = 500, в 3% примеров значения совпали, в 43% примеров F1/F2 < 1.002, в 28% примеров F1/F2 < 1.003, в 26% примеров F1/F2 < 1.004;
при размерности задачи = 1000, в 1% примеров значения совпали, в 40% примеров F1/F2 < 1.001, в 59% примерах F1/F2 < 1.002.
Из этого можно сделать вывод, что при увеличении размерности задачи процент совпадения решений уменьшается. Было определено, что в 88% примеров расписания с меньшим значением целевой функции были построены вторым приближенным алгоритмом (обобщенное правило Джексона), в 12% примеров значения целевой функции совпадают.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.