§ | библиотека – мастерская – | Помощь Контакты | Вход — |
Новиков А.М., Новиков Д.А. Методология. –– М.: СИНТЕГ. – 663 с.
Стр. 238 Теория графов – раздел дискретной математики. Неформальное определение графа таково: графом называется совокупность вершин (изображаемых кружками) и связей между ними, изображаемых ориентированными дугами (со стрелками) или неориентированными ребрами (без стрелок) – см. Рис. 18. Рис. 18. Пример графа Язык графов оказывается удобным для моделирования многих физических, технических, экономических, биологических, социальных и других систем. Приведем ряд примеров приложений теории графов (более подробное описание перечисляемых и других задач можно найти в [26, 29]). · «Транспортные» задачи, в которых вершинами графа являются пункты погрузки/разгрузки, а ребрами – дороги (автомобильные, железные и др.) и/или другие транспортные (например, авиационные) маршруты. Другой пример – сети снабжения (энергоснабжения, газоснабжения, снабжения товарами и т.д.), в которых вершинами являются пункты производства и потребления, а ребрами или дугами – возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.). Соответствующий класс задач оптимизации потоков грузов, размещения пунктов производства и потребления и т.д., иногда называется задачами обеспечения или задачами о размещении. Их подклассом являются задачи о грузоперевозках. · «Технологические задачи», в которых вершины отражают производственные элементы (заводы, цеха, станки и т.д.), а дуги – потоки сырья, материалов и продукции между ними, заключаются в определении оптимальной загрузки производственных элементов и обеспечивающих эту загрузку потоков. · Обменные схемы, являющиеся моделями таких явлений как бартер, взаимозачеты и т.д. Вершины графа при этом описывают участников обменной схемы (цепочки), а дуги – потоки материальных и финансовых ресурсов между ними. Задача заключается в определении цепочки обменов, оптимальной с точки зрения, например, организатора обмена и согласованной с интересами участников цепочки и существующими ограничениями. |
Реклама
|
||