Транспортная задача: методы северо-западного угла и потенциалов

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

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

Второй этап решения заключается в последовательном улучшении найденного опорного плана до достижения абсолютного оптимума. Для этой цели применяется метод потенциалов (модифицированный метод распределения, MODI). Суть метода заключается в присвоении каждому поставщику и потребителю специальных числовых оценок — потенциалов (u для строк и v для столбцов). Для всех занятых (базисных) ячеек таблицы должно строго выполняться условие: сумма потенциалов строки и столбца равна тарифу данной ячейки (u + v = c). Решая систему линейных уравнений, аналитик вычисляет потенциалы для всей матрицы. Затем проверяется условие оптимальности для пустых (свободных) ячеек: если для какой-либо пустой ячейки сумма потенциалов превышает реальный тариф перевозки, текущий план не является оптимальным.

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