Добавил:
master_slave
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Лекции (Лупин С. А.) / Лекция ОС - Задача о назначении.ppt
Процедура 2. По нулям матрицы построим простой граф.
|
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
|
|
|
|
|
|
X1 |
1 |
0 |
9 |
∞ |
8 |
|
|
|
|
|
|
X2 |
0 |
5 |
4 |
11 |
0 |
|
|
|
|
|
|
X3 |
2 |
1 |
0 |
8 |
10 |
|
|
|
|
|
|
X4 |
0 |
6 |
0 |
11 |
5 |
|
|
|
|
|
|
X5 |
0 |
6 |
∞ |
0 |
6 |
|
|
|
|
|
|
X1 |
Y1 |
X2 |
Y2 |
X3 |
Y3 |
X4 |
Y4 |
X5 |
Y5 |
Задача решена!
Запишем ответ.
|
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
|
|
|
|
|
|
X1 |
2 |
1 |
6 |
∞ |
9 |
|
|
|
|
|
|
|
|
|
|
|
|
X2 |
2 |
7 |
2 |
14 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
X3 |
7 |
6 |
1 |
14 |
15 |
|
|
|
|
|
|
|
|
|
|
|
|
X4 |
6 |
12 |
2 |
18 |
11 |
|
|
|
|
|
|
|
|
|
|
|
|
X5 |
1 |
7 |
∞ |
2 |
7 |
|
|
|
|
|
|
|
|
|
|
|
|
X1 |
Y1 |
X2 |
Y2 |
X3 |
Y3 |
X4 |
Y4 |
X5 |
Y5 |
∑=1+2+1+6+2=12