Решение оптимизационных задач методом «ветвей и границ»

Содержание

Введение 3
Глава 1. Оптимизация в математике 5
1.1. Основные понятия. 5
1.2. Оптимизационные модели. 7
1.2.1. Понятие оптимизационной модели и её разновидности. 7
1.2.2. Обобщенная оптимизационная модель. 7
1.3. Классификация методов оптимизации. 9
1.4. Оптимизационные задачи. 24
1.4.1. Классификация оптимизационных задач по содержанию. 24
1.4.2. Классификация оптимизационных задач исходя из математической трактовки. 29
1.4.3. Задача Коммивояжера. 32
Глава 2. Математическое программирование 33
2.1 Понятие математического программирования и его разновидности. 33
2.2. Общая постановка задачи математического программирования. 35
2.3. Обзор методов решения для задачи Коммивояжера. 38
2.4. Метод ветвей и границ. 41
2.5. Решение задачи коммивояжера методом ветвей и границ. 43
Заключение 54
Список литературы 55
Приложения 56
Приложение 1: Процедура чтения матрицы из Edit - ов. 56
Приложение 2: Реализация алгоритма решения задачи Коммивояжёра методом ветвей и границ в среде программирования Delphi. 56

Частью линейного программирования являются транспортные задачи, которые играют особую роль в уменьшении транспортных издержек, как для различных предприятий, так и для отдельных людей в частности. Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) - задача коммивояжера. Также встречается название «задача о бродячем торговце». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Любая задача транспортного типа, как задача линейно¬го программирования, может быть решена симплекс-методом, однако матрица системы ограничений транспортных задач весьма своеобразна, в связи с чем, разработаны более эффективные вычислительные методы. И один из них, который будет рассматриваться в выпускной квалификационной работе, это метод ветвей и границ, использующий направленный перебор вариантов с дальнейшим отсечением не нужных.
Актуальность. Данная работа даст возможность минимизировать затраты на перемещение, что в дальнейшем будет способствовать экономии времени и денег, что немало важно в наше время. Тем более для людей, которые часто путешествуют, появится возможность найти оптимальный путь для посещения всех интересующих их мест.
Цель выпускной квалификационной работы - решение базовой оптимизационной задачи Коммивояжёра методом ветвей и границ и реализация этого алгоритма в среде программирования Delphi.
Задачи выпускной квалификационной работы:
1) рассмотреть оптимизационные задачи и обобщённую оптимизационную модель.
2) рассмотреть методы оптимизации.
3) сделать обзор методов решения для задачи Коммивояжёра.
4) выявить плюсы использования метода ветвей и границ.
5) решить задачу Коммивояжёра методом ветвей и границ

В настоящее время оптимизация находит применение в науке, технике и в любой другой области человеческой деятельности.
Оптимизация - это целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.
Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации. Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.
В настоящее время новейшие достижения математики и современной вычислительной техники находят все более широкое применение в планировании. Этому способствует развитие таких разделов математики, как математическое программирование, теория игр, теория массового обслуживания, а также бурное развитие быстродействующей электронно-вычислительной техники. Уже накоплен достаточный опыт постановки и решения экономических задач с помощью математических методов.
Задачи, цель которых состоит в нахождении наилучшего (оптимального) варианта, с точки зрения некоторого критерия или критериев, называются оптимизационными. Оптимизационные задачи решаются с помощью оптимизационных моделей методами математического программирования.
Линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решений.