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

                                                              16
В дальнейшем нам потребуется следующее определение.
Определение. Любые k элементов ( k =2, n ) матрицы C= (cij ) порядка n×n на-
зываются независимыми, если всякие два из них располагаются в разных стро-
ках и в разных столбцах.

  Теперь можно переформулировать задачу о назначениях следующим обра-
зом: среди n 2 элементов данной матрицы C найти n независимых элементов
                                               n
ci s j s , s =1, n , таких, что сумма         ∑ ci     s js
                                                              минимальна.
                                              s =1
Для обоснования венгерского метода потребуются следующие понятия и ут-
верждения.

Матрицей назначений порядка n×n называется матрица, в которой имеются n
независимых единиц и n 2 −n =n(n −1) нулей. Иными словами, это матрица, у
которой в каждой строке и в каждом столбце имеется ровно одна единица, а ос-
тальные элементы являются нулями.
Обозначим через Ω допустимое множество задачи о назначениях. В соответст-
вии с определением матриц назначений можно утверждать, что множество та-
ких матриц составляет допустимое множество Ω .
Замечание. Все задачи о назначениях размера n×n имеют одно
и то же допустимое множество и отличаются друг от друга только коэффициен-
тами целевой функции, т.е. матрицей C= (cij ) .
Теорема 1. Если элементы матриц C и D порядка n×n связаны равенствами
d ij =cij +α i +β j , то задачи о назначениях с данными матрицами C и D эквива-
лентны, т.е. множества их решений (оптимальных точек) совпадают.
 Доказательство. Во-первых, как отмечалось выше, допустимые множества
обеих задач совпадают. Во-вторых, сравним значения целевых функций обеих
задач, используя ограничения. В результате получаем цепочку равенств
               n   n           n   n               n   n                n   n
              ∑ ∑ d ij xij =∑ ∑ cij xij +∑ ∑ αi xij +∑ ∑ β j xij =
              i =1 j =1       i =1 j =1        i =1 j =1               i =1 j =1
      n   n               n   n           n        n           n   n               n           n   n   n
   =∑ ∑ cij xij +∑ αi ∑ xij +∑ β j ∑ xij =∑ ∑ cij xij +∑ α i +∑ β j =∑ ∑ cij xij +F ,
    i =1 j =1    i =1 j =1   j =1  i =1   i =1 j =1    i =1      j =1
                                                       1    44 2 4  43 i =1 j =1
                                                                                       const
из которой следует, что значения двух целевых функций с матрицами C и D
отличаются на постоянную F. Это означает, что минимумы этих функций дос-
тигаются в одних и тех же точках (на одних и тех же матрицах назначений).
Теорема доказана.
В дальнейшем преобразования вида d ij =cij +α i +β j (добавление ко всем эле-
ментам любой строки или любого столбца одного и того же числа) будем назы-
вать эквивалентными преобразованиями.