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

У каждой фирмы есть остаток, он может быть нулевым, положительным, отрицательным.

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

Пример ряда: Из фирмы А перевести 50 рублей фирме Б, из фирмы Б 100 рублей фирме Ц, тогда на фирме Ц будет остаток 0.

Соответственно нужно чтобы лишних действий не производилось.

Можно ли свести эту задачу к существующим мат. методам?

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

Так что в жизненности данной постановке можете не сомневаться, а вот как ее решать - вопрос открыт.

Как то мне думается что метод поиска максимального потока в графах, тут не очень то и подходит.

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

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

поиск по рамблеруну, вот например, диссер готовый - с научной новизной, введением и выводами.
http://www.mirkin.ru/_docs/dissert017.pdf

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

А у меня другое, известно что есть набор фирм с деньгами, другой набор фирм с долгами и надо погасить долги. Конкретики изначально нет. То есть если на одной фирме 100 рублей и на другой фирме 100 рублей. А есть третяя фирма куда надо пригнать 100 рублей, то отправитель может быть как первая, так и вторая фирма.

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

Короче, чешу репу дальше.

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

Поясните пожалуйста как выглядит эта матрица?
скажем есть 9 фирм: 1,2,3,4,5,6,7,8,9

у фирм: 1,3,5 - положительный остаток +
у фирм 2,4 - отрицательный -
у остальных остаток = 0

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

По ходу дела да, а в качестве цены за доставку - будет выступать количество операций до поставщика.