Для клетки (1,2) :

1 +

2 = 15,

1 = 0,

2 = 15
Для клетки (2,2) :

2 +

2 = 10,

2 = -5,

2 = 15
Для клетки (2,4) :

2 +

= 6,

2 = -5,

4 = 11
Для клетки (2,5) :

2 +

= 4,

2 = -5,

5 = 9
Для клетки (3,3) :

+

= 10,

3 = 0,

3 = 10
Найденные значения потенциалов заносим в таблицу. Вычисляем оценки свободных клеток:
Δ13 =

1 +

3 – с 13 = 0 + 10 – 18 = - 8

0
Δ14 =

1 +

– с 14 = 0 + 11 – 16 = - 5

0
Δ15 =

1 +

– с 15 = 0 + 9 – 8 = 1

0
Δ21 =

+

– с 21 = -5 + 5 – 6 = -6

0
Δ23 =

+

– с 23 = -5 + 10 – 15 = -10

0
Δ31 =

+

– с 31 = 0 + 5 – 25 = -20

0
Δ34 =

+

– с 34 = 0 + 11 – 15 = -4

0
Δ35 =

+

– с 35 = 0 + 9 – 18 = -9

0
Получили одну оценку Δ15 = 1

0 следовательно, исходное решение не является оптимальным и его можно улучшить.
Переход от одного решения транспортной задачи к другому.
Наличие положительной оценки свободной клетки (

) при проверке решения на оптимальность свидетельствует о том, что полученное решение не оптимально и для уменьшения значения целевой функции надо перейти к другому решению. При этом надо перераспределить грузы, перемещая их из занятых клеток в свободные. Свободная клетка становится занятой, а одна из ранее занятых клеток – свободной.
Для свободной клетки Δ15 = 1

0 строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новое решение. Это решение проверяем на оптимальность, и так далее до тех пор, пока не получим оптимальное решение.
Х2 =

Стоимость перевозки при исходном решении составляет
f2 = 175 * 5 + 215 * 10 + 10 * 20 + 240 * 10 + 160 * 6 + 175 * 8 + 25 * 4 = 8085.
Проверим полученное решение на оптимальность. Для этого запишем его в распределительную таблицу, приведенную ниже, найдем потенциалы занятых и оценки свободных клеток.
Для клетки (1,1) :

1 +

1 = 5,

1 = 0,

1 = 5
Для клетки (1,5) :

1 +

5 = 8,

1 = 0,

5 = 8
Для клетки (2,5) :

2 +

= 4,

= -4,

= 8
Для клетки (2,4) :

2 +

= 6,

2 = -4,

4 = 10
Для клетки (2,2) :

2 +

= 10,

2 = -4,

= 14
Для клетки (3,3) :

+

= 10,

3 = 0,

3 = 10
Найденные значения потенциалов заносим в таблицу. Вычисляем оценки свободных клеток:
Δ12 =

1 +

– с 12 = 0 + 14 – 15 = - 1

0
Δ13 =

1 +

– с 13 = 0 + 10 – 18 = - 8

0
Δ14 =

1 +

– с 14 = 0 + 10 – 16 = - 6

0
Δ21 =

+

– с 21 = -4 + 5 – 6 = - 5

0