При п 1 оптимальное назначение находится тривиально, нужно просто найти минимум в единственном столбце матрицы. ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Романовский И.В. Алгоритмы решения экстремальных задач


При п 1 оптимальное назначение находится тривиально, нужно просто найти минимум в единственном столбце матрицы. Во вновь появившемся столбце мы находим минимум ( с учетом потенциалов строк - тех вычитаемых, которые были определены из предыдущих расчетов), объявляем его новым нулем матрицы или дугой и из описанного алгоритма построения паросочетаний. Если этот нуль может дополнить имеющееся паросочетание, итерация кончается, в противном случае он оказывается дублером некоторого нуля из паросочетания и через него соединяет n - й столбец с одним из предыдущих. Они образуют теперь множество неперечеркнутых столбцов, в этом множестве среди неперечеркнутых строк разыскивается элемент минимальной стоимости, после чего изменением потенциалов соответствующих строк и столбцов производится пересчет матрицы.

(cкачать страницу)

Смотреть книгу на libgen

При п 1 оптимальное назначение находится тривиально, нужно просто найти минимум в единственном столбце матрицы. Во вновь появившемся столбце мы находим минимум ( с учетом потенциалов строк - тех вычитаемых, которые были определены из предыдущих расчетов), объявляем его новым нулем матрицы или дугой и из описанного алгоритма построения паросочетаний. Если этот нуль может дополнить имеющееся паросочетание, итерация кончается, в противном случае он оказывается дублером некоторого нуля из паросочетания и через него соединяет n - й столбец с одним из предыдущих. Они образуют теперь множество неперечеркнутых столбцов, в этом множестве среди неперечеркнутых строк разыскивается элемент минимальной стоимости, после чего изменением потенциалов соответствующих строк и столбцов производится пересчет матрицы.