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

Широко распространенным методом решения транспортных задач является метод потенциалов. Этот метод позволяет упростить наиболее трудоемкую часть вычислений — нахождение оценок свободных клеток.

Теорема (признак оптимальности опорного решения). Если допустимое решение X = (х_ij), i = 1, 2,..., m, j = 1, 2,..., п транспортной задачи является оптимальным, то существуют потенциалы (числа) поставщиков и_i, i = 1, 2,..,, т и потребителей v _j, j = 1, 2,..., п, удовлетворяющие следующим условиям:

u_i+ v_j = c_ij при х_ij > 0 и u_i+ v_j ≤ c_ij при х_ij = 0.

Группа равенств u_i+ v_j = c_ij при х_ij > 0 используется как система уравнений для нахождения потенциалов. Нетрудно видеть, что эта система могла иметь несколько другой вид, например - u_i+ v_j = c_ij или u_i- v_j = c_ij, если перед тем, как записать двойственную задачу, все уравнения одной из групп уравнений исходной задачи умножить на (-1).

Данная система уравнений имеет т + п неизвестных и_i, i =1,2,..., т и v_j, j= 1, 2,..., п. Число уравнений системы, как и число отличных от нуля координат невырожденного опорного решения, равно т + п — 1. Так как число неизвестных системы на единицу больше числа уравнений, то одной из них можно задать значение произвольно, а остальные найти из системы.

Группа неравенств u_i+ v_j ≤ c_ij при х_ij = 0 используется для проверки оптимальности опорного решения. Эти неравенства удобно записать в виде

Δ _ij = u_i+ v_j - c_ij ≤ 0 при х_ij = 0.

Числа Δ _ij называются оценками свободных клеток таблицы или векторов ― условий транспортной задачи, не входящих в базис опорного решения. В этом случае признак оптимальности можно сформулировать так же, как в симплексном методе (для задачи на минимум): опорное решение является оптимальным, если для всех векторов-условий (клеток таблицы) оценки неположительные.

Оценки для свободных клеток транспортной таблицы используются для улучшения опорного решения. С этой целью находят клетку (l, k) таблицы, соответствующую max{Δ _ij }= Δ _lk. Если Δ _lk ≤ 0, то решение оптимальное. Если же Δ _lk > 0, то для соответствующей клетки (l, k) строят цикл и улучшают решение, перераспределяя груз θ = по этому циклу.

Дата добавления: 2014-01-04