Первое базисное допустимое решение легко построить по правилу ²северо-западного угла².

Общая стоимость всех перевозок для первого базисного допустимого решения:

L= 34* 2 + 40*7 + 6*2 + 32*4 + 28*2+25 =569

Обозначим через

m(p1, p2,…, pm, q1, q2,…, qn)

вектор симплексных множителей или потенциалов. Тогда

Дij = m Aij – cij i = (1,…,m), j = (1,…,n)

откуда следует

Дij = pi + qj– cij i = (1,…,m), j = (1,…,n) (1)

Один из потенциалов можно выбрать произвольно, так как в системе одно уравнение линейно зависит от остальных. Положим, что р1 = 0. Остальные потенциалы находим из условия, что для базисных клеток Дij = 0. В данном случае получаем

D11 = 0, p1 + q1 - c11 = 0, 0+q1 -2 = 0, q1 = 2

D12 = 0, p1 + q2 - c12 = 0, 0+q2 -7 = 0, q2 = 7

D13 = 0, p1 + q3 - c13 = 0, 0+q3 -2 = 0, q3 = 2

D23 = 0, p2 + q3 – c23 = 0, p2+2 -4 = 0, p2 = 2

D24 = 0, p2 + q4 – c24 = 0, 2+q4 -2 = 0, q4 = 0

D34 = 0, p3 + q4 – c34 = 0, p3+ 0 -1 = 0, p3 = 1

D35 = 0, p3 + q5 – c35 = 0, 1+ q5 -0 = 0, q5 = -1

Затем по формуле (1) вычисляем оценки всех свободных клеток:

D21 = p2 + q1 - c21 = 2+2-1 = 3

D31 = p3 + q1 - c31 = 1+2 -3 = 0

D22 = p2 + q2 – c22 = 2+7-5 = 4

D32 = p3 + q2 – c32 = 1+7-4 = 4

D33 = p3 + q3 – c33 = 1+2-6 = 3

D14 = p1 + q4 – c13 = 0+0-3 = 3

D15 = p1 + q5 – c15 = 0+(-1) = -1

D25 = p2 + q5 – c25 = 2+(-1) = 1

Находим наибольшую положительную оценку max (Dij > 0) = 4 = D22

Для найденной свободной клетки 22 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 22-12-13-23. Производим перераспределение поставок вдоль цикла пересчета

= 32

Получаем второе базисное допустимое решение: