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

[zandryukha]

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

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

[Atos]

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

Трудоёмкость можно ограничить сверху logN+log(N-1)+...+1 = log(N!), где N - общее количество всех пунктов

[zandryukha]

По поводу алгоритма...

Другая проблемка с алгоритмом - посерьезней ранжирования. Выбирая каждый раз максимум, мы "уверены", что не существует других нескольких значений (чуть поменьше), которые в сумме сразу закрывают потребность, что "экономит" в итоге одну итерацию. В этом части "жадный" алгоритм в эквивалентен "минималистскому", т.е. мы можем отбирать и перекрывать и минимальные пары потребностей-ресурсов с тем же успехом. Кстати, именно с такого алгоритма я и начал.
Таким образом, алгоритм необходимо "надстроить" полным перебором сочетаний для проверки, дают ли они сумму потребностей/избытка. При этом, откуда бы мы ни начали (хоть - с минимума, хоть - с максимума) , это не гарантирует оптмальности, что приводит к необходимости простого тотального перебора ВСЕХ вариантов. Этого, поначалу, я и хотел избежать, хотя теперь уже согласен и на такой подход...