Решение задачи о Коммивояжере методом ветвей и границ

    Для множества  матрица такова:

    Таблица 20

    Приведение  этой матрицы дает:

    Таблица 21

    Для оценочной функции: =17+1=18.

    Получилось, что для дальнейшей разработки можно  брать любое из множеств и . В первом случае уже получена матрица размером 2´2; ее нулевые клетки дают те ребра, которые с найденными ранее составляют обход коммивояжера, причем вес этого обхода равен значению оценочной функции - 18. Вот этот обход: 

(1,4)(4,3)(2,1)(5,2)(3,5) или 1®4®3®5®2®1. 

    Найденный рекорд на самом деле является искомым  оптимумом, потому что значения оценочной функции на всех оборванных ветвях (на границах) больше или равны весу рекорда.

    При ином варианте выборов по ходу разбиений  можно было получить другой оптимум: 1®4®3®2®5®1.

ПРАКТИЧЕСКОЕ ЗАДАНИЕ 

    Требуется найти легчайший простой основный ориентированный цикл в полном взвешенном ориентированном графе на четырех вершинах (рис. 2):

Рис. 2. Ориентированный  граф задачи коммивояжера 

    Попробуем решить данную задачу методом «жадный  алгоритм». 

    Из  пункта 1 существует только один путь – путь к пункту 2, стоимость пути равна 78. Из пункта 2 существует только один путь – путь к пункту 3, стоимость пути равна 81. Из пункта 3 существует два пути – путь к пункту 1 и путь к пункту 4. Выберем самый кратчайший путь – это путь к пункту 4, стоимость пути равна 16. Из пункта 4 существует два пути – путь к пункту 1 и путь к пункту 2. Так как в пункте 2 мы уже были, то идем в пункт 1, стоимость пути равна 25.

    Полный  обход коммивояжера, исходя из предыдущего решения, равен 1®2®3®4®1, а сумма пути равна: 78+81+16+25 = 200. 
 
 
 
 
 
 

Описание  работы программы 

    Программа реализована в среде Borland Pascal 7.0. Она включает несколько процедур и функций по обработке матриц согласно алгоритму метода ветвей и границ:

1. function to0 - функция  получает нули в строках и столбцах матрицы и выдает сумму вычтенных ей элементов.
2. procedure chooseedge - выбор нуля, по которому будем ветвиться
3. procedure add - добавление ребра i->ip к частичному решению
4. procedure process - обход узла
5. procedure readdata – чтение данных из текстового файла input.txt
6. procedure out – вывод результатов на экране

    В главной процедуре вызываются только две: readdata - чтение из файла и process - вывод на экран.

    От  пользователя требуется создать  файл с исходными данными input.txt и запустить программу в среде Borland Pascal 7.0. Конечный результат представляет собой оптимальный маршрут и длину пути, выводимый на экране компьютера. 
 
 
 
 
 
 
 
 
 
 

Приложение А

(обязательное)

    Пример  исходного текстового файла input.txt

    Конечные  результаты вычислений.

ЗАКЛЮЧЕНИЕ

    В данной курсовой работе были рассмотрены  основные теоретические вопросы  по задаче коммивояжера. Приведено  решение вручную задачи методом  ветвей и границ.   Изучено практическое применение задачи коммивояжера.  Приведен текст программы, позволяющей решить задачу коммивояжера методом ветвей и границ, написанный на языке Turbo Pascal 7.0.

     Существуют  несколько методов решения задачи коммивояжера: метод полного перебора, с помощью метода ветвей и границ (алгоритм Литтла), алгоритма Крускала, «деревянного» алгоритма и т.д. Однако только метод ветвей и границ дает нам в итоге самое оптимальное решение.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 
 

1. Вентцель  Е.С. Исследование операций: задачи, принципы, методология. – М.: Высшая школа, 2009. – 208 с.
2. Конюховский П.В. Математические методы исследования операций в экономике. Краткий курс. – СПб.: Питер, 2009. – 208 с.
3. Просветов Г.И. Математические методы в экономике: Учебно-методическое пособие. – М.: Издательство РДЛ, 2008. – 160 с.
4. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. – М.: Вузовский учебник, 2009. – 144 с.
5. Костевич Л.С. Математическое программирование: Информационные технологии оптимальных решений. – Мн.: Новое знание, 2008. – 424 с.
6. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 2008. – 319 с.
7. Фомин Г.П. Математические методы и модели в коммерческой деятельности. Учебник. – М.: Финансы и статистика, 2009 г.
8. О. Е. Акимов «Дискретная математика. Логика, группы, графы», Москва, 2009, 376 с., ил., изд. дом «Лаборатория базовых знаний».