Транспортные модели линейного программирования - это варианты решения задачи по определению оптимального плана перевозок грузов из пунктов отправления в пункты назначения с минимальными затратами на перевозки.
Понятие и содержание транспортной задачи
Решению экстремальных задач, то есть задач по определению максимальных или минимальных значений на заданном множестве, посвящена специальная математическая дисциплина – линейное программирование. В рамках линейного программирования рассматривают несколько задач специального вида, решение которых имеет четко выраженное практическое значение. Одной из таких задач является транспортная задача.
Суть транспортной задачи сводится к составлению оптимального плана перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. По теории сложности вычислений транспортная задача относится к классу сложности P, для которого существует «быстрые» алгоритмы решений задач.
Основные условия транспортной задачи в ее классическом виде заключаются в осуществлении перевозки со следующими характеристиками:
- перевозки однородного продукта;
- перевозки из однородных пунктов наличия;
- перевозки в однородные пункты потребления;
- перевозки на однородных транспортных средствах (предопределенном количестве);
- перевозки со статичными данными и линеарном подходе.
Обычно выделяют два типа классической транспортной задачи. Решение задач первого типа связано с критерием стоимости (т. е. стремятся достичь минимум затрат на перевозку) или расстояний. Решение задач второго типа связано с критерием времени (т. е. стремятся достичь минимум времени на перевозку).
Транспортной задачей может быть обозначен широкий круг задач с единой математической моделью, которые относятся к задачам линейного программирования и решаются через применение оптимального метода. Однако решение транспортной задачи может быть существенно упрощено благодаря специальному методу, поскольку разработка транспортной задачи велась с целью минимизации стоимости перевозок.
Методы решения транспортной задачи
Классическую транспортную задачу можно решить симплекс-методом. Этот метод предполагает перебор вершин выпуклого многогранника в многомерном пространстве. Иными словами, строятся базисные решения, на которых монотонно убывает линейная функция, до ситуации выполнения необходимых условий локальной оптимальности.
В силу ряда особенностей транспортные задачи малой размерности могут быть решены проще, чем через применение симплекс-метода.
План перевозок, сформулированный во время решения транспортной задачи, может быть постепенно (итерационно) улучшен. Для этого возможно использование следующих методов:
- метод северо-западного угла (диагональный или улучшенный);
- метод минимального (наименьшего) элемента;
- метод двойного предпочтения;
- метод аппроксимации Фогеля;
- метод падающего камня
- метод потенциалов.
Первые четыре метода направлены на определение опорного плана перевозок. Затем найденный план улучшают путем применения одного из последних двух методов, тем самым, приближая план перевозок к оптимальному.
Транспортная задача еще может быть решена при помощи теории графов. В данном случае рассматривают множество точек, которые соединяются друг с другом множеством линей. В отношении транспортной задачи рассматривается двудольный граф, в котором пункты производства находятся в верхней доле, а пункты потребления — в нижней.
Виды транспортной задачи
Практика решения транспортной задачи привела к формулированию нескольких обобщений, которые вызваны практическими потребностями логистической деятельности хозяйствующих субъектов. В качестве примеров можно назвать следующие разновидности транспортной задачи:
- Транспортная задача в сетевой постановке.
- Транспортная задача с ограничениями пропускной способности.
- Многопродуктовая транспортная задача.
В рамках транспортной задачи в сетевой постановке все пункты равноправны, т. е. подразделения на пункты отправления и пункты потребления не происходит. В то же время производство описывается при помощи положительного числа, а потребление — отрицательного. Предполагается, что перевозки осуществляются по заданной сети, в которой дугами могут быть соединены любые пункты (в том числе, два производителя или два потребителя). Эта задача решается практически так же, как и классическая задача - слегка измененным методом потенциалов.
Транспортная задача с ограничениями пропускной способности является частным вариантом транспортной задачи в сетевой постановке. Ее особенностью является наличие ограничения по максимальной пропускной способности некоторых дуг, которыми соединяются между собой пункты. Решение этой задачи требует применение слегка усложненного метода потенциалов.
Многопродуктовая транспортная задача, как видно из названия, исходит из наличия нескольких продуктов. При этом один и тот же пункт может производить или потреблять одновременно несколько продуктов. В отношении некоторых дуг может быть установлено ограничение на пропускную способность. В случае отсутствия данного ограничения задача распадается на несколько отдельных задач по продуктам. Задача решается при помощи симплекс-метода.
Таким образом, одной из базовых задач линейного программирования является транспортная задача. Необходимость ее формулирования и решения во многом объясняется логистическими потребностями хозяйствующих субъектов, а именно - подготовкой и организацией проведения грузовых перевозок оптимальным способом. Под оптимальностью в данном случае понимают минимум понесенных расходов, минимум преодоленного расстояния или минимум затраченного времени.
