Решение методом потенциалов Алгоритм метода потенциалов заключается в следующем. 1. Строим первоначальный опорный план, содержащий m n  1 занятых клеток (первый этап). (Решение → 19469)

Заказ №39166

Решение методом потенциалов Алгоритм метода потенциалов заключается в следующем. 1. Строим первоначальный опорный план, содержащий m n  1 занятых клеток (первый этап).

Решение:

Для полученного плана определяем систему потенциалов a i m i    1,2, ,  и b j n j    1,2,  , исходя из условия ij i j с a b   (это условие действительно для всех занятых клеток). Поскольку для построения системы потенциалов используем только занятые клетки, то число неизвестных ( i a и j b ), равное m n   , на единицу превышает число уравнений, равное m n  1 . Поэтому для однозначного определения всех потенциалов одному из них придают произвольное значение(как правило, тому, для которого в соответствующей ему строке или столбце находится наибольшее количество занятых клеток). Обычно в качестве такого произвольного значения выбирается нуль. Затем из условия ij i j с a b   последовательно находят значения остальных потенциалов. 3. Исследуем систему потенциалов на оптимальность. План оптимален, если для всех незанятых клеток выполняется условие ij i j с a b   или   0 ij i j с a b    . То есть, разность между оценкой незанятой клетки и суммой потенциалов строки и столбца, на пересечении которых находится эта клетка, является неотрицательной величиной. Обозначим эту разность через ij .