Тема: Метод «ветвей и границ» решения задач целочисленного программирования.

Введение Данная курсовая работа поднимает важную проблему — решение задачи коммивояжера. Так как эта задачи имеет дискретный характер, то ее можно решить методом «полного» перебора. Но такой метод является крайне не удачным, так как требует слишком много вычислительных мощностей ЭВМ. Нахождение и практическая реализация более быстрого метода нахождения оптимального решения является актуальной задачей. В середине 19 века в свет вышла детская головоломка, в которой предлагалось совершить «круговое путешествие» по 20 городам, расположенных в различных частях земного шара . Каждый город соединялся дорогами с тремя соседними так, что дорожная сеть образовывала 30 ребер додекаэдра, в вершинах которого находились города a, b, … t. Обязательным условием являлось требование: каждый город за исключением первого можно посетить один раз. Гамильтонова задача о путешественнике нередко преобразуется в задачу о коммивояжере.

---

Вам интересны контрольные онлайн для студентов ? Их выполнением занимается компания Work5.

---

. Коммивояжер – не свободно путешествующий турист, а деловой человек, ограниченный временными, денежными или какими-либо другими ресурсами. Гамильтонова задача может стать задачей о коммивояжере, если каждое из ребер снабдить числовой характеристикой. Это может быть километраж, время на дорогу, стоимость билета, расход горючего и т.д. Таким образом, условные характеристики дадут числовой ряд, элементы которого могут быть распределены между ребрами как угодно. Наиболее ярким и характерным примером применения задачи "О коммивояжере" стала оптимизация операций на конвейере: в 1984 году, после того как был проведен анализ последовательности и временных затрат на операции на конвейерах заводов компании "General Motors" и приняты рекомендованные меры, удалось увеличить общую производительность почти на 13% при неизменном числе рабочих и том же оборудовании. Расчеты производились на компьютерах IBM 360gr, которые в то время являлись одними из самых производительных систем в мире. Просчет и оптимизация 200 основных и 87 вспомогательных операций занял около 230 часов. Считается, что это было первое коммерческое применение компьютерных технологий в области управления производством в целом. Сейчас решение данной задачи необходимо во многих областях связанных с замкнутыми и при этом жестко связанными по времени системами, такими как: конвейерное производство, многооперационные обрабатывающие комплексы, судовые и железнодорожные погрузочные системы, перевозки грузов по замкнутому маршруту, расчет авиационных линий. Поэтому данная проблема на современном этапе развития общества имеет не самое последнее по значимости место. В коммерческой деятельности коммерсанты, торговые агенты постоянно проводят работу по поиску партнеров или клиентов для заключения договоров на поставку и покупку товаров. Для решения этих задач коммерсантам необходимо выезжать в командировки, выполнять вояж по целой сети городов как по нашей стране, так и за рубежом. Поскольку продолжительность командировки и транспортные расходы следует сокращать, то необходимо перед поездкой составить кратчайший маршрут, предусматривающий посещение каждого пункта только один раз, и вернуться обратно. Задача коммивояжера заключается в определении такой последовательности объезда городов, которая обеспечит минимальное время переезда, или минимальную стоимость проезда, или минимальное расстояние переезда. Результатом выполнения курсовой работы будет программа для ЭВМ, реализующая метод ветвей и границ для решения задачи коммивояжера.

Заключение Задача коммивояжера является частичным случаем гамильтоновой задачи о путешественнике. Суть задачи коммивояжера состоит в нахождении суммарной минимальной характеристики (расстояния, стоимости проезда и т.д.), при этом коммивояжер должен пройти все n городов по одному разу, вернувшись в тот город, с которого начал. Существуют несколько методов решения задачи коммивояжера,однако только метод ветвей и границ дает нам в итоге самое оптимальное решение. Основная идея метода Литтла состоит в том, что вначале строят нижнюю границу длин маршрутов для всего множества гамильтоновых контуров . Затем все множество контуров разбивают на два подмножества таким образом, чтобы первое подмножество состояло из гамильтоновых контуров, содержащих некоторую дугу (i,j), а другое подмножество не содержало этой дуги. Для практической реализации идеи метода ветвей и границ применительно к задаче коммивояжера нужно найти метод определения нижних границ подмножества и разбиения множества гамильтоновых контуров на подмножества (ветвление). Такое определение нижних границ базируется на том утверждении, что если ко всем элементам i-й строки или j-го столбца матрицы C прибавить или отнять число , то задача останется эквивалентной прежней, то есть оптимальность маршрута коммивояжера не изменится, а длина любого гамильтонова контура изменится на данную величину . В данной работе разработаны модель, алгоритм решения задачи коммивояжера методом ветвей и границ и создана программа, реализующая данный алгоритм. По результатам тестирования программа показала полную работоспособность и идентичность результатов теоретическим.

Список литературы 1. Вентцель Е.С. Исследование операций: задачи, принципы, методология. - М.: Высшая школа, 2004. - 208 с. 2. Исследование операций в экономике/ Под ред. Кремера Н.Ш. - М.:ЮНИТИ, 2004. - 407 с. 3. Конюховский П.В. Математические методы исследования операций в экономике. Краткий курс. - СПб.: Питер, 2002. - 208 с. 4. Просветов Г.И. Математические методы в экономике: Учебно-методическое пособие. - М.: Издательство РДЛ, 2004. - 160 с. 5. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. - М.: Вузовский учебник, 2004. - 144 с. 6. Костевич Л.С. Математическое программирование: Информационные технологии оптимальных решений. - М.: Новое знание, 2003. - 424 с. 7. Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986. - 319 с.