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

Главная arrow Логистика arrow ЛОГИСТИКА ГОРОДСКИХ ТРАНСПОРТНЫХ СИСТЕМ

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


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

СЕТЕВЫЕ И ПОТОКОВЫЕ МОДЕЛИ

В результате изучения данной главы студент должен:

знать

  • - определения сети, цепи, цикла, пути, контура и графа;
  • - определение понятий «дерево», «остовное связующее дерево», «кратчайший остов графа» и «максимальный остов графа»;
  • - определения потока и условие сохранения потока в узлах сети;
  • - содержательную и математическую постановку задачи выбора кратчайшего пути;
  • - содержательную и математическую постановку задачи коммивояжера;
  • - содержательную и математическую постановку задачи о максимальном потоке;
  • - содержательную и математическую постановку задачи о максимальном покрывающем дереве в графе;

уметь

- решать задачи выбора кратчайшего пути, коммивояжера, о максимальном потоке, максимальном покрывающем дереве в графе как задачи линейного программирования;

владеть

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

Основные определения и приложения сетевых и потоковых моделей

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

Построение математического определения графа С осуществляется путем формализации объектов и связей как элементов двух конечных множеств ? = (V, ?), где V — конечное множество вершин, Е — конечное множество ребер, которые соединяют вершины.

Примером задачи ЛП, которая может быть представлена в виде графа, является транспортная задача (см. табл. 8.1). Однако можно указать и такие сетевые задачи, которые нельзя сформулировать в виде задачи ЛП. Например, таковой является задача коммивояжера.

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

Рассмотрим основные определения в сетевых и потоковых задачах.

Сеть состоит из множества вершин I = 1,2, п (называемых также узлами, или точками соединения) и множества дуг е^, ?,у = 1,2,..., п (называемых также звеньями, или ребрсши), которые связываю т узлы v? и V.. Если дуга имеет определенную ориентацию (направление), то ее называют ориентированной, или направленной (рис. 9.1, а), а если не имеет, — неориентированной (рис. 9.1, 6).

Изображение графов

Рис. 9.1. Изображение графов:

а ориентированный граф: б — неориентированный граф

Сеть называют связной, если при любом разбиении множества узлов сети У на подмножества Р, и У2 найдется дуга е^ или дуга е^, связывающая 1-й узел V,, принадлежащий подмножеству V,, е У{, и у-й узел принадлежащий подмножеству У2, е У2.

Будем рассматривать только связные сети и считать, что между любыми двумя узлами и ту имеется нс больше одной ориентированной дуги вц и одной ориентированной дуги е^ либо имеется только одна неориентированная дуга вц. Одну неориентированную дугу можно заменить двумя ориентированными. Существование петель (дуг, ведущих из некоторого узла в тот же узел) исключается.

Последовательность узлов и дуг еХ 2, а2, е23,..., гк_{, ек_^, гк сети называют цепью (ориентированной цепью), ведущей из узла в узел ек. Если ь = = ок, то такую последовательность называют ориентированным циклом. Цепь называют простой, если она не содержит циклов.

Путем называют последовательность ь, е12, о2, е2%,..., ь'к_ ек_, ок, где

г)2, ..., 1'к узлы сети и либо е^_{, либо е/+1 ?=1,2, ..., к — дуга сети. Путь отличается от цепи тем, что при движении от узла к узлу ек можно пройти дугу сети и в направлении, противоположном се ориентации. Для неориентированных сетей понятия цепи и пути совпадают. В частности, циклами являются контуры.

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

В связной сети для любых двух различных узлов существует, по крайней мере, один соединяющий их путь (или цепь). Частным случаем связных ориентированных и неориентированных сетей являются деревья. Если множество всех узлов и дуг задать в виде графа С = (V, Е), где V = {г,,г>2,} - множество узлов, Е = е{2> -,еп } — множество дуг, то дерево определяют как связное подмножество (подграф) множества (графа) С, не содержащее

циклов, т.с. для любых двух узлов дерева существует единственный путь, соединяющий их. В сети, содержащей п узлов, подграф из к узлов (к < п) является деревом, если выполнены любые два из следующих условий:

  • 1) подграф является связным;
  • 2) подграф не имеет циклов;
  • 3) число дуг в подграфе равно к -

Остовным связующим деревом (остовом) называют дерево, содержащее все узлы сети. Если сеть содержит п узлов, дерево с п узлами и п - 1 дугами является остовом.

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

Весом (длиной) дуги называют число, соответствующее некоторой характеристике дуги (расстоянию, стоимости и т.п.). Каждой дуге вц или (?,у) ставят в соответствие положительное число с,у, называемое пропускной способностью дуги (ребра).

В сети выделяют два специальных узла: один из них называют источником а другой — стоком ъ.

Сеть можно рассматривать как водопроводную систему, в которой трубы соответствуют дугам, источник воды — источнику о5, сток воды — стоку 1)(, а соединения между трубами — остальным узлам сети. В качестве пропускной способности дуги выступает поперечное сечение трубы.

Потоком из источника в сток V, сети называют множество неотрицательных чисел Хц, поставленных в соответствие некоторой дуге сети, если эти числа удовлетворяют следующим линейным условиям-ограничениям:

В системе ограничений, выраженных формулами (9.1), отражается тот факт, что в каждый узел (кроме источника и стока) приходит столько потока, сколько из него уходит (условие сохранения потока). Здесь первая сумма берется по дугам, ведущим в узел V:, а вторая сумма — по дугам, ведущим из узла Ъу Неотрицательное число и называют величиной потока. Число Хц называют потоком по дуге еху или дуговым потоком. Ограничение (9.2) означает, что поток по дуге ограничен пропускной способностью дуги си.

Очевидно, что задача нахождения величины максимального потока в любой сети является задачей ЛП: максимизировать функцию

при условиях-ограничениях в формулах (9.1), (9.2). Однако в силу специфики задачи сетевые методы решения здесь оказываются более эффективными, чем симплекс-метод, применяемый для решения общей задачи линейного программирования.

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

Значительное место в приложениях занимают сетевые задачи, связанные с планированием и составлением расписания выполнения работ по осуществлению больших проектов, проведению научных исследований и опытно-конструкторских разработок. Сетевые задачи решают также при составлении расписаний движения транспорта, календарном планировании, распределении ресурсов и т.д.

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

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