Пусть задана сеть с графом обладающей матрицей инцидентности . Предположим что каждой дуге альфа итое поставлено в соответствие число сi означающее максимальную пропускную способность данной дуги.ТРЕБУЕТСЯ определить макс.пропускную способность всей сети в целом между узлом источником xp и узлом приёмником xq . Формализация задачи. Обозначим через zi величину потока по дуге альфа итое тогда задача о макс.потоке принимает вид следующей ЗЛП: f(z)=сумма по и от 1 до m giqzi стремится к макс(1);сумма по и от 1 до m (giq+gip )zi=0,сумма по и от 1 до m gikzi=0,0<=zi<=ci
