Введение 3
Постановка задачи 5
Обзор литературы 6
1. Изучение проблемы решения задач ЦЛП 7
1.1. Методы ветвей и границ 7
1.2. Методы отсечений 8
2. Реализация метода в приложении к рассматриваемой задаче 10
2.1. Входные данные задачи 10
2.2. Математическая постановка задачи 11
2.3. Первый алгоритм Гомори 13
3. Анализ работы реализованного алгоритма 18
4. Обзор реализованной системы 21
Выводы 24
Заключение 25
Список использованных источников 26
В современном мире любое производство, бизнес или любой другой вид деятельности сталкивается с проблемой оптимизации своей работы с целью минимизации затрат трудовых, финансовых и других ресурсов.
Одной из важнейших задач предприятий, занимающихся каким-либо производством, доставкой грузов или перевозкой пассажиров, является оптимальное распределение имеющихся транспортных ресурсов по тем или иным маршрутам с учетом грузоподъемности, вместимости груза или пассажиров, а также иных факторов. Необходимо не только обеспечить каждый маршрут достаточным количеством транспортных средств для перевозки нужного объема груза, но и сделать это так, чтобы расходы организации были снижены до минимума.
В качестве примера предприятий, сталкивающихся с такой задачей регулярно, можно привести организации, занимающиеся вывозом мусора из крупных городов. Разработка алгоритмов и систем управления вывозом твердых бытовых отходов из крупных мегаполисов является актуальной как по причине увеличения количества этих отходов, так и увеличения трафика в городах. В каждом городе существуют специальные организации, ответственные за сбор и вывоз бытовых отходов на полигоны или специализированные предприятия по их переработке. В данный момент ведется разработка системы «Чистый город», целью создания которой является динамическое составление маршрутов и оптимальное распределение по ним транспортных ресурсов. Ниже приведена схема работы вышеописанной системы [11:
Рисунок 1 - Схема работы системы «Чистый город»
Понятно, что существует еще множество приложений задачи оптимизации распределения транспорта к различным предметным областям.
В данной выпускной работе будет рассмотрела проблема нахождения оптимального распределения транспортных средств по маршрутам. Способы её решения будут заключатся в различных подходах к решению задач целочисленного линейного программирования.
В процессе выполнения выпускной квалификационной работы были решены следующие задачи:
1. Изучена литература по теме исследования. Выбраны инструменты для математической формализации поставленной задачи - методы ЦЛП.
2. Построена математическая модель, формализующая задачу оптимального распределения транспортных ресурсов предприятия.
3. Проведен сравнительный анализ большого количества алгоритмов для решения задач ЦЛП. Выбран алгоритм для дальнейшей программной реализации.
4. Реализована система, решающая поставленную задачу для небольших предприятий. Разработан простой пользовательский интерфейс, уже позволяющий использовать эту систему в практических целях.
5. Проведен анализ работы системы, её оптимизация.
