Метод транспортных затрат

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

Сущность метода

Метод транспортных затрат основан на построении начального опорного плана (базисного распределения) и его последовательном улучшении с помощью специальных критериев оптимальности. В отличие от общего симплекс-метода, он использует упрощённые правила перехода от одного базисного решения к другому, что делает его особенно удобным для ручных расчётов и задач малой размерности.

Основные понятия

• Транспортная таблица — матрица размером m×n, где m — количество поставщиков, n — количество потребителей. В каждой клетке (i, j) указывается объём перевозки xᵢⱼ и стоимость перевозки единицы груза cᵢⱼ.
• Опорный план — допустимое решение, в котором количество занятых перевозками клеток (базисных переменных) равно m + n − 1. Остальные клетки считаются свободными (нулевые перевозки).
• Потенциалы — вспомогательные числа uᵢ (для поставщиков) и vⱼ (для потребителей), которые вычисляются для оценки оптимальности текущего плана.

Этапы метода

1. Построение начального опорного плана

Существует несколько способов получения первого допустимого распределения. Наиболее распространённые:

• Метод северо-западного угла — заполнение таблицы начинается с левой верхней клетки. Перевозки назначаются максимально возможными, пока не исчерпается предложение или спрос. Этот метод прост, но часто даёт далёкое от оптимального решение.
• Метод минимальной стоимости — приоритет отдаётся клеткам с наименьшей стоимостью перевозки. Позволяет получить более близкое к оптимуму начальное решение, чем метод северо-западного угла.
• Метод Фогеля — основан на штрафах за неиспользование наименьших стоимостей. Считается наиболее точным среди эвристических методов построения начального плана.

2. Проверка плана на оптимальность

Для каждой свободной клетки (i, j) вычисляется оценка Δᵢⱼ = cᵢⱼ − (uᵢ + vⱼ). Если все Δᵢⱼ ≥ 0, текущий план является оптимальным. Если хотя бы одна Δᵢⱼ < 0, план неоптимален и требует улучшения.

Потенциалы uᵢ и vⱼ определяются из системы уравнений для занятых клеток: uᵢ + vⱼ = cᵢⱼ. Обычно одному из потенциалов (например, u₁) присваивается произвольное значение (чаще 0), после чего остальные вычисляются последовательно.

3. Улучшение плана (перераспределение)

Выбирается свободная клетка с наименьшей отрицательной оценкой (наиболее «невыгодная»). Для неё строится замкнутый цикл — многоугольник, вершины которого находятся в занятых клетках, а одна из вершин — в выбранной свободной. Вдоль цикла производится перераспределение груза: в вершинах цикла попеременно прибавляется и вычитается минимальное значение из тех клеток, где стоит знак «−». После этого план корректируется, и процедура повторяется с шага 2.

Применение

Метод транспортных затрат широко используется в логистике, экономике, планировании производства и распределении ресурсов. Типичные задачи:

• Оптимизация грузоперевозок — минимизация затрат на доставку товаров от складов до магазинов.
• Распределение сырья — определение маршрутов поставок от поставщиков к заводам.
• Планирование перевозок в сельском хозяйстве — доставка удобрений, зерна, техники.
• Управление цепочками поставок — нахождение баланса между предложением и спросом при ограниченных транспортных мощностях.

Метод лёг в основу многих алгоритмов, используемых в программных продуктах для транспортного планирования (например, в модулях SAP, 1С, специализированных логистических системах).

Разновидности и обобщения

• Закрытая транспортная задача — суммарное предложение равно суммарному спросу. Если это условие не выполняется, задача называется открытой и требует введения фиктивного поставщика или потребителя.
• Метод потенциалов — формальное название алгоритма, основанного на вычислении потенциалов и циклов.
• Модифицированный распределительный метод — использует матрицу оценок, вычисляемую через обратную матрицу базиса, что ускоряет расчёты при компьютерной реализации.
• Транспортная задача с промежуточными пунктами — обобщение, включающее транзитные склады или перевалочные пункты.

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

Метод транспортных затрат имеет ряд недостатков:

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

Несмотря на эти ограничения, метод остаётся классическим инструментом обучения основам линейного программирования и часто применяется в учебных курсах по логистике и экономико-математическому моделированию.

Историческая справка

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

Пример расчёта (упрощённый)

Рассмотрим задачу с двумя поставщиками (А₁ и А₂) и двумя потребителями (В₁ и В₂). Предложение: А₁ = 100 ед., А₂ = 150 ед. Спрос: В₁ = 120 ед., В₂ = 130 ед. Стоимости: c₁₁ = 5, c₁₂ = 7, c₂₁ = 4, c₂₂ = 6.

1. Начальный план (метод северо-западного угла): x₁₁ = 100, x₁₂ = 0, x₂₁ = 20, x₂₂ = 130. Стоимость: 100·5 + 20·4 + 130·6 = 500 + 80 + 780 = 1360.
2. Потенциалы: u₁ = 0, v₁ = 5, v₂ = 7 (из занятых клеток). Для свободной клетки (2,1): Δ₂₁ = 4 − (u₂ + v₁) = 4 − (u₂ + 5). Из занятой клетки (2,2): u₂ + v₂ = 6 → u₂ = −1. Тогда Δ₂₁ = 4 − (−1 + 5) = 0. План оптимален.

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

Источники

• Канторович Л. В. Математические методы организации и планирования производства. — Л.: Изд-во ЛГУ, 1939.
• Данциг Дж. Линейное программирование, его обобщения и применения. — М.: Прогресс, 1966.
• Таха Х. А. Введение в исследование операций. — М.: Вильямс, 2005.
• Акулич И. Л. Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986.
• Хичкок Ф. Распределение продукции от нескольких источников к нескольким потребителям // Journal of Mathematics and Physics, 1941.