30. Сетевая тз: критерий оптимальности.

Теорема(критерий оптимальности): пусть x – базисный поток, которому соотв-ет базисное мн-во дуг U_Б. - соотв-щие оценки. Тогда достаточный, а в случае невырожденности и необходимый признак для его оптимальности. Замечание: отметим, что при док-ве необх-сти возможна ситуация, когда в построенном цикле все дуги прямые. Это означает, что совок-сть x явл-ся потоком при . При этом условии следует, что целевая функция неограниченна снизу  задача не имеет решений.