Транспортная задача: метод северо-западного угла

Введение

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

Математическая постановка ТЗ

Однородный товар сосредоточен у m поставщиков в объемах A1, A2, ..., Am. Данный товар необходимо доставить n потребителям в объемах B1, B2 ... Bn. Известны Cij , i=1,2,...m; j=1,2,...n — стоимости перевозки товара от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором обеспечивается доставка необходимого количества товара в каждому из потребителей, вывоз товара от всех поставщиков, а также исключаются обратные перевозки.

Исходные данные

Запасы

Имя и метка поля Пояснение
 A_name Пункт отправления (Поставщик)
 A Количество запасов товара

Потребности

Имя и метка поля Пояснение
 B_name Пункт назначения (Потребитель)
 B Требуемое количество товара

Стоимость

Имя и метка поля Пояснение
 A Пункт отправления (Поставщик)
 B Пункт назначения (Потребитель)
 Price Стоимость перевозки от Поставщика до Потребителя

Сценарий

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

Сценарий метода северо-западного угла
Рисунок 1. Сценарий метода северо-западного угла

Слияние

Соединяет "Запасы" и "Потребности" в плоскую таблицу:

A_name A B_name B
A1 800 B1 500
A1 800 B2 1000
... ... ... ... ...
A4 800 B6 1000

В визуализаторе Куб таблицу для наглядности можно представить матрицей начальных условий. Результат решения ТЗ - заполненные ячейки матрицы. Заполнение начинается с левой верхней ячейки (северо-западный угол).

Матрица начальных условий
Рисунок 2. Матрица начальных условий

Количество точек потребления

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

Настройка переменных

Подготовительный узел. В нем формируются:

  • Переменная со списком Потребностей
  • Таблица с запасами Поставщика, которые доступны к распределению
Подмодель Настройка переменных
Рисунок 3. Подмодель Настройка переменных

Если во входных данных изменяется количество Потребителей, то их число необходимо скорректировать в вычисляемом выражении Калькулятора.

Калькулятор Настройка переменных
Рисунок 4. Калькулятор Настройка переменных

Расчет поставок. Базовый для цикла

После преобразования исходных данных, производится расчет поставок - распределение запасов по Потребителям. Например, значение запасов первого Поставщика (А1 = 800) сравнивается со значением нужд первого Потребителя (В1 = 500). Так как запасы перекрывают потребности, первый Потребитель (В1 = 0) не учитывается в дальнейших расчетах, а остатки запасов (А1 = 300) используются для нужд второго Потребителя (В2 = 1000-300). Таким образом, формируется обновленная таблица с новыми значениями потребностей (0, 700, ... )

Расчет поставок
Рисунок 5. Расчет поставок

Расчет поставок от каждого производителя

Производится запуск узла "Расчет поставок. Базовый для цикла" до тех пор, пока не исчерпаются запасы Поставщиков или не закроются нужды Потребителей.

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

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

Таблица поставок
Рисунок 6. Таблица поставок

Расчет стоимости доставки

Рассчитывает затраты на перевозку, учитывая ее "Cтоимость", исключая "Не 0 поставка" нулевые значения в таблице поставок.

Стоимость доставки
Рисунок 7. Стоимость доставки

Компоненты, используемые в сценарии

Файлы

Скачать

results matching ""

    No results matching ""