Задачи о назначениях
В таблице строки соответствуют рабочим, а столбцы работам. Необходимо составить план работ так, чтобы все работы были выполнены, каждый рабочий был загружен только на одной работе, а суммарная стоимость выполнения всех работ была минимальной. Если задача не сбалансирована (т.е. число работ не совпадает с числом рабочих), то перед началом решения её надо сбалансировать, введя недостающее число фиктивных строчек или столбцов с достаточно большими штрафными стоимостями работ.
Вариант 1
|
|
Стоимость выполнения работ |
||||
|
Рабочий 1 |
3 |
6 |
2 |
5 |
11 |
|
Рабочий 2 |
1 |
2 |
7 |
11 |
3 |
|
Рабочий 3 |
5 |
12 |
11 |
9 |
1 |
|
|
Работа 1 |
Работа 2 |
Работа 3 |
Работа 4 |
Работа 5 |
Вариант 2
|
|
Стоимость выполнения работ |
||||
|
Рабочий 1 |
1 |
3 |
6 |
5 |
7 |
|
Рабочий 2 |
5 |
2 |
7 |
8 |
3 |
|
Рабочий 3 |
3 |
5 |
1 |
9 |
2 |
|
Рабочий 4 |
6 |
4 |
2 |
10 |
5 |
|
|
Работа 1 |
Работа 2 |
Работа 3 |
Работа 4 |
Работа 5 |
Вариант 3
|
|
Стоимость выполнения работ |
||||
|
Рабочий 1 |
9 |
4 |
8 |
5 |
7 |
|
Рабочий 2 |
1 |
2 |
9 |
8 |
3 |
|
Рабочий 3 |
3 |
8 |
1 |
9 |
2 |
|
Рабочий 4 |
3 |
4 |
2 |
4 |
5 |
|
|
Работа 1 |
Работа 2 |
Работа 3 |
Работа 4 |
Работа 5 |
Вариант 4
|
|
Стоимость выполнения работ |
|||
|
Рабочий 1 |
8 |
6 |
2 |
5 |
|
Рабочий 2 |
5 |
2 |
9 |
8 |
|
Рабочий 3 |
3 |
8 |
1 |
9 |
|
Рабочий 4 |
1 |
4 |
2 |
3 |
| Рабочий 5 | 3 | 7 | 10 | 5 |
|
|
Работа 1 |
Работа 2 |
Работа 3 |
Работа 4 |
Вариант 5
|
|
Стоимость выполнения работ |
||
|
Рабочий 1 |
10 |
8 |
6 |
|
Рабочий 2 |
6 |
2 |
9 |
|
Рабочий 3 |
3 |
7 |
1 |
|
Рабочий 4 |
9 |
10 |
2 |
|
|
Работа 1 |
Работа 2 |
Работа 3 |