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

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

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

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

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

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

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
бизнес-задачи

Скачайте и откройте файл в Loginom. При необходимости Loginom CE можно скачать бесплатно

Скачать демопример

Минимальные требования к системе:

  • Операционная система: Windows 8.1 и выше.
  • CPU x64: 1 core.
  • Оперативная память: 1 GB.
  • Жесткий диск: 10 GB.