Рассмотрим пример решения транспортной задачи.




Графовая модель

Графовая модель (или граф) - это множество вершин графа (элементов) и множество ребер графа, т.е. соответствий, отношений между этими элементами.

 

Графовую модель удобно представлять в виде геометрической схемы. Кибернетические модели в виде графов получили широкое распространение в задачах управления благодаря геометрической трактовке процессов управления.

Началом теории графов считается 1736 год, когда вышла в свет статья Эйлера с его знаменитыми рассуждениями о Кенигсбергских мостах. Затем около 100 лет эта статья оставалась единственной, а методы теории графов невостребованными практикой. Интерес к графам появился только в середине 19 века благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. С тех пор сфера применений теории графов непрерывно расширялась и сегодня она представляет собой мощную формальную систему, имеющую необозримое множество областей практического применения.

 

(Задача Эйлера: в Кенигсберге течет река Неман. Она омывает два острова. Между берегами реки и островами во времена проживания в Кенигсберге Эйлера существовали 7 мостов, расположение которых показывает рисунок 1. Задача Эйлера состояла в том, чтобы определить, можно ли выйдя из пункта С (или любого другого пункта) пройти каждый мост только по одному разу и вернуться в исходный пункт. Рассуждения и действия Эйлера в ходе решения этой задачи можно представить последовательностью следующих шагов: 1) он нарисовал план, 2) нарисовал неориентированный граф, ассоциированный с берегами, островами и мостами, 3) абстрагировал ассоциированный с данными граф от его содержания (см. рис. 1); это решающий шаг рассуждений Эйлера, поскольку абстрактный граф можно ассоциировать с чем угодно, например с площадями и улицами между ними, 4) граф должен быть связным и каждая его вершина должна быть инцидентна чётному числу рёбер.)

Рис.1 – Задача Эйлера

 

 

В отличии от произвольно нарисованной схемы графовая модель строится по определенным правилам. При изображении графов чаще всего используется следующая система обозначений: каждой вершине сопоставляется точка на плоскости, и если между вершинами существует ребро, то соответствующие точки соединяются отрезком. В случае ориентированного графа отрезки заменяют стрелками. Не следует путать изображение графа с собственно графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет. В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.

 

Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.

 

Среди дискретных математических моделей графовые модели занимают заметное место. Абстрактный математический объект – граф, при использовании его в качестве средства математического моделирования, подвергся серьезной модернизации. В качестве инструмента математического моделирования используются, как правило, ориентированные взвешенные графы. В различных задачах веса заданные на рёбрах и вершинах могут иметь различное истолкование: стоимость, длина, вес, время прохождения сигнала, вероятность перехода, и т.д.

 

Графовые математические модели стали эффективным средством формализации задач из самых различных областей: экономики, физики, химии, планово-производственной практики, управления производством, сетевого и календарного планирования, информационных систем, и многих других. Эффективные алгоритмы, разработанные для решения задач о кратчайших путях, максимальных потоках в сетях, задач о случайных блужданиях стали мощным инструментом решения различных задач маршрутизации, анализа и расчета электрических сетей. Все более активно графовые математические модели применяются для анализа и синтеза коммуникационных сетей и навигации в них. Маршрутизация в Интернете осуществляется с помощью эффективного графового алгоритма нахождения кратчайшего пути между заданными узлами этой глобальной сети. Широкая применимость графовых методов и математических моделей, основанных на использовании ориентированных взвешенных графов привела к формированию класса алгоритмов, который сегодня имеет свое собственное название «Алгоритмы на графах».

 

Области применения графовых моделей:

 

  • В химии (для описания структур, путей сложных реакций); компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений.
  • В информатике и программировании (граф-схема алгоритма)
  • В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.
  • В экономике
  • В логистике
  • В схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф)

 

Конкретные примеры применения:

 

  • Блок-схема
  • Карта улиц города
  • Схема метро
  • Родословная (фамильное дерево)
  • Топология компьютерной сети
  • PERT-диаграмма (план работы над проектом)

Рассмотрим пример решения транспортной задачи.

Пусть имеются 5 пунктов, соединенных между собой дорогами так, что из любого пункта можно проехать в любой другой пункт (рис.2).Известно время перевозки из пункта i в пункт j (табл.1). Требуется найти такой маршрут, начинающийся в данном пункте, проходящий через все пункты и заканчивающийся в пункте выезда, чтобы его продолжительность была наименьшей.

Таблица 1.

Рисунок 2.

Решение. Для решения этой задачи необходимо составить математическую модель. введем обозначения: i и j – номера пунктов выезда и въезда; tij – время переезда из пункта i в пункт j из таблицы 1 видно, что tij в общем случае может бы не равно времени переезда в обратном направлении tij <> tji (например, когда один пункт на вершине горы, а другой – у ее подножия). Введем булевы переменные:

Составим модель (Рис.7). Из пункта 1 можно выехать в любой из пункта 2 или 5, или 3, или 4, или остаться в пункте 1. но при этом можно выехать только в одном единственном направлении. Это условие можно записать так:

или для производительного i-го пункта

Эти зависимости обеспечивают выполнение условия, что из каждого пункта выезда производится только один раз и только в одном направлении.

Условие въезда в пункт 1 аналогично условию въезда из пункта 1 (Рис.7). Требование минимальной продолжительности маршрута запишется в виде целевой функции:

где tij берутся из исходной таблица, а ij - искомые переменные.

 

Тогда всю задачу можно сформулировать:

В результате решения системы (*) получим (Рис.8) следующие значения

переходя от частной к общей постановке, задачу коммивояжера можно сформулировать как:

 

Список литературы:

1. Электронный ресурс: https://pvti.ru/lect1-lecture6.htm

2. Электронный ресурс: https://ru.wikipedia.org/

3. Электронный ресурс: https://www.coolreferat.com

4. Электронный ресурс: https://lmatrix.ru/news/theory/teoriya-grafov-obshhie-svedeniya_35.html



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2021-04-20 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: