Optprob/Назначение задач операторам — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 85: Строка 85:
 
| 10
 
| 10
 
| 0
 
| 0
−
| valign="bottom" | 23
+
| | 23
−
| valign="bottom" | 18
+
| | 18
−
| valign="bottom" | 19
+
| | 19
−
| valign="bottom" | 12
+
| | 12
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 32
+
| | 32
−
| valign="bottom" | 25
+
| | 25
 
|-
 
|-
 
| 2
 
| 2
Строка 99: Строка 99:
 
| 0
 
| 0
 
| 0
 
| 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 4
+
| | 4
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 5
+
| | 5
−
| valign="bottom" | 0
+
| | 0
 
|-
 
|-
 
| 3
 
| 3
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 7
+
| | 7
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 15
+
| | 15
−
| valign="bottom" | 19
+
| | 19
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 9
+
| | 9
−
| valign="bottom" | 0
+
| | 0
 
|-
 
|-
 
| 4
 
| 4
 
| 0
 
| 0
 
| 0
 
| 0
−
| valign="bottom" | 13
+
| | 13
 
| 0
 
| 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 13
+
| | 13
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
 
|-
 
|-
 
| 5
 
| 5
Строка 134: Строка 134:
 
| 0
 
| 0
 
| 0
 
| 0
−
| valign="bottom" | 34
+
| | 34
−
| valign="bottom" | 12
+
| | 12
−
| valign="bottom" | 15
+
| | 15
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 45
+
| | 45
−
| valign="bottom" | 13
+
| | 13
 
|-
 
|-
 
| 6
 
| 6
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 15
+
| | 15
−
| valign="bottom" | 13
+
| | 13
−
| valign="bottom" | 45
+
| | 45
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 35
+
| | 35
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
 
|-
 
|-
 
| 7
 
| 7
−
| valign="bottom" | 12
+
| | 12
−
| valign="bottom" | 15
+
| | 15
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 45
+
| | 45
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 15
+
| | 15
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 22
+
| | 22
−
| valign="bottom" | 12
+
| | 12
 
|-
 
|-
 
| 8
 
| 8
 
| 0
 
| 0
−
| valign="bottom" | 0
+
| | 0
 
| 0
 
| 0
−
| valign="bottom" | 35
+
| | 35
−
| valign="bottom" | 13
+
| | 13
−
| valign="bottom" | 13
+
| | 13
−
| valign="bottom" | 19
+
| | 19
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 10
+
| | 10
−
| valign="bottom" | 0
+
| | 0
 
|-
 
|-
 
| 9
 
| 9
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 12
+
| | 12
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 25
+
| | 25
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 25
+
| | 25
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
 
|-
 
|-
 
| 10
 
| 10
Строка 194: Строка 194:
 
| 24
 
| 24
 
| 0
 
| 0
−
| valign="bottom" | 34
+
| | 34
−
| valign="bottom" | 12
+
| | 12
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 72
+
| | 72
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
 
|-
 
|-
 
| 11
 
| 11
 
| 0
 
| 0
−
| valign="bottom" | 35
+
| | 35
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 19
+
| | 19
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 19
+
| | 19
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 21
+
| | 21
 
|-
 
|-
 
| 12
 
| 12
Строка 218: Строка 218:
 
| 24
 
| 24
 
| 0
 
| 0
−
| valign="bottom" | 34
+
| | 34
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 19
+
| | 19
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 19
+
| | 19
 
| 0
 
| 0
 
| 0
 
| 0
Строка 228: Строка 228:
 
| 13
 
| 13
 
| 14
 
| 14
−
| valign="bottom" | 35
+
| | 35
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 13
+
| | 13
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 19
+
| | 19
−
| valign="bottom" | 13
+
| | 13
−
| valign="bottom" | 0
+
| | 0
 
| 0
 
| 0
 
|-
 
|-
 
| 14
 
| 14
−
| valign="bottom" | 18
+
| | 18
−
| valign="bottom" | 19
+
| | 19
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 12
+
| | 12
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 72
+
| | 72
−
| valign="bottom" | 0
+
| | 0
 
| 21
 
| 21
 
| 0
 
| 0
−
| valign="bottom" | 23
+
| | 23
 
|-
 
|-
 
| 15
 
| 15
 
| 14
 
| 14
−
| valign="bottom" | 35
+
| | 35
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 19
+
| | 19
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 25
+
| | 25
 
| 0
 
| 0
 
| 0
 
| 0
Строка 266: Строка 266:
 
| 24
 
| 24
 
| 0
 
| 0
−
| valign="bottom" | 34
+
| | 34
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 12
+
| | 12
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 72
+
| | 72
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
 
|-
 
|-
 
| 17
 
| 17
 
| 0
 
| 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 13
+
| | 13
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 25
+
| | 25
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 25
+
| | 25
 
|-
 
|-
 
| 18
 
| 18
Строка 290: Строка 290:
 
| 24
 
| 24
 
| 0
 
| 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 72
+
| | 72
−
| valign="bottom" | 0
+
| | 0
 
| 21
 
| 21
 
|-
 
|-
Строка 301: Строка 301:
 
| 20
 
| 20
 
| 14
 
| 14
−
| valign="bottom" | 35
+
| | 35
−
| valign="bottom" | 13
+
| | 13
−
| valign="bottom" | 13
+
| | 13
−
| valign="bottom" | 19
+
| | 19
−
| valign="bottom" | 39
+
| | 39
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 25
+
| | 25
−
| valign="bottom" | 0
+
| | 0
 
|-
 
|-
 
| 20
 
| 20
Строка 314: Строка 314:
 
| 0
 
| 0
 
| 0
 
| 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 13
+
| | 13
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
 
| 20
 
| 20
 
| 21
 
| 21
Строка 325: Строка 325:
 
| 0
 
| 0
 
| 22
 
| 22
−
| valign="bottom" | 0
+
| | 0
 
| 0
 
| 0
−
| valign="bottom" | 35
+
| | 35
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 13
+
| | 13
−
| valign="bottom" | 0
+
| | 0
 
|-
 
|-
 
| 22
 
| 22
−
| valign="bottom" | 12
+
| | 12
−
| valign="bottom" | 13
+
| | 13
 
| 0
 
| 0
−
| valign="bottom" | 35
+
| | 35
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 19
+
| | 19
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 19
+
| | 19
−
| valign="bottom" | 15
+
| | 15
 
|-
 
|-
 
| 23
 
| 23
 
| 11
 
| 11
 
| 0
 
| 0
−
| valign="bottom" | 35
+
| | 35
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 39
+
| | 39
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 12
+
| | 12
 
| 13
 
| 13
 
|-
 
|-
 
| 24
 
| 24
 
| 10
 
| 10
−
| valign="bottom" | 0
+
| | 0
 
| 0
 
| 0
−
| valign="bottom" | 35
+
| | 35
−
| valign="bottom" | 13
+
| | 13
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 19
+
| | 19
−
| valign="bottom" | 0
+
| | 0
 
| 11
 
| 11
−
| valign="bottom" | 12
+
| | 12
 
|-
 
|-
−
| valign="bottom" | 25
+
| | 25
−
| valign="bottom" | 19
+
| | 19
 
| 0
 
| 0
 
| 0
 
| 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 25
+
| | 25
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 25
+
| | 25
−
| valign="bottom" | 19
+
| | 19
 
|}
 
|}
  
Строка 584: Строка 584:
 
| 1
 
| 1
 
|-
 
|-
−
| valign="bottom" | 16
+
| | 16
 
| 0
 
| 0
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
 
|-
 
|-
−
| valign="bottom" | 17
+
| | 17
 
| 0
 
| 0
 
| 0
 
| 0
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
 
|-
 
|-
−
| valign="bottom" | 18
+
| | 18
−
| valign="bottom" | 0
+
| | 0
 
| 1
 
| 1
 
| 0
 
| 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 1
+
| | 1
 
|-
 
|-
−
| valign="bottom" | 19
+
| | 19
 
| 1
 
| 1
−
| valign="bottom" | 1
+
| | 1
 
| 1
 
| 1
 
| 1
 
| 1
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 0
+
| | 0
 
|-
 
|-
−
| valign="bottom" | 20
+
| | 20
 
| 0
 
| 0
 
| 0
 
| 0
−
| valign="bottom" | 0
+
| | 0
 
| 0
 
| 0
 
| 0
 
| 0
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 1
+
| | 1
 
|-
 
|-
−
| valign="bottom" | 21
+
| | 21
−
| valign="bottom" | 0
+
| | 0
 
| 1
 
| 1
 
| 0
 
| 0
−
| valign="bottom" | 0
+
| | 0
 
| 1
 
| 1
 
| 0
 
| 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 0
+
| | 0
 
|-
 
|-
−
| valign="bottom" | 22
+
| | 22
 
| 1
 
| 1
−
| valign="bottom" | 1
+
| | 1
 
| 0
 
| 0
 
| 1
 
| 1
−
| valign="bottom" | 0
+
| | 0
 
| 0
 
| 0
 
| 1
 
| 1
−
| valign="bottom" | 0
+
| | 0
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 1
+
| | 1
 
|-
 
|-
−
| valign="bottom" | 23
+
| | 23
−
| valign="bottom" | 1
+
| | 1
 
| 0
 
| 0
−
| valign="bottom" | 1
+
| | 1
 
| 0
 
| 0
 
| 0
 
| 0
−
| valign="bottom" | 0
+
| | 0
 
| 1
 
| 1
 
| 0
 
| 0
−
| valign="bottom" | 1
+
| | 1
−
| valign="bottom" | 1
+
| | 1
 
|-
 
|-
−
| valign="bottom" | 24
+
| | 24
 
| 1
 
| 1
−
| valign="bottom" | 0
+
| | 0
 
| 0
 
| 0
−
| valign="bottom" | 1
+
| | 1
 
| 1
 
| 1
 
| 0
 
| 0
−
| valign="bottom" | 1
+
| | 1
 
| 0
 
| 0
 
| 1
 
| 1
−
| valign="bottom" | 1
+
| | 1
 
|-
 
|-
−
| valign="bottom" | 25
+
| | 25
 
| 1
 
| 1
 
| 0
 
| 0
−
| valign="bottom" | 0
+
| | 0
 
| 0
 
| 0
−
| valign="bottom" | 0
+
| | 0
 
| 0
 
| 0
 
| 1
 
| 1
−
| valign="bottom" | 0
+
| | 0
 
| 1
 
| 1
 
| 1
 
| 1
Строка 750: Строка 750:
 
Ограничения:
 
Ограничения:
 
* Для каждой выполненненной задачи, количество задач с более высоким приоритетом, чем она, и не может превышать 2.
 
* Для каждой выполненненной задачи, количество задач с более высоким приоритетом, чем она, и не может превышать 2.
−
* У компании есть лимит расходов, который не должен быть превышен.  
+
* У компании есть лимит расходов G=900, который не должен быть превышен.  
  
 
Цель — максимизировать количество выполненных задач.
 
Цель — максимизировать количество выполненных задач.

Версия 18:28, 17 ноября 2022

Система имеет N=25 задач и M=10 операторов.

Каждая задача имеет следующие характеристики:

  • Приоритет задачи: Значение от 0 до 10.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Приоритет 4 8 9 9 10 2 3 4 7 7 7 5 5 3 2 2 1 1 1 2 1 1 2 3 4
  • Время обработки задачи каждым оператором.


1 2 3 4 5 6 7 8 9 10
1 10 0 23 18 19 12 0 0 32 25
2 0 14 0 0 0 4 0 0 5 0
3 0 7 0 0 15 19 0 0 9 0
4 0 0 13 0 0 13 0 0 0 0
5 23 0 0 34 12 15 0 0 45 13
6 0 0 15 13 45 0 35 0 0 0
7 12 15 0 0 45 0 15 0 22 12
8 0 0 0 35 13 13 19 0 10 0
9 0 0 12 0 25 0 25 0 0 0
10 0 24 0 34 12 0 72 0 0 0
11 0 35 0 0 19 0 19 0 0 21
12 23 24 0 34 0 19 0 19 0 0
13 14 35 0 13 0 0 19 13 0 0
14 18 19 0 12 0 72 0 21 0 23
15 14 35 0 0 19 0 0 25 0 0
16 0 24 0 34 0 12 0 72 0 0
17 0 0 13 0 0 0 0 25 0 25
18 0 24 0 0 0 0 0 72 0 21
19 20 14 35 13 13 19 39 0 25 0
20 0 0 0 0 0 13 0 0 20 21
21 0 22 0 0 35 0 0 0 13 0
22 12 13 0 35 0 0 19 0 19 15
23 11 0 35 0 0 0 39 0 12 13
24 10 0 0 35 13 0 19 0 11 12
25 19 0 0 0 0 0 25 0 25 19

Каждый оператор имеет следующие характеристики:

  • Совместимость с задачами: Есть задачи, которые они могут выполнять (1), и другие, которые

они не могут (0).



1 2 3 4 5 6 7 8 9 10
1 1 0 1 1 1 1 0 0 1 1
2 0 1 0 0 0 1 0 0 1 0
3 0 1 0 0 1 1 0 0 1 0
4 0 0 1 0 0 1 0 0 1 0
5 1 0 0 1 1 1 0 0 0 0
6 0 0 1 1 1 0 1 0 1 1
7 1 1 0 0 1 0 1 0 0 0
8 1 0 0 1 1 1 1 0 1 1
9 0 0 1 0 1 0 1 0 1 0
10 0 1 0 1 1 0 1 0 0 0
11 0 1 0 0 1 0 1 0 0 0
12 1 1 0 1 0 1 0 1 0 1
13 1 1 0 1 0 0 1 1 0 0
14 1 1 0 1 0 1 0 1 0 0
15 1 1 0 0 1 0 0 1 0 1
16 0 1 0 1 0 1 0 1 0 0
17 0 0 1 0 0 1 0 1 0 0
18 0 1 0 0 0 0 0 1 0 1
19 1 1 1 1 1 1 1 0 1 0
20 0 0 0 0 0 1 0 0 1 1
21 0 1 0 0 1 0 0 0 1 0
22 1 1 0 1 0 0 1 0 1 1
23 1 0 1 0 0 0 1 0 1 1
24 1 0 0 1 1 0 1 0 1 1
25 1 0 0 0 0 0 1 0 1 1

Каждый оператор имеет:

  • Максимальное время работы.
  • фиксированную стоимость.
1 2 3 4 5 6 7 8 9 10
Costs 35 34 38 41 42 50 39 31 25 29
Maximum Times 100 80 70 70 50 40 80 90 50 50

Ограничения:

  • Для каждой выполненненной задачи, количество задач с более высоким приоритетом, чем она, и не может превышать 2.
  • У компании есть лимит расходов G=900, который не должен быть превышен.

Цель — максимизировать количество выполненных задач.

Задача зарезервирована: ScherbakIA 14:15, 17 ноября 2022 (UTC)

Источник — «https://discopal.ispras.ru/index.php?title=Optprob/Назначение_задач_операторам&oldid=21862»