Полная версия

Главная arrow Туризм arrow Основы функционирования систем сервиса

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

ОСНОВЫ ТЕОРИИ СЕТЕЙ И ИХ ИСПОЛЬЗОВАНИЕ В ЗАДАЧАХ СЕРВИСА

Основы теории сетей

Сетью называется конечный граф N = (К, R) без циклов и петель, ориентированный в одном общем направлении от вершин х, являющихся входами графа, к вершинам у, являющимся его выходами [36].

Сети используются для моделирования способов пересылки в заданном направлении некоторых объектов из одной вершины графа в другую по его дугам. Как правило, в сети нет кратных дут. Поэтому в сетях чаще употребляют термин «связь» вместо терминов «ребро» или «дуга». Вместо термина «вершина» используют термин «узел». Узел служит для обозначения физического объекта, являющегося начальным или конечным пунктом. В задачах сервиса узел может обозначать предприятие сервиса, клиента, производителя, потребность, средство удовлетворения потребности и др.

В теории сетей используются следующие понятия:

О источник s — узел, из которого начинается перемещение объектов; источник порождает поток, например предприятие сервиса порождает поток потребительских товаров;

О сток t — узел, в котором заканчивается перемещение объектов; сток поглощает поток, например потребитель потребляет товары; все другие узлы называются промежуточными;

О единицы потока — объекты, которые перемещаются или «протекают» из источника в сток. В задачах сервиса в качестве единиц потока могут выступать какие-либо средства удовлетворения потребностей, например товары, комплектующие, информация и др.

Каждый нулевой столбец матрицы смежности соответствует источнику, а каждая нулевая строка — стоку.

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

Обозначим f(x, у) — поток, проходящий по связи (х,у). Очевидно, что 0 у) < с(х, у). Для любого потока число единиц, выходящих из любого промежуточного узла х, должно быть равно числу единиц, входящих в этот узел:

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

где v — суммарное число единиц потока, проходящего через сеть.

Данные условия означают, что единицы потока нигде не теряются.

Циркуляцией называется поток по связям сети, для которого в каждом узле выполняется условие сохранения. При этом поток по любой связи (х, у) не превышает ее пропускной способности:

Поток в транспортной сети называют целочисленным, если значения f{x, у) целые для всех (х, у).

В задачах о потоках с выигрышами отказываются от допущения сохранности потока и предполагают, что потоки могут порождаться и поглощаться самим графом. При этом выходной поток связи принимают равным ее входному потоку, умноженному на некоторое неотрицательное число.

Потоки в сети удобно изучать с использованием понятия разрезов. Разрезом (5, Т) транспортной сети N= (К, R) называют разбиение множества узлов на множества Sи Т— К— S, такие, что источник s е S, а сток t е Т. Таким образом, разрез состоит из совокупности всех связей, начало которых принадлежит множеству S, а конец — множеству Т. Любой путь из источника к стоку содержит по меньшей мере одну дугу (связь) каждого разреза. Если из сети исключить все связи какого-нибудь разреза, то в новой сети не останется ни одного ориентированного пути, связывающего источник со стоком. Поэтому разрез сети нередко называют разделяющим сечением.

Если/ — поток, то чистый поток через разрез (S, Т), по определению, равен f(S, Т). Пропускной способностью разреза (5, Т) является суммарная пропускная способность всех дуг разреза c(S, Т). Минимальным разрезом сети является разрез, пропускная способность которого меньше, чем у всех остальных разрезов сети.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>