Не совсем транспортная задача, Нужен Soft или хотя бы метод Опции

[zandryukha]

Практическая не совсем транспортная задача
Некоторый однородный продукт, сосредоточенный у m поставщиков Ai в количестве ai (i=1,2,3,...,m) единиц соответственно, необходимо доставить n потребителям Bj в количестве bj (j=1,2,3,...,n) единиц. Необходимо составить план перевозок, позволяющий вывезти все грузы, полностью удовлетворить Cij xij потребности.
Если в транспортной задаче известна цена Cij перевозки единицы груза от i-го поставщика к j-му потребителю, а целью является минимизация стоимости, то в нашем проблемном случае известна собственно стоимость (с целью задания приоритетности маршрутов), а минимизировать необходимо количество перевозок.

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

[Atos]

Только вот с ранжированиеим приоритетов "запас-источник" - пока не понятно

просто все значения отсортировываем по порядку в один массив - и запасы, и потребности.

которые в сумме сразу закрывают потребность, что "экономит" в итоге одну итерацию.

Э-э... не думаю.

т.е. мы можем отбирать и перекрывать и минимальные пары потребностей-ресурсов с тем же успехом.

нет. То есть, в худшем случае, да, но не забывай, что , после уменьшения значения Б, ему может найтись "комплементарная пара", что позволит исключить сразу ещё два пункта. Если действовать с минимумами, то вероятность этого меньше, а во многих случаях равна нулю.

При этом, откуда бы мы ни начали (хоть - с минимума, хоть - с максимума) , это не гарантирует оптмальности,

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

[zandryukha]

Э-э... не думаю.
нет. То есть, в худшем случае, да, но не забывай, что , после уменьшения значения Б, ему может найтись "комплементарная пара", что позволит исключить сразу ещё два пункта. Если действовать с минимумами, то вероятность этого меньше, а во многих случаях равна нулю.

Видимо у меня - действительно худший случай. Правда я закрывал минимумы, но на матрице 11x17 - у меня в избытке оказались две итерации.
Надеюсь, что текст проги с венгерским методом все-же удасться найти... Ну а если не удасться, вернусь к "жадному" алгоритму.