Транспортная задача: метод наименьшей стоимости

Термин «транспортная задача» объединяет широкий круг вопросов с общей математической моделью, необязательно транспортного характера. Объектом моделирования могут быть материальные, финансовые, информационные потоки, сопровождающие производственную и коммерческую деятельность. В данном примере рассмотрено решение классической транспортной задачи о поиске плана перевозок однородного продукта (товара) из пунктов отправления (Поставщик) в пункты назначения (Потребитель).

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

Запустить демо

Установить локально

Описание алгоритма

1. Импорт данных

а) Загрузка данных

Таблица «Стоимость перевозки»

Имя	Метка
price	Cтоимость перевозки
provider	Поставщик
consumer	Потребитель

Таблица «Необходимое потребителю количество товара»

Имя	Метка
consumer	Потребитель
required_quantity	Требуемое количество товара

Таблица «Количество запасов товара у поставщика»

Имя	Метка
provider	Поставщик
inventory_quantity	Количество запасов товара

2. Обработка данных

а) Дополнение и идентификация данных

С помощью обработчика Дополнение данных исходные данные объединены в таблицу «Матрица перевозок». Для удобства дальнейших расчетов с помощью узла Присвоение идентификаторов каждому варианту каждому варианту перевозки определяется номер.

Таблица «Матрица перевозок»

ID	Cтоимость перевозки	Поставщик	Потребитель	Требуемое количество товара	Количество запасов товара
1	20	A1	B1	500	800
...	...	...	...	...	...
24	84	A4	B6	1000	800

3. Алгоритм наименьшей стоимости

а) Получение заданного количества вариантов доставки

Для объединения необходимых данных используется узел Выбор количества вариантов доставки, где из матрицы производится выборка:

Стоимость:

IF(RowNum()=0, Concat(price, ";"), Concat(Data("list_price",RowNum()-1), Data("price",RowNum()), ";"))

price — стоимость перевозки

Количество запасов:

IF(RowNum()=0,Data("inventory_quantity",0), Concat(Data("list_provider",RowNum()-1), ";", Data("inventory_quantity",RowNum())))

inventory_quantity — количество запасов товара

Требуемое количество:

IF(RowNum()=0,Data("required_quantity",0), Concat(Data("list_consumer",RowNum()-1), ";", Data("required_quantity",RowNum())))

required_quantity — требуемое количество товара

Для преобразования таблицы в набор переменных используется узел Компоновка вариантов доставки.

Таблица «Выборка заданного количества значений»

Имя	Метка	Значение
list_consumer	Требуемое количество	500;...;1000
list_provider	Количество запасов	800;...;800
list_price	Стоимость	20;...;84;

б) Расчет маршрута с минимальной ценой

В узле Новые потребности и запасы, при наименьшей цене идет поиск первой наименьшей стоимости из матрицы перевозок, а также сравниваются Запасы и Потребности.

Например, при наименьшей стоимости в 1 ед., у Поставщика А1 в наличии 800 ед. товара, а Потребителю В1 требуется 500 ед. товара. Так как запасы А1 полностью покрывают потребности В1, то в дальнейших расчетах Потребитель В1 не участвует.

В узле Новый набор переменных формируется набор переменных с учетом исключенных Потребителей или Поставщиков.

С помощью Цикла производится многократный запуск узла «Расчет маршрута с минимальной ценой» до тех пор, пока не исчерпаются запасы Поставщиков, или не закроются нужды Потребителей.

В конечном итоге получена «Расширенная матрица оптимального варианта перевозок».

4. Оптимальное представление рассчитанных данных

а) Таблица поставок и стоимость доставки

С помощью узла Таблица поставок выводится оптимальный план распределения товара без учета стоимости перевозки.

Из «Расширенной матрицы оптимального варианта перевозок» с помощью узлов Не 0 поставка и Расчет стоимости доставки исключены промежуточные результаты и получен расчет доставки с учетом ее стоимости и объема поставляемого товара соответственно.

Таблица «Таблица поставок»

B1	B2	B3	B4	B5	B6	Поставщик
500,00	200,00	100,00	0,00	0,00	0,00	A1
0,00	0,00	200,00	400,00	0,00	400,00	A2
0,00	0,00	0,00	0,00	400,00	600,00	A3
0,00	800,00	0,00	0,00	0,00	0,00	A4

Таблица «Стоимость доставки»

Стоимость доставки	Целевая	Price	Поставщик	Потребитель
8 000,00	800,00	10	A4	B2
10 000,00	500,00	20	A1	B1
4 000,00	200,00	20	A1	B2
8 400,00	400,00	21	A3	B5
3 000,00	100,00	30	A1	B3
6 800,00	200,00	34	A2	B3
18 000,00	400,00	45	A2	B4
21 600,00	400,00	54	A2	B6
54 000,00	600,00	90	A3	B6

бизнес-задачи