Метод потенциалов

Этот специальный метод решения ТЗ позволяет автоматически выделять циклы с отрицательной ценой и определять их цены.

Идея метода состоит в следующем. Для каждого поставщика и потребителя вводятся псевдоплатежи за перевозки единицы груза поставщиком и получателем a_i и b_j соответственно, не зависящие от направления перевозок. Псевдостоимость перевозки единицы груза от А_i к B_j равна =a_i+b_j; i=1, 2, …, m; j=1, 2, …, n. При этом a_i и b_j не обязательно положительны.

Известна так называемая «теорема о платежах», которую мы приведем без доказательства, отсылая интересующихся к литературным источникам:

для каждой совокупности псевдоплатежей (a_i, b_j) суммарная псевдостоимость перевозок при любом допустимом плане перевозок (x_ij) сохраняет одно и то же значение

=const

Для невырожденного плана перевозок (с числом базисных клеток в таблице перевозок m+n–1) псевдоплатежи (a_i, b_j) определяют так, чтобы во всех базисных клетках псевдостоимости перевозок были равны стоимостям: =a_i+b_j=c_ij при x_ij>0. Оказывается, что соотношение между псевдостоимостями и стоимостями в свободных клетках является индикатором оптимальности плана. Это положение фиксируется следующей теоремой:

Если для всех базисных клеток плана (x_ij>0) =a_i+b_j=c_ij, а для всех свободных клеток (x_ij=0) =a_i+b_j≤c_ij, то план оптимален и не может быть улучшен.

Эта теорема справедлива также и для вырожденного плана с наличием нулевых базисных клеток.

План с указанными в теореме свойствами называют потенциальным, а соответствующие ему псевдоплатежи (a_i, b_j) – потенциалами пунктов А_i, B_j, то есть всякий потенциальный план оптимален.

Таким образом, задача сводится к поиску потенциального плана и решается методом последовательных приближений – сначала задаются произвольной системой платежей, удовлетворяющей условию =c_ij для всех базисных клеток, затем одновременно меняют систему платежей так, чтобы они приближались к потенциалам, используя следующее свойство псевдоплатежей и псевдостоимостей:

При любой системе платежей, удовлетворяющей условию =c_ij для всех базисных клеток, для каждой свободной клетки цена цикла переноса равна разности между стоимостью и псевдостоимостью в данной клетке c_ij– .

Алгоритм решения задачи по методу потенциалов может выглядеть так:

- Берется любой опорный план с m+n–1 базисных клеток.

- Для этого плана определяются псевдоплатежи по условию a_i+b_j=c_ij; один из платежей можно определить произвольным, например нулевым.

- Вычисляются псевдостоимости для всех свободных клеток =a_i+b_j;

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

- Заново подсчитываются платежи и псевдостоимости и так до тех пор, пока во всех свободных клетках не окажутся псевдостоимости не более стоимостей.