Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui

Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 100 + 200 + 70 = 370 ∑b = 190 + 120 + 30 = 340 Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 30 (370—340). Тарифы перевозки единицы груза к этому магазину полагаем равны нулю. Занесем исходные данные в распределительную таблицу. 
B1 B2 B3 B4 Запасы
A1 4 2 2 0 100
A2 3 5 3 0 200
A3 9 3 6 0 70
Потребности 190 120 30 30
Поиск первого опорного плана(метод наименьшей стоимости)
B1 B2 B3 B4 Запасы
A1 4 2[100] 2 0 100
A2 3[190] 5 3[10] 0 200
A3 9 3[20] 6[20] 0[30] 70
Потребности 190 120 30 30
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6 . Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 2*100 + 3*190 + 3*10 + 3*20 + 6*20 + 0*30 = 980 Улучшение опорного плана( метод потенциалов)Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v2 = 2; 0 + v2 = 2; v2 = 2 u3 + v2 = 3; 2 + u3 = 3; u3 = 1 u3 + v3 = 6; 1 + v3 = 6; v3 = 5 u2 + v3 = 3; 5 + u2 = 3; u2 = -2 u2 + v1 = 3; -2 + v1 = 3; v1 = 5 u3 + v4 = 0; 1 + v4 = 0; v4 = -1 
v1=5 v2=2 v3=5 v4=-1
u1=0 4 2[100] 2 0
u2=-2 3[190] 5 3[10] 0
u3=1 9 3[20] 6[20] 0[30]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;1): 0 + 5 > 4; ∆11 = 0 + 5 - 4 = 1 > 0 (1;3): 0 + 5 > 2; ∆13 = 0 + 5 - 2 = 3 > 0 max(1,3) = 3 Выбираем максимальную оценку свободной клетки (1;3): 2 Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 
1 2 3 4 Запасы
1 4 2[100][-] 2[+] 0 100
2 3[190] 5 3[10] 0 200
3 9 3[20][+] 6[20][-] 0[30] 70
Потребности 190 120 30 30
Цикл приведен в таблице (1,3 → 1,2 → 3,2 → 3,3). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е