Навигация
Применение теории графов
34329
знаков
6
таблиц
25
изображений
2. Применение теории графов
2.1 Практическое применение жадного алгоритма
На территории некого города N размещены заводы и магазины, в которые поставляется продукция с этих заводов. В результате разработки были определены возможные трассы для прокладки коммуникаций и оценена стоимость их создания для каждой трассы. Стоимость прокладки коммуникаций для трассы между заводом №1 и магазином удобрений составляет 15 у.е., между заводом №1 и заводом №3 – 85 у.е., между заводом №1 и хлебозаводом – 20 у.е. Между магазином №1 и заводом №2 составит 25 у.е., между магазином №1 и обувной фабрикой – 65 у.е. Стоимость прокладки коммуникаций для трассы, соединяющей хлебозавод и магазин №2 - 5 у.е., между хлебозаводом и кафе – 50 у.е., между заводом №2 и кафе - 20 у.е., между магазином №2 и продуктовым магазином - 20 у.е., между продуктовым магазином и обувной фабрикой - 25 у.е, между продуктовым магазином и кафе – 35 у.е., между обувной фабрикой и магазином №3 - 15 у.е, между обувной фабрикой и аптекой – 40 у.е., между кафе и аптекой - 10 у.е., между магазином №3 и торговым центром - 20 у.е., между аптекой и заводом №3 составит 30 у.е, между аптекой и торговым центром – 45 у.е., между заводом №3 и торговым центром, - 25 у.е. Необходимо, чтобы коммуникации связали все объекты, затраты на прокладку данных коммуникаций должны быть минимальны.
Для удобства записи вводятся следующие обозначения:
V1 – завод №1, V2 – магазин №1, V3 – хлебозавод, V4 –завод №2, V5 – магазин №2 V6 –продуктовый магазин, V7 – обувная фабрика, V8 –кафе, V9 – магазин №3, V10 – аптека, V11 –завод №3, V12 – торговый центр.
Если создать графическую интерпретацию данной модели, то видно что получился граф с 12 вершинами и 18 ребрами.
Рисунок 1– Графическая интерпретация задачи о оптимальной структуре сети
Из вышесказанного следует, что данную экономическую задачу можно решить с помощью теории графов. Требуется найти дерево покрытия минимального веса. Задача решается с помощью разновидности «жадного» алгоритма, алгоритма Краскала.
Пусть имеется конечное множество Е, |E|=18, весовая функция w: E®R+ и семейство ℇ⊂ 2Е. Требуется найти ХÎЕ, такое что :
Пусть Е – непустое конечное множество, w: E®R+ - функция, ставящая в соответствие каждому элементу е этого множества неотрицательное действительное число w(e) – вес элемента е. Для Х Í Е вес w(Х)определим как сумму весов всех элементов множества Х:
где 
Другими словами, необходимо выбрать в данном семействе непустое подмножество наименьшего веса.
Сопоставим каждому пункту сети вершину графа G. А каждому ребру этого графа сопоставим число, равное стоимости строительства соответствующей коммуникации: (рисунок 1).
Примером жадного алгоритма служит алгоритм Краскала /3/.
Существует теорема, которая утверждает, что алгоритм Краскала всегда приводит к ребру, имеющему минимальный вес.
Согласно алгоритму Краскала, выбирается ребро минимального веса. В данном случае это будет ребро е1 = {3,5}, получаем граф Т1.
Строится граф Т2 = Т1 + е2, где е2 - ребро, имеющее минимальный вес среди ребер, не входящих в Т1 и не составляющий циклов с ребрами Т1, е2 {8,10}.
Т3 = Т2 + е3, где е3 = {7,9}.
Т4 = Т3 + е4, где е4 = {1,2}.
Т5 = Т4 + е5, где е5 = {1,3}.
Т6 = Т5 + е6, где е6 = {5,6}.
Т7 = Т6 + е7, где е7 = {4,8}.
Т8 = Т7 + е8, где е8 = {9,12}
Т9 = Т8 + е9, где е9 = {2,4}.
Т10 = Т9 +е10, где е10 = {6,7}.
Т11 = Т10 + е11, где е11 = {11,12}.
Найдено минимальное дерево покрытия взвешенного графа, следовательно, найдена и оптимальная структура сети, где общая стоимость затраченная на прокладку коммуникаций составит:
и это минимальная сумма затрат из всех возможных. При прокладке коммуникационной сети, соединяющей все данные пункты затрачивается 200 у.е.
Рисунок 2 – Решение задачи о оптимальной структуре сети
Коммуникации проложат между следующими пунктами: аптека – кафе - завод №2 – магазин №1 - завод №1 – хлебозавод – магазин №2 - продуктовый магазин – обувная фабрика – магазин №3 – торговый центр.
Похожие работы
... и др. Они сформировались путем интеграции экспертных и формализованных методов. Схема классификации методов приведена на рис. 1 Рис. 1 - Классификация методов исследования систем управления 2. МЕТОДЫ ФОРМАЛИЗОВАННОГО ПРЕДСТАВЛЕНИЯ СИСТЕМ В ИССЛЕДОВАНИЯХ В настоящее время известны различные классификации методов формализованного представления систем. В результате этого методы, иногда ...
... . Вторая группа - методы формализованного представления систем управления, основанные на использовании математических, экономико-математических методов и моделей исследования систем управления. Среди них можно выделить следующие классы: аналитические (включают методы классической математики - интегральное исчисление, дифференциальное исчисление, методы поиска экстремумов функций, вариационное ...
... на одном этапе исследования, а иные – на другом. ЗАКЛЮЧЕНИЕ В процессе написания курсовой работы мною была изучена такая тема: «Аудит как метод исследования». Выяснила, что аудит входит в комплексно-комбинированные методы исследования систем управления, это указано на рис. 1, см. приложение 1. Комплексно-комбинированные методы исследования систем управления базируются на использовании ...
... . Это обстоятельство учитывается не только на этапе построения модели, но и на завершающей стадии, когда происходит объединение и обобщение результатов исследования, получаемых на основе многообразных средств познания. Моделирование - циклический процесс. Это означает, что за первым четырехэтапным циклом может последовать второй, третий и т.д. При этом знания об исследуемом объекте расширяются и ...
0 комментариев