Алгоритмы оптимизации на сетях и графах, Майника Э., 1981

Алгоритмы оптимизации на сетях и графах, Майника Э., 1981.

   Книга Э. Майники — профессора Иллинойского университета (США) — посвящена дискретному программированию, которое широко попользуется для решения проблем оптимизации, возникающих при проектировании экономических систем. Рассматриваются задачи почтальона, коммивояжера, управления проектами и размещений. Приводится количественная оценка времени сходимости описываемых алгоритмов, которые могут быть сравнительно легко запрограммированы и практически реализованы с помощью ЭВМ.




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

В отличие от других научных дисциплин теория графов имеет вполне определенную дату рождения. Первая работа по теории графов, написанная швейцарским математиком Леонардом Эйлером (1707—1783 гг.), была?опубликована в 1736 г. в Трудах Академии наук в Санкт-Петербурге. Исследование Эйлера было проведено в связи с так называемой задачей о Кенигсбергских мостах. Город Кенигсберг (нынешний Калининград), располагавшийся тогда в Восточной Пруссии, был построен в месте слияния двух рек на их берегах и на двух островах (рис. 1.1). В городе было семь мостов, которые соединяли острова между собой и с береговыми частями города. Мог ли любой житель Кенигсберга, выйдя из дома, пройти по всем семи мостам города в точности по одному разу и вернуться домой? Ответ на этот вопрос должен быть отрицательным. В дальнейшем, когда в гл. 6 будет рассмотрен обобщенный вариант данной задачи, названной задачей почтальона, мы поймем, с чем это связано.

ОГЛАВЛЕНИЕ.
Предисловие редактора перевода.
Предисловие.
Глава 1. Введение в теорию графов и сетей.
1.1. Вводные замечания.
1.2. Некоторые понятия и определения.
1.3. Линейное программирование.
Упражнения.
Литература.
Глава 2. Алгоритмы построения деревьев.
2.1. Алгоритмы построения покрывающих деревьев.
2.2. Алгоритм построения максимального ориентированного леса.
Упражнения.
Литература.
Глава 3. Алгоритмы поиска путей.
3.1. Алгоритм поиска кратчайшего пути.
3.2. Алгоритмы поиска всех кратчайших путей.
3.3. Алгоритм поиска k кратчайших путей.
3.4. Поиск других оптимальных путей.
Упражнения.
Литература.
Глава 4. Потоковые алгоритмы.
4.1. Введение.
4.2. Алгоритм поиска максимального потока.
4.3. Алгоритм поиска потока минимальной стоимости.
4.4. Алгоритм дефекта.
4.5. Алгоритм поиска динамического потока.
4.6. Потоки с усилениями.
Упражнения.
Литература.
Глава 5. Алгоритмы поиска паросочетаний и покрытий.
5.1. Введение.
5.2. Алгоритм решения задачи о паросочетаний максимальной мощности.
5.3 Алгоритм выбора паросочетания с максимальным весом.
5.4. Алгоритм построения покрытия с минимальным весом.
Упражнения.
Литература.
Глава 6. Задача почтальона.
6.1. Введение.
6.2. Задача почтальона для неориентированного графа.
6.3. Задача почтальона для ориентированного графа.
6.4. Задача почтальона для смешанного графа.
Упражнения.
Литература.
Глава 7. Задача коммивояжера.
7.4. Формулировка и некоторые свойства решений задачи коммивояжера.
7.2. Условия существования гамильтонова контура.
7.3. Нижние границы.
7.4. Методы решения задачи коммивояжера.
Упражнения.
Литература.
Глава 8. Задачи размещения.
8.1. Введение.
8.2. Задачи поиска центра.
8.3. Задачи поиска медиан.
8.4. Обобщения.
Упражнения.
Литература.
Глава 9. Сетевые графики.
9.1. Метод критического пути (МКП).
9.2. Определение длительности выполнения  операций из условия обеспечения минимальной стоимости.
9.3. Обобщенные сетевые графики.
Упражнения.
Литература.
Предметный указатель.



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

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


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




Теги: учебник по математике :: математика :: Майника