Представленные в пособии методы и алгоритмы позволяют
эффективно решать ряд оптимизационных задач на графах, имеющих
прикладную направленность в экономике и технике. К таким задачам
относятся: задача о кратчайшем пути; задача коммивояжера и ее
обобщение; задача о пропускных способностях сетей; об оптимальном
размещении баз, обслуживающих пунктов.
Базовым методом, положенным в основу остальных методов, является
эстафетный метод построения кратчайшего маршрута на графе. Он дает
точное решение и требует минимального объема вычислений (полином 2-й
степени). Метод расширения цикла обеспечивает эффективное решение
классической задачи коммивояжера с заданной точностью. Модификация
метода позволяет решить задачу коммивояжера и при неполной (ф < 1)
матрице смежности.
Обобщенная задача коммивояжера, как частный случай, включает в
себя классическую задачу. Методы поиска экстремальных точек на графе
также связаны с решением ряда задач, имеющих важное практическое
значение (размещение рембаз, автозаправочных станций, пожарных депо и
т.д.).
Разработанные методы и алгоритмы являются новыми и позволяют
решать задачи больших размеров. Для их использования не требуется
специальной математической подготовки, что делает их удобными для
студентов при освоении специальных дисциплин в технических вузах,
а также для научных работников при решении сложных
оптимизационных задач на графах элементарными методами.
Предназначено для использования в учебном процессе по ряду
учебных дисциплин кафедр «Информационные системы»,
«Автомобильный транспорт» и «Электроснабжение и электротехника».
Рецензенты: заведующий кафедрой математического моделирования,
Заслуженный деятель науки РФ, доктор физико-математических наук,
профессор А.Н. Кудинов; заведующий кафедрой вычислительной техники
и математического моделирования агросистем, доктор технических наук,
профессор В.Р. Гриднев.
Author(s): Берзин Е.А.
Publisher: ТГТУ
Year: 2005
Language: Russian
Pages: 243
City: Тверь
Tags: Математика;Дискретная математика;Теория графов;
Элементарные решения неэлементарных задач на графах. Учебное пособие. Берзин Е.А. Под ред. А.Н. Кудинова. Тверь: ТГТУ, 2005 г. 136 с. ISBN 5-7995-0293-0......Page 1
Оглавление......Page 138
Предисловие......Page 6
Принятые обозначения......Page 7
Введение......Page 8
1.1. Основные понятия и определения......Page 10
2.1. Постановка задачи......Page 13
2.2. Эстафетный метод построения кратчайшего пути на графе......Page 14
2.3. Алгоритм эстафетного метода (эм)......Page 21
2.4. Оценка эффективности алгоритма......Page 25
Выводы......Page 27
3.1. Постановка классической задачи коммивояжера (φ=1)......Page 28
3.2. Метод расширения цикла, алгоритм, пример вычисления и эффективность алгоритма......Page 30
3.3. Модифицированный метод расширения цикла, примеры вычислений и эффективность метода......Page 38
Выводы......Page 45
4.1. Постановка обобщенной задачи коммивояжера......Page 47
4.2. Алгоритм решения обобщенной задачи коммивояжера методом расширения цикла при полной матрице расстояний (φ=1) и пример расчета......Page 48
4.3. Модифицированный метод расширения цикла и решение обобщенной задачи коммивояжера......Page 55
4.4. Решение обобщенной задачи коммивояжера методом последовательного наращивания цикла......Page 61
Выводы......Page 74
5.1. Решение тестового примера задачи коммивояжера методом расширения цикла......Page 75
5.2. Решение тестового примера задачи коммивояжера модифицированным методом расширения цикла......Page 79
5.4. Решение тестового примера задачи коммивояжера методом последовательного наращивания цикла......Page 82
5.5. Решение тестового примера обобщенной задачи коммивояжера методом последовательного наращивания цикла......Page 85
5.6. Решение тестового примера обобщенной задачи коммивояжера методом расширения цикла......Page 87
5.7. Решение тестового примера обобщенной задачи коммивояжера модифицированным методом расширения цикла......Page 88
6.1. Построение маршрута с максимальной пропускной способностью методом улучшения оценок......Page 93
6.2. Определение максимальной пропускной способности сети......Page 99
Выводы......Page 107
7.1. Поиск точек с минимальной суммарной длиной маршрутов......Page 108
7.2. Учет грузопотоков и грузоподъемности транспортных средств при размещении баз......Page 116
7.3. Поиск минимаксных точек на графе......Page 120
Заключение......Page 127
Приложение 1. Определение пропускной способности сети методом Форда-Фалкерсона и методом улучшения оценок......Page 130
Приложение 2. Решение задачи коммивояжера размера 10 х 10 модифицированным методом расширения цикла......Page 132
Библиографический список......Page 137
