Дискретная оптимизация - 15 стр.

                                              15
                   ЗАДАЧА О НАЗНАЧЕНИЯХ
                 ВЕНГЕРСКИЙ МЕТОД РЕШЕНИЯ

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

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

      � 1, если i-й претендент назначен на j-e место,
xij =�
       � 0, в противном случае.
Теперь задача принимает следующий вид:
                                         n   n
                           L( X ) =∑ ∑ cij xij → min
                                        i =1 j =1

                             �    n

                             �   ∑ xij =1,          j =1, n,
                                 i =1
                             �
                             �    n
                           Ω�    ∑ xij =1,          i =1, n,
                             �   j =1
                             � x ∈{0,1}, i, j =1, n.
                             �  ij
                                �
Замечание. Если последние ограничения               заменить условиями вида
0 ≤xij ≤1, ∀i, j , то полученная задача является частным случаем транспортной
задачи, у которой, как известно, оптимальное решение всегда существует. Та-
ким образом, задачу о назначениях можно решать методом потенциалов, при-
чем в соответствии со спецификой этого метода можно утверждать, что реше-
нием является n 2 - мерный вектор, или матрица порядка n×n, элементы кото-
рой равны 0 или 1. Это означает, что полученный ответ будет также являться
ответом в исходной задаче о назначениях. Однако начальная базисная точка,
полученная, например, по методу северо-западного угла, содержит не
m+n-1=2n-1, а всего лишь n ненулевых компонент равных 1, cледовательно,
при n ≥2 этот план становится вырожденным. Как известно, это обстоятельст-
во существенно усложняет вычислительную процедуру решения транспортной
задачи. По этой причине для решения задачи о назначениях существуют специ-
альные методы. Рассмотрим один из них, который носит название венгерский
метод.