Discrete Location Problems ballred.gif (861 bytes) Benchmarks Library
line.jpg (1129 bytes)

Невзвешенная задача о максимальном многопродуктовом потоке с ограничением
на длину цепей          

ballred.gif (861 bytes)  Главная страница библиотеки  

ballred.gif (861 bytes)  Тестовые примеры

ballred.gif (861 bytes)  GAMS-model

Text in pdf-file mcf.pdf

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

Значение

является величиной потока из  в .

Пусть  — набор путей (простых цепей) из из  в , тогда суммарный поток по также является потоком из  в . Если  , то поток  назовем потоком вдоль путей .

Предположим, что поток  продукта имеет источник  и сток .   Если — потоки  продуктов, то называется многопродуктовым потоком в .

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

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

Формулировка LBMCF1 в виде задачи линейного программирования, содержащая  ограничений и  переменных, может быть построена как задача о многопродуктовом потоке в специально сконструированной многоуровневой сети [2]. Множество вершин  такой сети содержит копию  исходного множества графа  для каждого дискретного момента времени . Каждой дуге  в исходном графе соответствует дуга в  из вершины  уровня  в вершину  уровня . Кроме того,  содержит дуги  для всех . Также на многопродуктовый поток в новой сети накладывается условие, что для любой исходной дуги  суммарный поток по всем дугам  не превосходит . Для всех  источник для продукта  размещается в вершине  соответствующей исходной вершине  на уровне . Сток располагается в вершине  соответствующей исходной вершине  на уровне . Модель ЛП выглядит следующим образом:

(1)

(2)

(3)

(4)

(5)

ЛИТЕРАТУРА

[1] Т. Ху. Целочисленное программирование и потоки в сетях. Москва: Изд-во "Мир". 1974.

[2] P. Kolman and C. Scheideler, Improved bounds for the unsplittable flow problem, J. Algor. 61 (1) (2006), pp 20-44.