Алгоритм расчета потенциалов

 

В данном алгоритме введен механизм пометок. Строка или столбец помечены знаком '+', если соответствующий потенциал найден, знаком '–' в противном случае.

В начале все строки и столбцы таблицы помечаем символом '–'

1 – ый шаг. u ₁:=0, 1–ую строку помечаем символом '+' (это означает, что потенциал для данной строки найден).

k – ый шаг.

a) Для каждой строки i, помеченной символом '+', выполнить:

для каждого столбца j =1,2,3,..., n такого, что клетка (i, j) базисная и j – ый столбец помечен символом '–' v_j:= u_i+c_ij,столбец помечаем символом '+'.

b) Для каждого столбца j, помеченного символом '+', выполнить:

для каждой строки i= 1,2,3,..., n такой, что клетка (i, j)базисная, и i –я строка помечена символом '–' u_i:= v_j–c_ij,строку помечаем символом '–'.

k – шаг выполняем до тех пор, пока все строки и столбцы не станут помеченными символами '+'.

 

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

Для того, чтобы базисное решение x_ij, i= 1,2,3,..., m, j= 1,2,3,..., n,было оптимальным, необходимо и достаточно, чтобы для всех i= 1,2,3,..., m, j= 1,2,3,..., n было справедливо неравенство d_ij = v_j–u_i–c_ij £0. Таким образом, для проверки найденного решения на оптимальность достаточно выполнить следующий алгоритм

1. Для всех i= 1,2,3,..., m, j= 1,2,3,..., n положить d_ij = v_j–u_i–c_ij.

2. Найти такие (k, p), что d _kp =max{ d_ij| i= 1,2,3,..., n, j= 1,2,3,..., m }

3. Если d_kp £0, то полученное базисное решение является оптимальным и транспортная задача решена, иначе необходимо перейти к новому базису.

Алгоритм перехода к новому базису.

Вводим в базис клетку (k, p). Для определения клетки (q, l), выводимой из базиса, воспользуемся следующим алгоритмом:

1. Строим последовательность клеток

П ={(i ₁, j 1), (i ₂, j ₂), ... (i, j), ...)}такую, что

a) (k, p)Î П;

b) все остальные клетки базисные;

с) последовательность П образует цикл (смотри транспортную задачу в сетевой постановке).

2. Задаем направление обхода этого цикла, совпадающего с направлением k Þ p. В клетку (k, p)заносим символ '+'. Для остальных клеток (i, j)Î П, если направление i Þ j совпадает с направлением обхода цикла с направлением обхода цикла, то заносим в позицию q символ '+', в противном случае заносим '–'.

3. Определяем клетку (q, l), для которой х (q, l)=min x_ij, где (i, j) – пробегает все клетки из П, помеченные символом '–'.

Полагаем Q = x (q, l).Из базиса выводится клетка (q, l).

4. Для всех (i, j)Î П, если клетка помечена символом '+', то полагаем x_ij = x_ij + Q, в противном случае x_ij = x_ij – Q.

5. Перейти к выполнению проверки критерия оптимальности.

Замечание 1. Иногда минимум достигается на нескольких клетках одновременно. В этом случае в качестве клетки (q, l) выбирается произвольно только одна из них.

Замечание 2. При заполнение таблицы для нового базиса значения x_ij вносятся только в базисные клетки.

Пример. Рассмотрим пример, в котором требуется решить транспортную задачу методом потенциалов. Значения a_i, b_j, c_ij (i =1,2,3, j =1,2,3,4), заданы в таблице

 

j= 1

j= 2

j= 3

j= 4

b 1

b 2

b 3

b 4

i= 1

a 1

u 1

i= 2

a 2

u 2

i= 3

a 3

u 3

v 1

v 2

v 3

v 4

 

Начинаем с определения исходного базиса методом северо–западного угла. Таковым является клетка (1,1), для нее x ₁₁=min (11,10)=10, это число заносим в эту клетку. Изменяем a ₁ и b ₁. Так как b ₁=0, затемняем столбец j= 1.

 

j= 1

j= 2

j= 3

j= 4

b 1

b 2

b 3

b 4

i= 1

a 1

u 1

i= 2

a 2

u 2

i= 3

a 3

u 3

v 1

v 2

v 3

v 4

В незатемненной части таблицы северо–западный угол (1,2), для нее x ₁₂=min (1,16)=1, это число заносим в эту клетку. Изменяем a ₁ и b ₂. Так как a ₁=0, затемняем строку i= 1.

j= 1

j= 2

j= 3

j= 4

b 1

b 2

b 3

b 4

i= 1

a 1

u 1

i= 2

a 2

u 2

i= 3

a 3

u 3

v 1

v 2

v 3

v 4

Продолжая аналогично далее, получим следующую таблицу:

j= 1

j= 2

j= 3

j= 4

b 1

b 2

b 3

b 4

i= 1

a 1

u 1

i= 2

a 2

u 2

i= 3

a 3

u 3

v 1

v 2

v 3

v 4

В ней восстановлены значения a_i, b_j, а также затемнены базисные клетки. Значение функционала на этом решении будет равно

F =2´10+7´1+4´15+3´2+3´12+7´12=213.

Алгоритм поиска начального базиса может быть достаточно произвольным. В результате должно получиться решение, удовлетворяющее требованиям:

1. ,

2. Число базисных клеток должно быть равно n + m –1.