Лекция №11 Метод потенциалов

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

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

при , (6.12)

при . (6.13)

Доказательство. Используем вторую теорему двойственности (теорема 5.2). Запишем математическую модель транспортной задачи

,

, i = 1, 2, ..., m; j = 1, 2, ..., n.

Составим математическую модель двойственной задачи. Обозначим через , i = 1, 2, ..., m переменные (оценки), соответствующие первым m уравнениям системы ограничений, и через
, j = 1, 2, ..., n, переменные, соответствующие последним n уравнениям. Записываем

,

, i = 1, 2, ..., m; j = 1, 2, ..., n.

Каждое ограничение двойственной задачи содержит только две переменные, так как каждый вектор-условие системы ограничений исходной задачи имеет только две отличные от нуля (равные единице) координаты, i-ю и (m+j)-ю. Условий неотрицательности двойственная задача не имеет, так как все ограничения в исходной задаче – равенства. По второй теореме двойственности (теорема 5.2), если при подстановке в систему ограничений двойственной задачи некоторое ограничение выполняется как строгое неравенство , то соответствующая координата оптимального решения исходной задачи равна нулю . Если же оптимальным решением ограничение удовлетворяется как равенство , то соответствующая координата оптимального решения отлична от нуля,
т. е. .

Группа равенств (6.12)

при ,

используется как система уравнений для нахождения потенциалов. Нетрудно видеть, что эта система могла иметь несколько другой вид, например, или , если перед тем, как записать двойственную задачу, все уравнения одной из групп уравнений исходной задачи умножить на (-1).

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

Группа неравенств

при

используется для проверки оптимальности опорного решения. Эти неравенства удобно записать в следующем виде

при . (6.14)

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

Оценки для свободных клеток транспортной таблицы используются для улучшения опорного решения. Для этого находят клетку (l, k) таблицы, соответствующую . Если , то решение оптимальное. Если же , то для соответствующей клетки (l, k) строят цикл и улучшают решение, перераспределяя груз по этому циклу.