Венгерский метод транспортной задачи

Размещено на http://www.allbest.ru/

1 ВЕНГЕРСКИЙ МЕТОД РЕШЕНИЯ КЛАССИЧЕСКОЙ ТРАНСПОРТНОЙ ЗАДАЧИ

Обсуждаемый метод называют венгерским, так как его идея высказана еще в 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*, для которого

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

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

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

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

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

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

Рассмотрим пример решения задачи при следующих данных:

Отыскав значения двойственных переменных (9)-(10)

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

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

Отмечаем ненасыщенные строки. Из отмеченных строк по «допустимым» клеткам отмечаем неотмеченные столбцы.

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

Находим

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

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

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

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

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

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

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

Продолжая процесс отмечаний. Величина корректуры потока равна и минимизирующая цепочка, согласно

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

2 ВЕНГЕРСКИЙ МЕТОД ДЛЯ ТРАНСПОРТНОЙ ЗАДАЧИ В СЕТЕВОЙ ПОСТАНОВКЕ

Рассмотрим более общую задачу на примере нижеприведенной сети, где числа на дугах определяют стоимость единичной перевозки, вершины 1 и 2 - пункты производства продукта в количествах 20 и 10 единиц, вершины6 и 7 - пункты потребления в количествах 15 и 15 единиц. К тому же на маршрутах 2 - 5 и 3 - 6 пропускная способность не превышает соответственно 5 и 7 единиц продукта.

Воплощая основную идею венгерского метода, введем фиктивные вход 0 и выход 8. Соединим вход 0 с вершинами 1 и 2 дугами с пропускной способностью, равной объемам производства, и вершины 6 и 7 с выходом 8 - дугами с пропускной способностью, равной объемам потребления. Стоимости перевозок на этих дугах берем нулевыми.

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

при условиях

Если переписать (4) в виде

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

Один из возможных алгоритмов состоит в следующем. Отмечаем вход некоторым значком (множество отмеченных вершин в дальнейшем будем обозначать через М). Отыскиваем неотмеченные вершины ( j ), в которые ведут ненасыщенные дуги с нулевыми стоимостями перевозок из вершин множества М, т.е. дуги с характеристиками C_Mj = 0, X_Mj < d_Mj. При отсутствии таковых переходим к пункту 3 алгоритма и при наличии - к пункту 4.

Отыскиваем среди неотмеченных вершину, из которой идет дуга во множество М с нулевой стоимостью и ненулевой перевозкой, и переходим к пункту 4. При отсутствии таких - к пункту 7.

Выбранную вершину включаем во множество М и, если выход остался непомеченным, переходим к пункту 2.

По меткам, сопоставленным отмеченным вершинам (откуда и сколько), отыскиваем путь от входа к выходу и его пропускную способность и корректируем суммарный поток и пропускные способности (по аналогии с поиском максимального потока в простейшем случае).

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

Выясняем наличие дуг, для которых C_Mj > 0 при j M или C_iM < 0 при i ? M. Если таковых нет, задача неразрешима.

Среди модулей найденных C_Mj и C_iM отыскиваем минимальное значение и корректируем матрицу стоимостей, вычитая ? из стоимостей на дугах, ведущих из множества М, и добавляя к стоимостям на дугах, ведущих во множество М. Возвращаемся к пункту 2.

Покажем реализацию алгоритма в матричной форме для вышеприведенной сети.

Выбрав для начала нулевой поток X⁰, устанавливаем начальные метки:

Так как в отмеченных строках не обнаруживается нулевых стоимостей
C_Mj, j ? M, дальнейшее отмечание невозможно.

Отыскиваем

вычитаем из отмеченных строк матрицы C, добавляя к отмеченным столбцам (получаем матрицу С₁) и, продолжая процедуру отмечаний с учетом С₁ и D, получаем возможность отметить в дополнение к отмеченным ранее вершину 5:

после чего опять-таки приходится расширять сеть путем коррекции матрицы C₁ на величину

получая матрицу С₂.

Продолжив отмечания, имеем:

Обратным ходом по меткам выясняем путь с пропускной способностью V₈ = 5 и корректируем матрицу D, уменьшая ее элементы, соответствующие дугам пути в прямом направлении, и увеличивая симметричные элементы на V₈ = 5.

Повторяя процедуру отмечаний (на основе C₂,D₁ и X₁), имеем:

(вершину 5 отметить не удается, так как D₂₅=0). Соответственно находим ? = min(4,3,7,2)=2 (значение С₂₅=0 не учитываем, так как соответствующей дуги на этом этапе решения нет). После вычитания из отмеченных строк добавления к отмеченным столбцам получаем матрицу С₃.

Продолжая процесс отмечаний, имеем: откуда получаем путь с пропускной способностью 5.

Выполнив обычную коррекцию матрицы пропускных способностей и потока, получаем D₂ и X₂.

Повторяя процедуру отмечаний, имеем: ?₀ = -1, V₀ = 20; т.е. путь с величиной потока 2.

Повторяя процедуру отмечаний, имеем. Находим ? = min(3, 2, 2) = 2 и получаем матрицу С₄ (продолжение опять-таки невозможно). Ищем min(1, 8, 6, 6) = 1 и получаем матрицу С₅, из которой возникает возможность отметить вершину 2 (но не выход сети).

Опять-таки ищем min(5, 5) = 5 и перестраиваем матрицу стоимостей к виду С₆.

Процедура отмечаний обнаруживает возможность перехода с пропускной способностью 3:

Здесь обнаруживается возможность отмечания всех вершин, кроме 7 и 8. Находим ? = min(2, 8) = 2 и перестраиваем матрицу стоимостей к виду С₇.

Теперь очевидна возможность отмечания всех вершин и обнаруживается путь с пропускной способностью 15.

В итоге получаем D₅ и X⁵.

Граф максимального потока представлен на рисунке.

Заметим, что матрицу X₅ можно получать и по окончании счета, вычитая D₅ из исходной матрицы D₀.

Нет сомнений, что мало-мальски приличную транспортную задачу вручную никто не будет решать и необходимо прибегнуть к помощи компьютера (если у вас есть соответствующее программное средство).

3 ТРАНСПОРТНАЯ ЗАДАЧА ПО КРИТЕРИЮ ВРЕМЕНИ

транспортный задача венгерский метод

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

Пусть имеется m поставщиков продукта в количествах A_i (i=1.. m) и n потребителей в количествах B_j (j = 1 .. n), причем соблюдается баланс предложения и спроса.

Известно время t_ij доставки груза от i - го поставщика к j - му потребителю, не зависящее от объема перевозки.

Требуется среди всех допустимых планов перевозок X = {X_ij} найти план, оптимальный по времени. Очевидно, что время, необходимое для реализации плана, совпадает с наибольшим временем отдельных перевозок и оптимальное время перевозок равно

при условиях

X_ij 0, i = 1 .. m, j = 1 .. n

Алгоритм решения базируется на идеях венгерского метода для классической транспортной задачи и элементарном здравом смысле.

Предварительно выбирается минимальное значение t_ij и строится допустимая сеть по значениям t_ij, не превышающим выбранного.

В этой сети отыскивается максимальный поток. Если этот поток отвечает условиям задачи, то выбранное время оптимально. В противном случае выбирается очередное наименьшее время, сеть расширяется и в ней вновь ищется максимальный поток.

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

Пример. Пусть задача определена следующими данными.

Минимальные значения t_ij в строках равны 1, 2, 1 и в столбцах 1, 1, 4, 10.

Выбираем t*=10, строим вспомогательную сеть по t_ij ? t* и отыскиваем в ней начальное приближение для потока, например, методом северо-западного угла.

Так как найденный поток X⁰ не является насыщающим, пытаемся его улучшить с использованием процесса отмечаний венгерского метода

Дальнейшее отмечание невозможно и приходится расширить сеть, взяв t*=12 (появится возможность перевозки на маршруте 1 - 4, поток X_o').

Очевидно, что это расширение ничего нового не даст; берем t*=13, поток X_o»).

Отталкиваясь от ранее выбранного потока, пытаемся его улучшить. Продолжая процесс отмечаний, имеем

Так как отмечен ненасыщенный столбец, отыскиваем минимизирующую цепочку [X₃₄ X₃₂ X₁₂] и корректирукорректируем ее на величину ? = min (?₄, B₄) = 7.

В итоге мы получаем насыщающий поток и можем утверждать, что минимальное время транспортировки составляет 13 единиц.

Размещено на Allbest.ru