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

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

Это как? если надо минимизировать только количество перевозок, то стоимость вообще ни на что влиять не будет. Объясни подробнее... и что будет считаться одной перевозкой? перевозка любого количество груза между двумя конкретными пунктами?

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

[quote name='Atos' date='28.02.2006 14:40' post='62974']
Это как? если надо минимизировать только количество перевозок, то стоимость вообще ни на что влиять не будет. Объясни подробнее... и что будет считаться одной перевозкой? перевозка любого количество груза между двумя конкретными пунктами?

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

Алгоритм то как раз и не известен...
Но проблему бы решил и сторонний Soft, в который можно загрузить и выгрузить массив данных через текст. Подскажите, решение, экспорт и импорт возможны в MathCad'e? Если да, то отправляюсь разбираться, если - скорее нет, то надеюсь на Вашу помощь/софт.

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

Результаты моих экспериментов по данному вопрому: если загнать данные в ПО, решающее задачу по "венгерскому" методу, поставив в таблицу стоимости "1" - в приоритетные маршруты, и значение - большее максимальной стоимости в прочие клетки (ну чтобы показать машине - где выгоднее), то результат иногда получается оптимальным. Хотя исходный массив данных большой - могу и ошибаться...

из софта есть библиотечка GTL... не знаю, будет ли там что-то подходящее, я практически не смотрел, мне её, в общем-то случайно скинули вместе с лекциями по МО. Установщик чуть больше 2 Мб. zandryukha, напиши емейл, скину.

<> - ловлю, спасибо!

и удали, пожалуйста, e-mail с форума...

Сделано

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

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

Пожалуй - то, что нужно. Только вот с ранжированиеим приоритетов "запас-источник" - пока не понятно. Попробую реализовать на Excel (Basic). Если что-то получится - сообщу.

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

И всё-таки о венгерском методе для транспортной задачи. Там на одном из этапов в каждой итерации, мне кажется, возможно заменить стоимость частным, чтобы прийти к моей формулировке, при которой известны стоимости, а не цены. Помогите с исходниками для венгерского метода (Basic, Pascal, С++, да хоть подробная блок-схема), потому-что писать всё целиком - немалая работа.

Здесь было: МИО 2004 (смотри версию Alpha 4)

Посмотрел, спасибо. Только там, по-моему, только заготовка модуля, а собственно программы и нет. Или я что-то не то смотрю?

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

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