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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

19
которой задача с новой матрицей
1
C
оказывается эквивалентной исходной и,
кроме того, элементы этой новой матрицы неотрицательны .
Если
1
C
оказалась неприведенной матрицей , то следует перейти к этапу 1.
Если же
1
C
- приведенная матрица, то переходят к этапу 2.
Пример 3. Взяв матрицу
'
'
C
из примера 2, пересчитаем ее элементы
при
1
=
α
, в итоге получим приведенную матрицу
1
C
=
Все ее нули содержат, например, 1-я горизонталь и три вертикали : 1-я, 2-я, 3-я.
Следовательно , здесь k =4 < 5 и
2
=
α
.
Еще один пересчет дает приведенную матрицу
2
C
=
Здесь уже k=n=5.
Этап 4.
Отыскание n независимых нулей осуществляется перебором всех возможных
вариантов. Удобно перебор начинать с отыскания строк или столбцов, содер-
жащих единственный нулевой элемент, поскольку такой элемент обязательно
войдет в группу независимых. Выбрав элемент
ls
c , исключают из рассмотрения
l -ю строку и s -й столбец , после чего переходят к отысканию следующего
единственного нулевого элемента строки или столбца оставшейся части матри -
цы . Действуя подобным образом, можно столкнуться со следующими двумя си -
туациями.
1. В результате удается выбрать n независимых нулей . ОСТАНОВ. Выписать
ответ.
2. На некотором шаге все оставшиеся строки и столбцы содержат более одно -
го нулевого элемента . В этом случае выбирается любой нулевой элемент,
"помечается" номер строки, из которой выбран 0, и осуществляется переход
к выбору следующего нулевого элемента . Если таким образом удается вы -
брать все n независимых нулей , то ОСТАНОВ. Выписать ответ. В против-
ном случае следует возвратиться к помеченной строке и выбрать из нее дру-
гой нулевой элемент. По этой схеме надодействовать до тех пор, пока не
получим n независимых нулей .
3
0
0
0
0
0
0
1
4
2
0
3
3
2
6
0
2
0
4
6
0
0
0
6
8
5
2
2
0
0
0
0
1
2
0
0
3
3
0
4
0
2
0
2
4
0
0
0
4
6
                                      19
которой задача с новой матрицей C 1 оказывается эквивалентной исходной и,
кроме того, элементы этой новой матрицы неотрицательны.
Если C1 оказалась неприведенной матрицей, то следует перейти к этапу 1.
Если же C 1 - приведенная матрица, то переходят к этапу 2.
Пример 3. Взяв матрицу C ' ' из примера 2, пересчитаем ее элементы
при α =1 , в итоге получим приведенную матрицу


         3   0   0   0   0
 1
C =      0   0   1   4   2
         0   3   3   2   6
         0   2   0   4   6
         0   0   0   6   8

Все ее нули содержат, например, 1-я горизонталь и три вертикали: 1-я, 2-я, 3-я.
Следовательно, здесь k=4 < 5 и α =2 .
Еще один пересчет дает приведенную матрицу

         5   2   2   0   0
  2
C =      0   0   1   2   0
         0   3   3   0   4
         0   2   0   2   4
         0   0   0   4   6

Здесь уже k=n=5.

Этап 4.
 Отыскание n независимых нулей осуществляется перебором всех возможных
вариантов. Удобно перебор начинать с отыскания строк или столбцов, содер-
жащих единственный нулевой элемент, поскольку такой элемент обязательно
войдет в группу независимых. Выбрав элемент cls , исключают из рассмотрения
l -ю строку и s -й столбец, после чего переходят к отысканию следующего
единственного нулевого элемента строки или столбца оставшейся части матри-
цы. Действуя подобным образом, можно столкнуться со следующими двумя си-
туациями.
 1. В результате удается выбрать n независимых нулей. ОСТАНОВ. Выписать
    ответ.
 2. На некотором шаге все оставшиеся строки и столбцы содержат более одно-
    го нулевого элемента. В этом случае выбирается любой нулевой элемент,
    "помечается" номер строки, из которой выбран 0, и осуществляется переход
    к выбору следующего нулевого элемента. Если таким образом удается вы-
    брать все n независимых нулей, то ОСТАНОВ. Выписать ответ. В против-
    ном случае следует возвратиться к помеченной строке и выбрать из нее дру-
    гой нулевой элемент. По этой схеме надодействовать до тех пор, пока не
    получим n независимых нулей.

Страницы