Заказать работу


Тип работы:
Предмет:
Язык работы:


Применение биоинспирированных алгоритмов для оптимизации работы торгового представителя оптовой компании

Работа №30423
Тип работыДипломные работы
Предметматематика
Объем работы44
Год сдачи2018
Стоимость3700 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено 8
Не подходит работа?

Узнай цену на написание
Введение 3
1. Классические задачи теории расписаний и построения маршрутов в графах 5
1.1. Методы составления расписаний 5
1.2. Методы построения оптимальных маршрутов 11
1.3. Биоинспирированные методы 14
2. Практическое применение биоинспирированных методов
2.1. Биоинспирированные методы решения задачи составления
расписания 21
2.2. Применение муравьиных алгоритмов для составления
оптимальных маршрутов 26
2.3. Описание программы и полученных результатов 30
Заключение 34
Список литературы 35
Приложение
Задача составления расписания зачастую возникает во многих сферах деятельности: транспортной, энергетической, коммунальной, промышленной и так далее. Компаниям необходимо сформировывать различного рода расписания, например: график отпусков рабочих, расписание обработки документации и другие. Чем крупнее компания, тем сложнее организовать для нее оптимальное расписание выполнения тех или иных задач.
Наряду с задачей о составлении расписания также стоит проблема построения оптимального маршрута. Сделать такой маршрут между тремя или четырьмя точками не составляет проблем. Однако, чем больше компания, тем больше точек необходимо посетить и тем сложнее построить хороший маршрут.
Каждое предприятие решает проблемы составления расписания и оптимизации маршрута по-разному, но чаще всего это происходит вручную. При таком подходе к составлению расписания и маршрута маловероятно, что получившийся результат будет оптимальным. В связи с вышеизложенным возникает необходимость в построении автоматизированных систем составления расписания и маршрута.
Цель и задачи исследования.
Целью выпускной квалификационной работы является построение математической модели составления расписания для торгового представителя оптовой компании на неделю и получение оптимального маршрута передвижения.
Для решения данной проблемы необходимо решить ряд задач.
1. Рассмотреть некоторые классические методы решения задач теории расписаний.
2. Рассмотреть метод создания расписания, основанный на применении генетического алгоритма.
3. Рассмотреть метод муравьиного алгоритма для решения задачи составления оптимального маршрута.
Выпускная квалификационная работа объемом 37 листов состоит из введения двух частей, заключения и списка литературы, включающего 23 источника. Работа содержит 10 рисунков, 4 таблицы и приложение.
В настоящей работе была сформулирована задача о составлении расписания для торговых компаний. Для ее решения были рассмотрены два классических метода теории расписаний. После тщательного анализа было установлено, что их применение на практике оказывается достаточно труднореализуемым в случае, когда необходимо учесть все факторы, имеющиеся в поставленной задаче. Это потребовало применения альтернативных способов поиска решения.
Также в работе были рассмотрены некоторые классические алгоритмы решения задачи поиска оптимального маршрута в графе. Точное решение такой задачи возможно только при помощи полного перебора возможных решений, что практически реализуемо лишь только при малых значениях числа пунктов посещения. Существуют алгоритмы неполного перебора. В качестве такового в исследовании был рассмотрен еще один биоинспирированный метод - муравьиный алгоритм.
Как показало исследование, биоинспирированные методы оказались очень гибкими алгоритмами для решения подобных задач. Генетический алгоритм может учесть множество различных факторов. Требуется только правильно представить особь и реализовать эволюционные операторы. Он был использован в качестве метода, для составления расписания. Муравьиный алгоритм может быть использован для построения оптимального маршрута с дополнительными условиями, которые отсутствуют в классических постановках задач.
Для того, чтобы сформировать расписание и найти оптимальный маршрут, на языке программирования C# была создана программа с графическим интерфейсом пользователя.
На данный момент в приложении реализована только часть, выполняющая составление расписания на неделю для торгового представителя по заданным исходным данным. В дальнейшем планируется усовершенствовать и расширить приложения за счет добавления распараллеливания вычислений, а также включения муравьиного алгоритма для построения оптимального маршрута.
1. Gantt, H.L. A graphical daily balance in manufacture / H.L. Gantt ASME Transactions 1903. - Vol. 24. - P. 1322-1336.
2. Bellman, R. Mathematical aspects of scheduling theory / R. Bellman // Journal of the Society of Industrial and Applaid Mathematics. 1956. - Vol. 4. - P. 168 -205.
3. Johnson, S.M. Optimal two- and three-stage production schedules with setup times included. / S.M. Johnson // Naval Research Logistics Quarterly. 1954. -
V. 1. - P. 61-68.
4. Jackson, J.R. Scheduling a production line to minimize maximum tardiness / J. R. Jackson // Los Angeles, CA: University of California. 1955. - Manag. Sci. Res. Project. Research Report N 43. - P. 72.
5. Smith, W.E. Various optimizers for single stage production / W. E. Smith // Naval Research Logistics Quarterly. 1956. - V. 3. - P. 59-66.
6. Graham, R.L., A.H.G Optimization and approximation in determenistic sequencing and scheduling: a servey / R. L. Graham, E. L. Lawler, J. K. Lenstra, Kan Rinnooy // Ann. Descrete Optimization. 1979. - V. 2. - P. 287-325.
7. Лазарев, А. А. Теория расписаний. Задачи и алгоритмы /
A. А. Лазарев, Е. Р. Гафаров, Москва, 2011. - 222 с.
8. Танаев, В. С. Введение в теорию расписаний / В. С. Танаев,
B. В. Шкурба. - М.: Наука, 1975. - 256 с.
9. Тюхтина, А. А. Методы дискретной оптимизации: Часть 1 / А. А. Тюхтина. Методическое пособие. - Нижний Новгород: Нижегородский госуниверситет, 2014. - 62 с.
10. Geunes, J. Operations Planning: Mixed Integer Optimization Models (Operations Research Series). / J. Geunes CRC Press, 2014. - P. 167-172.
11. Тюхтина, А. А. Методы дискретной оптимизации: Часть 2 / А. А. Тюхтина. Методическое пособие. - Нижний Новгород: Нижегородский госуниверситет, 2015. - 72 с.
12. Задачи оптимизации [Электронный ресурс]: / Алгоритм Литтла -
метод решения задачи коммивояжера. Режим доступа:
http://uchimatchast.ru/teory/litl.php, свободный.
13. Holland, J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis With Applications to Biology, Control, and Artificial Intelligence / J. H. Holland. — The MIT Press, Cambridge, 1992. — ISBN 0262581116
14. Дарвин, Ч. О происхождении видов путем естественного отбора или сохранении благоприятствуемых пород в борьбе за жизнь / Ч. Дарвин. - М.: АН СССР, 1939. - 184 с.
15. Еремеев, А. В. Генетические алгоритмы и оптимизации /
A. В. Еремеев. Учебное пособие. - Омск, 2008. - 34 с.
16. Национальный открытый университет «ИНТУИТ» [Электронный ресурс]: / Модификации генетических алгоритмов. Режим доступа: https://www.intuit.ru/studies/courses/14227/1284/lecture/24172?page=2, свободный.
17. Панченко, Т.В. Генетические алгоритмы / Т.В. Панченко; учебно-методическое пособие под ред. Ю.Ю. Тарасевича. - Астрахань: Издательский дом «Астраханский университет», 2007. - 87 с.
18. Спицын, В. Г. применение генетического алгоритма для решения задач оптимизации / В. Г. Спицын, Ю. Р. Цой. Учебное пособие. - Томск, 2007. - 27 с.
19. Гладков, Л. А. Генетические алгоритмы / Л. А. Гладков,
B. В. Курейчик, В. М. Курейчик. Под ред. В. М. Курейчика. - 2-е изд., испр. и доп. - М.: ФИЗМАТЛИТ, 2006. - 320 c.
20. Dorigo, M. Distrubets Optimization by Ant Colonies / M. Dorigo, A. Colomi, V. Maniezzo // Actes de la premiere conference european sur la vie artificielle. - 1991. - P. 134 - 142.
21. Штовб, С. Д. Муравьиные алгоритмы / С. Д. Штовб // ExponentaPro. - 2003. - №4. - C. 70-75.
22. Шарп, Д. Microsoft Visual C#. Подробное руководство. / Д. Шарп. - М.: Питер, 8-е издание, 2017. - 848 с.
23 Мартишин, С. А. Проектирование и реализация баз данных в СУБД MySQL с использованием MySQL Workbench: Методы и средства проектирования информационных систем / С. А. Мартишин, В. Л. Симонов. Учебное пособие. - М.: ИНФРА-М, 2012. - 160 с.

Работу высылаем на протяжении 30 минут после оплаты.

Пожалуйста, укажите откуда вы узнали о сайте!




Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании студенческих
и аспирантских работ!



Задача составления расписания зачастую возникает во многих сферах деятельности: транспортной, энергетической, коммунальной, промышленной и так далее. Компаниям необходимо сформировывать различного рода расписания, например: график отпусков рабочих, расписание обработки документации и другие. Чем крупнее компания, тем сложнее организовать для нее оптимальное расписание выполнения тех или иных задач.
Наряду с задачей о составлении расписания также стоит проблема построения оптимального маршрута. Сделать такой маршрут между тремя или четырьмя точками не составляет проблем. Однако, чем больше компания, тем больше точек необходимо посетить и тем сложнее построить хороший маршрут.
Каждое предприятие решает проблемы составления расписания и оптимизации маршрута по-разному, но чаще всего это происходит вручную. При таком подходе к составлению расписания и маршрута маловероятно, что получившийся результат будет оптимальным. В связи с вышеизложенным возникает необходимость в построении автоматизированных систем составления расписания и маршрута.
Цель и задачи исследования.
Целью выпускной квалификационной работы является построение математической модели составления расписания для торгового представителя оптовой компании на неделю и получение оптимального маршрута передвижения.
Для решения данной проблемы необходимо решить ряд задач.
1. Рассмотреть некоторые классические методы решения задач теории расписаний.
2. Рассмотреть метод создания расписания, основанный на применении генетического алгоритма.
3. Рассмотреть метод муравьиного алгоритма для решения задачи составления оптимального маршрута.
Выпускная квалификационная работа объемом 37 листов состоит из введения двух частей, заключения и списка литературы, включающего 23 источника. Работа содержит 10 рисунков, 4 таблицы и приложение.

В настоящей работе была сформулирована задача о составлении расписания для торговых компаний. Для ее решения были рассмотрены два классических метода теории расписаний. После тщательного анализа было установлено, что их применение на практике оказывается достаточно труднореализуемым в случае, когда необходимо учесть все факторы, имеющиеся в поставленной задаче. Это потребовало применения альтернативных способов поиска решения.
Также в работе были рассмотрены некоторые классические алгоритмы решения задачи поиска оптимального маршрута в графе. Точное решение такой задачи возможно только при помощи полного перебора возможных решений, что практически реализуемо лишь только при малых значениях числа пунктов посещения. Существуют алгоритмы неполного перебора. В качестве такового в исследовании был рассмотрен еще один биоинспирированный метод - муравьиный алгоритм.
Как показало исследование, биоинспирированные методы оказались очень гибкими алгоритмами для решения подобных задач. Генетический алгоритм может учесть множество различных факторов. Требуется только правильно представить особь и реализовать эволюционные операторы. Он был использован в качестве метода, для составления расписания. Муравьиный алгоритм может быть использован для построения оптимального маршрута с дополнительными условиями, которые отсутствуют в классических постановках задач.
Для того, чтобы сформировать расписание и найти оптимальный маршрут, на языке программирования C# была создана программа с графическим интерфейсом пользователя.
На данный момент в приложении реализована только часть, выполняющая составление расписания на неделю для торгового представителя по заданным исходным данным. В дальнейшем планируется усовершенствовать и расширить приложения за счет добавления распараллеливания вычислений, а также включения муравьиного алгоритма для построения оптимального маршрута.



1. Gantt, H.L. A graphical daily balance in manufacture / H.L. Gantt ASME Transactions 1903. - Vol. 24. - P. 1322-1336.
2. Bellman, R. Mathematical aspects of scheduling theory / R. Bellman // Journal of the Society of Industrial and Applaid Mathematics. 1956. - Vol. 4. - P. 168 -205.
3. Johnson, S.M. Optimal two- and three-stage production schedules with setup times included. / S.M. Johnson // Naval Research Logistics Quarterly. 1954. -
V. 1. - P. 61-68.
4. Jackson, J.R. Scheduling a production line to minimize maximum tardiness / J. R. Jackson // Los Angeles, CA: University of California. 1955. - Manag. Sci. Res. Project. Research Report N 43. - P. 72.
5. Smith, W.E. Various optimizers for single stage production / W. E. Smith // Naval Research Logistics Quarterly. 1956. - V. 3. - P. 59-66.
6. Graham, R.L., A.H.G Optimization and approximation in determenistic sequencing and scheduling: a servey / R. L. Graham, E. L. Lawler, J. K. Lenstra, Kan Rinnooy // Ann. Descrete Optimization. 1979. - V. 2. - P. 287-325.
7. Лазарев, А. А. Теория расписаний. Задачи и алгоритмы /
A. А. Лазарев, Е. Р. Гафаров, Москва, 2011. - 222 с.
8. Танаев, В. С. Введение в теорию расписаний / В. С. Танаев,
B. В. Шкурба. - М.: Наука, 1975. - 256 с.
9. Тюхтина, А. А. Методы дискретной оптимизации: Часть 1 / А. А. Тюхтина. Методическое пособие. - Нижний Новгород: Нижегородский госуниверситет, 2014. - 62 с.
10. Geunes, J. Operations Planning: Mixed Integer Optimization Models (Operations Research Series). / J. Geunes CRC Press, 2014. - P. 167-172.
11. Тюхтина, А. А. Методы дискретной оптимизации: Часть 2 / А. А. Тюхтина. Методическое пособие. - Нижний Новгород: Нижегородский госуниверситет, 2015. - 72 с.
12. Задачи оптимизации [Электронный ресурс]: / Алгоритм Литтла -
метод решения задачи коммивояжера. Режим доступа:
http://uchimatchast.ru/teory/litl.php, свободный.
13. Holland, J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis With Applications to Biology, Control, and Artificial Intelligence / J. H. Holland. — The MIT Press, Cambridge, 1992. — ISBN 0262581116
14. Дарвин, Ч. О происхождении видов путем естественного отбора или сохранении благоприятствуемых пород в борьбе за жизнь / Ч. Дарвин. - М.: АН СССР, 1939. - 184 с.
15. Еремеев, А. В. Генетические алгоритмы и оптимизации /
A. В. Еремеев. Учебное пособие. - Омск, 2008. - 34 с.
16. Национальный открытый университет «ИНТУИТ» [Электронный ресурс]: / Модификации генетических алгоритмов. Режим доступа: https://www.intuit.ru/studies/courses/14227/1284/lecture/24172?page=2, свободный.
17. Панченко, Т.В. Генетические алгоритмы / Т.В. Панченко; учебно-методическое пособие под ред. Ю.Ю. Тарасевича. - Астрахань: Издательский дом «Астраханский университет», 2007. - 87 с.
18. Спицын, В. Г. применение генетического алгоритма для решения задач оптимизации / В. Г. Спицын, Ю. Р. Цой. Учебное пособие. - Томск, 2007. - 27 с.
19. Гладков, Л. А. Генетические алгоритмы / Л. А. Гладков,
B. В. Курейчик, В. М. Курейчик. Под ред. В. М. Курейчика. - 2-е изд., испр. и доп. - М.: ФИЗМАТЛИТ, 2006. - 320 c.
20. Dorigo, M. Distrubets Optimization by Ant Colonies / M. Dorigo, A. Colomi, V. Maniezzo // Actes de la premiere conference european sur la vie artificielle. - 1991. - P. 134 - 142.
21. Штовб, С. Д. Муравьиные алгоритмы / С. Д. Штовб // ExponentaPro. - 2003. - №4. - C. 70-75.
22. Шарп, Д. Microsoft Visual C#. Подробное руководство. / Д. Шарп. - М.: Питер, 8-е издание, 2017. - 848 с.
23 Мартишин, С. А. Проектирование и реализация баз данных в СУБД MySQL с использованием MySQL Workbench: Методы и средства проектирования информационных систем / С. А. Мартишин, В. Л. Симонов. Учебное пособие. - М.: ИНФРА-М, 2012. - 160 с.


Работу высылаем на протяжении 30 минут после оплаты.

Пожалуйста, укажите откуда вы узнали о сайте!



© 2008-2018 Сервис продажи готовых курсовых работ, дипломных проектов, рефератов, контрольных и прочих студенческих работ.