Читать онлайн «Экстремальные задачи на графах»

Ю. М. ЕРМОЛЬЕВ . М. МЕЛЬН ЭКСТРЕМАЛЬНЫЕ ЗАДАЧ И НА ГРАФАХ 6П2Л5 Ε 74 В книге излагается теория и методы решения задач об оптимальном распределении однородных и неоднородных потоков в сетях. Рассматриваются задачи на построение в графе путей, удовлетворяющих различным ограничениям. Рассчитана на научных работников и лиц> занимающихся вопросами математического программирования и планирования. Отв. редактор канд. физ. - мат. наук В. В. ШКУРБА 2-2-4 62-β8Μ КИЕВСКАЯ КНИЖНАЯ ФАБРИКА № 1 ПРЕДИСЛОВИЕ Понятие графа исключительно наглядно: это — совокупность точек, соединенных линиями. В виде графа можно представить сеть железных дорог, сеть трубопроводов, совокупность работ, образующих сложное задание, информационную систему, структуру управления сложной иерархической системой. На языке теории графов формулируются многие практические задачи. За последние два десятилетия благодаря успехам вычислительной техники существенно расширился круг прикладных задач, решаемых математическими методами. В частности, появилось множество задач, которые с формальной точки зрения можно представить как экстремальные задачи на^графах. Они являются частными задачами математического программирования, и могут быть линейными, нелинейными, выпуклыми, дискретными, частично дискретными. К сожалению, пока невозможно дать другую, более полную классификацию их по тем специфическим особенностям, благодаря которым можно получать простые методы решения. Известными классическими экстремальными задачами на графах являются, например, задача о раскраске вершин графа и задача об определении чисел внешней и внутренней устойчивости. В настоящей книге рассматриваются задачи, которые можно разбить на два класса: задачи, формулируемые в терминах однородных и неоднородных потоков в сетях, и задачи на построение некоторых допустимых путей. Эти задачи важны тем, что к ним сводится большинство вопросов из области планирования, управления и проектирования, практически решенных математическими методами. 3 В гл. I приводятся основные понятия теории графов, которые потребуются в дальнейшем. Вкратце излагается теория однородных потоков, причем приводятся некоторые малоизвестные результаты. В гл. II излагается теория решения линейной сетевой и двойственной к ней задач. В отличие от книги Л. Форда и Д. Фал- керсона [37] здесь дана специфическая теория двойственности, метод потенциалов. В гл. III рассматривается аналогичная задача, но с нелинейным функционалом цели. Гл. IV посвящена теории оптимальных неоднородных потоков и методам их построения. В гл. V рассматриваются задачи на построение в графе путей, удовлетворяющих различным ограничениям, в частности, задача коммивояжера. Изложение иллюстрируется приложениями из различных областей, например обсуждаются вопросы складирования, управления запасами, проектирования объектов, перевозок грузов и размещения предприятий (одноп роду кто вые и многопродуктовые модели), развития сетей, управления дискретными системами, составления расписаний, прогнозирования пассажиропотоков.