Лекция 9
Методы решения транспортной задачи

Получаем, что двойственная задача имеет вид:

при ограничениях:

y_ij = u_i - v_j + c_ij ≥ 0, i = 1, ..., m, j = 1, ..., n,
т.е.

v_j - u_i ≤ 0, i = 1, ..., m, j = 1, ..., n.

Пусть X = [x_ij]_m´n – оптимальное решение транспортной задачи. Тогда на основании теоремы двойственности двойственная задача имеет оптимальное решение .

Убедимся, что эти числа являются потенциалами соответствующих пунктов транспортной задачи. Действительно, все как опорное решение двойственной задачи удовлетворяют первому условию потенциальности.

Если x_ij > 0, то по второй теореме двойственности соответствующее ограничение двойственной задачи обращается в строгое равенство .

Теорема доказана

Алгоритм метода потенциалов

Алгоритм метода потенциалов состоит из предварительного этапа и повторяющегося основного этапа.

Предварительный этап

1. Каким-либо способом ищется допустимый план X (методом северо-западного угла или минимального элемента).
2. Для полученного плана строится система m + n чисел u₁, u₂, ..., u_m; v₁, v₂, ..., v_n, таких что v_j - u_i = c_ij, для всех x_ij > 0.
3. Построенная система u_i и v_j исследуется на потенциальность (то есть план X исследуется на оптимальность). Для этого проверяется v_j - u_i ≤ c_ij, для всех x_ij = 0.

Если система непотенциальна, то переходят к основному этапу (т.к. план не оптимален), иначе оптимальный план найден.

Основной этап

1. Улучшаем план, то есть от плана X переходим к плану X^' такому, что Q(X) ≥ Q(X^').
2. Для плана X^' строим новую систему u^'_i, v^'_j, i = 1, ..., m, j = 1, ..., n, такую, что v^'_j - u^'_i = c_ij, для всех x_ij > 0.
3. Исследуем систему u^'_i, v^'_j на потенциальность. Если система непотенциальна, то переходим на п.1. Иначе найден оптимальный план.

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

2. Строим систему потенциалов:

v₁ - u₁ = 2, v₂ - u₁ = 4, v₃ - u₁ = 2, v₃ - u₂ = 6,

v₄ - u₂ = 6, v₄ - u₃ = 4, v₅ - u₃ = 5, v₅ - u₄ = 4.

Число неизвестных больше числа уравнений, поэтому можем взять, например, u₁ = 0 и найти значения остальных потенциалов, u₂ = -4, u₃ = -2, u₄ = -1, v₁ = 2, v₂ = 4, v₃ = 2, v₄ = 2, v₅ = 3.

3. Проверяем систему на потенциальность:

v₁ - u₂ = 6 ≤ 3 (!), v₁ - u₃ = 4 ≤ 6, v₁ - u₄ = 3 ≤ 3, v₂ - u₂ = 8 ≤ 5 (!),

v₂ - u₃ = 6 ≤ 8, v₂ - u₄ = 5 ≤ 4 (!), v₃ - u₃ = 4 ≤ 7, v₃ - u₄ = 3 ≤ 2 (!),

v₄ - u₁ = 2 ≤ 3, v₄ - u₄ = 3 ≤ 1 (!), v₅ - u₁ = 3 ≤ 8, v₅ - u₂ = 7 ≤ 2 (!).

Система непотенциальна. Переходим к общему этапу.

1. Выбираем клетку, для которой неравенство вида v_j - u_i ≤ c_ij нарушается в наибольшей степени, то есть, находится число α_i0j0 = max_i,j{α_ij = v_j - u_i - c_ij >0} среди тех клеток, для которых первое условие потенциальности не выполняется: α_i0j0 = α₂₅ = 5.

Начиная с клетки i₀ j₀ в направлении против часовой стрелки строится цепь из заполненных клеток таблицы (цикл). Совершая обход по цепи, помечаем клетки, начиная с i₀ j₀, попеременно знаками + и –. Клетки со знаками + образуют положительную полуцепь, а со знаками – отрицательную полуцепь. В клетках отрицательной полуцепи ищем минимальную перевозку θ = min{x^-_ij}.

Теперь улучшаем план следующим образом: перевозки отрицательной полуцепи уменьшаем на величину θ, а перевозки положительной полуцепи увеличиваем на θ. Новые

В нашем примере θ = min{x^-_ij} = 20.

1. Новому плану соответствует таблица.

Затраты на перевозку по построенному плану равны:

Q = 30´2 + 4´80 + 2´10 + 6´10 + 4´30 + 2´20 + 5´10 + 4´60 = 910.

2. Строим систему потенциалов

v₁ - u₁ = 2, v₂ - u₁ = 4, v₃ - u₁ = 2, v₃ - u₂ = 6,

v₅ - u₂ = 2, v₄ - u₃ = 4, v₅ - u₃ = 5, v₅ - u₄ = 4.
Полагаем u₁ = 0 и находим значения остальных потенциалов:

u₂ = -4, u₃ = -7, u₄ = -6, v₁ = 2, v₂ = 4, v₃ = 2, v₄ = -3, v₅ = -2.

3. Проверяем систему на потенциальность:

v₁ - u₂ = 6 ≤ 3 (!), v₁ - u₃ = 9 ≤ 6(!), v₁ - u₄ = 8 ≤ 3(!), v₂ - u₂ = 8 ≤ 5 (!),

v₂ - u₃ = 11 ≤ 8(!), v₂ - u₄ = 10 ≤ 4 (!), v₃ - u₃ = 9 ≤ 7(!), v₃ - u₄ = 8 ≤ 2 (!),

v₄ - u₁ = -3 ≤ 3, v₄ - u₄ = 3 ≤ 1 (!), v₅ - u₁ = -2 ≤ 8, v₄ - u₂ = 1 ≤ 6.

Система непотенциальна.

1. Находим α_i0j0 = α₄₃ = 6, строим цикл, θ = min{x^-_ij} = 10. Улучшаем план. Новому плану соответствует таблица:

Затраты на перевозку по построенному плану равны:

Q = 30´2 + 4´80 + 2´10 + 2´10 + 4´30 + 2´30 + 5´10 + 4´50 = 850.

2. Строим систему потенциалов

v₁ - u₁ = 2, v₂ - u₁ = 4, v₃ - u₁ = 2, v₃ - u₄ = 2,

v₅ - u₂ = 2, v₄ - u₃ = 4, v₅ - u₃ = 5, v₅ - u₄ = 4.
Полагаем u₁ = 0 и находим значения остальных потенциалов:

u₂ = 2, u₃ = -1, u₄ = 0, v₁ = 2, v₂ = 4, v₃ = 2, v₄ = 3, v₅ = 4.

3. Проверяем систему на потенциальность:

v₁ - u₂ = 0 ≤ 3, v₁ - u₃ = 3 ≤ 6, v₁ - u₄ = 2 ≤ 3, v₂ - u₂ = 2 ≤ 5,

v₂ - u₃ = 5 ≤ 8, v₂ - u₄ = 4 ≤ 4, v₃ - u₃ = 3 ≤ 7, v₃ - u₂ = 0 ≤ 6,

v₄ - u₁ = 3 ≤ 3, v₄ - u₄ = 3 ≤ 1 (!), v₅ - u₁ = 4 ≤ 8, v₄ - u₂ = 1 ≤ 6.

Система непотенциальна.

1. Находим α_i0j0 = α₄₄ = 2, строим цикл, θ = min{x^-_ij} = 30. Улучшаем план. Новому плану соответствует таблица:

Затраты на перевозку по построенному плану равны:

Q = 30´2 + 4´80 + 2´10 + 2´10 + 1´30 + 2´30 + 5´40 + 4´20 = 790.

2. Строим систему потенциалов

v₁ - u₁ = 2, v₂ - u₁ = 4, v₃ - u₁ = 2, v₃ - u₄ = 2,

v₅ - u₂ = 2, v₄ - u₄ = 1, v₅ - u₃ = 5, v₅ - u₄ = 4.
Полагаем u₁ = 0 и находим значения остальных потенциалов:

u₂ = 2, u₃ = -1, u₄ = 0, v₁ = 2, v₂ = 4, v₃ = 2, v₄ = 1, v₅ = 4.

3. Проверяем систему на потенциальность:

v₁ - u₂ = 0 ≤ 3, v₁ - u₃ = 3 ≤ 6, v₁ - u₄ = 2 ≤ 3, v₂ - u₂ = 2 ≤ 5,

v₂ - u₃ = 5 ≤ 8, v₂ - u₄ = 4 ≤ 4, v₃ - u₃ = 3 ≤ 7, v₃ - u₂ = 0 ≤ 6,

v₄ - u₁ = 1 ≤ 3, v₄ - u₄ = 1 ≤ 1, v₅ - u₁ = 4 ≤ 8, v₄ - u₂ = 1 ≤ 6.

Система потенциальна, следовательно, план оптимален и окончательные затраты Q_min = 790.

Следующая теорема позволяет определить вырожденность задачи до ее решения.

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

Другими словами, это условие означает, что для любых двух систем индексов i₁, i₂, ..., i_t, j₁, j₂, ..., j_s, где t + s < n + m, имеет место неравенство . (Доказательство не сложно, от противного.)

Для решения транспортной задачи методом потенциалов строится система потенциалов v_j - u_i = c_ij, для всех x_ij > 0. Если опорное решение невырожденно, то число неизвестных на 1 больше числа уравнений. При вырожденном опорном решении число этих уравнений еще меньше. По аналогии симплекс-методом, в невырожденном решении x_ij > 0 представляют собой базисные переменные, а x_ij = 0 – небазисные. Если опорное решение вырожденно, то часть базисных переменных принимает нулевые значения.

Пусть первое опорное решение, найденное методом северо-западного угла или методом минимального элемента, является вырожденным. Тогда, чтобы решать задачу методом потенциалов необходимо выбрать в качестве базисных переменных некоторые перевозки x_ij = 0 и для них также составить уравнения v_j - u_i = c_ij по второму условию потенциальности. Какие перевозки вида x_ij = 0 включать в базисные? Выбираются такие клетки таблицы с x_ij = 0, чтобы из базисных переменных нельзя было организовать ни одного цикла!

При переходе к новому улучшенному плану задачи в небазисные переменные переводится перевозка в отрицательной полуцепи, которая находится следующим образом θ = min{x^-_ij}. В вырожденной задаче это значение может достигаться на нескольких перевозках x_ij отрицательной полуцепи. В этом случае на каждом шаге в небазисные переменные переводится та минимальная перевозка отрицательной полуцепи, которая связана с пунктом производства, имеющим меньший номер. Это правило уменьшает вероятность возникновения зацикливания, что само по себе достаточно редкое явление в практических задачах.