Общая характеристика метода потенциалов

Транспортная задача, в которой имеет место равенство (4), называется закрытой и может быть решена как задача линейного программирования с помощью симплексного метода. Однако благодаря особенностям переменных задачи и системы ограничений разработаны специальные, менее громоздкие методы ее решения. Наиболее применяемым методом является метод потенциалов, при котором для каждой i-й строки (i-го поставщика) определяется потенциал u_i, а для каждого столбца j - потенциал v_j. Сумма потенциалов для перевозки груза от i-го поставщика к j-му потребителю должна быть равна величине транспортных расходов c_ij, т.е. быть оценена с точки зрения критерия решаемой задачи:

c_ij=v_j+u_i (5)

Если баланс (4) не выполняется, то ограничения (1) или (2) имеют вид неравенств типа «меньше или равно»; транспортная задача в таком случае называется открытой. Для решения открытой транспортной задачи методом потенциалов ее сводят к закрытой задаче путем ввода фиктивного потребителя, если в неравенства превращаются условия (2), или фиктивного поставщика в случае превращения в неравенства ограничений (1).

Рассмотрим этапы реализации метода потенциалов для закрытой транспортной задачи. Прежде всего следует отметить, что при условии баланса (4) ранг системы линейных уравнений (1), (2) равен т + п - 1; таким образом из общего числа (m ´ n) неизвестных базисных неизвестных будет (т + п – 1). Вследствие этого при любом допустимом базисном распределении в матрице перевозок, представленной в общем виде в табл. 9, будет занято ровно т + п - 1 клеток, которые будем называть базисными в отличие от остальных свободных клеток. Коэффициент целевой функции в занятых клетках будем выделять полукругом.

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

Таблица 9 – Матрица планирования перевозок груза