Алгоритмы оптимизации на сетях и графах

Abstract

Книга Э. Майники - профессора Иллинойского университета (США) - посвящена дискретному программированию, которое широко попользуется для решения проблем оптимизации, возникающих при проектировании экономических систем. Рассматриваются задачи почтальона, коммивояжера, управления проектами и размещений. Приводится количественная оценка времени сходимости описываемых алгоритмов, которые могут быть сравнительно легко запрограммированы и практически реализованы с помощью ЭВМ. Предисловие редактора перевода: Сетевые и графовые модели охватывают довольно широкий класс задач, встречающихся при проектировании систем, планировании работ, распределении продукции, организации транспортных перевозок, размещении различных центров обслуживания населения и т. п. Во многих практически интересных случаях эти задачи характеризуются линейной целевой функцией и линейными ограничениями, так что для их решения, вообще говоря, могли бы успешно применяться известные методы линейного программирования. Однако характерной особенностью таких задач (если только они правильно отображают реальную ситуацию) является большая размерность, обусловливающая необходимость поиска более эффективных алгоритмов оптимизации, которые позволяли бы экономить вычислительные ресурсы конкретных систем и обеспечивать их гибкость по отношению к изменениям исходных данных. Плодотворной основой для построения таких алгоритмов могут служить их представления на сетях и графах. С этой точки зрения предлагаемая вниманию советского читателя книга Майники интересна прежде всего тем, что содержит инженерное изложение основных вопросов теории графов. При этом уровень формализации задач выбран таким, чтобы книга была доступна специалистам с самой различной математической подготовкой: для ее чтения не требуется обращаться к каким-либо фундаментальным работам по теории графов, так как все основные понятия и определения вводятся по ходу изложения. Называя это изложение'интуитивным', автор подчеркивает прикладной характер книги, заключающийся в постепенном продвижении от физического смысла задачи к алгоритмическим построениям. Математики-теоретики, вероятно, не найдут для себя в книге ничего нового, а при желании даже обнаружат в ряде мест недостаточную строгость доказательств, отличную от принятой терминологию, отсутствие теорем существования и т. п. Однако и для. них книга будет весьма полезна, поскольку в ней по существу впервые дано систематическое рассмотрение актуальных задач на ориентированных графах, сочетающее в себе несомненные достоинства теоретической монографии Ф. Харрари'Теория графов', Мир, 1973) и блестящей прикладной работы Л. Форда и Д. Фалкерсона'Потоки в сетях? (М.: Мир, 1966).