koob.ru

Элементарные решения неэлементарных задач на графах

Автор: Кудинов А.Н. | Раздел: Математика

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

Он дает точное решение и требует минимального объема вычислений (полином 2-й степени). Метод расширения цикла обеспечивает эффективное решение классической задачи коммивояжера с заданной точностью. Модификация метода позволяет решить задачу коммивояжера и при неполной (ср < 1) матрице смежности.

Обобщенная задача коммивояжера, как частный случай, включает в себя классическую задачу. Методы поиска экстремальных точек на графе также связаны с решением ряда задач, имеющих важное практическое значение (размещение рембаз, автозаправочных станций, пожарных депо и т.д.). Разработанные методы и алгоритмы являются новыми и позволяют решать задачи больших размеров.

Для их использования не требуется специальной математической подготовки, что делает их удобными для студентов при освоении специальных дисциплин в технических вузах, а также для научных работников при решении сложных оптимизационных задач на графах элементарными методами. Предназначено для использования в учебном процессе по ряду учебных дисциплин кафедр «Информационные системы», «Автомобильный транспорт» и «Электроснабжение и электротехника».

Рецензенты: заведующий кафедрой математического моделирования, Заслуженный деятель науки РФ, доктор физико-математических наук, профессор А.Н. Кудинов; заведующий кафедрой вычислительной техники и математического моделирования агросистем, доктор технических наук, профессор В.Р. Гриднев.

Добавить отзыв о книге
Авторы сайта
Владимир Никонов & Георгий Ефимов
Библиотека «Куб»
Поддержать проектПодписаться