7.3. Венгерский метод решения классической транспортной задачи

7.3. Венгерский метод решения классической транспортной задачи

Обсуждаемый метод называют венгерским, так как его идея высказана еще в 1931 году венгерским математиком Эгервари. Эта забытая работа была открыта в 1953 году американским математиком Г.Куном, который развил эту идею и назвал созданный им метод венгерским.

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

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

Рассмотрим идеологию и алгоритм метода на примере классической транспортной задачи минимизации

при условиях

X_ij ³ 0, i = 1.. m, j = 1.. n (4)

Как показано ранее, сопряженная задача сводится к максимизации

при условиях

U_i + V_j £ C_ij при всех i, j. (7)

Если построить матрицу

где

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

Рассмотрим вспомогательную сеть, состоящую из дуг исходной сети, для которых T_ij = C_ij - U_i - V_j равны нулю,

Если в этой сети удастся найти максимальный поток, удовлетворяющий (2)-(5), то по второй теореме двойственности он дает решение исходной задачи.

Для классической транспортной задачи воспользуемся компактной схемой поиска максимального потока с использованием матрицы m*n.

Пусть найден некоторый поток в сети S, удовлетворяющий условиям

Для строк i, в которых

сопоставим метки

Выбираем отмеченные строки (например, i-ю) и отмечаем неотмеченные столбцы j такие, что (i j) Î S, метками

Затем берем отмеченные столбцы (например, j - й) и для неотмеченных строк i, в которых X_ij > 0, сопоставляем метки

Повторяем процесс отмечания столбцов и строк до тех пор, пока не будет отмечен "ненасыщенный" столбец j*, для которого

Отыскиваем величину

определяющую величину потока в найденном пути; поочередно добавляем и вычитаем Q из значений X_ij в цепочке

где

и вновь продолжаем процесс отмечаний.

Если не удастся отметить ни одного из ненасыщенных столбцов, то перестраиваем сеть: отыскиваем величину

где I, J - множества отмеченных строк и столбцов, вычитаем K из отмеченных строк матрицы T и добавляем к отмеченным столбцам. Это действие эквивалентно корректуре двойственных переменных

Такой процесс продолжается до тех пор, пока максимальный поток не окажется насыщающим для строк и столбцов.

Рассмотрим пример решения задачи при следующих данных:
Отыскав значения двойственных переменных (9)-(10)

U₁ = 2, U₂ = 2, U₃ = 3, V₁ = 1, V2 = 0, V₃ = 0, V₄ = 0,

строим матрицу T и ищем в допустимой сети некоторый поток, например, по правилу минимальной стоимости:

Отмечаем ненасыщенные строки

m₁ = 0, u₁ = 6-3 = 3,
m₃ = 0, u₃ = 8-7 = 1.

Из отмеченных строк по "допустимым" клеткам отмечаем неотмеченные столбцы l₂ = 1, w₂ = u₁ = 3,
l₃ = 3, w₃ = u₃ = 1.

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

Находим вычитаем K из строк 1 и 3 и добавляем к столбцам 2 и 3 матрицы T₀, сохраняя в новой сети тот же поток:

Продолжая процесс отмечаний, имеем

Поскольку отмечен ненасыщенный столбец 1, ищем величину коррекции потока Q = min(w₁, 4-0) = 1 и выявляем "минимизирующую цепочку":

которая определяет последовательность [X₂₁ X₂₄ X₃₄].

Поочередное добавление-вычитание Q дает поток X₁.

Повторяем процесс отмечаний:

m₁=0, u₁=6-3 = 3, l₂ = 1, w2 = u₁ = 3

и обнаруживаем невозможность последующих отмечаний. Отыскиваем значение корректуры двойственных переменных

вычитаем K из строки 1 и добавляем к столбцу 2 матрицы T₁, сохраняя в новой сети тот же поток:

Продолжая процесс отмечаний, имеем l₁ = 1, w₁ = u₁ = 3.

Величина корректуры потока равна Q = min(w₁, 6-3) = 3 и минимизирующая цепочка, согласно

состоит их единственного элемента X₁₁; отсюда получаем улучшенный поток X₂, который является насыщающим и дает решение поставленной задачи. Заметим, что при другой системе отмечаний дающей Q=3 и цепочку [X₂₁, X₂₄, X₃₄, X₃₃, X₁₃], получаем другой оптимальный поток X₂'.

Дата добавления: 2015-09-28