РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ

ТРАНСПОРТНЫЕ ЗАДАЧИ

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

Основным критерием оценки доставки груза зачастую служит анализ полной стоимости. При этом учитывается возможность увеличения затрат на одну из рассматриваемых областей, что может привести к экономии в целом. Как правило, составляется 2-5 вариантов решения поставленной задачи и, исходя из критериев оценки (цена, время, сохранность груза), выбирается лучший из них. Верное решение возможно только при плодотворном взаимодействии всех участников логистической схемы.

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

Транспортные задачи характеризуется тем, что коэффициенты искомой функции положительны и могут либо равняться нулю, либо быть целочисленными (так как себестоимость перевозок — неотрицательное число). Решение данных задач входит в класс сложных.

МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ

Классическая транспортная задача решается линейно (симплексным методом). Необходимо сформировать опорный план, найти оптимальный вариант перевозки. При этом условия задачи записывают в табличной форме (объем груза и тарифы).

Количество вариантов определяется методом решения транспортной задачи, при этом применяют методы математического программирования. Основными программными комплексами моделирования являются TransCad, ЕММЕ/2, Tmodel2, UfosNet, MINUTP.

Опорный план формируется следующим способом: левую верхнюю клетку таблицы заполняют максимально возможным числом таким образом, что потребность удовлетворяется полностью. Либо применяется метод наименьшего элемента, заключающийся в перераспределении товаров между потребителями и минимизации побочных товаров.

Из ценовой таблицы выбирают минимальную стоимость и записывают в ячейку, которая соответствует минимальному числу. Затем проверяют столбцы и строки на наличие израсходованных запасов, и далее такие элементы таблицы уже не рассматриваются. В случае, если не все поставщики израсходовали товары, происходит возврат в начало алгоритма. Также для решения подобных задач существуют алгоритм Форда — Фалкерсона, алгоритм Веллмана — Форда, алгоритм «min cost — max flow». При решении несбалансированной транспортной задачи вводят фиктивные пункты назначения, тем самым сводя задачу к сбалансированной.

К примеру, существует следующая транспортная задача. Из трех складов Cl, С2, СЗ, вмещающих запасы товара 3 [т], требуется перевезти продукцию в пять магазинов Ml, М2, М3, М4, М5 согласно потребности П [т]. Стоимость перевозки 1 т из склада С в магазин М [у.е.] представлена в форме таблицы 12.1. Требуется написать математическую модель перевозок так, чтобы их общая стоимость была минимальной. (Задача имеет закрытый тип, т.к. запасы 3 равны потребностям П.)

Решение выглядит следующим образом. Определяем пустую ячейку с минимальной стоимостью перевозки: (СЗ, Ml). Помещаем в нее наименьшую потребность П = 150. Определяем пустую ячейку с минимальной стоимостью перевозки: (СЗ, М5). Помещаем потребность П = 3 (3) — 3 (СЗ, Ml) = 250 — 150 = 100. Определяем пустую ячейку с минимальной стоимостью перевозки: (Cl, М4). Помещаем в нее потребность П = 230. Определяем пустую ячейку с минимальной стоимостью перевозки: (С2, М2). Помещаем в нее потребность П = 140. Определяем пустую ячейку с минимальной стоимостью перевозки (С2, М3). Помещаем в нее потребность П = 110. Определяем пустую ячейку с минимальной стоимость перевозки: (Cl, М5). Помещаем потребность П = 3 (1) — 3 (Cl, М4) = 320 - 230 = 90. Определяем пустую ячейку с минимальной стоимостью перевозки: (С2, М5). Помещаем потребность П = 3 (2) - 3 (С2, М2) - 3 (С2, М3) = 280 - 140 - ПО = 30.

Таблица 12.1

Решение транспортной задачи по правилу минимального элемента

Общие расходы на транспортировку равны произведению стоимости С и потребности П по всем клеткам — 12 040 у.е. Данную задачу также возможно решить методом потенциалов либо методом свободных клеток.