II. Общий повторяющийся шаг

I. Предварительный шаг

Алгоритм метода потенциалов

Алгоритм метода потенциалов разделяется на предваритель­ный шаг, выполняемый в начале решения, и общий шаг, повторяемый до тех пор, пока не будет получен оптимум.

 

Этот шаг включает следующих три этапа.

1. Находим допустимый ациклический план.

2. Составляем систему чисел — потенциалов пунктов отправ­ления и пунктов назначения.

3. Анализируем систему на потенциальность. Если она по­тенциальна, то найденный план опти­мален, иначе приступаем к общему шагу.

 

 

Общий шаг выполняется в такой последовательности.

1. Выделим случаи нарушения условий и запишем их в виде

Затем находим наибольшую разность, :

.

Пусть этот максимум имеет место для клетки (i₀,j₀). Вклю­чаем эту клетку в набор базисных (m + n – 1) клеток. Клеток становится (m + n), а для такого их количества всегда можно построить цикл. Этот цикл будет в данной ситуации единственным.

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

2. Означиваем цикл, т. е. расставляем знаки в его верши­нах. В исходной клетке (i₀,j₀) ставим плюс, двигаемся по ходу или против хода часовой стрелки и ставим знаки попеременно минус, плюс, — пока не придем к исходной вершине. Так как количество вершин в цикле четно, направ­ление движения безразлично. В результате получим означенный цикл, клетки которого делятся поровну на клетки положительной и отрицательной полуцепи.

3. Выбираем наименьшее значение перевозки θ в клетках отри­цательной полуцепи

min (x_ij)^– = θ.

Если таких значений несколько, берем любое из них.

4. Из перевозок каждой клетки отрицательной полуцепи вы­читаем θ, а к перевозкам каждой клетки положительной полу­цепи прибавляем θ. Эта операция называется сдвигом по циклу на величину θ.

Процесс сдвига меняет план, но план остается допустимым.

Действительно, допустимый план обеспечивает баланс в стро­ках и столбцах; всякий план, не нарушающий этот баланс, бу­дет допустимым. Любой цикл, по которому производится сдвиг, содержит в каждом ряду (строке, столбце) по две вершины. В одну клетку добавляем θ, а из другой вычитаем θ, и баланс не нарушается. Следовательно, план, найденный в результате сдвига, останется допустимым.

После сдвига в клетке отрицательной полуцепи с минималь­ной перевозкой будет стоять ноль, а в клетке (i₀, j₀) окажется число θ. Первую клетку из плана ис­ключаем, а вторую включаем; план остается по-прежнему ацикли­ческим, так как единственный имевшийся цикл нарушается исключением клетки.

Полученный после сдвига план можно записать следующим образом:

5. Для полученного после сдвига плана составляем новую систему потенциалов. Эти новые потенциалы можно вычислить так же, как это делалось в предварительном шаге, а можно найти исправлением уже имеющейся системы.

Для занятых клеток должны выполняться равенства

.

Поэтому берем в таблице клетку, занятую в результате сдвига, и исправляем для нее потенциалы так, чтобы их разность рав­нялась тарифу. Лучше изменять один из них — тот, который стоит в строке или столбце с меньшим числом занятых клеток.

Затем испытываем другие занятые клетки и корректируем последовательно остальные потенциалы. Изменению подвер­гаются, как правило, не все числа, и такой порядок сокращает расчеты.

6. Производим исследование новой системы на потенциаль­ность, т. е. исследование найденного плана на оптимальность. Для этого проверяем выполнение неравенств

для всех незанятых клеток. Если для них неравенства выпол­няются, то система потенциальна и план оптимален, т. е. решение закончено.

Если для каких-то клеток неравенства не выполняются, переходим к пункту 1 общего повторяющегося шага.

 

Лекция 3.