Постановка задачи. Некоторые свойства

Пусть имеются n претендентов (каждому из них отвечает индекс ) на n мест работы (каждому из них отвечает индекс ). При этом известна стоимость затрат, связанных с назначением i -го претендента на j-е место. Требуется распределить претендентов по рабочим местам так, чтобы каждый претендент занял одно место, каждое место было занято одним претендентом, и так, чтобы связанные с этим распределением суммарные затраты были минимальными.

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

Теперь задача принимает следующий вид:

Замечание. Если последние ограничения заменить условиями вида то полученная задача является частным случаем транспортной задачи, у которой, как известно, оптимальное решение всегда существует. Таким образом, задачу о назначениях можно решать методом потенциалов, причем в соответствии со спецификой этого метода можно утверждать, что решением является -мерный вектор, или матрица порядка n×n, элементы которой равны 0 или 1. Это означает, что полученный ответ будет также являться ответом в исходной задаче о назначениях. Однако начальная базисная точка, полученная, например, по методу северо-западного угла, содержит не m+n-1=2n-1, а всего лишь n ненулевых компонент равных 1, cледовательно, при этот план становится вырожденным. Как известно, это обстоятельство существенно усложняет вычислительную процедуру решения транспортной задачи. По этой причине для решения задачи о назначениях существуют специальные методы. Рассмотрим один из них, который носит название венгерский метод.

В дальнейшем нам потребуется следующее определение.

Определение. Любые k элементов ( ) матрицы C= порядка n×n называются независимыми, если всякие два из них располагаются в разных строках и в разных столбцах.

Теперь можно переформулировать задачу о назначениях следующим образом: среди элементов данной матрицы C найти n независимых элементов , , таких, что сумма минимальна.

Для обоснования венгерского метода потребуются следующие понятия и утверждения.

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

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

Замечание. Все задачи о назначениях размера n×n имеют одно и то же допустимое множество и отличаются друг от друга только коэффициентами целевой функции, т.е. матрицей C= .

Теорема 1. Если элементы матриц C и D порядка n×n связаны равенствами , то задачи о назначениях с данными матрицами C и D эквивалентны, т.е. множества их решений (оптимальных точек) совпадают.

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

из которой следует, что значения двух целевых функций с матрицами C и D

отличаются на постоянную F. Это означает, что минимумы этих функций достигаются в одних и тех же точках (на одних и тех же матрицах назначений).

Теорема доказана.

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

Следствие. Всегда можно считать, что все элементы матрицы C неотрицательны, т.е.

Действительно, этого можно добиться применением эквивалентных преобразований.

Теорема 2. Пусть все элементы матрицы C неотрицательны, т.е. Если в ней имеются n независимых нулевых элементов то их сумма является минимальной.

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