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

Метод потенциалов позволяет, исходя из некоторого опорного плана, построить за конечное число итераций решение Т-задачи.

Общая схема метода такова. В данном начальном опорном плане перевозок каждому пункту ставят в соответствие некоторое число, называемое его предварительным потенциалом. Предварительные потенциалы выбирают так, чтобы их разность для любой пары пунктов A _i i B _j, связанных основной коммуникацией, была равна c_ij. Если окажется, что разность предварительных потенциалов для всех других коммуникаций не превосходит c_ij, то данный план перевозок – оптимальное решение задачи. В противном случае указывают способ улучшения текущего плана Т-задачи.

Описание алгоритма метода потенциалов. Алгоритм складывается из предварительного этапа и конечного числа однотипных итераций.

На предварительном этапе строят начальный опорный план и составляют матрицу С1.

Предварительный этап. С помощью известного метода (например северо-западного угла или минимального элемента) определяют начальный опорный план Х ₀ и вычисляют предварительные потенциалы .

Первый этап. Вычисляют матрицу С _{k +1}. Преобразвание матрицы С _k в матрицу С _{k +1} состоит в следующем. Выбирают наибольший по модулю отрицательный элемент С _k

Пусть это элемент . Тогда вычеркивают (или выделяют) строку , в которой он содержится. Просматривают эту строку и отыскивают множество существенных его элементов. Х _k -существенными элементами называют те элементы =0, которые отвечают базисным элементам плана Х _k т.е. для которых . Вычеркивают столбцы, которые содержат эти элементы. Далее просматривают вычеркнутые столбцы и ищут в них новые существенные элементы, которые лежат в строках отличных от уже вычеркнутых ранее. Если такие элементы имеются, то вычеркивают строки, в которых они содержатся. Процесс выделения продолжают до тех пор, пока очередное множество новых существенных элементов не окажется пустым. Поскольку каждые строка и столбец не могут быть выделены дважды, то весь процесс заканчивается не более чем за l =m+ n – 1 шагов. Далее строят матрицу С _{k +1}. Для этого величину прибавляют ко всем элементам выделенных строк и вычитают из элементов всех выделенных столбцов матрицы С _k. При этом все существенные элементы матрицы С _k остаются равными нулю, а кроме того, в нуль превращается и элемент .

Если все элементы матрицы С _{k +1} окажутся неотрицательными, то X _k – оптимальный план, и на этом процесс заканчивается. В противном случае переходят ко второму этапу.

Второй этап. Цель этого этапа – построить более экономичный план Х _{k +1}. Выбирают наибольший по модулю отрицательный элемент матрицы С _{k +1}.