Опорный план перевозок

Опорный план перевозок — это допустимое базисное решение транспортной задачи линейного программирования, которое удовлетворяет всем ограничениям модели (балансу поставок и потребностей) и содержит не более \( m + n - 1 \) ненулевых поставок (где \( m \) — количество пунктов отправления, \( n \) — количество пунктов назначения). Опорный план является начальным этапом поиска оптимального решения и служит основой для применения методов его последовательного улучшения, таких как метод потенциалов или распределительный метод.

Сущность и назначение

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

• обеспечивает выполнение всех балансовых ограничений (сумма поставок от каждого поставщика равна его запасу, сумма поставок каждому потребителю равна его потребности);
• не содержит циклов (то есть не является линейно зависимым);
• включает не более \( m + n - 1 \) занятых клеток (базисных переменных).

Опорный план не обязательно является оптимальным по стоимости, но он гарантированно допустим и служит отправной точкой для итеративного улучшения. В случае вырожденности (количество занятых клеток меньше \( m + n - 1 \)) в план вводятся фиктивные нулевые поставки.

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

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

Метод северо-западного угла

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

Преимущества: простота, отсутствие необходимости в расчёте стоимостей. Недостатки: высокая начальная стоимость, так как маршруты выбираются без учёта тарифов.

Метод минимальной стоимости (метод наименьшего элемента)

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

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

Метод Фогеля (метод аппроксимации Фогеля)

Считается наиболее точным среди эвристических методов. Для каждой строки и каждого столбца вычисляется штраф — разность между двумя наименьшими тарифами в этой строке или столбце. Выбирается строка или столбец с максимальным штрафом, и в клетку с наименьшей стоимостью в этой строке/столбце помещается максимально возможная поставка. После корректировки запасов и потребностей штрафы пересчитываются.

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

Метод двойного предпочтения

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

Пример построения опорного плана

Рассмотрим транспортную задачу с двумя поставщиками (запасы 50 и 60 единиц) и тремя потребителями (потребности 30, 40, 40 единиц). Тарифы (стоимость перевозки единицы груза) заданы матрицей:

Метод северо-западного угла: Начинаем с клетки A1B1. Запас A1 = 50, потребность B1 = 30 → ставим 30. Остаток A1 = 20, B1 закрыт. Переходим к A1B2. Потребность B2 = 40, остаток A1 = 20 → ставим 20. A1 исчерпан. Переходим к A2B2. Потребность B2 осталась 20, запас A2 = 60 → ставим 20. B2 закрыт. Переходим к A2B3. Потребность B3 = 40, остаток A2 = 40 → ставим 40. План: (30, 20, 0; 0, 20, 40). Стоимость = 30·2 + 20·3 + 20·2 + 40·5 = 60 + 60 + 40 + 200 = 360.

Метод минимальной стоимости: Наименьший тариф 1 (A1B3). Ставим min(50, 40) = 40. B3 закрыт, остаток A1 = 10. Следующий наименьший тариф 2 (A1B1 и A2B2). Выбираем A1B1: ставим min(10, 30) = 10. A1 исчерпан, остаток B1 = 20. Далее A2B2: ставим min(60, 40) = 40. B2 закрыт, остаток A2 = 20. Последняя клетка A2B1: ставим 20. План: (10, 0, 40; 20, 40, 0). Стоимость = 10·2 + 40·1 + 20·4 + 40·2 = 20 + 40 + 80 + 80 = 220.

Метод Фогеля: Вычисляем штрафы: строка A1: |2-1| = 1, строка A2: |2-4| = 2, столбец B1: |2-4| = 2, B2: |2-3| = 1, B3: |1-5| = 4. Максимальный штраф 4 — столбец B3. В нём наименьший тариф 1 (A1B3). Ставим 40. B3 закрыт. Пересчёт: строка A1: |2-3| = 1, A2: |2-4| = 2, B1: |2-4| = 2, B2: |2-3| = 1. Максимальный штраф 2 — строка A2 или столбец B1. Выбираем A2: наименьший тариф 2 (A2B2). Ставим min(60, 40) = 40. B2 закрыт, остаток A2 = 20. Далее A1B1: ставим min(10, 30) = 10. A1 исчерпан. Остаток A2B1: 20. План: (10, 0, 40; 20, 40, 0). Стоимость = 220 (совпала с методом минимальной стоимости в данном примере).

Свойства опорного плана

• Допустимость: все ограничения задачи выполнены.
• Базисность: количество занятых клеток равно \( m + n - 1 \) (или меньше при вырожденности).
• Отсутствие циклов: набор занятых клеток не образует замкнутых маршрутов, что гарантирует линейную независимость соответствующих векторов условий.
• Неоптимальность (в общем случае): опорный план, как правило, не является оптимальным, за исключением случаев, когда он совпадает с оптимальным решением.

Вырожденность опорного плана

Вырожденным называется опорный план, в котором количество занятых клеток меньше \( m + n - 1 \). Это происходит, когда на каком-то шаге построения одновременно обнуляются запас поставщика и потребность потребителя. Для продолжения оптимизации в план вводятся фиктивные нулевые поставки (обычно в клетки с наименьшими тарифами среди свободных), которые не меняют стоимость, но восстанавливают базисность.

Применение

Опорный план перевозок является обязательным этапом решения транспортной задачи в логистике, планировании грузоперевозок, управлении цепями поставок, распределении ресурсов. В промышленности и торговле он используется для минимизации транспортных расходов при заданных объёмах производства и потребления. В учебных курсах по исследованию операций и методам оптимизации построение опорного плана рассматривается как базовый навык.

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

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

Источники

• Акулич И. Л. Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986.
• Таха Х. А. Введение в исследование операций. — М.: Вильямс, 2005.
• Кузнецов А. В., Сакович В. А., Холод Н. И. Сборник задач по математическому программированию. — Минск: Вышэйшая школа, 1990.
• Юдин Д. Б., Гольштейн Е. Г. Задачи и методы линейного программирования. — М.: Советское радио, 1964.