Задачка:)

В некоторых городах излишек товара, а в некоторых запасов на складе не хватает для обеспечения заказов (это отрицательные значения). Цель - перевести товар из городов-излишков в город, где товара не хватает, с наименьшими транспортными затратами.

Для этого есть выборка -
Город, Количество товара. К примеру:
Москва +600
Киев филиал1 -200
Киев филиал2 +300
Одесса -500
СПБ 500
Воронеж -700

Есть значение расстояний между городами.

Сделал обработку, которая в таблицезначений сортирует по убыванию кол-во товара, берет первое значение (максимальное кол-во товара), затем  строит вторую выборку добавляя в нее колонку расстояний от города первого значения, затем сортирую по расстоянию, и закрываю отрицательные значения.

Работает быстро, но неверно - по моему алгоритму 200 единиц товара поедет из Москвы в Киев, а должны поехать из Киев филиал2 в Киев филиал1.

Т.е. фактически надо вычислить самые короткие расстояния и сначала перебрасывать между ними. Пока не нашел лучшего алгоритма для этого, чем построить огромную временную таблицу вида:

город1, Город2, расстояние, возможное количество товара к переброске

Но возникает несколько проблем:
1) таблица получается размером кол-во городов в квадрате
2) эту таблицу надо перестраивать каждый раз после переброски товара

Итого на 100 филиалов порядка полумиллиона операций:(

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

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

(2) ну так составь формулу для вычисления общей стоимости доставки, ограничением будет наличие товара на каждом складе, ну и находи минимум функции
ru.wikipedia.org/wiki/%D0%9E%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)

я пару месяцев назад решал задачу оптимизации за 100тыс, а ты здесь хочешь получить готовое за бесплатно... можно сделать прямой перебор и найти оптимум, но количество перебираемых вариантов при этом функция факториала, т.е. перебрать комбинации более ~десяти объектов не получится. Можно сделать случайный перебор и выбрать оптимальную из перебранных - что будет посложнее.

в школе, т.е. в университете решали вот такие задачи wiki:Линейное_программирование

Я думаю раз вариантов ограниченное число, т.е. из Одессы в Питер товар доставляется только через Москву, а не через произвольное число городов, то задача упрощается.

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

если задача частная - то проще через заранее заложеный не универсальный алгоритм

а вообще многие крупные логистические монтстры плюют на оптимизацию и гонят все через центральный терминал, например из Москвы в Одинцово пойдет через Франкфурт

Управление цепочкой поставки используйте из ТОС. тогда будете решать причину, а не последствия.

хм, а нужно ли учитывать, что в определенном городе должен быть свой минимум товара? Скажем, для москвы 1000, а для воронежа 500. поэтому, если в Москве 1100 на складе, а в Воронеже 700 и требуется 200 ед, то везем из Воронежа, не из Москвы.

(8) они правы)))

(10) Минимум уже учтен. В таблице те данные, которые необходимо закрывать.

Задачу уже решил. Втупую -
построил таблицу значений

Город1, Город2, Расстояние, СуммаИзбыткагорода1,СуммаНедостаткаГорода2

В колонке СуммаИзбыткагорода1 только положительные, в колонке СуммаНедостаткаГорода2 только отрицательные. Кол-во товара получается дублируется по строкам.

Сортирую по расстояние возр, затем по суммаИзбытка убыв.

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

И так до нуля в последней колонке.

работает менее 1 секунды на выборке 100 записей, почти моментально...

(8) (11) Прикольно так. Из Киева Филиал1 в Киев Филиал2 отправлять через Франкфурт. там откаты больше?

(0) предлагаю вариант "частная задача"

город - это справочник, делаем у него ТЧ в ней указываем город и коэф. доставки

далее все просто, делаем соединение ТЧ с остатками и закрываем первые х строк.

работать будет лучше чем (0), но это частный случай.

реальный алгоритм написать будет совсем не просто

(9) Веришь в людей? У них математика и графы, им не до реальности...

(14) минус - при добавлении пункта/города - нужно дофига где его прописать

Есть спрос и есть обеспечение спроса, а это решается через центральный склад)))

(17) Для ТОС нужно быть немножечко больше, чем кодером. Кодер идею не продаст.

(14) имхо, лучше использовать РС с измерениями город выхода и город прихода и ресурсом на стоимость доставки. а его уже можно удобно обрабатывать.

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

(19) так и делаю. расстояния и стоимость 1 км (она блин разная в зависимости от города, состояние дорог что ли) в РС, это обсуждалось в другой теме.

классическая задача транспортная

там где излишки это "проиводители"
где недостача - "покупатели"

(0) это курсовая / диплом?
на практике ТАК задача обычно никогда не стоит - чаще всего уже есть некоторая схема (расписание) перевозок, когда идет плановое пополнение складов, и уже на эти перевозки накладывается выполнение заказов покупателей не по стандартному маршруту следования товаров.

столько теории и книжок по этой теме написано а вы велосипед изобретаете. неучи

(22) Точно. И судя по всему, я ее решил методом северо-западного угла.

(23) нет, нормальная система в продакшене с некоторыми недоговариваемыми моментами, которые все равно никак не влияют на решение:)

(24) зато как приятно самому найти решение и понимать, что ты повторил путь великих ученых:)))