Русский
!

Conference publications

Abstracts

XV conference

О некоторых аспектах изложения задачи коммивояжера в курсе "Исследование операций"

Аснина А.Я.

E-mail: boris03@mail.ru, Россия, 394026, г. Воронеж, Московский пр., д. 12, кв. 24.

1 pp.

Курс «Исследование операций» занимает одну из ключевых позиций в программе обучения студентов по таким специальностям и направлениям как «Прикладная математика», «Прикладная информатика по областям», «Экономика». Целью данного курса является ознакомление студентов с методами математического моделирования в различных предметных областях, а так же с методами решения полученных задач. Наиболее полно различные аспекты курса рассмотрены в известных монографиях Г. Вагнера «Основы исследования операций» и А. Таха «Введение в исследование операций». Выходящие же в настоящее время многочисленные учебники и учебные пособия освещают, как правило, лишь некоторые его разделы.

Рассматриваемая в докладе «задача коммивояжера» как правило включается в учебные пособия по курсу «Исследование операций» так как обладает следующими достоинствами: во-первых, многие задачи из различных предметных областей моделируются как задачи коммивояжера (задача о переналадках и др.), во-вторых, она является одним из ярких примеров NP-трудных задач дискретной оптимизации.

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

В докладе рассматривается пример задачи коммивояжера, в котором при применении известного эвристического метода «ближайшего города» получается маршрут длиной 101, в то время как существует маршрут длиной 6, который так же не обязательно является оптимальным. Эта задача с шестью городами, где C12=C23=C31=C45=C56=C64=0; C15=C52=C26=C63=C34=C41=1; C16=C24=C35=C42=C53=C61=100. Все остальные значения Cij могут быть любыми целыми положительными числами от 2 до 10. К достоинствам данного примера относится и то, что он легко модифицируется путем замены некоторых коэффициентов в любое количество различных задач, обладающих теми же свойствами, что удобно при составлении заданий для лабораторных работ.

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



© 2004 Designed by Lyceum of Informational Technologies №1533