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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена Категория:OptimizationProblems на {{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}})
 
(не показано 6 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
<!-- p20 -->
 
<!-- p20 -->
 
{{checked|}}
 
{{checked|}}
 +
  
 
Система имеет N=25 задач и M=10 операторов.  
 
Система имеет N=25 задач и M=10 операторов.  
Строка 64: Строка 65:
 
| 4
 
| 4
 
|}
 
|}
 +
 +
[[File:Назначение задач операторам_2023-12-23_03-11-04_image0.png|right|200px]]
  
 
* Время обработки задачи каждым оператором.
 
* Время обработки задачи каждым оператором.
Строка 85: Строка 88:
 
| 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: Строка 102:
 
| 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: Строка 137:
 
| 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: Строка 197:
 
| 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: Строка 221:
 
| 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: Строка 231:
 
| 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: Строка 269:
 
| 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: Строка 293:
 
| 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: Строка 304:
 
| 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: Строка 317:
 
| 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: Строка 328:
 
| 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: Строка 587:
 
| 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
Строка 749: Строка 752:
  
 
Ограничения:
 
Ограничения:
−
* Для каждой выполненненной задачи, количество задач с более высоким приоритетом, чем она, и не может превышать 2.
+
* Для каждой выполненненной задачи, количество невыполненных задач с более высоким приоритетом, чем она не может превышать 2 (чем выше цифра приоритета — тем больше приоритет).
−
* У компании есть лимит расходов, который не должен быть превышен.  
+
* У компании есть лимит расходов G=900, который не должен быть превышен.  
  
 
Цель — максимизировать количество выполненных задач.
 
Цель — максимизировать количество выполненных задач.
 +
 +
* [[Участник:ScherbakIA/Назначение задач операторам]] — перепроверить.
 
{{enddiv}}
 
{{enddiv}}
−
{{reserve-task|[[Участник:ScherbakIA|ScherbakIA]] 14:15, 17 ноября 2022 (UTC)}}
 
  
−
[[Категория:OptimizationProblems]]
+
{{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}}

Текущая версия на 11:59, 23 декабря 2023


Система имеет 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
Назначение задач операторам 2023-12-23 03-11-04 image0.png
  • Время обработки задачи каждым оператором.


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, который не должен быть превышен.

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

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