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