Задача комивояжера

  • 01 апр. 2012 г.
  • 1270 Слова
Министерство образования Российской Федерации
Санкт-Петербургский государственный Университет Сервиса и Экономики

Контрольная работа
По дисциплине: Методы дискретного анализа и регрессионного анализа в экономических задачах.

Выполнила:Студенка г.3514, 3 курса
Заочного отделения
Кочарян Е.М

Проверила:

Санкт-Петербург
2012 г.
Данаматрица Ω расстояний, представленная в таблице:
| А1 | А2 | А 3 | А 4 | А 5 | А 6 |
А 1 | - | 30 | 25 | 17 | 39 | 18 |
А 2 | 31 | - | 26 | 25 | 30 | 42 |
А 3 | 28 | 27 | - | 29 | 18 | 40 |
А 4 | 37 | 16 | 21 | - | 17 | 25 |
А 5 | 19 | 23 | 25 | 31 | - | 19 |
А 6 | 21 | 27 | 32 | 16 | 19 | - |

Решим эту задачу методом ветвей и границ. Данный метод состоит из многократного повторениядвух операций: 1) вычисление нижней границы и 2) ветвление множества.
Вычислим нижнюю границу множества всех маршрутов, которая вычисляется при помощи операции приведения:
Справа к таблице присоединяем столбец, в котором записываем минимальные элементы соответствующих строк. Вычитаем элементы из соответствующих элементов строки матрицы.
  | А1 | А2 | А 3 | А 4 | А 5 | А 6 | min |
А 1 | - | 30| 25 | 17 | 39 | 18 | 17 |
А 2 | 31 | - | 26 | 25 | 30 | 42 | 25 |
А 3 | 28 | 27 | - | 29 | 18 | 40 | 18 |
А 4 | 37 | 16 | 21 | - | 17 | 25 | 16 |
А 5 | 19 | 23 | 25 | 31 | - | 19 | 19 |
А 6 | 21 | 27 | 32 | 16 | 19 | - | 16 |
Получим:
  | А1 | А2 | А 3 | А 4 | А 5 | А 6 |
А 1 | - | 13 | 8 | 0 | 12 | 1 |
А 2 | 6 | - | 1 | 0 | 5 | 17 |
А 3 | 10 | 9 | - | 11 | 0 | 22 |
А 4 | 21| 0 | 5 | - | 1 | 9 |
А 5 | 0 | 4 | 6 | 12 | - | 0 |
А 6 | 5 | 11 | 16 | 0 | 3 | - |

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

  | А1 | А2 | А 3 | А 4 | А 5 | А 6 |
А 1 | - | 13 | 8 | 0 | 12 | 1 |
А 2 | 6 | - | 1 | 0 | 5 | 17 |
А 3 | 10 | 9 | - | 11 | 0 | 22 |
А 4 | 21| 0 | 5 | - | 1 | 9 |
А 5 | 0 | 4 | 6 | 12 | - | 0 |
А 6 | 5 | 11 | 16 | 0 | 3 | - |
min | 0 | 0 | 1 | 0 | 0 | 0 |

В результате вычислений получаем матрицу Ω0, приведенную по строкам и столбцам, которая изображена в виде таблицы
  | А1 | А2 | А 3 | А 4 | А 5 | А 6 |
А 1 | - | 13 | 7 | 0 | 12 | 1 |
А 2 | 6 | - | 0 | 0 | 5 | 17 |
А 3 | 10 | 9 | - | 11 | 0 | 22 |
А 4 | 21 | 0 | 4| - | 1 | 9 |
А 5 | 0 | 4 | 5 | 12 | - | 0 |
А 6 | 5 | 11 | 15 | 0 | 3 | - |

Каждая строка и столбец содержит хотя бы один нулевой элемент. Все те постоянные, которые вычитались в процессе, называются постоянными приведения. Нижняя граница матрицы расстояния Ω представляет собой их сумму:
φ = 1+17+25+18+16+19+16=112
Длина любого маршрута вычисленного по матрице расстояний Ω и поприведенной матрице Ω0 связаны следующим соотношением:
L = L0 + φ*
А1 А3 А5 А2 А4 А6 А1
L = 25+18+23+25+25+21=137
L0 = 7+0+4+0+9+5=25
137 = 112+25
Нижняя граница определена. Переходим к общему шагу, который повторяется многократно. Определим способ ветвления. Ветвлением множества называется разбиение множества на несколько непересекающихся множеств (т.е. не имеющих общих элементов) в суммесоставляющих исходное множество.
Для задачи коммивояжера множество Ω разбивается на 2 непересекающихся подмножества. Подмножество Ω2, которое содержит дугу xixj
Ω2 = Ω2 (xixj)
и подмножества Ω1, которое не содержит эту дугу
Ω1 = Ω1 (xixj)
Дуга выбирается следующим образом: в приведенной матрице Ω0 записываем дуги, которым соответствует 0 элемент и подсчитаем сумму постоянных...
tracking img