Метод минимальной стоимости

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

История возникновения

Транспортная задача как класс задач линейного программирования была формализована в 1940-х годах в работах советского математика Леонида Канторовича и американского учёного Джорджа Данцига. Метод минимальной стоимости как один из способов построения опорного плана был предложен в середине XX века в рамках развития методов решения транспортных задач. Он пришёл на смену более простому, но менее эффективному методу «северо-западного угла», который не учитывал стоимость перевозок. Метод минимальной стоимости стал стандартным инструментом в учебных курсах по исследованию операций и экономико-математическому моделированию.

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

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

Алгоритм выполнения

1. Инициализация. Составляется транспортная таблица размером \( m \times n \), где \( m \) — число поставщиков, \( n \) — число потребителей. В каждой клетке указана стоимость перевозки \( c_{ij} \). Заданы запасы \( a_i \) и потребности \( b_j \).
2. Выбор клетки. Среди всех незаполненных клеток находится клетка с минимальным значением \( c_{ij} \). Если таких клеток несколько, выбирается любая из них (например, первая по порядку).
3. Назначение перевозки. В выбранную клетку записывается значение \( x_{ij} = \min(a_i, b_j) \).
4. Обновление данных. Из запаса \( a_i \) вычитается \( x_{ij} \), из потребности \( b_j \) вычитается \( x_{ij} \).
5. Исключение строки или столбца. Если после шага 4 запас поставщика \( a_i \) стал равен нулю, строка \( i \) исключается из дальнейшего рассмотрения. Если потребность потребителя \( b_j \) стала равна нулю, столбец \( j \) исключается. В случае одновременного обнуления (вырожденный случай) исключается только одна строка или один столбец, а в оставшейся клетке записывается нулевая перевозка (базисный ноль).
6. Повторение. Шаги 2–5 повторяются, пока не будут заполнены все \( m + n - 1 \) базисных клеток (или пока не будут исчерпаны все запасы и потребности).

Пример применения

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

1. Минимальный тариф — 1 (клетки (1,3) и (2,2)). Выбираем (1,3). Назначаем \( x_{13} = \min(50, 40) = 40 \). Запас поставщика 1 становится 10, потребность потребителя 3 — 0. Столбец 3 исключается.
2. Среди оставшихся клеток минимальный тариф — 2 (клетка (1,1)). Назначаем \( x_{11} = \min(10, 30) = 10 \). Запас поставщика 1 — 0, потребность потребителя 1 — 20. Строка 1 исключается.
3. Остались клетки (2,1) и (2,2). Минимальный тариф — 1 (клетка (2,2)). Назначаем \( x_{22} = \min(60, 40) = 40 \). Запас поставщика 2 — 20, потребность потребителя 2 — 0. Столбец 2 исключается.
4. Осталась клетка (2,1) с тарифом 4. Назначаем \( x_{21} = \min(20, 20) = 20 \). Все запасы и потребности исчерпаны.

Получен опорный план: \( x_{11}=10, x_{13}=40, x_{21}=20, x_{22}=40 \). Суммарная стоимость перевозок: \( 10 \cdot 2 + 40 \cdot 1 + 20 \cdot 4 + 40 \cdot 1 = 20 + 40 + 80 + 40 = 180 \) единиц.

Сравнение с другими методами

Метод минимальной стоимости занимает промежуточное положение между методом северо-западного угла и методом аппроксимации Фогеля.

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

Ограничения и особенности

Метод минимальной стоимости не является точным и не гарантирует оптимальность полученного плана. Для нахождения оптимального решения требуется дополнительное применение метода потенциалов или симплекс-метода. В некоторых случаях, особенно при наличии большого числа одинаковых тарифов, метод может давать планы, далёкие от оптимальных.

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

Применение

Метод минимальной стоимости широко используется в учебном процессе при изучении транспортных задач в курсах исследования операций, логистики и экономико-математического моделирования. В практической логистике он применяется для быстрого получения начального плана перевозок, который затем оптимизируется с помощью специализированного программного обеспечения (например, в системах SAP, Oracle Transportation Management, отечественных разработках типа «1С:Логистика»). Метод также может быть адаптирован для решения задач распределения ресурсов, назначения и других задач комбинаторной оптимизации.

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

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

Источники

• Канторович Л. В. Математические методы организации и планирования производства. — Л.: Изд-во ЛГУ, 1939.
• Данциг Дж. Линейное программирование, его обобщения и применения. — М.: Прогресс, 1966.
• Таха Х. Введение в исследование операций. — М.: Вильямс, 2005.
• Акулич И. Л. Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986.
• Кузнецов А. В., Сакович В. А., Холод Н. И. Высшая математика: Математическое программирование. — Минск: Вышэйшая школа, 1994.