Метод потенциалов
Общий принцип определения оптимального плана транспортной задачи методом потенциалов: сначала находят опорный план транспортной задачи, а затем его последовательно улучшают до получения оптимального плана.
Для определения опорного плана транспортной задачи будем пользоваться одним из методов, рассмотренных выше. Эти методы гарантируют получение m+n-1 занятых клеток в исходной таблице условий, причем в некоторых из них могут стоять нули. Полученный таким образом план следует проверить на оптимальность.
Теорема 1.2.
Если для некоторого опорного плана X*=(xij*) (i=1,m; j=1,n) транспортной задачи существуют такие числа U1, U2, . . . , Um, V1, V2, . . . , Vn, что
Vj- Ui=cij при xij>0
Vj- Ui<=cij при xij=0
для всех (i=1,m) и (j=1,n), то X*=(xij*) - оптимальный план транспортной задачи.
Определение 1. 3.
Числа Ui и Vj (i=1,m; j=1,n) называются потенциалами соответственно пунктов назначения и пунктов отправления.
Сформулированная теорема позволяет построить алгоритм нахождения решения транспортной задачи
. Он состоит в следующем.
1. Пусть одним из рассмотренных выше методов найдет опорный план транспортной задачи. Для каждого из пунктов отправления и назначения определяются потенциалы Ui и Vj (i=1,m; j=1,n). Эти числа находят из системы уравнений
Uj- Vi=cij
где cij - тарифы, стоящие в заполненных клетках таблицы условий транспортной задачи.
. Так как число заполненных клеток равно m+n-1, то система с m+n неизвестными содержит m+n-1 уравнений.
Поскольку число неизвестных превышает на единицу число уравнений, одно из неизвестных можно положить равным произвольному числу, например α1=0, и найти последовательно из уравнений значения остальных неизвестных.
. После того как все потенциалы найдены, для каждой из свободных клеток определяют числа Δij=Vj- Ui-cij.
4. Если среди чисел Δij (i=1,m; j=1,n) нет положительных, то найденный опорный план является оптимальным.
Если же для некоторой свободной клетки Δij>0, то исходный опорный план не является оптимальным и необходимо перейти к новому опорному плану.
Для этого рассматривают все свободные клетки, для которых Δij>0, и среди данных чисел выбирают максимальное. Клетку, которой соответствует это число, следует заполнить.
Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде других занятых клеток и связанных с заполняемой клеткой, так называемым циклом.
Определение 1.4.
Циклом
в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое в столбце.
Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами.
Примеры некоторых циклов показаны на рис. 1
При правильном построении опорного плана для любой свободной клетки можно построить лишь один цикл. После того как для выбранной свободной клетки он построен, следует перейти к новому опорному плану. Для этого необходимо переместить грузы в пределах клеток, связанных циклом с данной свободной клеткой.
Это перемещение производят по следующим правилам:
) каждой из клеток, связанных циклом с данной свободной клеткой, приписывают определенный знак, причем свободной клетке - знак плюс, а всем остальным клеткам - поочередно знаки минус и плюс (будем называть эти клетки минусовыми и плюсовыми);
) в данную свободную клетку переносят меньшее из чисел xij, стоящих в минусовых клетках. Одновременно это число прибавляют к соответствующим числам, стоящим в плюсовых клетках, и вычитают из чисел, стоящих в минусовых клетках. Клетка, которая ранее была свободной, становиться занятой, а минусовая клетка, в которой стояло минимальное из чисел xij, считается свободной.