Метод потенц-в в решении трансп-й задачи

Необх-мо сделать оценку свобод.клеток. Сущ-ть метода потенциалов состоит в том, что д/кажд.строки и кажд.столбца таблицы опр-ют спец.числа, называемые потенциалами. С помощью них можно установить, нужно ли заполнять свобод.клетку таблицы или ее можно оставить незаполненной. Потенциалы строк и столбцов опр-ся по заполнен.клеткам, нах-щимся на их пересечении. Эл-т заполнен.клетки должен равняться сумме потенциалов строки и столбца, на пересеч-и ктр нах-ся эта заполнен.клетка. Д/начала вычислений I потенциал д/строки или столбца приним-ся условно = 0, а все остальные потенциалы опр-ся с помощью эл-тов заполнен.клеток. Обознач-я: V_j – потенциалы столбцов, U_i – строк, С_ij – эл-ты заполнения клеток. С_ij = U_i + V_j. После того, как потенциалы столбцов и строк опр-ны, выясняется, явл-ся ли план оптимальным или нет. С этой целью д/кажд.свобод.клетки вычисл-ся сумма потенциалов строк и столбцов, на пересеч-и ктр нах-ся эта клетка. Сравнение суммы потенциалов с величиной эл-та в свобод.клетках позволяет опр-ть, нужно ли заполнять эту клетку или ее нужно оставить свобод. При решении задачи на min (max) не заполн-ся те свобод.клетки, в ктр сумма потенциалов < (>) величины эл-та. Если хар-ка, знач-е ктр = С_ij – (U_i + V_j) положит. (отриц.), то свобод.клетка не заполн-ся при решении задач на min (на max). Свобод.клетки, имеющие нулевое знач-е хар-ки, показывают на то, что их заполнение приведет к перераспред-ю поставок, но объем работ останется неизменным. После этого числа заносим в таблицу и опр-ем связь с неск-кими незаполнен.клетками. Эта связь выявл-ся путем построения замкнутых многоуг-ков, вершинами ктр явл-ся клетки таблицы. Углы в этих многоуг-ках должны быть прямыми. Одна вершина нах-ся в свобод.клетке, а все остальные – в заполнен. Многоуг-к имеет четное кол-во вершин. В этом цикле пересчета + помечены те клетки, поставка в ктр увелич., и «-» – уменьш-ся. Замечание: иногда д/произвол.означенного цикла вводится понятие оценка цикла – алгебраич.сумма коэф-тов, стоящих в вершинах цикла, взятых с соотв-щими знаками. Д/кажд.свобод.клетки базис.распред-я поставок сущ-ет и при том единствен.цикл пересчета. Причем, операция означивания цикла явл-ся корректной. Т.(о потенциалах): оценка свобод.клетки не измен-ся, если к коэф-там затрат некоторой строки (столбца) таблицы поставок прибавить некоторое число. Изменение коэф-тов затрат можно начинать с любого столбца (строки). Потенциал столбца (строки), избранного д/начала, может быть произвольным. Остальные соотв-но необх-мо пересчитывать.