Назначения на критичный участок

ЗАДАЧА 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.