оптимальные маршруты перевозок при огранич пропускн способн

[xelAlex]

Задача такая: дана транспортная сеть, для каждого ребра задана стоимость перевозки и пропускная способность. Также задана
матрица корреспонденций для всех вершин, т.е. для каждой пары вершин (v,u) задан объем груза, который нужно перевезти
из вершины u в вершину v. Нужно перевезти грузы в соответствии с заданной матрицей корреспонденций по таким маршрутам, чтобы общая стоимость всех перевозок была минимальной.
Понятно, что при неограниченных пропускных способностях задача становится тривиальной (перевозки нужно осуществлять по путям с наименьшей стоимостью), но вот что делать если пропускные способности ограниченные?
Если кто-то знает где можно найти информацию по такой задаче, то буду очень признателен.

[Dmitriy40]

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

[xelAlex]

Dmitriy40 в сообщении #1266218 писал(а):

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

Такой подход не дает (гарантировано) оптимальное решение. Может быть так: пропускная способность некоторого ребра e уже исчерпана грузами $q_1$,$q_2$,...,$q_n$, и груз q, для которого путь наименьшей стоимости содержит ребро e, пускаем по маршруту без ребра e. Однако, может оказаться, что если бы мы пустили груз q по маршруту, содержащему ребро e, а какой-то из грузов $q_1$,$q_2$,...,$q_n$ по маршруту, не содержащему ребро e, то мы бы получили более оптимальный план перевозок.

[grizzly]

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

[xelAlex]

grizzly в сообщении #1266356 писал(а):

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

Давайте уточним. У меня задана матрица корреспонденций, т.е. для каждой упорядоченной пары вершин u и v задан объем груза, который необходимо перевезти из u в v. Этот объем груза можно разбить на любое количество частей и провозить по разным маршрутам. Подчеркну, что этот груз должен быть доставлен именно в вершину v, т.е. удовлетворить потребности вершины v в этом грузе за счет перевозок из других вершин нельзя. Наверное можно сказать, что мы имеем дело с многопродуктовой задачей и каждой корреспонденции соответствует свой уникальный продукт.

[grizzly]

xelAlex в сообщении #1266372 писал(а):

Давайте уточним.

Пока не совсем получилось. Я понял, что груз можно разбивать. А можно не разбивать? Утрируя: в одном пункте есть миллион единиц груза объёмом 1 м.куб. каждая. Весь этот груз нужно доставить в (один) другой пункт. Разрешается это сделать одной транзакцией? Я просто хочу понять, зачем заданы объёмы.

-- 18.11.2017, 13:19 --

А, наверное, пропускная способность рёбер выражается в объёмах, а не в количествах транзакций?

[Iam]

Задача сводится к задаче линейного программирования.
Пользуюсь обозначениями из недавно вышедшей статьи http://rts-md.com/index.php/jornalRTS/article/view/25/18.
Там же есть ссылки, на работы, которые могут быть полезными.
Пусть $ \mathcal M, \mathcal M<i,j> \subseteq \mathcal M, \mathcal M(k,l) \subseteq \mathcal M $ - соответственно множество всех маршрутов, множество маршрутов из $i $ в $ j $, множество маршрутов, проходящих по дуге $ (k,l) $;
$\lambda (\mu) $– интенсивность потока на маршруте $\mu \in \mathcal M, \lambda = (\lambda (\mu) )_{\mu \in \mathcal M } $ - поток (функция распределения потоков, система потоков, или вектор-поток, или вектор интенсивностей потоков – как угодно) в сети;
$\Lambda = \{\lambda | 0 \le \lambda (\mu) \land \sum_{\mu \in \mathcal M(k,l) } \le c(k,l) \}$- множество допустимых потоков (ограничено линейными неравенствами).

Задача формулируется в виде:
$S(\lambda) \Rightarrow \max_{\lambda \in \Lambda} $,
где $S()$– стоимость потока (линейный функционал).

Другой вариант задания системы потоков $\lambda $ посмотрите в книге Шварца (см. ссылку выше).

[xelAlex]

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

-- 18.11.2017, 18:06 --

Iam
По-моему это то, что нужно. Спасибо огромное!