Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






методом ветвей и границ




Задача про коммивояжера. Пусть n есть городов. Известна матрица расстояний между любой парой городов .Выезжая из начального города, коммивояжер должен побывать во всех городах ровно один раз и вернуться в начальный город. Необходимо узнать в каком порядке нужно объезжать города, чтобы пройденный путь был минимальным.

Введем неизвестные

Тогда получаем задачу

Первая группа ограничений говорит о том , что коммивояжер выезжает из каждого города один раз, а вторые о том, что он один раз въезжает в каждый город.

Пример:Рассмотрим пример объезда 4 городов. Задана матрица расстояний между городами:

 

i \ j 1 2 3 4
1 ¥ 4 5 3
2 6 ¥ 7 2
3 5 7 ¥ 8
4 4 2 3 ¥

 

Необходимо найти последовательность объезда городов так чтобы путь был минимальным.

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

 

i \ j 1 2 3 4
1 ¥ 4 5 3 3
2 6 ¥ 7 2 2
3 5 7 ¥ 8 5
4 4 2 3 ¥ 2

 

i \ j 1 2 3 4
1 ¥ 1 2 0
2 4 ¥ 5 0
3 0 2 ¥ 3
4 2 0 1 ¥
0 0 1 0

 

 

 

i \ j 1 2 3 4
1 ¥ 1 1 0
2 4 ¥ 4 0
3 0 2 ¥ 3
4 2 0 0 ¥

 

Обозначим полученную матрицу через .

В ней на месте минимальных переездов стоят 0.

Посчитаем оценку данного множества:

 

Таким образом, мы нашли минимальное расстояние объезда городов без учета въезда и выезда из каждого города один раз. Теперь найдем последовательность объезда городов уже с учетом данного условия. Для этого оценим каждый из нулей и выберем ноль с максимальной оценкой. Он нам покажет, какой переезд нам лучше включить в искомый путь.



Для того чтобы оценить ноль необходимо найти минимальный элемент в строке и столбце соответствующих данному элементу и сложить их.

 

Нашли первую пару городов объезда - переезд из города 2 в город 4. Проверим это. Для этого множество разобьем на два множества: .

Множество - множество всех переездов, в которых разрешен переезд из города 2 в город 4. Этому множеству соответствует матрица, полученная из матрицы вычеркиванием 2 строки и 4 столбца и запретом обратного переезда, т.е. элемент .

Множество - - множество всех переездов, в которых запрещен переезд из города 2 в город 4. Этому множеству соответствует матрица, полученная из матрицы заменой элемента .

Рассмотрим :

i \ j 1 2 3
1 ¥ 1 1 1
3 0 2 ¥ 0
4 2 0 0

 

i \ j 1 2 3
1 ¥ 1 1
3 0 2 ¥
4 2 0

 

 

i \ j 1 2 3
1 ¥ 0 0
3 0 2 ¥
4 2 0
0 0 0

 

 

Рассмотрим :



i \ j 1 2 3 4
1 ¥ 1 1 0
2 4 ¥ 4
3 0 2 ¥ 3
4 2 0 0 ¥

 

 

Так как то дальше дробить мы будем множество . Для этого оценим нули множество :

Нашли следующую пару объезда: .

Дробим множество .

Рассмотрим :

i \ j 2 3
1 0
4 0

 

Мы получили матрицу второго порядка. Дальнейшее дробление невозможно. Получили объезд:

Длина объезда:

 

Рассмотрим :

 

i \ j 1 2 3
1 ¥ 0 0
3 2 ¥
4 2 0

 

Так как , то найденный переход оптимален и его длина 14.

 

Построим дерево решений.

 

 

 

Графическое изображение переезда.

 

 

 

Вопрос для самоподготовки

1. Сформулируйте задачу о коммивояжере?

2. Что определяют ограничения в задаче о коммивояжере?

3. По какому признаку множественное число решений разделяется на подмножества?

4. На матрице какого порядка мы заканчиваем решение задачи, и почему?

 

Литература.

Основна

  1. Зайченко Ю.П. Исследование операций.- К.:Высшая школа,1988-552с.
  2. Зайченко Ю.П. Исследование операций. Сборник задач.- К.:Высшая школа,1990-239с.
  3. Юхименко Б.І. Математичне програмування для єкономистів. Навчальний посібник.- Одеса: Наука та техника,2006 – 167с.
  4. Вітлінський В.В. Моделювання економіки: Навч. посібник. –К.: КНЕУ, 2003.-408с.

 

Дополнительная

  1. Вагнер Г. Основы исследования операций. В 3т.- М.:Мир,1983
  2. Кутковецкий В.Я. Дослідження операцій. Навчальний посібник. –К.:2004.-350с.
  3. Наконечний С.І., Савіна С.С. Математичне програмування –К.: 2003.-452с.

 


mylektsii.ru - Мои Лекции - 2015-2019 год. (0.011 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал