Здравствуйте, Кодт, Вы писали:

К>Я сформулировал наиболее общий случай. Скажем, один агент выставляет множество предложений и множество же заявок.
К>Это может означать, что
К>- нужно удовлетворить все заявки (т.е. мы разбиваем граф на циклы, разбивая множество рёбер-заявок)
К>- нужно удовлетворить ровно одну заявку (т.е. мы разбиваем множество вершин-агентов)
К>- нужно удовлетворить хотя бы одну заявку агента, чтобы он "имел навар с яиц" (т.е. мы не разбиваем, а покрываем множество вершин-агентов)

К>А возможно, что условия задачи провозглашают, что у агента ровно одна заявка и ровно одно предложение.
К>В таком случае заявка-агент-предложение является ребром.
К>И тогда у нас получается просто орграф из вершин-товаров и рёбер-агентов.
К>И мы разбиваем его на циклы, разбивая (или покрывая) множество рёбер.

Сразу пост не переварил и буду еще сегодня курить ...

Условия задачи вообще тоже в процессе разработки, озвучены заказчиком просто как "Бартер". Но пока выглядит так. Клиент размещает заявку в которой указывает что у него есть, на что он готов это поменять и на каких условиях (возможно как-то дальше будет преобразовываться в вес ребра). Если есть прямые предложения обмена шило-на-мыло, то пользователь может совершить операцию самостоятельно. Если прямых нету то включается брокер, который пытается совершить этот сложный обмен.

Пока не думал над множеством предложений от одного человека и рассматривал простой случай, который приведен в первом посте. Тогда для первого случая я построил граф товаров что-на-что меняется и получил цикл конфеты->сахар->масло.

В общем задача видится так
— клиент размещает предложения 1..* и потребности 1..*
— клиент обращается к агенту для того, чтобы агент помог совершить ему обмен (конечно только то что получится, т.е. есть в базе товар и сложные пути его обмена — циклы)
— агент при помощи системы ищет все возможные варианты и выбирает наиболее оптимальные, вернее системе помогает ему подобрать оптимальные варианты (различные условия доставки товара могут влиять на вес ребер обмена)

Пока покурив немного литературу нашел
— Иванов, Дискретная математика. Алгоритмы и программы.
На стр. 151 "Кратчайшие пути на графе" решается очень похожая задача, но пока не разобрался с другими путями кроме кратчайшего.

Покурю еще раз двудольный орграф и продолжение поста ...

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