ВУЗ:
Составители:
Рубрика:
5
УДК 519.8
ББК
Берзин Е.А. Элементарные решения неэлементарных задач на графах /
Под ред. А.Н. Кудинова. Тверь: ТГТУ, 2005. 136 с.
Представленные в пособии методы и алгоритмы позволяют
эффективно решать ряд оптимизационных задач на графах, имеющих
прикладную направленность в экономике и технике. К таким задачам
относятся: задача о кратчайшем пути; задача коммивояжера и ее
обобщение; задача о пропускных способностях сетей; об оптимальном
размещении баз, обслуживающих пунктов.
Базовым методом, положенным в основу остальных методов, является
эстафетный метод построения кратчайшего маршрута на графе. Он дает
точное решение и требует минимального объема вычислений (полином 2-й
степени). Метод расширения цикла обеспечивает эффективное решение
классической задачи коммивояжера с заданной точностью. Модификация
метода позволяет решить задачу коммивояжера и при неполной (φ < 1)
матрице смежности.
Обобщенная задача коммивояжера, как частный случай, включает в
себя классическую задачу. Методы поиска экстремальных точек на графе
также связаны с решением ряда задач, имеющих важное практическое
значение (размещение рембаз, автозаправочных станций, пожарных депо и
т.д.).
Разработанные методы и алгоритмы являются новыми и позволяют
решать задачи больших размеров. Для их использования не требуется
специальной математической подготовки, что делает их удобными для
студентов при освоении специальных дисциплин в технических вузах,
а также для научных работников при решении сложных
оптимизационных задач на графах элементарными методами.
Предназначено для использования в учебном процессе по ряду
учебных дисциплин кафедр «Информационные системы»,
«Автомобильный транспорт» и «Электроснабжение и электротехника».
Рецензенты: заведующий кафедрой математического моделирования,
Заслуженный деятель науки РФ, доктор физико-математических наук,
профессор А.Н. Кудинов; заведующий кафедрой вычислительной техники
и математического моделирования агросистем, доктор технических наук,
профессор В.Р. Гриднев.
ISBN 5-7995-0293-0
© Тверской государственный
технический университет, 2005
