Задача о назначениях или задача выбора

из "Практикум по логистике "

Задача (2) при выполнении условий (3)—(5), как и любая транспортная задача с целыми а,- и 6у-, всегда имеет целочисленное решение. Оптимальный план задачи о назначениях представляет собой матрицу X = (х1), у которой в каждой строке и каждом столбце стоит только один ненулевой элемент, равный единице. [c.202]
Хотя для транспортной задачи есть методы, которые проще методов решения общей задачи линейного программирования, особенности задачи о назначениях позволяют решить ее с помощью более простых приемов. Эффективным методом решения задачи о назначениях является венгерский метод, который рассматривается ниже. [c.202]
Блок-схема алгоритма венгерского метода для задачи о назначениях представлена на рис. 7.1, а ниже приводится более подробное описание алгоритма. [c.204]
Предварительный этап. На этом этапе выполняются два последовательных преобразования матрицы С, в результате которых получается эквивалентная ей неотрицательная матрица С , в каждом столбце и каждой строке которой есть хотя бы один нуль. [c.204]
Полученная матрица С является неотрицательной, и в каждом столбце этой матрицы имеется хотя бы один нуль. [c.204]
Если в каждой строке матрицы С = (с, у), полученной после первого преобразования матрицы С, уже имеется хотя бы один нуль, то второе преобразование не производится. [c.204]
В результате предварительных преобразований мы переходим от задачи выбора на максимум с матрицей С к задаче выбора на минимум с матрицей С . Наименьшее возможное значение суммы п элементов неотрицательной матрицы равно, очевидно, нулю. Следовательно, наша задача сводится к выбору в матрице С (или в эквивалентной ей матрице с неотрицательными элементами) п нулевых элементов, по одному в каждой строке и каждом столбце. [c.204]
Отмечаем произвольный нуль в первом столбце звездочкой ( ). Затем просматриваем второй столбец, и если в нем есть нуль, расположенный в строке, где нет 0, то отмечаем его звездочкой. Аналогично просматриваются один за другим все остальные столбцы матрицы С . Очевидно, что нули матрицы С , отмеченные звездочкой, по построению являются независимыми. [c.204]
Допустим, что к-я итерация проведена и в результате получена матрица Ск. Если в матрице -Ск имеется ровно п нулей со звездочкой, то процесс решения заканчивается. Если же число нулей со звездочкой меньше и, то переходим к (к + 1)-й итерации. Каждая итерация начинается первым и заканчивается вторым этапом. Между ними может несколько раз проводиться пара этапов третий—первый. [c.204]
Перед началом итерации знаком + выделяют столбцы матрицы Ск, которые содержат нули со звездочкой. [c.205]
Первый этап. Просматривают, невыделенные столбцы матрицы Ск. Если среди них не окажется нулевых элементов, то переходят к третьему этапу. Если же невыделенный нуль матрицы Ск обнаружен, то возможен один из двух случаев а) строка, содержащая невыделенный нуль, содержит также нуль со звездочкой б) эта строка не содержит нуля со звездочкой. [c.205]
В случае (б), отметив невыделенный нуль штрихом, сразу переходят ко второму этапу. [c.205]
Второй этап. Строят следующую цепочку из нулевых элементов матрицы Ск. отмеченный последним нуль со штрихом, нуль со звездочкой, расположенный в одном столбце с ним, нуль со штрихом, расположенный в одной строке с предшествующим нулем со звездочкой, и т. д. Итак, цепочка образуется передвижением от О к 0 по столбцу, от 0 к 0 по строке и т. д. [c.205]
Третий этап. К этому этапу переходят после первого, если все нули матрицы Ск выделены, т. е. находятся в выделенных строках или столбцах. В таком случае среди невыделенных элементов матрицы Ск выбирают минимальный и обозначают его h 0. Далее величину h вычитают из всех элементов матрицы Ск, расположенных в невыделенных строках, и прибавляют ко всем элементам, расположенным в выделенных столбцах. Получают новую матрицу С/ll эквивалентную Ск. [c.205]
После конечного числа построений очередной первый этап обязательно закончится переходом на второй этап и количество независимых нулей увеличится на единицу, т. е. (к + 1)-я итерация будет завершена. Обоснование отдельных этапов алгоритма венгерского метода для задачи выбора приведено в [1, с. 172—176]. [c.206]
Для иллюстрации алгоритма решения задачи о назначениях приведем численный пример. [c.206]
Ниже приводится цепочка матриц, получаемых в процессе решения задачи, с соответствующими пометками. Снятие знака выделения + отмечено заключением его в рамку. Цепочка на этапе 2 отмечается стрелками. [c.206]
Пояснения к решению задачи. Процесс нахождения оптимального варианта назначений состоит из предварительного этапа и двух итераций. [c.208]
Предварительный этап. На этом этапе осуществляются два последовательных преобразования матрицы С. Сначала находится максимальный элемент в каждом столбце в первом столбце максимальный элемент равен 5, во втором — 4, в третьем — 6, в четвертом — 5, в пятом — 5. Из максимального элемента вычитаются элементы этого столбца. Получается неотрицательная матрица, в каждом столбце которой есть хотя бы один нуль. Затем из каждой строки полученной матрицы вычитаем минимальный элемент этой строки. В результате подготовительного этапа осуществлен переход к неотрицательной матрице, в каждом столбце и каждой строке которой имеется хотя бы один нуль. [c.208]

Вернуться к основной статье