Формальные постановки задач потокового программирования.

Система обозначений в потоковых задачах.

Ориентированный граф определяется множеством узлов и множеством дуг, которые связывают эти узлы. Узел i является элементом множества узлов N = [1, 2, 3,..., i,..., n]. Дугу можно определить как упорядоченную пару узлов (i,j) или как, скажем, элемент К, списка дуг M = [1, 2, 3,..., k,..., m].

M_oi = [k|o_k=i] - список дуг, которые выходят из узла i;

M_Ti = [k|t_k=i] - список дуг, которые входят в узел i.

 

Поток.

Потоками по дугам сети называют множество чисел f_k, определенных на дугах k.

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

Вектор потока.

Вектор потока определяется как

'

где верхний индекс "штрих" означает операцию транспонирования данной вектор-строки, т.е. является вектор столбцом.

Стоимость.

Стоимость h_k(f_k) является функцией только потока по дуге k и не зависит от потоков по другим дугам сети. Во многих потоковых задачах требуется найти поток минимальной стоимости. При этом цель состоит в минимизации суммы дуговых стоимостей (целевой функции);

В дальнейшем будут рассматриваться линейные функции стоимости.

Линейная функция стоимости

h_k(t_k)=h_kf_k

а тогда

Пропускная способность.

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

f_k£C_k

Вектор пропускной способности

С = [C₁, C₂,..., C_m]'

можно использовать для записи набора ограничений по пропускной способности;

f<C.

Ограничение на поток снизу.

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

f³ c.

Внешние потоки.

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

В моделях используются внешние потоки в узле двух типов: фиксированный и свободный потоки.

Пусть b_i - фиксированный внешний поток в узле i. Будем говорить, что поток b_i входит в узел i, если b_i>0, и выходит из сети, если b_i<0. Все фиксированные внешние потоки заданы и полностью учитываются в любом допустимом решении задачи о потоке в сети.

Свободный внешний поток в узле i, f_si пересчитывается в процессе выполнения соответствующих алгоритмов. Направление этого потока и границы изменения его значений определяются параметром узла i, b_si - пропускной способностью узла для свободного потока. Если величина b_si положительна (отрицательна), то поток f_si входит в сеть (покидает сеть) и должно выполняться ограничение 0£f_si£|b_si|

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

Свободные потоки можно представить иначе, используя параметры дуг, а не узлов. При этом в сеть вводится свободный узел n, в котором не требуется выполнения условия сохранения потока. Для положительного свободного потока f_si вводится дуга из свободного узла n в узел i. Для отрицательного свободного потока строится дуга в свободный узел n из узла i. Пропускная способность этой дуги полагается равной |b_si|, а стоимость - h_si.

Условие сохранения потока.

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

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