Page 120 - 6197

інші рядки матриці залишаються без змін. Отриману матрицю
  2
C приводимо по стовпцям. Оскільки всі стовпці матриці,
1
  2
яка отримана після приведення матриці C по рядкам,
вміщують нульові елементи, то немає необхідності змінювати
  2
стовпці матриці C . У такому випадку h  0 і
1 2
  r  h  1 0 1  .
0 2 0
  2
Після приведення матриці C отримаємо таку матрицю:
1 2 3 5 6
2 0 M 14 28 23

 
3 15 13 M 5 0
 
  3

C  4 M 0 9 2 2  .
 
5 2 41 22 M 0
 

6 13 0 0 0 M 


За формулою (2.22) знаходимо, що
 
L G 1   2  48 1 49  .
  3
Знаходимо значення  для матриці C , використавши
ij
формулу (2.20). Отже,
  14 2 16  ,   5 0 5  ,   2 0 2  ,   2 0 2  ,
21 36 42 56
  0 0 0  ,   0 9 9  .
62 63
  3
Для виділених пар матриці C знаходимо
  max 16 5 2 2 0 9 2, , , , , ,  16 , тобто i  2, j  1 і
i 0 0 j 0 0
 
відповідно L G   2  49 16 65  . Множина G 1   3    1,
2
2
підлягає розгалуженню. Шлях (2,1) долучаємо до
    .
оптимального маршруту L   1 4, , 2 1,
  3
У матриці C викреслюємо другий рядок і перший
  4
стовпець; отримуємо матрицю C . Переходи (2.1) і (1.4)

120