ВУЗ:
Составители:
Рубрика:
9
требуемого числа операций ограничена полиномом третьей степени, при
этом решение – точное.
Без существенных изменений эстафетный метод может быть
применен и для поиска наиболее длинного (критического) маршрута, что
представляет интерес при сетевом планировании.
В разделе 3 предложен
метод расширения цикла, позволяющий
получить решение известной (классической) задачи коммивояжера,
получены оценки точности и объёма вычислений. Модификация метода
расширения цикла в сочетании с эстафетным методом позволили найти
эффективное решение задачи коммивояжера для случая
неполной матрицы
расстояний, описывающей граф дорожной сети. Приводимые оценки
подтверждают эффективность модифицированного метода расширения
цикла.
При обсуждении материала было высказано важное для практики
требование: коммивояжер обязан в каждый из посещаемых пунктов
доставить определённый груз. Такое обобщение классической задачи
коммивояжера потребовало выполнения раздела 4, где поставлена и
решена
обобщенная задача коммивояжера, в которой минимизируется
не длина цикла, а требуемые при этом
энергозатраты. Классическая
задача коммивояжера рассматривается как частный случай обобщенной
задачи, в которой вес перевозимых грузов равен нулю.
В разделе 5 рассмотрен иной подход к решению задач коммивояжера.
В его основе лежит
последовательное наращивание цикла путём
последовательного выбора и подключения участков кратчайших
маршрутов с последующим замыканием цикла.
Раздел 6 посвящен новому решению задачи о
пропускной
способности сети
.
Раздел 7 содержит некоторые теоретические обобщения и метод
определения
особых точек на графе, удовлетворяющих заданным
требованиям, возникающим при решении ряда практических задач.
В заключении обобщены основные результаты, полученные в работе,
и даны возможные направления дальнейших исследований в указанной
области.
Страницы
- « первая
- ‹ предыдущая
- …
- 5
- 6
- 7
- 8
- 9
- …
- следующая ›
- последняя »
