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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

18
Пример 1. Пусть
С=
Легко проверить, что
'
C
= , A
'
'
C
= ,
причем матрица
'
'
C
является приведенной.
Этап 2.
При вычислении максимального числа k независимых нулей в приведенной
матрице обычно организуют полный перебор всевозможных вариантов. При
этом необходимо воспользоваться следующим утверждением :
Теорема 3. Максимальное число независимых нулей равно минимальному
суммарному числу горизонтальных и вертикальных линий (строк и столбцов),
которыми можно зачеркнуть все нулевые элементы приведенной матрицы .
Пример 2. Пусть имеется приведенная матрица из примера 1.
'
'
C
=
Все ее нули содержат 1-я горизонталь и 1-я вертикаль, следовательно , здесь
k=2 < 5. При решении задачи о назначениях будем проводить указанные линии,
в результате чего некоторые элементы окажутся зачеркнутыми, другие -
зачеркнутыми дважды и остальные - незачеркнутыми.
Этап 3.
Обозначим через
r
ij
c элемент приведенной матрицы
'
'
C
, зачеркнутый r раз
( r =0, 1, 2) на 2-м этапе, и положим
0
min
ij
c=α , где минимум берется по всем i, j,
т.е. ищется наименьший из незачеркнутых элементов матрицы
'
'
C
. Построим
матрицу
1
C
, проведя пересчет элементов матрицы
'
'
C
следующим образом:
a) из элементов
0
ij
c
вычитается значение
α
;
b) элементы
1
ij
c
остаются без изменения;
c) к элементам
2
ij
c
прибавляется значение
α
.
Такие преобразования являются следствием применения Теоремы 1, согласно
2
1
2
1
0
1
3
5
7
4
2
7
8
6
9
1
5
4
7
8
1
3
4
9
10
2
0
0
0
0
0
1
2
5
3
0
4
4
3
7
0
3
1
5
7
0
1
1
7
9
2
1
2
1
0
0
2
4
6
3
0
5
6
4
7
0
4
3
6
7
0
2
3
8
9
2
0
0
0
0
0
1
2
5
3
0
4
4
3
7
0
3
1
5
7
0
1
1
7
9
                                                    18
Пример 1. Пусть

          2   1   2   1   0
          1   3   5   7   4
          2   7   8   6   9
 С=
          1   5   4   7   8
          1   3   4   9   10

  Легко проверить, что

          2   1   2   1   0                 2   0   0    0   0
   C' =   0   2   4   6   3    ,A C ' ' =   0   1   2    5   3   ,
          0   5   6   4   7                 0   4   4    3   7
          0   4   3   6   7                 0   3   1    5   7
          0   2   3   8   9                 0   1   1    7   9

причем матрица C ' ' является приведенной.

Этап 2.
При вычислении максимального числа k независимых нулей в приведенной
матрице обычно организуют полный перебор всевозможных вариантов. При
этом необходимо воспользоваться следующим утверждением:
Теорема 3. Максимальное число независимых нулей равно минимальному
суммарному числу горизонтальных и вертикальных линий (строк и столбцов),
которыми можно зачеркнуть все нулевые элементы приведенной матрицы.
Пример 2. Пусть имеется приведенная матрица из примера 1.
          2   0   0   0   0
  C'' =   0   1   2   5   3
          0   4   4   3   7
          0   3   1   5   7
          0   1   1   7   9
Все ее нули содержат 1-я горизонталь и 1-я вертикаль, следовательно, здесь
k=2 < 5. При решении задачи о назначениях будем проводить указанные линии,
в результате чего некоторые элементы окажутся зачеркнутыми, другие -
зачеркнутыми дважды и остальные - незачеркнутыми.

Этап 3.
Обозначим через cijr элемент приведенной матрицы C ' ' , зачеркнутый r раз
(r=0, 1, 2) на 2-м этапе, и положим α =min cij0 , где минимум берется по всем i, j,
т.е. ищется наименьший из незачеркнутых элементов матрицы C ' ' . Построим
матрицу C1 , проведя пересчет элементов матрицы C ' ' следующим образом:
    a) из элементов cij0 вычитается значение α ;
   b) элементы c1ij остаются без изменения;
  c) к элементам cij2 прибавляется значение α .
Такие преобразования являются следствием применения Теоремы 1, согласно

Страницы