ЗАДАЧА 7. Назначения на критичный участок.
Задача 7.1.
Назначить имеющихся сотрудников на вакантные должности так, чтобы маленький размер оплаты труда оказался максимально возможным. Размер оклада (в тыс. руб в месяц) приведен в таблице.
Должн. 1 | Должн. 2 | Должн. 3 | Должн. 4 | Должн. 5 | |
Канд. 1 | 8 | 7 | 5 | 3 | 4 |
Канд. 2 | 5 | 4 | 4 | 2 | 3 |
Канд. 3 | 8 | 2 | 7 | 4 | 4 |
Канд. 4 | 5 | 6 | 5 | 4 | 4 |
Канд. 5 | 8 | 3 | 7 | 9 | 4 |
Пример решения задачи 7.1.
Ввод:
A[i,j]
1` | 2` | 3` | 4` | 5` | 6` | |
1 | 12 | 11 | 10 | 8 | 14 | 6 |
2 | 13 | 8 | 6 | 8 | 8 | 9 |
3 | 11 | 9 | 14 | 3 | 15 | 8 |
4 | 5 | 7 | 12 | 8 | 6 | 10 |
5 | 8 | 12 | 10 | 7 | 6 | 11 |
6 | 9 | 11 | 6 | 12 | 9 | 10 |
Инициализация:
f:=Б (большое число);
в цикле по i от 1 до 6
p[i]:=i;
если a[i,i]< f то f=a[i,i], i:=i+1;
получим:
p[i]={12,8,14,8,6,10};
f=6;
Общий шаг:
1-ая итерация
1. В цикле по i от 1 до 6
в цикле по j от 1 до 6
если a[i,j]> 6 то b[i,j]=1 иначе b[i,j]=0
(получим матрицу на рис. П7.1).
1` | 2` | 3` | 4` | 5` | 6` | |
1 | 1 | 1 | 1 | 1 | 1 | 0 |
2 | 0 | 1 | 0 | 1 | 1 | 1 |
3 | 1 | 1 | 1 | 0 | 1 | 1 |
4 | 0 | 1 | 1 | 1 | 0 | 1 |
5 | 1 | 1 | 1 | 1 | 0 | 1 |
6 | 1 | 1 | 0 | 1 | 1 | 1 |
Рис. П7.1. 1-ая итерация.
2. Использовать АЛГОРИТМ НАХОЖДЕНИЯ МАКСИМАЛЬНОГО ПАРОСОЧЕТАНИЯ, ввод – матрица В, вывод – Nas_u. Nas_u={1,2,3,4,6,5}.
3. f_new:=Б (большое число);
В цикле по i от 1 до 6
если nas_u [i]¹-1 то
если a[i, nas_u[i]]<f_new то f_new:= a[i, nas_u[i]]
при i=6 находится новый минимум: a[6,5]=9
иначе.. (не встречается по всем i)
f:=9
в цикле по i от 1 до M p[i]:= nas_u [i]
p[i]:= {1,2,3,4,6,5}
2-ая итерация
В цикле по i от 1 до 6
в цикле по j от 1 до 6
если a[i,j]> 9 то b[i,j]=1 иначе b[i,j]=0
(получим матрицу на рис. П7.2, а)
1` | 2` | 3` | 4` | 5` | 6` | |
1 | 1 | 1 | 1 | 0 | 1 | 0 |
2 | 1 | 0 | 0 | 0 | 0 | 0 |
3 | 1 | 0 | 1 | 0 | 1 | 0 |
4 | 0 | 0 | 1 | 0 | 0 | 1 |
5 | 0 | 1 | 1 | 0 | 0 | 1 |
6 | 0 | 1 | 0 | 1 | 0 | 1 |
а) б)
Рис. П7.2. 2-ая итерация.
2. Использовать АЛГОРИТМ НАХОЖДЕНИЯ МАКСИМАЛЬНОГО ПАРОСОЧЕТАНИЯ, ввод – матрица В, вывод – Nas_u. Nas_u={2,1,5,3,6,4}, (рис. П7.2, б);
3. f_new:=Б (большое число);
В цикле по i от 1 до 6
если nas_u [i]¹-1 то
если a[i, nas_u[i]]<f_new то f_new:= a[i, nas_u[i]]
при i=1 находится новый минимум: a[1,2]=11
иначе.. (не встречается по всем i)
f:=11;
В цикле по i от 1 до M p[i]:= nas_u [i]
p[i]:={2,1,5,3,6,4}
3-яя итерация
1. В цикле по i от 1 до 6
в цикле по j от 1 до 6
если a[i,j]> 11 то b[i,j]=1 иначе b[i,j]=0
(получим матрицу на рис. П7.3, а)
1` | 2` | 3` | 4` | 5` | 6` | |
1 | 1 | 0 | 0 | 0 | 1 | 0 |
2 | 1 | 0 | 0 | 0 | 0 | 0 |
3 | 0 | 0 | 1 | 0 | 1 | 0 |
4 | 0 | 0 | 1 | 0 | 0 | 0 |
5 | 0 | 1 | 0 | 0 | 0 | 0 |
6 | 0 | 0 | 0 | 1 | 0 | 1 |
 |
а) б)
Рис. П7.3. 3-яя итерация.
2. Использовать АЛГОРИТМ НАХОЖДЕНИЯ МАКСИМАЛЬНОГО ПАРОСОЧЕТАНИЯ, ввод – матрица В, вывод –Nas_u. Nas_u={5,1,3,-1,2,4} (рис. П7.3, б)
3. f_new:=Б (большое число)
в цикле по i от 1 до 6
если nas_u [i]¹-1 то …(уже неважно)
иначе выход (происходит при i=4)
Вывод:
P={5,1,3,-1,2,4};
F=11.
