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

Распределение поставок называется базисным, если переменные, соответствующие заполненным клеткам, можно принять за основные (базисные) переменные. Клетки, соответствующие свободным переменным, остаются незаполненными (пустыми).

Теорема: число базисных переменных закрытой транспортной задачи равно , где – число поставщиков, – число потребителей.

Критерий оптимальности опорного решения ТЗ: распределение поставок оптимально тогда и только тогда, когда оценки всех свободных клеток неотрицательны.

Теорема о потенциалах: Оценка свободной клетки не изменится, если к коэффициентам затрат некоторой строки (столбца) таблицы поставок прибавить некоторое число. Это число, прибавляемое к коэффициентам затрат выделенной строки (столбца), будем называть потенциалом данной строки (столбца).

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

При переходе к следующему опорному решению, т.е. в результате ввода нового элемента в базис, нарушается общий баланс ресурсов и потребностей. Для того чтобы привести его в норму, необходимо преобразовать некоторые базисные элементы по какому-нибудь замкнутому циклу для сохранения баланса по строкам и столбцам таблицы поставок. Циклом пересчета называется такой цикл в таблице с базисным распределением поставок, при котором одна из его вершин лежит в свободной клетке, а остальные – в заполненных. Цикл пересчета называется означенным, если в его вершинах расставлены знаки «+» и «-» так, что в свободной клетке стоит знак «+», а соседние вершины имеют противоположные знаки. Объем поставки, передаваемой по циклу, определяют, как наименьшее из чисел, стоящих в вершинах цикла со знаком «-». Циклы встречаются самые разные. Например, следующих видов: