Элементарные решения неэлементарных задач на графах, Кудинов А.Н., Берзин Е.А., 2005

Элементарные решения неэлементарных задач на графах, Кудинов А.Н., Берзин Е.А., 2005.

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

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





ПРЕДИСЛОВИЕ.

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

ОГЛАВЛЕНИЕ.

ПРЕДИСЛОВИЕ.
ПРИНЯТЫЕ ОБОЗНАЧЕНИЯ.
ВВЕДЕНИЕ.
1. НЕКОТОРЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ.
2. ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ НА ГРАФЕ.
3. КЛАССИЧЕСКАЯ ЗАДАЧА КОММИВОЯЖЕРА И ЕЕ РЕШЕНИЕ МЕТОДОМ РАСШИРЕНИЯ ЦИКЛА.
4. ОБОБЩЕННАЯ ЗАДАЧА КОММИВОЯЖЕРА.
5. СРАВНИТЕЛЬНАЯ ОЦЕНКА РАССМОТРЕННЫХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ КОММИВОЯЖЕРА.
6. ПРОПУСКНАЯ СПОСОБНОСТЬ СЕТИ.
7. ПОИСК ОСОБЫХ ТОЧЕК НА ГРАФЕ.
ЗАКЛЮЧЕНИЕ.
Приложение 1. Определение пропускной способности сети методом Форда-Фалкерсона и методом улучшения опенок.
Приложение 2. Решение задачи коммивояжера размера 10 х 10 модифицированным методом расширения цикла.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Элементарные решения неэлементарных задач на графах, Кудинов А.Н., Берзин Е.А., 2005 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать djvu
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - djvu - Яндекс.Диск.




Теги: Кудинов :: Берзин :: 2005 :: решение :: задача :: граф