Экстремальные модели менеджмента и экономики

Скачать в pdf «Экстремальные модели менеджмента и экономики»


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


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


Другой метод — метод Мака — основан на идее выбора в каждой строке минимального элемента и идее сложения (или вычитания) одного и того же значения со всеми элементами строки или столбца, чтобы распределить минимальные элементы строк по столбцам (тогда они образуют оптимальный выбор).


Алгоритм решения задачи о назначениях методом Мака. Рассматривается задача о назначениях размерности (задача выбора) п»п, где Cj — данные значения эффективности назначения i-го работника на j работу (где i, j = 1^п).


В каждой строке выбирается и подчеркивается минимальный элемент:


at = miniCj, j = 1 ^п .    (27)


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

Скачать в pdf «Экстремальные модели менеджмента и экономики»