Заполнить опорный план транспортной задачи методом северо-западного угла и найти оптимальный план методом потенциалов

Поскольку , задача имеет открытый тип. Сбалансируем задачу, введя фиктивного поставщика, имеющего запас в 2 ед. товара. Построим опорный план методом северо-западного угла.
Поставщики Потребители Запас Затраты
1 2 3
1 3 5 2 8 26
7 1  
2 8 3 2 7 21
  7  
3 2 1 4 6 18
  2 4
4 0 0 0 2 0
    2
Потребность 7 10 6 Итого
23 65
Число заполненных ячеек совпадает с числом , следовательно, план невырожденный. Далее рассчитаем соответственно потенциалы строк и столбцов и из соотношения (положим ) . Для незаполненных ячеек рассчитаем невязки . Если , план можно улучшить. Тогда включим в план ячейку с наибольшей величиной невязки (вершины замкнутого контура указаны в таблице). При этом в нечетные вершины необходимо добавить комплектов, а из четных – отнять. Преобразования будем выполнять до тех пор, пока .
vj
3 5 8 Запас Вывезено
Поставщики ui
Потребители
b1 b2 b3
a1 0 3   5   2 6 8 8
7   1   0  
a2 2 8 -7 3   2 4 7 7
0   7   0  
a3 4 2 -3 1   4   6 6
0   2   4  
a4 8 0 -5 0 -3 0 0 2 2
0   0   2  
Потребность 7 10 6 Стоимость
Поставлено 7 10 4 65
vj
3 -1 2 Запас Вывезено
Поставщики ui
Потребители
b1 b2 b3
a1 0 3   5 -6 2   8 8
7   0   1  
a2 -4 8 -1 3   2 4 7 7
0   7   0  
a3 -2 2 3 1   4   6 6
0   3   3  
a4 2 0 1 0 -3 0   2 2
0   0   2  
Потребность 7 10 6 Стоимость
Поставлено 7 10 4 59
vj
3 3 2 Запас Вывезено
Поставщики ui
Потребители
b1 b2 b3
a1 0 3   5 -2 2   8 8
7   0   1  
a2 0 8 -5 3   2   7 7
0   4   3  
a3 2 2 -1 1   4 -4 6 6
0   6   0  
a4 2 0 1 0 1 0   2 2
0   0   2  
Потребность 7 10 6 Стоимость
Поставлено 7 10 4 47
После двух итераций получен оптимальный план:
1) пункт a1 – 7 ед