Метод потенциалов

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

История и предпосылки

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

В 1949 году советский математик Леонид Канторович, впоследствии лауреат Нобелевской премии по экономике, предложил метод решения транспортной задачи, основанный на анализе потенциалов пунктов отправления и назначения. Позднее, в 1950-х годах, американские исследователи (в частности, Уильям Воган) развили эти идеи, формализовав алгоритм, известный сегодня как метод потенциалов. В СССР метод получил широкое распространение благодаря работам В. С. Немчинова и других экономистов-математиков.

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

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

F = Σᵢ Σⱼ cᵢⱼ · xᵢⱼ → min

при условии, что все запасы вывезены (Σⱼ xᵢⱼ = aᵢ для всех i) и все потребности удовлетворены (Σᵢ xᵢⱼ = bⱼ для всех j). Задача называется закрытой (сбалансированной), если сумма запасов равна сумме потребностей: Σᵢ aᵢ = Σⱼ bⱼ. В противном случае вводится фиктивный поставщик или потребитель с нулевыми стоимостями перевозок.

Основные этапы метода потенциалов

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

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

Первым шагом находится любое допустимое базисное решение (опорный план). Для этого используются эвристические методы:

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

Количество занятых ячеек (базисных переменных) в опорном плане должно быть равно m + n – 1 (для закрытой задачи). Если их меньше, план называется вырожденным, и требуется введение фиктивных перевозок с нулевым объёмом.

2. Расчёт потенциалов

После построения опорного плана для каждой строки i вводится потенциал uᵢ, а для каждого столбца j — потенциал vⱼ. Для всех занятых ячеек (базисных переменных) должно выполняться условие:

uᵢ + vⱼ = cᵢⱼ

Поскольку число занятых ячеек на единицу меньше числа неизвестных (m + n против m + n – 1), одному из потенциалов присваивается произвольное значение (обычно u₁ = 0), и остальные вычисляются последовательно.

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

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

4. Переход к новому плану

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

Процесс повторяется до тех пор, пока все оценки Δᵢⱼ не станут неотрицательными.

Особенности и модификации

Вырожденность

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

Открытая транспортная задача

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

Многоиндексные задачи

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

Применение

Метод потенциалов широко применяется в логистике, экономике, планировании перевозок, управлении цепями поставок. Он позволяет оптимизировать маршруты доставки товаров, распределение ресурсов между предприятиями, минимизировать транспортные расходы. В СССР метод активно использовался при планировании грузопотоков в рамках народного хозяйства. В современных условиях метод реализован во многих программных продуктах (например, в Microsoft Excel через надстройку «Поиск решения», в специализированных системах управления транспортом).

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

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

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

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

• Леонид Канторович получил Нобелевскую премию по экономике в 1975 году «за вклад в теорию оптимального распределения ресурсов», и транспортная задача с методом потенциалов была одним из ключевых примеров его работ.
• Метод потенциалов часто изучается в курсах экономико-математического моделирования и исследования операций как классический пример применения двойственности в линейном программировании.
• В некоторых учебниках метод потенциалов называют «методом Канторовича — Хичкока», хотя сам Канторович использовал несколько иной подход.

Источники

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