Транспортные модели линейного программирования и их использование в логистике
Транспортные модели линейного программирования — это варианты решения задачи по определению оптимального плана перевозок грузов из пунктов отправления в пункты назначения с минимальными затратами на перевозки.
Понятие и содержание транспортной задачи
Решению экстремальных задач, то есть задач по определению максимальных или минимальных значений на заданном множестве, посвящена специальная математическая дисциплина – линейное программирование. В рамках линейного программирования рассматривают несколько задач специального вида, решение которых имеет четко выраженное практическое значение. Одной из таких задач является транспортная задача.
Суть транспортной задачи сводится к составлению оптимального плана перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. По теории сложности вычислений транспортная задача относится к классу сложности P, для которого существует «быстрые» алгоритмы решений задач.
Основные условия транспортной задачи в ее классическом виде заключаются в осуществлении перевозки со следующими характеристиками:
- перевозки однородного продукта;
- перевозки из однородных пунктов наличия;
- перевозки в однородные пункты потребления;
- перевозки на однородных транспортных средствах (предопределенном количестве);
- перевозки со статичными данными и линеарном подходе.
Обычно выделяют два типа классической транспортной задачи. Решение задач первого типа связано с критерием стоимости (т. е. стремятся достичь минимум затрат на перевозку) или расстояний. Решение задач второго типа связано с критерием времени (т. е. стремятся достичь минимум времени на перевозку).
Транспортной задачей может быть обозначен широкий круг задач с единой математической моделью, которые относятся к задачам линейного программирования и решаются через применение оптимального метода. Однако решение транспортной задачи может быть существенно упрощено благодаря специальному методу, поскольку разработка транспортной задачи велась с целью минимизации стоимости перевозок.
Методы решения транспортной задачи
Классическую транспортную задачу можно решить симплекс-методом. Этот метод предполагает перебор вершин выпуклого многогранника в многомерном пространстве. Иными словами, строятся базисные решения, на которых монотонно убывает линейная функция, до ситуации выполнения необходимых условий локальной оптимальности.
В силу ряда особенностей транспортные задачи малой размерности могут быть решены проще, чем через применение симплекс-метода.
План перевозок, сформулированный во время решения транспортной задачи, может быть постепенно (итерационно) улучшен. Для этого возможно использование следующих методов:
- метод северо-западного угла (диагональный или улучшенный);
- метод минимального (наименьшего) элемента;
- метод двойного предпочтения;
- метод аппроксимации Фогеля;
- метод падающего камня
- метод потенциалов.
Первые четыре метода направлены на определение опорного плана перевозок. Затем найденный план улучшают путем применения одного из последних двух методов, тем самым, приближая план перевозок к оптимальному.
Транспортная задача еще может быть решена при помощи теории графов. В данном случае рассматривают множество точек, которые соединяются друг с другом множеством линей. В отношении транспортной задачи рассматривается двудольный граф, в котором пункты производства находятся в верхней доле, а пункты потребления — в нижней.
Виды транспортной задачи
Практика решения транспортной задачи привела к формулированию нескольких обобщений, которые вызваны практическими потребностями логистической деятельности хозяйствующих субъектов. В качестве примеров можно назвать следующие разновидности транспортной задачи:
- Транспортная задача в сетевой постановке.
- Транспортная задача с ограничениями пропускной способности.
- Многопродуктовая транспортная задача.
В рамках транспортной задачи в сетевой постановке все пункты равноправны, т. е. подразделения на пункты отправления и пункты потребления не происходит. В то же время производство описывается при помощи положительного числа, а потребление — отрицательного. Предполагается, что перевозки осуществляются по заданной сети, в которой дугами могут быть соединены любые пункты (в том числе, два производителя или два потребителя). Эта задача решается практически так же, как и классическая задача — слегка измененным методом потенциалов.
Транспортная задача с ограничениями пропускной способности является частным вариантом транспортной задачи в сетевой постановке. Ее особенностью является наличие ограничения по максимальной пропускной способности некоторых дуг, которыми соединяются между собой пункты. Решение этой задачи требует применение слегка усложненного метода потенциалов.
Многопродуктовая транспортная задача, как видно из названия, исходит из наличия нескольких продуктов. При этом один и тот же пункт может производить или потреблять одновременно несколько продуктов. В отношении некоторых дуг может быть установлено ограничение на пропускную способность. В случае отсутствия данного ограничения задача распадается на несколько отдельных задач по продуктам. Задача решается при помощи симплекс-метода.
Таким образом, одной из базовых задач линейного программирования является транспортная задача. Необходимость ее формулирования и решения во многом объясняется логистическими потребностями хозяйствующих субъектов, а именно — подготовкой и организацией проведения грузовых перевозок оптимальным способом. Под оптимальностью в данном случае понимают минимум понесенных расходов, минимум преодоленного расстояния или минимум затраченного времени.
МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В ЛОГИСТИКЕ
В логистике имеется ряд ситуаций, которые описываются моделями линейного программирования. Эти ситуации формулируются в виде задач. К таким задачам в логистике относятся:
- • транспортная задача;
- •задача на раскрой материалов;
- •задача размещения баз снабжения;
- •задача по оптимизации ассортиментной загрузки производства.
Транспортная задача
Наиболее распространенной является транспортная задача линейного программирования. Эта задача формируется следующим образом:
товары сосредоточенные в т пунктах отправления в количествах а, аг, ат, необходимо доставить в каждый из п пунктов назначения в количествах bj, b2, . bn. Стоимость перевозки товара из i пункта отправления в j пункт назначения равна Су. Следует определить оптимальный план развозки, т.е. найти *у для этого оптимального плана.
В общем виде модель линейного программирования состоит из целевой функции и ограничений (условий). Для транспортной задачи целевая функция имеет следующий вид:
Целевая функция предусматривает минимизацию перевозки всех товаров из пункта i в пункт).
Ограничения показывают, что все имеющиеся товары, сосредоточенные во всех i-x пунктах отправления, должны быть полностью доставлены в требуемых количествах в пункты потребления j.
Пример 1. Сущность транспортной задачи иллюстрируется следующим примером (числа условные):
Имеются следующие количества товаров, находящихся в трех пунктах отправления: а = 6, аг = 8, аз = 10, потребность в этих товарах в следующих четырех пунктах назначения bi = 4, 62 = 6, Ьз = 8, 64 = 6.
Стоимость перевозок из пункта i в пункт j единицы товара представлена в табл. 6.1.
Для решения транспортной задачи предварительно составляется исходный план перевозки по правилу «Северо- западного угла» (табл. 6.2.)
Далее определяется стоимость перевозки по исходному плану
Исходный план с помощью специальных алгоритмов улучшается до оптимального, т.е. когда стоимость перевозки будет минимальна. С этой целью используются такие алгоритмы, как симплекс-метод, метод потенциалов и др.
Используя указанные алгоритмы, получаем оптимальный план развозки продукции (таблица 6.3.) ______Таблица 6.3.
Определяется стоимость перевозки по оптимальному плану:
Алгоритмы решения задач линейного программирования предусматривают перебор возможных вариантов, ориентируясь на целевую функцию и ограничения. Стоймость перевозки по оптимальному варианту — 38 стоимостных единиц, экономия составила 16 стоимостных единиц или 29,6 %.
В реальных условиях транспортная задача линейного программирования применяется в сетевой торговле при развозке товаров с распределительных центров каждому магазину сети, в соответствии с потребностями каждого магазина.
В условиях рыночной экономики, когда действует рынок транспортных услуг, грузоотправители выбирают себе подходящего перевозчика согласно своим критериям оптимальности по Парето и независимо друг от друга. Однако за определенный период времени (например, за год) суммарный объем транспортной работы для совокупности грузоотправителей и грузополучателей установится на оптимальном уровне согласно модели транспортной задачи линейного программирования.