Конспект: потоки минимальной стоимости

Понятия

Цена ребра a(u, v) - стоимость ЕДИНИЦЫ потока по нему. Стоимость потока - сумма a(u, v)·f(u, v) по всем рёбрам.

Остаточная сеть со стоимостями: прямое ребро - остаток c − f по цене a(u, v); обратное - остаток f−ℓ по цене −a(u, v), где ℓ - нижняя граница потока на ребре. При ℓ=0 обратный остаток равен f; отмена возвращает заплаченное.

Задача о назначениях - n исполнителей, n работ, цена пары; раздать так, чтобы сумма была наименьшей. Транспортная задача - то же самое с объёмами вместо единиц.

Сетевой симплекс - дерево базисных дуг T и небазисные дуги на нижней границе L или верхней U. На T приведённая цена r=0. Улучшение ищут при r<0 на L или r>0 на U; шаг ограничивают остаточные зазоры по циклу. Без верхних ёмкостей U пусто: дуги вне дерева стоят на нижних границах; при нулевых нижних границах их потоки нулевые. Старт проверяют первой фазой с искусственными дугами или обоснованно большой штрафной ценой.

Что унести

критерий оптимальности:
    поток величины K минимален по стоимости
    ⇔ в ОСТАТОЧНОЙ сети нет цикла отрицательной стоимости

проверяется Беллманом-Фордом за O(V·E) по всей остаточной сети
начальные расстояния 0 у всех вершин находят и недостижимые из s циклы

поиск дешёвого пути:  Беллман-Форд          O(V·E) за шаг    (возможны отрицательные цены)
с потенциалами:       Дейкстра              O(E·log V) за шаг
итого SSP:            O(K·V·E)  или  O(K·E·log V),  K - ВЕЛИЧИНА потока
начальный Беллман-Форд при отрицательных исходных ценах: ещё O(V·E)

Потенциалы Джонсона - те же, что в разделе про кратчайшие пути: a'(u, v) = a(u, v) + p[u] − p[v], обновляются после каждого шага. Нулевые начальные потенциалы подходят при неотрицательных исходных ценах. Если отрицательные рёбра есть, а отрицательных циклов нет, начальные потенциалы можно получить Беллманом-Фордом с временным общим источником. При обновлении не прибавляй бесконечные расстояния до недостижимых вершин. Оценка с множителем K предполагает целые нижние и верхние границы потока, целочисленный старт и целую требуемую величину K: каждый шаг увеличивает её хотя бы на 1.

Сведения: назначения - единичные пропускные способности и цены на рёбрах между долями; транспортная задача - запасы и потребности; кратчайший путь - задай каждому ребру ёмкость 1 и нижнюю границу 0, затем найди поток величины 1; для этого сведения в сети не должно быть отрицательных циклов; максимальный поток - цены отсутствуют. Одна модель, разные числа на рёбрах.

Если задача имеет конечный оптимум, при целых нижних и верхних границах потока и балансах есть целый оптимальный поток: матрица ограничений вполне унимодулярна. Другие оптимальные точки могут быть дробными смесями целых оптимумов. Округлять их независимо нельзя: выбирай целую оптимальную вершину или алгоритм, который сохраняет целость потока. Дробные объёмы транспортной задачи сами по себе целого решения не гарантируют.

Тихие ошибки: искать отрицательный цикл в исходной сети вместо остаточной; забыть минус у обратного ребра; запускать SSP с потока без доказанной оптимальности для своей величины; применять Дейкстру без допустимых потенциалов; считать, что «максимальный поток» и «самый дешёвый поток данной величины» - одна задача; решать назначения жадно (по строкам на пяти исполнителях это 18 против 13).

Куда это ведёт

Дальше - выпуклые стоимости и обобщённые потоки. В первом случае цена следующей единицы зависит от уже отправленного объёма; во втором на дуге меняется сам объём. После этих двух глав конспект раздела соберёт признаки всех изученных моделей.