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

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

17
Следствие. Всегда можно считать, что все элементы матрицы C неотрицатель-
ны , т.е. .,,0 jic
ij
∀
≥
Действительно , этого можно добиться применением эквивалентных преобразо -
ваний .
Теорема 2. Пусть все элементы матрицы C неотрицательны , т.е. .,,0 jic
ij
∀
≥
Если в ней имеются n независимых нулевых элементов
,0
=
ij
c
то их сумма
является минимальной.
Доказательство. Какова бы ни была допустимая точка
Ω
∈
X
,
∑∑
==
≥=
n
i
n
j
ijij
xcXL
11
0)( . Введем матрицу назначений
0
X
с единицами именно на
тех местах , где расположены выбранные независимые элементы 0
=
ij
c . Тогда
0)(
0
=XL , следовательно ,
0
X
оптимальная точка. Теорема доказана.
§ 5. Венгерский метод
Алгоритм венгерского метода включает в себя 4 этапа.
1. Приведение матрицы .
2. Вычисление максимального числа
k
независимых нулей в приведенной
матрице.
3. Получение новых нулей при
n
k
<
.
4. Отыскание n независимых нулей при
n
k
=
.
Рассмотрим каждый этап подробнее.
Этап 1.
Матрица C называется приведенной , если все ее элементы неотрицательны и,
кроме того, в каждой строке и в каждом столбце имеются нулевые элементы .
Таким образом, приведенная матрица C удовлетворяет двум условиям :
1.
.,,0 jic
ij
∀
≥
2. .,0,,0 jcuic
ijij
∀
=
∃
∀
=
∃
Для приведения матрицы C с элементами 0
≥
ij
c нужно воспользоваться эк-
вивалентными преобразованиями. При этом вначале осуществляется приведе-
ние матрицы по строкам , т.е. ищется наименьший элемент
i
α
в каждой строке и
осуществляется переход к матрице
'
C
с элементами
iijij
cc
α
−
=
' . Если матрица
'
C
оказывается неприведенной по столбцам , то ищется наименьший элемент
j
в каждом столбце и осуществляется переход к матрице
'
'
C
, элементы кото -
рой вычисляются следующим образом:
jijij
cc
β
−
=
''' . Матрица по построению
является приведенной. 
                                      17
Следствие. Всегда можно считать, что все элементы матрицы C неотрицатель-
ны, т.е. cij ≥0, ∀i, j.
Действительно, этого можно добиться применением эквивалентных преобразо-
ваний.
Теорема 2. Пусть все элементы матрицы C неотрицательны, т.е. cij ≥0, ∀i, j.
Если в ней имеются n независимых нулевых элементов cij =0, то их сумма
является минимальной.
  Доказательство. Какова бы ни была допустимая точка X ∈Ω ,
        n   n
L( X ) =∑ ∑ cij xij ≥0 .Введем матрицу назначений X 0 с единицами именно на
       i =1 j =1
тех местах, где расположены выбранные независимые элементы cij =0 . Тогда
L( X 0 ) =0 , следовательно, X 0 оптимальная точка. Теорема доказана.

                            § 5. Венгерский метод

Алгоритм венгерского метода включает в себя 4 этапа.

   1. Приведение матрицы.
   2. Вычисление максимального числа k независимых нулей в приведенной
      матрице.
   3. Получение новых нулей при k

Страницы