Эта задача обощает задачу о макс потоке. -все ребра ориентированы-каждой дуге поставлена неотрицательная стоимость-дуги могут иметь верхнюю и нижнюю границу пропускной способности. -любой узел может выступать в качестве истока и стока. Сетвая модель:xij - велечина потока протекающего от узла i к juij - верняя пропуск спопобность дугиlij - нижн пропуск способность дугиcij - стоимость прохождения потокаfj - велечина результирущего потока, протекающего через узел jЗадача ЛП:min(SumSum(i,j v A)cijxij)Sum(k)xjk - Sum(k)xij=fj, j v Nlij<=xij<=uijУсловие сбалансиров Sum(j)fj=0Решений может не быть. Ш0 Определ допустмаое базисное решение - мин остав дерево. Ш1 С помощ уловия оптимальности определяем вводимую в базис переменную(дугу). Если на основе условия оптималь определяем, что последнее решение оптимально заканчиваем вычисления, иначе Ш2Ш2 На основе уловия допуустимости определяем исключаемую из базиса переменную, уменьшив базис переход к Ш 1)В сети с n уздами, будет n-1 вводимая пременная. ВВодимая переменная определяется zij-cij для текущей не базисной дуги, если разность <=0 то решени оптимально, иначе вводимая вбазис переменная будет та, у которой эта разность имеет наибольшее положит значение.