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

Производители Потребители Объем
производства
А1 А2 А3 А4
S1 35[6] 7[10] 43[29] 39 45
S2 31 13 45[1] 35[32] 33
S3 47 31 13 45[9] 9
Спрос 6 10 30 41
Значение целевой функции для этого опорного плана равно:
F(x) = 35*6 + 7*10 + 43*29 + 45*1 + 35*32 + 45*9 = 3097
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 35; 0 + v1 = 35; v1 = 35
u1 + v2 = 7; 0 + v2 = 7; v2 = 7
u1 + v3 = 43; 0 + v3 = 43; v3 = 43
u2 + v3 = 45; 43 + u2 = 45; u2 = 2
u2 + v4 = 35; 2 + v4 = 35; v4 = 33
u3 + v4 = 45; 33 + u3 = 45; u3 = 12
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;1): 2 + 35 > 31; ∆21 = 2 + 35 - 31 = 6 > 0
(3;3): 12 + 43 > 13; ∆33 = 12 + 43 - 13 = 42 > 0
max(6,42) = 42
Выбираем максимальную оценку свободной клетки (3;3): 13
Для этого в перспективную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Производители Потребители Объем
производства
А1 А2 А3 А4
S1 35[6] 7[10] 43[29] 39 45 u1=0
S2 31 13 45[1][-] 35[32][+] 33 u2=2
S3 47 31 13[+] 45[9][-] 9 u3=12
Спрос 6 10 30 41
v1=35 v2=7 v3=43 v4=33
Цикл приведен в таблице (3,3 → 3,4 → 2,4 → 2,3).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е . у = min (2, 3) = 1. Прибавляем 1 к объемам грузов, стоящих в плюсовых клетках и вычитаем 1 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Производители Потребители Объем
производства
А1 А2 А3 А4
S1 35[6] 7[10] 43[29] 39 45
S2 31 13 45 35[33] 33
S3 47 31 13[1] 45[8] 9
Спрос 6 10 30 41
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 35; 0 + v1 = 35; v1 = 35
u1 + v2 = 7; 0 + v2 = 7; v2 = 7
u1 + v3 = 43; 0 + v3 = 43; v3 = 43
u3 + v3 = 13; 43 + u3 = 13; u3 = -30
u3 + v4 = 45; -30 + v4 = 45; v4 = 75
u2 + v4 = 35; 75 + u2 = 35; u2 = -40
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;4): 0 + 75 > 39; ∆14 = 0 + 75 - 39 = 36 > 0
Выбираем максимальную оценку свободной клетки (1;4): 39
Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Производители Потребители Объем
производства
А1 А2 А3 А4
S1 35[6] 7[10] 43[29][-] 39[+] 45 u1=0
S2 31 13 45 35[33] 33 u2=-40
S3 47 31 13[1][+] 45[8][-] 9 u3=-30
Спрос 6 10 30 41
v1=35 v2=7 v3=43 v4=75
Цикл приведен в таблице (1,4 → 1,3 → 3,3 → 3,4).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е