9. Теория графов и оптимизация
Один из разделов дискретной математики, часто используемый при принятии решений — теория графов (см., например, учебное пособие [8]). Граф — это совокупность точек, называемых вершинами графа, некоторые из которых соединены дугами. Примеры графов приведены на рис.5.
Рис.5. Примеры графов.
На только что введенное понятие графа «навешиваются» новые свойства. Исходному объекту приписывают новые качества. Например, вводится и используется понятие ориентированного графа. В таком графе дуги имеют стрелки, направленные от одной вершины к другой. Примеры ориентированных графов даны на рис.6.
Рис.6. Примеры ориентированных графов.
Ориентированный граф был бы полезен, например, для иллюстрации организации перевозок в транспортной задаче. В экономике дугам ориентированного или обычного графа часто приписывают числа, например, стоимость проезда или перевозки груза из пункта А (начальная вершина дуги) в пункт Б (конечная вершина дуги).
Примеры задач, решаемых с помощью графов
Рассмотрим несколько типичных задач принятия решений, связанных с оптимизацией на графах.
Задача коммивояжера. Требуется посетить все вершины графа и вернуться в исходную вершину, минимизировав затраты на проезд (или минимизировав время).
Исходные данные здесь — это граф, дугам которого приписаны положительные числа — затраты на проезд или время, необходимое для продвижения из одной вершины в другую. В общем случае граф является ориентированным, и каждые две вершины соединяют две дуги — туда и обратно. Действительно, если пункт А расположен на горе, а пункт Б — в низине, то время на проезд из А в Б, очевидно, меньше времени на обратный проезд из Б в А.
Многие постановки экономического содержания сводятся к задаче коммивояжера. Например:
составить наиболее выгодный маршрут обхода наладчика в цехе (контролера, охранника, милиционера), отвечающего за должное функционирование заданного множества объектов (каждый из этих объектов моделируется вершиной графа);
составить наиболее выгодный маршрут доставки деталей рабочим или хлеба с хлебозавода по заданному числу булочных и других торговых точек (парковка у хлебозавода).
Задача о кратчайшем пути. Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число — время движения по этой дуге от начальной вершины до конечной. Рассмотрим пример (рис.7).
Рис.7. Исходные данные к задаче о кратчайшем пути.
Ситуацию можно описать не только ориентированным графом с весами, приписанными дугам, но и таблицей (табл.8).
Табл.8. Исходные данные к задаче о кратчайшем пути.
Спрашивается в задаче: как кратчайшим путем попасть из вершины 1 в вершину 4?
Решение. Введем обозначение: С(Т) — длина кратчайшего пути из вершины 1 в вершину Т. (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С(4) и указании пути, на котором этот минимум достигается.
Графический метод решения задачи линейного программирования (ЗЛП)
Для исходных данных, представленных на рис.7 и в табл.6, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому С(3) = 1. Кроме того, очевидно, что С(1) = 0.
В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение
Таким образом, проведена реструктуризация задачи — нахождение С(4) сведено к нахождению С(2) и С(5).
В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение
Мы знаем, что С(3) = 1. Поэтому
Поскольку очевидно, что С(6) — положительное число, то из последнего соотношения вытекает, что С(5) = 3.
В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение
Нам известно, что С(1) = 0, С(3) = 1, С(5) = 3. Поэтому
Теперь мы можем найти С(4):
Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков:
Задача о кратчайшем пути для конкретных исходных данных (рис.7 и табл.6) полностью решена.
Оптимизационные задачи на графах, возникающие при подготовке управленческих решений в производственном менеджменте, весьма многообразны. Рассмотрим в качестве примера еще одну задачу, связанную с перевозками.
Задача о максимальном потоке. Как (т.е. по каким маршрутам) послать максимально возможное количество грузов из начального пункта в конечный пункт, если пропускная способность путей между пунктами ограничена?
Для решения этой задачи каждой дуге ориентированного графа, соответствующего транспортной системе, должно быть сопоставлено число — пропускная способность этой дуги. Рассмотрим пример (рис.8).
Рис.8. Исходные данные к задаче о максимальном потоке
Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис.8, можно также задать таблицей (табл.9).
Табл.9. Исходные данные к задаче о максимальном потоке
Решение задачи о максимальном потоке может быть получено из следующих соображений.
Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3.
Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу — в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 3. Их направляем в пункт 4.
Итак, максимальная пропускная способность рассматриваемой транспортной системы — 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 — по ней направлены 2 единицы груза при пропускной способности в 3 единицы.
Решение можно представить в виде таблицы (табл.10)
Табл.10. Решение задачи о максимальном потоке
Задача линейного программирования при максимизации потока. Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть ХKM — объем перевозок из пункта К в пункт М. Согласно рис.8 К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных ХKM , а именно, Х01 , Х02 , Х03 , Х12 , Х13 , Х14 , Х23 , Х24 , Х34 . Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:
ХКМ ≥ 0 , К, М = 0, 1, 2, 3, 4
Здесь F — целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1) — (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не «рождаются» в ней. Условие (4) — это условие «выхода» грузов из системы.
Вместе с условием (0) оно составляет балансовое соотношение для системы в целом («вход» равен «выходу»). Следующие девять неравенств задают ограничения на пропускную способность отдельных «веток» транспортной системы. Затем указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию — через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом «не знает»).
О многообразии оптимизационных задач. В различных проблемах принятия решений возникают самые разнообразные задачи оптимизации. Для их решения применяются те или иные методы, точные или приближенные. Задачи оптимизации часто используются в теоретико-экономических исследованиях. Достаточно вспомнить оптимизацию экономического роста страны с помощью матрицы межотраслевого баланса Василия Леонтьева или микроэкономические задачи определения оптимального объема выпуска по функции издержек при фиксированной цене (или в условиях монополии) или минимизации издержек при заданном объеме выпуска путем выбора оптимального соотношения факторов производства (с учетом платы за них).
Кроме затронутых выше методов решения задач оптимизации, напомним о том, что гладкие функции оптимизируют, приравнивая 0 производную (для функций нескольких переменных — частные производные). При наличии ограничений используют множители Лагранжа. Эти методы обычно излагаются в курсах высшей математики и потому опущены здесь.
Источник: www.aup.ru
ГЛАВА 4. ЗАДАЧИ ПО ТЕОРИИ ГРАФОВ
Задача 1.На строительном участке нужно создать телефонную сеть, соединяющую все бытовки. Для того, чтобы телефонные линии не мешали строительству, их решили проводить вдоль дорог. Схема участка изображена на рис.6, где бытовкам соответствуют вершины графа и указаны длины дорог между ними.
Каким образом провести телефонные линии, чтобы их общая длина была минимальной?
Решение.Подграф графа G, содержащий все вершины графа, называется остовным. Если остовный подграф является деревом, то он называется остовным деревом. Очевидно, что наша задача заключается в построении остовного дерева, имеющего минимальную суммарную длину рёбер (минимального остовного дерева).
Длину ребра графа G будем обозначать l(e),а суммарную длину рёбер дерева T – L(T).
Рассмотрим следующий алгоритм построения остовного дерева.
На первом шаге выберем ребро минимальной длины. На каждом последующем шаге будем выбирать из оставшихся ребро минимальной длины, не образующее цикла с ранее выбранными рёбрами. Процесс оканчивается после построения остовного дерева.
Этот алгоритм носит название алгоритма Краскала. Докажем, что он действительно строит минимальное остовное дерево. Доказательство проведём от противного.
Пусть T – дерево, построенное с помощью алгоритма Краскала, а S- минимальное остовное дерево, и L(S)1, e2, …, ei, … . Пусть ei = (a, b) – ребро с наименьшим номером в списке, не принадлежащее дереву S. В дереве S между вершинами a и b существует единственная цепь. Добавив ребро e1 к этой цепи, получим цикл C в новом графе S1. Поскольку T – дерево, то какое – то ребро ep цикла C не должно принадлежать T ((рис.7) дерево T изображено сплошной линией, а дерево S – пунктирной).
рис.7.
Сравним длины ребер еi и еp. Ребро еi принадлежит дереву S, следовательно оно не образует циклов с ребрами е1, е2,…,ei-1, также принадлежащими дереву S. Поэтому, если бы его длина была бы меньше, чем длина ребра еp, то на і-м шаге алгоритма было бы выбрано не ребро еi, а ребро еp . Следовательно, l (еi,)≤l (еp).В графе S1 удалим ребро еp.
Этим самым мы разрушаем единственный цикл графа S1 и получаем дерево S2. Деревья S и S2 отличаются друг от друга только ребрами еi и ep. Из соотношения длин этих ребер следует что L (S2) ≤ L(S ). Но дерево S было минимальным остовным деревом, поэтому L(S2) = L(S) и S2 — также минимальное остовное дерево.
Мы получили противоречие с выбором дерева S, так как дерево S2 имеет больше общих ребер с деревом T, чем дерево S. Доказано, что алгоритм Краскала в самом деле строит минимальное дерево. Теперь с помощью алгоритма построим минимальное дерево для нашего графа. На первом шаге выбираем одно из ребер (1,4) или (3,6), на втором шаге — оставшееся из них.
Третьим выбирается ребро (2,3), четвертым — (2,5). Теперь ребром минимальной длины из оставшихся является ребро (2,6), но оно образует цикл с ранее выбранными ребрами и поэтому не попадает в дерево. Затем в минимальное дерево выбираются ребра (1,2) и (5,7). На рисунке ребра минимального дерева выделены. Вдоль дорог, соответствующим выделенным ребрам, нужно проводить телефонные линии.
Задача 2.Почтальон должен разнести почту по всем улицам своего участка. На схеме указаны расстояния между перекрёстками. Буквой П обозначается почта (рис.8). Найдите кратчайший маршрут почтальона.
Решение.Если бы граф G был бы эйлеровым, то маршрут почтальона определялся бы эйлеровым циклом. Но степени вершин 1 и 6 не чётные, поэтому эйлерова цикла не существует и некоторые улицы почтальон должен будет пройти дважды. Допустим, что мы нашли маршрут обхода.
Если улица проходится почтальоном дважды, то добавим соответствующее ребро к графу G. Таким образом мы получим элеров мультиграф. Следовательно, для решения задачи мы должны удвоить некоторые рёбра так, чтобы степени всех вершин стали чётными. При этом сумма длин добавленных рёбер должна быть наименьшей. В нашем графе степени вершин 1 и 6 должны стать чётными.
Но при удвоении некоторого ребра, выходящего из вершины 1, например рёбра (1, 2), степень вершины 2 станет нечётной и придётся удваивать какое – то ребро, выходящее из вершины 2 и т.д. процесс удваивания рёбер может окончиться только в вершине 6. Следовательно, мы должны найти кратчайшую цепь, соединяющую вершины 1 и 6, и удвоить рёбра это цепи. Такой цепью является цепь L = (1, 2, 4, 6). В полученном мультиграфе найдём эйлеров цикл, который и определит маршрут почтальона(рис.9).
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.
Источник: cyberpedia.su
Задачи оптимизации на графах задача размещения задача почтальона задача строительство дорог
В практической деятельности постоянно возникают задачи «наилучшего» размещения оборудования (или средств обслуживания) в сетях или графах. В частности, если граф представляет сеть дорог и вершины соответствуют отдельным районам, то можно поставить задачу оптимального размещения больниц, полицейских участков, пожарных частей и многих других крайне необходимых предприятий и служб.
В таких случаях критерий оптимальности может состоять в минимизации расстояния (или времени проезда) от пункта обслуживания до самой отдаленной вершины графа, т. е. в оптимизации «наихудшего варианта». В более общей задаче требуется разместить несколько таких пунктов обслуживания (а не только один).
При этом самая отдаленная вершина графа должна находиться по крайней мере от одного пункта обслуживания на минимально возможном расстоянии. К таким задачам относятся задачи размещения аварийных служб, и поэтому объективным требованием здесь является минимизация наибольшего расстояния от произвольной вершины графа до ближайшего к ней пункта обслуживания. По очевидным причинам задачи такого типа называются минимаксными задачами размещения. Полученные при решении этих задач места размещения пунктов обслуживания называются центрами графа.
В некоторых задачах размещения лучше всего было бы минимизировать сумму всех расстояний от вершин графа до центра обслуживания (если предполагать, что ищется место для размещения только одного такого пункта обслуживания). Такой критерий является наиболее подходящим, например, в задаче о размещении склада в сети дорог, где вершины представляют потребителей, обслуживаемых этим складом, или в задаче размещения телефонных станций в телефонной сети, где вершины представляют абонентов. Задачи такого типа вообще относятся к минисуммным задачам размещения, хотя целевая функция является часто не просто суммой расстояний, а суммой различных функций от расстояний (см. гл. 6). Места размещения пунктов обслуживания, полученные в результате решения минисуммной задачи, называются медианами графа.
Целью этой главы является рассмотрение минимаксной задачи размещения для взвешенных графов с весами соответствующими дугам (и представляющими длины) и другими весами связанными с вершинами (и представляющими, скажем, размеры или важность объектов). Приводятся алгоритмы определения оптимального размещения центров в таких графах и результаты вычислений для графов средних размеров.
Минисуммная задача размещения рассматривается отдельно в следующей главе. Хотя эти две задачи, очевидно, связаны между собой, но, поскольку методы их решения различны, гл. 5 и 6 можно читать независимо друг от друга.
Источник: scask.ru
Оптимизационные задачи на графах
Развитие теории графов связано с большим числом всевозможных приложений, графы занимают одно из первых мест в качестве формальных моделей реальных систем во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т.п. Наибольшей популярностью теоретико-графовые модели пользуются при исследовании коммуникационных сетей, систем управления, химических и генетических структур, электрических цепей, проектировании сложных систем связи, в исследованиях транспортных и информационных потоков, путей материального снабжения, финансовых операций.
Типовые задачи теории графов и их приложения:
— задача о кратчайшей цепи:замена оборудования; составление расписания движения транспортных средств; размещение пунктов скорой помощи; размещение ретрансляционных и телефонных станций;
— задача о максимальном потоке:анализ пропускной способности коммуникационной сети; организация движения в динамической сети; оптимальное назначение интенсивностей выполнения работ; синтез двухполюсной сети с заданной структурной надежностью; задача о распределении работ;
— задача об упаковках и покрытиях:оптимизация структуры ПЗУ; размещение диспетчерских пунктов городской транспортной сети;
— раскраска в графах:распределение памяти в ЭВМ; проектирование сетей теле- и радиовещания;
— связность графов и сетей:проектирование кратчайшей коммуникационной сети; синтез структурно-надежной сети циркуляционной связи; анализ надежности стохастических сетей связи;
— изоморфизм графов и сетей:структурный синтез линейных избирательных цепей; автоматизация контроля при проектировании БИС;
— изоморфное вхождение и пересечение графов:локализация неисправности с помощью алгоритмов поиска;покрытие схемы заданным набором типовых подсхем;
— автоморфизм графов:конструктивное перечисление структурных изомеров для производных органических соединений; синтез тестов цифровых устройств.
Сеть состоит из множества вершин (узлов) и множества ребер (дуг), соединяющих вершины. Примерами узлов сети могут быть пересечения автострад, электростанции, телефонные узлы, аэропорты, определенные временные события и т.д. Вообще узлом может быть точка, являющаяся источником или стоком любого проекта, через которую протекает поток информации, материалов, а также любая точка, в которой величина этого потока изменяется. Поэтому узел можно рассматривать как точку ветвления в сети.
Примерами ребер могут быть дороги, линии электропередач, телефонные линии, водные магистрали или обобщенные магистрали, по которым протекает некоторый поток. Иногда дуги не имеют физического смысла и необходимы лишь для определения нужной логической последовательности событий. Узлам обычно приписывают номера или имена, чтобы различать их в процессе анализа сети.
Сетью Тназывают пару объектов (G, c), где G=(V, E) — произвольный ориентированный граф (или неориентированный граф), а c — функция, которая каждой дуге (u,v) ставит в соответствие неотрицательное вещественное число c(u,v), называемое пропускной способностью этой дуги (вес дуги).
Источником называют некоторую вершину сети, из которой достижимы все остальные вершины. В более широкой трактовке источником называют вершину сети, которая является начальной для некоторой задачи, например, начальной вершиной при поиске кратчайшего пути или при поиске максимального потока. Стоком называют некоторую вершину, которая достижима из всех остальных вершин. В более широкой трактовке стоком называют вершину, которая является конечной для некоторой задачи, например, конечной вершиной при поиске кратчайшего пути или при поиске максимального потока. Потоком из s в t (где s — источник, t — сток, s не равно t) в сети S называют произвольную функцию f: E→R, для которой выполняются условия: 0 f(u,v) c(u,v) для каждой дуги (u,v) из E и Div(v)=0 для каждой вершины v из V. Величину Div(s) для потока f называют величиной потока f.
Согласно приведенному поток не возникает и не накапливается ни в одной из вершин, отличных от s и t, тогда поток может применим для формализации поведения газа или жидкости в трубопроводе, потоков автомобилей в сети автострад, перевозок товаров по железной дороге (без хранения их на промежуточных станциях), передачи информации в информационной сети и т.д.
Источник: studopedia.ru
Решение задач с помощью графа
Мне нравится Проект нравится 23 участникам
1736 год, г.Кёнигсберг. Через город протекает река Прегеля. В городе — семь мостов, расположенных так, как показано на рисунке выше. С давних времен жители Кенигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому только один раз? Эту задачу решали и теоретически, на бумаге, и на практике, на прогулках — проходя по этим самым мостам.
Никому не удавалось доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку по мостам никто не мог.
Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. Причем, он решил не только эту конкретную задачу, но придумал общий метод решения подобных задач. При решении задачи о Кенигсбергских мостах Эйлер поступил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в линии. Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют ГРАФОМ.
Граф – это совокупность непустого множества вершин и связей между вершинами. Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами.
Виды графов:
1. Ориентированный граф (кратко орграф) — рёбрам которого присвоено направление.
2. Неориентированный граф — это граф, в котором нет направления линий.
3. Взвешенный граф – дуги или ребра имеют вес (дополнительная информация).
Решение задач с помощью графов:
Задача 1.
Решение: Обозначим ученых вершинами графа и проведем от каждой вершины линии к четырем другим вершинам. Получаем 10 линий, которые и будут считаться рукопожатиями.
Задача 2.
На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.
Вершины графа — это деревья, обозначенный первой буквой названия дерева. В данной задача два отношения: “быть ниже” и “быть выше”. Рассмотрим отношение “быть ниже” и проведем стрелки от более низкого дерева к более высокому. Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине и т.д. Получаем граф, на котором видно, что самое низкое дерево – клен, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь.
Задача 3.
У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?
Источник: globallab.org