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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

20
Пример 4. Взяв матрицу
2
C
из примера 3, замечаем , что независимыми
здесь будут нули с индексами (1, 5), (2, 2), (3, 4), (4, 3), (5, 1). Это
означает, что ответом в задаче о назначениях с матрицей C из примера 1
является матрица назначений вида
=
1
min
X ,;;;для которой 14)(
1
min
=XL .
Важно отметить, что наряду с указанными, здесь будут также независимыми
нули с индексами (1, 4), (2, 5), (3, 1), (4, 3), (5, 2). Следовательно , эта задача о
назначениях имеет еще один ответ- матрицу назначений вида
=
2
min
X , причем 14)(
2
min
=XL .
УПРАЖНЕНИЯ
1. Является ли данная матрица приведенной? Укажите количество в ней неза-
висимых нулей .
а) в)
пп
C
= бьбьбюб
C
=
2. Решите задачу о назначениях с матрицей С вида:
а) в) c)
C
= б ь
C
= mdhsj
C
=
f
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
1
0
0
0
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
0
1 3 2 4
1
-1
6 0 3
3
0 -4
3 8
2
5 0 -5
7
4
3 8 7 0
2
3
4
2
4
0
3
5
6
7
4
3
6
7
2
6
2
6
3
5
7
4
3
1
8
3
5
2
1
2
1
5
6
4
9
1
2
2
1
2
1
0
1
3
5
6
9
4
2
7
8
5
3
6
1
5
4
7
8
3
1
3
4
9
5
6
2
4
6
5
3
1
3
4
2
1
3
0
4
3
6
7
3
4
7
6
2
6
3
5
1
4
7
8
3
2
3
2
4
8
4
6
1
6
5
4
9
2
                                                              20
 Пример 4. Взяв матрицу C 2 из примера 3, замечаем, что независимыми
здесь будут нули с индексами (1, 5), (2, 2), (3, 4), (4, 3), (5, 1). Это
означает, что ответом в задаче о назначениях с матрицей C из примера 1
является матрица назначений вида

                0       0    0      0    1
                0       1    0      0    0
  1
X min =         0       0    0      1    0
                                              ,;;;для которой Lmin ( X 1 ) =14 .
                0       0    1      0    0
                1       0    0      0    0

Важно отметить, что наряду с указанными, здесь будут также независимыми
нули с индексами (1, 4), (2, 5), (3, 1), (4, 3), (5, 2). Следовательно, эта задача о
назначениях имеет еще один ответ- матрицу назначений вида

                0       0    0      1    0
                0       0    0      0    1
  2
X min   =                                     , причем Lmin ( X 2 ) =14 .
                1       0    0      0    0
                0       0    1      0    0
                0       1    0      0    0

                                                     УПРАЖНЕНИЯ

1. Является ли данная матрица приведенной? Укажите количество в ней неза-
висимых нулей.
а)                            в)
            2       0       0    0      0                         0       1    3    2    4
пп C =      0       1       2    5      3     бьбьбюб C =         1       -1   6    0    3
            0       4       4    3      7                         3       0    -4   3    8
            0       3       1    5      7                         2       5    0    -5   7
            0       1       1    7      9                         4       3    8    7    0


2. Решите задачу о назначениях с матрицей С вида:

а)                                              в)                                       c)
   2        2       1    2      1       0            3    4   2       1    3   0              2   3   4   2   4   0
C= 1        3       5    6      9       4 б     ьC = 4    3   6       7    3   4 mdhsj C =    3   5   6   7   4   3
   2        7       8    5      3       6            7    6   2       6    3   5              6   7   2   6   2   6
   1        5       4    7      8       3            1    4   7       8    3   2              3   5   7   4   3   1
f  1        3       4    9      5       6            3    2   4       8    4   6              8   3   5   2   1   2
   2        4       6    5      3       1            1    6   5       4    9   2              1   5   6   4   9   1

Страницы