Лекции по "Экономике организации"

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

ЗАДАЧА О НАЗНАЧЕНИЯХ [assignment problem] — вид задачи линейного программирования, с помощью которой решаются вопросы типа: как распределить рабочих по станкам, чтобы общая выработка была наибольшей или затраты на заработную плату наименьшими (поскольку для каждой комбинации “рабочий — станок” характерна своя производительность труда), как наилучшим образом распределить экипажи самолетов, как назначить людей на различные должности (отсюда и название задачи) и т. д.

Математически такие задачи — частный  случай распределительных задач  с той особенностью, что в них  объемы наличных и требующихся для  выполнения каждой работы ресурсов равны  единице, т. е. aj = bj = 1, и все xij=1, если работник i назначен на работу j, или нулю в остальных случаях (обозначения см. в ст. “Распределительные задачи”). Иначе говоря, для выполнения каждой работы расходуется только один вид ресурса, а каждый ресурс может быть использован на одной работе: ресурсы неделимы между работами, а работы — между ресурсами. Исходные данные группируются в таблице, которая называется матрицей оценок, результаты — в матрице назначений.

Количество возможных вариантов  назначений равно факториалу числа  работ и ресурсов и огромно  даже в небольшой задаче. Поэтому  для нахождения оптимального варианта применяют специальные алгоритмы. Среди них особенно эффективен при решении З. о н. вручную т. н. венгерский метод.

2.1 Сущность Венгерского метода

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

 

Частным случаем транспортной задачи является задача о назначениях, в  которой число пунктов производства равно числу пунктов назначения, т.е. транспортная таблица имеет форму квадрата. Кроме того, в каждом пункте назначения объем потребности равен 1, и величина предложения каждого пункта производства равна 1. Любая задача о назначениях 2может быть решена с использованием методов линейного программирования или алгоритма решения транспортной задачи. Однако ввиду особой структуры данной задачи был разработан специальный алгоритм, получивший название Венгерского метода.

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

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

Постановка задачи. Предположим, что  имеется  различных работ  и  механизмов , каждый из которых может выполнять любую работу, но с неодинаковой эффективностью. Производительность механизма при выполнении работы  обозначим , и = 1,...,n; j = 1,...,n. Требуется так распределить механизмы по работам, чтобы суммарный эффект от их использования был максимален. Такая задача называется задачей выбора или задачей о назначениях.

Формально она записывается так. Необходимо выбрать такую последовательность элементов  из матрицы

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

Введем следующие понятия.

Нулевые элементы  матрицы С  называются независимыми нулями, если для любого  строка и столбец, на пересечении которых расположен элемент , не содержат другие такие элементы .

Две прямоугольные матрицы С и D называются эквивалентными (C ~ D), если  для всех i,j . Задачи о назначениях, определяемые эквивалентными матрицами, являются эквивалентными (т.е. оптимальные решения одной из них будут оптимальными и для второй, и наоборот).

- Описание алгоритма венгерского метода

 

Алгоритм состоит из предварительного этапа и не более чем (n-2) последовательно  проводимых итераций. Каждая итерация связана с эквивалентными преобразованиями матрицы, полученной в результате проведения предыдущей итерации, и с выбором  максимального числа независимых  нулей. Окончательным результатом  итерации является увеличение числа  независимых нулей на единицу. Как  только количество независимых нулей  станет равным n, проблему выбора оказывается решенной, а оптимальный вариант назначений определяется позициями независимых нулей в последней матрице.

 

Предварительный этап. Разыскивают  максимальный элемент в j - м столбце и все элементы этого столбца последовательно вычитают из максимального. Эту операцию проделывают над всеми столбцами матрицы С. В результате образуется матрица с неотрицательными элементами, в каждом столбце которой имеется, по крайней мере, один нуль.

 

Далее рассматривают i - ю строку полученной матрицы, разыскивают ее минимальный элемент ai и из каждого элемента этой строки вычитают минимальный. Эту процедуру повторяют со всеми строками. В результате получим матрицу С0 (С0 ~ C), в каждой строке и столбце которой имеется, по крайней мере, один нуль. Описанный процесс преобразования С в С0 называется приведением матрицы.

 

Находим произвольный нуль в первом столбце и отмечаем его звездочкой. Затем просматриваем второй столбец, и если в нем есть нуль, расположенный  в строке, где нет нуля со звездочкой, то отмечаем его звездочкой. Аналогично просматриваем один за другим все  столбцы матрицы С0 и отмечаем, если возможно, следующие нули знаком “*”. Очевидно, что нули матрицы С0, отмеченные звездочкой, являются независимыми. На этом предварительный этап заканчивается.

 

(k+1)-ая итерация. Допустим, что k-я итерация уже проведена и в результате получена матрица Сk. Если в ней имеется ровно n нулей со звездочкой, то процесс решения заканчивается. В противном случае переходим к (k+1) - й итерации.

 

Каждая итерация начинается первым и заканчивается вторым этапом. Между  ними может несколько раз проводиться  пара этапов: третий - первый. Перед  началом итерации знаком “+” выделяют столбцы матрицы Сk, которые содержат нули со звездочками.

 

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

 

Во втором случае переходим сразу  ко второму этапу, отметив этот нуль штрихом.

 

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

 

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

 

Этот процесс за конечное число  шагов заканчивается одним из следующих исходов:

 

1). все нули матрицы Сk выделены, т.е. находятся в выделенных строках или столбцах. При этом переходят к третьему этапу;

 

2). имеется такой невыделенный нуль в строке, где нет нуля со звездочкой. Тогда переходят ко второму этапу, отметив этот нуль штрихом.

 

Второй этап. На этом этапе строят следующую цепочку из нулей матрицы  Сk: исходный нуль со штрихом, нуль со звездочкой, расположенный в одном столбце с первым нулем со штрихом в одной строке с предшествующим нулем со звездочкой и т.д. Итак, цепочка образуется передвижением от 0' к 0* по столбцу, от 0* к 0' по строке и т.д.

Можно доказать, что описанный алгоритм построения цепочки однозначен и  конечен, при этом цепочка всегда начинается и заканчивается нулем со штрихом.

Далее над элементами цепочки, стоящими на нечетных местах ( 0' ) -, ставим звездочки, уничтожая их над четными элементами ( 0* ). Затем уничтожаем все штрихи над элементами Сk и знаки выделения “+”. Количество независимых нулей будет увеличено на единицу. На этом (k+1) -я итерация закончена.

Третий этап. К этому этапу  переходят после первого, если все  нули матрицы Сk выделены. В таком случае среди невыделенных элементов Сk выбирают минимальный и обозначают его h (h>0). Далее вычитают h из всех элементов матрицы Сk, расположенных в невыделенных строках и прибавляют ко всем элементам, расположенным в выделенных столбцах. В результате получают новую матрицу С'k, эквивалентную Сk. Заметим, что при таком преобразовании, все нули со звездочкой матрицы Сk остаются нулями и в С'k, кроме того, в ней появляются новые невыделенные нули. Поэтому переходят вновь к первому этапу. Завершив первый этап, в зависимости от его результата либо переходят ко второму этапу, либо вновь возвращаются к третьему этапу.

После конечного числа повторений очередной первый этап обязательно  закончится переходом на второй этап. После его выполнения количество независимых нулей увеличится на единицу и (k+1) - я итерация будет  закончена.

Пример. Решить задачу о назначениях  с матрицей

При решении задачи используем следующие  обозначения:

Знак выделения “+”, подлежащий уничтожению, обводим кружком; цепочку, как и ранее, указываем стрелками.

Предварительный этап. Отыскиваем максимальный элемент первого столбца - 4. Вычитаем из него все элементы этого столбца. Аналогично для получения второго, третьего, четвертого и пятого столбцов новой матрицы вычитаем все элементы этих столбцов от п'яти, трех, двух и трех соответственно. Получим матрицу С'(C'~C). Так как в каждой строке С' есть нуль, то С' = С0 и процесс приведения матрицы заканчивается. Далее ищем и отмечаем знаком “*” независимые нули в С0, начиная с первой строки.

Первая итерация. Первый этап. Выделяем знаком “+” первый, второй, и четвертый  столбцы матрицы С0, которые содержат 0*.

Просматриваем невыделенный третий столбец, находим в нем невыделенный нуль С23 = 0, отмечаем его штрихом и выделяем знаком “+” вторую строку. Просматриваем  эту строку, находим в ней элемент  С22 = 0* и уничтожаем знак выделения  второго столбца, содержащего 0*. Затем  просматриваем второй столбец - в  нем нет невыделенных элементов. Переходим к последнему невыделенному  столбцу (пятому), ищем в нем невыделенные нули. Поскольку невыделенных нулей  нет, то переходим к третьему этапу.

Третий этап. Находим минимальный  элемент в невыделенной части  матрицы С0 (т.е. элементы, которые лежат в столбцах и строках, не отмеченных знаком “+”). Он равен h = 1.

Вычтем h = 1 из всех элементов невыделенных строк (т.е. всех, кроме второго) и прибавим ко всем элементам выделенных столбцов (первого и четвертого). Получим матрицу С'1 и перейдем к первому этапу.

Первый этап. Перед его началом  вновь выделяем знаком “+” первый, второй и четвертый столбцы. Просматриваем  невыделенный третий столбец, находим  в нем невыделенный нуль С23 = 0, отмечаем его знаком штрих. Поскольку во второй строке есть 0* (элемент С22), то выделяем знаком “+” вторую строку, далее  уничтожаем знак выделения второго  столбца, где лежит 0*. Потом просмотрим второй столбец, находим в нем  невыделенный нуль С12 = 0, отмечаем его  знаком штрих. Поскольку в первой строке есть нуль со звездочкой С14 = 0*, то выделяем его знаком “+”, и уничтожаем знак выделения четвертого столбца, где находился этот знак 0*. Затем  пересматриваем четвертый столбец  и находим в нем невыделенный нуль С54 = 0. Так как в строке, где  он находится, нет нуля со звездочкой, то отметив этот 0 штрихом, переходим ко второму этапу.

Второй этап. Начиная с элемента с54 = 0', строим цепочку, двигаясь от него по столбцу. Находим нуль со звездочкой с14 = 0*, далее от него движемся вдоль  первой строки и находим 0'(с12), от этого  элемента движемся вдоль первого  столбца к с22 = 0*, в конечном итоге, двигаясь от с22 = 0* вдоль второй строки приходим к исходному с23 = 0'. Таким образом, цепочка построена: 0'54-0*14-0'12-0*22-0'23. Заменяем штрих на звездочку и уничтожаем звездочки над четными элементами цепочки, а также все знаки выделения столбцов и строк. На этом первая итерация заканчивается. В результате число независимых нулей увеличилось на единицу. Поскольку следующие итерации выполняются аналогично, то приведем результаты их выполнения без дополнительных пояснений. После второй итерации количество независимых нулей (0*) стало равно 5 (размерности матрицы С) и поэтому алгоритм заканчивает работу. Искомые элементы назначения соответствуют позициям независимых нулей матрицы С3 (т.е. 0*).

 

Соответствующее значение целевой  функции

 

 

Первая итерация. Первый этап Третий этап

 

h=1

 

Первая итерация. Первый этап. Второй этап.

 

Вторая итерация

 

Первый этап Второй этап

 Основы теории графов: определение графа, цепи, циклы,  пути, контуры. Связные и сильно  связные графы. Матрица смежности  графа. Матрица инцинденций дуг и ребер графов. Деревья. Плоские графы. Кратчайшие пути и контуры. Алгоритмы Форда и Данцига. Циркуляция максимальной величины и потенциалы перестановок. Поток максимальной величины. Алгоритм Форда—Фалкерсона. Задачи распределения ресурса на сетях и графах.

- Граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами).

 

Объекты представляются как вершины, или узлы графа, а связи — как  дуги, или рёбра. Для разных областей применения виды графов могут различаться  направленностью, ограничениями на количество связей и дополнительными  данными о вершинах или рёбрах.

- Цепь в графе — маршрут, все рёбра которого различны. Если все вершины (а тем самым и рёбра) различны, то такая цепь называется простой (элементарной). В цепи  вершины  и  называются концами цепи. Цепь с концами u и v соединяет вершины u и v. Цепь, соединяющая вершины u и v обозначается . Для орграфов цепь называется орцепью.

- Цикл — замкнутая цепь. Для орграфов цикл называется контуром.

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

- Путь — последовательность рёбер (в неориентированном графе) и/или дуг (в ориентированном графе), такая, что конец одной дуги (ребра) является началом другой дуги (ребра). Или последовательность вершин и дуг (рёбер) в которой каждый элемент инцидентен предыдущему и последующему. Может рассматриваться как частный случай маршрута.