Срс 11. Задача о назначениях
(распределение работ в семье на выходной день)
Решить задачу о назначениях по предлагаемым условиям индивидуального задания. Сформировать исходные данные для примера, используя оригинальный цифровой код слушателя «ФАМИЛИЯ ИМЯ ОТЧЕСТВО».
|
Мама |
Папа |
Сын |
Дочь |
Бабушка |
Дедушка |
|
1 |
2 |
3 |
4 |
5 |
6 |
||
Готовка |
1 |
А |
Л |
Е |
К |
С |
А |
Уборка |
2 |
Н |
Д |
Р |
А |
Ч |
Е |
Мытье посуды |
3 |
Р |
Т |
О |
Л |
Я |
С |
Вынос мусора |
4 |
О |
Л |
Е |
Г |
О |
В |
Стирка |
5 |
Н |
А |
А |
Л |
Е |
К |
Глажка |
6 |
С |
А |
Н |
Д |
Р |
А |
|
Мама |
Папа |
Сын |
Дочь |
Бабушка |
Дедушка |
Минимум по строкам (Cij(i)) |
Максимум по строкам (Cij(i)) |
|||||||||
1 |
2 |
3 |
4 |
5 |
6 |
||||||||||||
Готовка |
1 |
1 |
13 |
6 |
12 |
19 |
1 |
1 |
19 |
||||||||
Уборка |
2 |
15 |
5 |
18 |
1 |
25 |
6 |
1 |
25 |
||||||||
Мытье посуды |
3 |
18 |
20 |
16 |
13 |
33 |
19 |
13 |
33 |
||||||||
Вынос мусора |
4 |
16 |
13 |
6 |
4 |
16 |
3 |
3 |
16 |
||||||||
Стирка |
5 |
15 |
1 |
1 |
13 |
6 |
12 |
1 |
15 |
||||||||
Глажка |
6 |
19 |
1 |
15 |
5 |
18 |
1 |
1 |
19 |
||||||||
Решаем задачу на минимум:
Вычитаем наименьший элемент каждой строки из всех остальных и получаем С’, затем находим наименьший элемент в каждом столбце:
C’ij=Cij-Cij(i)
Cij(i)=minCij.
|
Решаем на минимум |
|
|
|
|||
|
0 |
12 |
5 |
11 |
18 |
0 |
|
|
14 |
4 |
17 |
0 |
24 |
5 |
|
|
5 |
7 |
3 |
0 |
20 |
6 |
|
|
13 |
10 |
3 |
1 |
13 |
0 |
|
|
14 |
0 |
0 |
12 |
5 |
11 |
|
|
18 |
0 |
14 |
4 |
17 |
0 |
|
Мин |
0 |
0 |
0 |
0 |
5 |
0 |
|
Вычитаем наименьший элемент каждого столбца из всех остальных и получаем С’’:
C’’ij= C’ij-C’i(j)j
C’i(j)j=minC’ij.
Решаем на минимум |
|
|
|
|
|
0 |
12 |
5 |
11 |
13 |
0 |
14 |
4 |
17 |
0 |
19 |
5 |
5 |
7 |
3 |
0 |
15 |
6 |
13 |
10 |
3 |
1 |
8 |
0 |
14 |
0 |
0 |
12 |
0 |
11 |
18 |
0 |
14 |
4 |
12 |
0 |
Выписываем нули и зачеркиваем строки с нулями. Находим количество независимых нулей.
-
0 *
0
0*
0
0*
0
0
0*
0*
0
Число независимых нулей =5, а ранг матрицы r=6 => решение не найдено, строим дополнительные нули (среди не вычеркнутых столбцов и строк) за счет эквивалентных преобразований матрицы.
1
итерация
-
0 *
12
5
1 1
13
0
14
4
17
0*
19
5
5
7
3
0
15
6
13
10
3
1
8
0*
1 4
0
0
12
0*
11
1 8
0*
14
4
12
0
Минимальный элемент = 3
Вычтем его из выделенных элементов:
В итоге получим:
-
0*
12
5
11
13
0
11
1
13
0*
16
5
2
4
0*
0
12
6
10
7
0
1
5
0*
14
0
0
12
0*
11
18
0*
14
4
12
0
Число независимых нулей =6 и r=6 => решение найдено.
Z(x*) – оптимальное решение.
1 |
13 |
6 |
12 |
19 |
1 |
15 |
5 |
18 |
1 |
25 |
6 |
18 |
20 |
16 |
13 |
33 |
19 |
16 |
13 |
6 |
4 |
16 |
3 |
15 |
1 |
1 |
13 |
6 |
12 |
19 |
1 |
15 |
5 |
18 |
1 |
Z(x*) =1+1+16+3+6+1=28.
Решаем задачу на максимум:
Исходная матрица:
-
1
13
6
12
19
1
15
5
18
1
25
6
18
20
16
13
33
19
16
13
6
4
16
3
15
1
1
13
6
12
19
1
15
5
18
1
Вычитаем из наибольшего элемента каждой строки все остальные и получаем С’ и находим наименьший элемент в каждом столбце:
C’ij=Cij(i)-Cij
Cij(i)=maxCij.
Получаем:
18 |
6 |
13 |
7 |
0 |
18 |
10 |
20 |
7 |
24 |
0 |
19 |
15 |
13 |
17 |
20 |
0 |
14 |
0 |
3 |
10 |
12 |
0 |
13 |
0 |
14 |
14 |
2 |
9 |
3 |
0 |
18 |
4 |
14 |
1 |
18 |
Вычитаем наименьший элемент каждого столбца из всех остальных и получаем С’’:
C’’ij= C’ij-C’i(j)j
C’i(j)j=minC’ij.
18 |
3 |
9 |
5 |
0 |
15 |
10 |
17 |
3 |
22 |
0 |
16 |
15 |
10 |
13 |
18 |
0 |
11 |
0 |
0 |
6 |
10 |
0 |
10 |
0 |
11 |
10 |
0 |
9 |
0 |
0 |
15 |
0 |
12 |
1 |
15 |
Находим независимые нули.
|
|
|
|
0 |
|
|
|
|
|
0 |
|
|
|
|
|
0* |
|
0 |
0* |
|
|
0 |
|
0 |
|
|
0 |
|
0* |
0 * |
|
0 |
|
|
|
Число независимых нулей =4, а ранг матрицы r=6 => решение не найдено, строим дополнительные нули (среди не вычеркнутых столбцов и строк) за счет эквивалентных преобразований матрицы.
1 итерация
1 8 |
3 |
9 |
5 |
0 |
15 |
10 |
17 |
3 |
22 |
0 |
16 |
15 |
10 |
13 |
18 |
0* |
11 |
0 |
0* |
6 |
10 |
0 |
10 |
0 |
11 |
10 |
0 |
9 |
0* |
0 * |
15 |
0 |
12 |
1 |
15 |
Минимальный элемент = 3
Вычтем его из выделенных элементов:
В итоге получим:
1 8 |
0 |
6 |
2 |
0 |
12 |
10 |
14 |
0* |
19 |
0 |
13 |
15 |
7 |
10 |
15 |
0* |
18 |
0 |
0* |
6 |
10 |
0 |
10 |
0 |
11 |
10 |
0 |
9 |
0* |
0 * |
15 |
0 |
12 |
1 |
15 |
Число независимых нулей =5, а ранг матрицы r=6 => решение не найдено, строим дополнительные нули (среди не вычеркнутых столбцов и строк) за счет эквивалентных преобразований матрицы.
2 итерация
1 8 |
0 |
6 |
2 |
0 |
12 |
10 |
14 |
0* |
19 |
0 |
13 |
15 |
7 |
10 |
15 |
0* |
18 |
0 |
0* |
6 |
10 |
0 |
10 |
0 |
11 |
10 |
0 |
9 |
0* |
0 * |
15 |
0 |
12 |
1 |
15 |
Минимальный элемент = 2
Вычтем его из выделенных элементов:
В итоге получим:
1 8 |
0 |
6 |
0* |
0 |
10 |
10 |
14 |
0* |
17 |
0 |
11 |
15 |
7 |
10 |
13 |
0* |
16 |
0 |
0* |
6 |
10 |
0 |
10 |
0 |
11 |
10 |
0 |
9 |
0* |
0 * |
15 |
0 |
12 |
1 |
15 |
Число независимых нулей =6 и r=6 => решение найдено.
Z(x*) – оптимальное решение.
18 |
0 |
6 |
0* |
0 |
10 |
10 |
14 |
0* |
17 |
0 |
11 |
15 |
7 |
10 |
13 |
0* |
16 |
0 |
0* |
6 |
10 |
0 |
10 |
0 |
11 |
10 |
0 |
9 |
0* |
0* |
15 |
0 |
12 |
1 |
15 |
-
1
13
6
12
19
1
15
5
18
1
25
6
18
20
16
13
33
19
16
13
6
4
16
3
15
1
1
13
6
12
19
1
15
5
18
1
Находим оптимальное решение:
Z(x*)=12+18+33+13+12+19=107