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

Производители Потребители Объем
производства
А1 А2 А3 А4
S1 19[10] 26 47 25[42] 52
S2 22 23 47[7] 28[6] 13
S3 23 22[19] 47[3] 29 22
Спрос 10 19 10 48
Значение целевой функции для этого опорного плана равно:
F(x) = 19*10 + 25*42 + 47*7 + 28*6 + 22*19 + 47*3 = 2296
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
Проверим оптимальность опорного плана . Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 19; 0 + v1 = 19; v1 = 19
u1 + v4 = 25; 0 + v4 = 25; v4 = 25
u2 + v4 = 28; 25 + u2 = 28; u2 = 3
u2 + v3 = 47; 3 + v3 = 47; v3 = 44
u3 + v3 = 47; 44 + u3 = 47; u3 = 3
u3 + v2 = 22; 3 + v2 = 22; v2 = 19
Производители Потребители Объем
производства
А1 А2 А3 А4
S1 19[10] 26 47 25[42] 52 u1=0
S2 22 23 47[7] 28[6] 13 u2=3
S3 23 22[19] 47[3] 29 22 u3=3
Спрос 10 19 10 48
v1=19 v2=19 v3=44 v4=25
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Минимальные затраты составят:
F(x) = 19*10 + 25*42 + 47*7 + 28*6 + 22*19 + 47*3 = 2296
Ответ: От 1-го производителя необходимо 10 ед