Транспортная задача

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

История

Первая математическая постановка транспортной задачи была предложена французским математиком Гаспаром Монжем в 1781 году в работе «О выемке и насыпке земли» (фр. Mémoire sur la théorie des déblais et des remblais). Монж рассматривал задачу перемещения грунта при строительстве фортификационных сооружений, стремясь минимизировать суммарную работу (произведение массы на расстояние). Однако его работа носила скорее теоретический характер и не содержала эффективных алгоритмов решения.

Современная формулировка транспортной задачи в виде задачи линейного программирования была разработана в 1941 году американским математиком Фрэнком Л. Хичкоком. В 1947 году Джордж Данциг, создатель симплекс-метода, показал, что транспортная задача может быть решена этим универсальным методом, но из-за её специфической структуры (матрица ограничений состоит из единиц и нулей) были разработаны более эффективные специализированные алгоритмы. В 1949 году американский математик Тьяллинг Купманс, впоследствии лауреат Нобелевской премии по экономике, независимо сформулировал транспортную задачу в контексте экономического планирования и анализа затрат. В 1951 году Джордж Данциг и Филип Вулф разработали метод потенциалов (модифицированный распределительный метод), который до сих пор остаётся основным алгоритмом для решения транспортных задач вручную или в учебных целях.

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

Пусть имеется m поставщиков (пунктов отправления) с запасами однородного груза a₁, a₂, …, aₘ и n потребителей (пунктов назначения) с потребностями b₁, b₂, …, bₙ. Известна матрица транспортных издержек cᵢⱼ — стоимость перевозки единицы груза от i-го поставщика к j-му потребителю. Необходимо найти план перевозок — матрицу xᵢⱼ (количество груза, перевозимого от i-го поставщика к j-му потребителю), минимизирующий суммарные транспортные издержки:

\[ Z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \to \min \]

при следующих ограничениях:

• Каждый поставщик может отгрузить не более своего запаса: \(\sum_{j=1}^{n} x_{ij} = a_i\) для всех i = 1, …, m.
• Каждый потребитель должен получить не менее своей потребности: \(\sum_{i=1}^{m} x_{ij} = b_j\) для всех j = 1, …, n.
• Объёмы перевозок неотрицательны: \(x_{ij} \ge 0\) для всех i, j.

Условие баланса

Транспортная задача называется закрытой (сбалансированной), если суммарные запасы всех поставщиков равны суммарным потребностям всех потребителей: \[ \sum_{i=1}^{m} a_i = \sum_{j=1}^{n} b_j \] В этом случае ограничения выполняются как равенства. Если баланс не соблюдается, задача называется открытой. Для её решения вводят фиктивного поставщика (при избытке потребностей) или фиктивного потребителя (при избытке запасов) с нулевыми или штрафными тарифами на перевозку.

Классификация и виды

Транспортные задачи классифицируются по нескольким признакам:

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

Методы решения

Для решения транспортной задачи разработано несколько классов методов.

Методы построения начального опорного плана

• Метод северо-западного угла: самый простой, но далёкий от оптимального план. Заполнение таблицы начинается с левой верхней ячейки.
• Метод наименьшей стоимости: на каждом шаге выбирается ячейка с минимальной стоимостью перевозки и заполняется максимально возможным объёмом. Даёт более близкий к оптимуму план.
• Метод Фогеля (аппроксимации Фогеля): учитывает разницу между двумя наименьшими стоимостями в каждой строке и столбце. Считается одним из лучших эвристических методов для ручного расчёта.

Методы оптимизации (нахождения оптимального плана)

• Распределительный метод (метод потенциалов): классический итеративный метод. На каждой итерации для текущего плана рассчитываются потенциалы поставщиков и потребителей, затем проверяется условие оптимальности. Если условие не выполняется, строится цикл перераспределения и план улучшается. Метод гарантирует нахождение глобального оптимума за конечное число шагов.
• Венгерский метод: используется для решения задач о назначениях (частный случай транспортной задачи, когда m = n и все объёмы равны единице). Основан на теории двойственности.
• Симплекс-метод: универсальный метод, но для транспортной задачи его применение менее эффективно из-за большого количества переменных и ограничений.
• Методы линейного программирования: современные программные пакеты (например, CPLEX, Gurobi, SciPy, MATLAB) решают транспортную задачу как частный случай задачи линейного программирования, используя специализированные алгоритмы.

Применение

Транспортная задача и её модификации находят широкое применение в различных сферах:

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

Интересные факты

• Транспортная задача является частным случаем более общей задачи о потоках в сети. Если представить поставщиков и потребителей как узлы сети, а маршруты — как дуги с пропускной способностью, то задача сводится к поиску потока минимальной стоимости.
• Для транспортной задачи существует свойство целочисленности: если все запасы и потребности являются целыми числами, то оптимальный план перевозок также будет целочисленным. Это свойство не выполняется для общей задачи линейного программирования.
• В 1975 году Тьяллинг Купманс получил Нобелевскую премию по экономике (совместно с Леонидом Канторовичем) за вклад в теорию оптимального распределения ресурсов, в том числе за разработку математического аппарата транспортной задачи.
• В СССР транспортная задача активно применялась при планировании народного хозяйства, в частности, для оптимизации перевозок угля, нефти, леса и других массовых грузов. Леонид Канторович, советский математик и экономист, внёс значительный вклад в теорию линейного программирования и её применение в плановой экономике.

Критика и ограничения

Несмотря на широкое применение, классическая транспортная задача имеет ряд ограничений:

• Предположение о линейности: стоимость перевозки считается пропорциональной объёму груза, что не всегда соответствует реальности (скидки за объём, плата за порожний пробег, фиксированные затраты на маршрут).
• Однородность груза: задача предполагает, что груз однороден и неделим, что не подходит для случаев с разными видами товаров, требующих разных условий перевозки.
• Статичность: классическая постановка не учитывает изменения спроса, предложения или тарифов во времени.
• Игнорирование временных ограничений: задача минимизирует только стоимость, но не учитывает время в пути, срочность доставки или штрафы за просрочку.
• Упрощение логистики: не учитываются такие факторы, как перегрузка, хранение на складах, обратные рейсы, совмещение грузов разных типов.

Для преодоления этих ограничений разработаны многочисленные модификации: транспортная задача с ограничениями на время, многопродуктовая транспортная задача, задача с фиксированными затратами, динамическая транспортная задача и другие.

Источники

• Данциг Дж. Линейное программирование, его применения и обобщения. — М.: Прогресс, 1966.
• Канторович Л. В. Экономический расчёт наилучшего использования ресурсов. — М.: Издательство АН СССР, 1959.
• Хемди А. Таха. Введение в исследование операций. — 10-е изд. — М.: Вильямс, 2016.
• Вагнер Г. Основы исследования операций. — М.: Мир, 1972.
• Кофман А., Анри-Лабордер А. Методы и модели исследования операций. — М.: Мир, 1977.