Выбрать численный метод

> […] чтобы заполнить стоки (частично, полностью или даже переполнить — не имеет значения).
Наверное, не совсем ясно выразился — главной целью является перемещение по графу всех элементов источников, стремясь заполнить максимальное количество стоков.

> А все алгоритмы макс. потока, что я знаю, предполагают наличие единственной пары источник-сток.
Что в постановке задачи мешает завести воображаемые единственные сток и источник, которые соединены с реальными?

> Что в постановке задачи мешает завести воображаемые единственные сток и источник, которые соединены с реальными?
Мм… Что-то мне подсказывает, что оптимальностью тут и не пахнет.

> Тут, на мой взгляд, что-то довольно близкое к транспортной задаче, но на больно специфической нише (графы, однако).

Ты говоришь это так, как будто транспортная задача не на графах. :3

Естественно, оптимальности никто не требует, достаточно хорошего приближения.

Оптимальности и приближения по какому, блджад, параметру?

или даже переполнить

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

Задачи как бы нет, считать нечего.

И да, погугли на предмет значения термина «численный метод».

Я бы завел дополнительный псевдоисточник и псевдосток, а затем бы использовал алгоритм Форда-Фалкерсона. Хотя в принципе, можно обойтись и без псевдоэлементов.

Таааак... давай ты четко сформулируешь задачу. Или хотя бы, млять, укажешь, _что_ хотелось бы минимизировать/максимизировать?

Да, с формулировкой дело туго.

> Таааак... давай ты четко сформулируешь задачу. Или хотя бы, млять, укажешь, _что_ хотелось бы минимизировать/максимизировать?
ОК, виноват.
Есть A источников по a_i элементов в каждом. Есть B стоков, способных принять b_i элементов каждый. Необходимо максимизировать количество удовлетворяемых (полностью заполняемых) стоков при общей минимальной протяженности пути (каждый элемент пойдёт к стоку каким-то путём, сумма длин всех путей, т.е. кол-ва рёбер должна быть минимальна).
Вроде бы, так описал гораздо лучше.

Результатом, соответственно, является карта [откуда; куда; сколько послать]. Расчитать достаточно лишь одну итерацию.

>что-то довольно близкое к транспортной задаче

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

P.S. Ещё посмотри Задачи математического программирования транспортного типа

Спасибо, буду изучать.

>неориентированный граф, в котором присутствует некое количество источников и стоков (A и B соотв.), каждый источник может поставить a_i элементов и каждый сток принять b_i элементов. в дискретной математике такой граф называется сетью

Требуется рассчитать сколько элементов и по каким путям (веса ребёр одинаковы) необходимо пустить, чтобы заполнить стоки (частично, полностью или даже переполнить — не имеет значения)

Какой смысл тогда имеют значение b_i?

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

> P.S. Ещё посмотри Задачи математического программирования транспортного типа
Замечательная книжка! Считаю тему решённой.
Всем спасибо за критику и советы.

Не слушай голос интуиции, а лучше читни-ка анализ сложности алгоритмов поиска максимального потока.
Уверен, простейшая реализация метода Форда-Фалкерсона тебе подойдет. Есть более быстрые «поднять-и-в-начало» и «проталкивание предпотока», но без четкой постановки посылать в них не буду. :-)