Optprob/Распределение рабочих по производственным центрам — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 12: Строка 12:
  
 
{| class='wikitable'
 
{| class='wikitable'
−
| n
+
| L
 
| 25
 
| 25
 
|-
 
|-
Строка 18: Строка 18:
 
| 40
 
| 40
 
|}
 
|}
 +
 +
Сколько работников в каждом городе?
 +
{| class='wikitable'
 +
|-
 +
|
 +
| 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
 +
|-
 +
| n
 +
| 4
 +
| 8
 +
| 16
 +
| 13
 +
| 10
 +
| 12
 +
| 11
 +
| 10
 +
| 7
 +
| 7
 +
| 7
 +
| 5
 +
| 5
 +
| 3
 +
| 2
 +
| 2
 +
| 1
 +
| 1
 +
| 1
 +
| 2
 +
| 1
 +
| 1
 +
| 2
 +
| 3
 +
| 4
 +
|}
 +
 +
Расстояние между 25 городами (расстояния симметричные, представлены верхней треугольной матрицей).
 +
 +
{| class='wikitable'
 +
|-
 +
|
 +
| 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
 +
|-
 +
| 1
 +
| 0
 +
| 21
 +
|  | 23
 +
|  | 18
 +
|  | 19
 +
|  | 12
 +
|  | 12
 +
|  | 25
 +
|  | 72
 +
|  | 25
 +
|  | 4
 +
|  | 25
 +
|  | 25
 +
|  | 25
 +
|  | 18
 +
|  | 67
 +
|  | 67
 +
|  | 67
 +
|  | 67
 +
|  | 67
 +
|  | 25
 +
|  | 19
 +
|  | 12
 +
|  | 12
 +
|  | 25
 +
|-
 +
| 2
 +
| 0
 +
| 0
 +
| 25
 +
| 5
 +
|  | 13
 +
|  | 4
 +
|  | 4
 +
|  | 12
 +
|  | 5
 +
|  | 12
 +
|  | 19
 +
|  | 12
 +
|  | 12
 +
|  | 12
 +
|  | 12
 +
|  | 75
 +
|  | 75
 +
|  | 75
 +
|  | 75
 +
|  | 75
 +
|  | 12
 +
|  | 13
 +
|  | 4
 +
|  | 4
 +
|  | 12
 +
|-
 +
| 3
 +
|  | 0
 +
|  | 0
 +
|  | 0
 +
|  | 13
 +
|  | 15
 +
|  | 19
 +
|  | 19
 +
|  | 4
 +
|  | 9
 +
|  | 4
 +
|  | 13
 +
|  | 4
 +
|  | 25
 +
|  | 4
 +
|  | 25
 +
|  | 55
 +
|  | 55
 +
|  | 55
 +
|  | 55
 +
|  | 55
 +
|  | 4
 +
|  | 15
 +
|  | 19
 +
|  | 19
 +
|  | 4
 +
|-
 +
| 4
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 35
 +
|  | 13
 +
|  | 13
 +
|  | 19
 +
|  | 39
 +
|  | 19
 +
|  | 15
 +
|  | 19
 +
|  | 12
 +
|  | 19
 +
|  | 12
 +
|  | 25
 +
|  | 25
 +
|  | 25
 +
|  | 25
 +
|  | 25
 +
|  | 19
 +
|  | 12
 +
|  | 13
 +
|  | 13
 +
|  | 19
 +
|-
 +
| 5
 +
| 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 15
 +
|  | 15
 +
|  | 13
 +
|  | 45
 +
|  | 13
 +
|  | 12
 +
|  | 13
 +
|  | 12
 +
|  | 13
 +
|  | 4
 +
|  | 12
 +
|  | 12
 +
|  | 12
 +
|  | 12
 +
|  | 12
 +
|  | 13
 +
|  | 12
 +
|  | 15
 +
|  | 15
 +
|  | 13
 +
|-
 +
| 6
 +
|  | 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 35
 +
|  | 15
 +
|  | 23
 +
|  | 15
 +
|  | 4
 +
|  | 15
 +
|  | 4
 +
|  | 15
 +
|  | 19
 +
|  | 4
 +
|  | 4
 +
|  | 4
 +
|  | 4
 +
|  | 4
 +
|  | 15
 +
|  | 4
 +
|  | 12
 +
|  | 12
 +
|  | 15
 +
|-
 +
| 7
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 12
 +
|  | 22
 +
|  | 12
 +
|  | 19
 +
|  | 12
 +
|  | 19
 +
|  | 12
 +
|  | 13
 +
|  | 19
 +
|  | 19
 +
|  | 19
 +
|  | 19
 +
|  | 19
 +
|  | 12
 +
|  | 19
 +
|  | 12
 +
|  | 19
 +
|  | 12
 +
|-
 +
| 8
 +
| 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 10
 +
|  | 4
 +
|  | 13
 +
|  | 4
 +
|  | 13
 +
|  | 4
 +
|  | 15
 +
|  | 4
 +
|  | 15
 +
|  | 15
 +
|  | 4
 +
|  | 13
 +
|  | 4
 +
|  | 13
 +
|  | 4
 +
|  | 13
 +
|  | 4
 +
|-
 +
| 9
 +
|  | 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 19
 +
|  | 15
 +
|  | 19
 +
|  | 15
 +
|  | 19
 +
|  | 12
 +
|  | 19
 +
|  | 12
 +
|  | 12
 +
|  | 19
 +
|  | 15
 +
|  | 19
 +
|  | 4
 +
|  | 19
 +
|  | 15
 +
|  | 19
 +
|-
 +
| 10
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 12
 +
|  | 13
 +
|  | 12
 +
|  | 13
 +
|  | 4
 +
|  | 13
 +
|  | 4
 +
|  | 4
 +
|  | 13
 +
|  | 12
 +
|  | 13
 +
|  | 19
 +
|  | 13
 +
|  | 12
 +
|  | 13
 +
|-
 +
| 11
 +
|  | 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 15
 +
|  | 4
 +
|  | 15
 +
|  | 19
 +
|  | 15
 +
|  | 19
 +
|  | 19
 +
|  | 15
 +
|  | 4
 +
|  | 15
 +
|  | 13
 +
|  | 15
 +
|  | 4
 +
|  | 15
 +
|-
 +
| 12
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 19
 +
|  | 29
 +
|  | 13
 +
|  | 12
 +
|  | 13
 +
|  | 13
 +
|  | 12
 +
|  | 19
 +
|  | 12
 +
|  | 15
 +
|  | 12
 +
|  | 19
 +
|  | 25
 +
|-
 +
| 13
 +
| 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 43
 +
|  | 15
 +
|  | 4
 +
|  | 15
 +
|  | 15
 +
|  | 4
 +
|  | 13
 +
|  | 4
 +
|  | 12
 +
|  | 15
 +
|  <br>
 +
| 13
 +
|  | 12
 +
|-
 +
| 14
 +
|  | 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 12
 +
|  | 19
 +
|  | 24
 +
|  | 12
 +
|  | 19
 +
|  | 15
 +
|  | 19
 +
|  | 4
 +
|  | 12
 +
|  | 15
 +
|  | 4
 +
|-
 +
| 15
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 13
 +
|  | 36
 +
|  | 4
 +
|  | 13
 +
|  | 4
 +
|  | 13
 +
|  | 19
 +
|  | 11
 +
|  | 78
 +
|  | 19
 +
|-
 +
| 16
 +
|  | 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 15
 +
|  | 15
 +
|  | 19
 +
|  | 15
 +
|  | 19
 +
|  | 15
 +
|  | 13
 +
|  | 77
 +
|  | 49
 +
|  | 13
 +
|-
 +
| 17
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 13
 +
|  | 32
 +
|  | 13
 +
|  | 4
 +
|  | 15
 +
|  | 12
 +
|  | 29
 +
|  | 15
 +
|-
 +
| 18
 +
|  | 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 23
 +
|  | 15
 +
|  | 19
 +
|  | 4
 +
|  | 4
 +
|  | 43
 +
|  | 12
 +
|-
 +
| 19
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 25
 +
|  | 13
 +
|  | 19
 +
|  | 19
 +
|  | 9
 +
|  | 4
 +
|-
 +
| 20
 +
|  | 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 15
 +
|  | 13
 +
|  | 13
 +
|  | 11
 +
|  | 19
 +
|-
 +
| 21
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 15
 +
|  | 15
 +
|  | 12
 +
|  | 13
 +
|-
 +
| 22
 +
|  | 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 12
 +
|  | 23
 +
|  | 15
 +
|-
 +
| 23
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 34
 +
|  | 20
 +
|-
 +
| 24
 +
| 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|  | 11
 +
|-
 +
|  | 25
 +
|  | 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
| 0
 +
| 0
 +
|  | 0
 +
|  | 0
 +
|}
 +
 +
----
 +
Рабочие центры
 +
 +
 +
{| class='wikitable'
 +
|-
 +
|
 +
| 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
 +
| 26
 +
| 27
 +
| 28
 +
| 29
 +
| 30
 +
| 31
 +
| 32
 +
| 33
 +
| 34
 +
| 35
 +
| 36
 +
| 37
 +
| 38
 +
| 39
 +
| 40
 +
|-
 +
|  | '''Mini'''
 +
|  | 2
 +
|  | 3
 +
|  | 2
 +
|  | 3
 +
|  | 4
 +
|  | 2
 +
|  | 3
 +
|  | 4
 +
|  | 2
 +
|  | 3
 +
|  | 4
 +
|  | 2
 +
|  | 3
 +
|  | 4
 +
|  | 2
 +
| 2
 +
|  | 2
 +
| 2
 +
| 2
 +
|  | 3
 +
|  | 4
 +
|  | 2
 +
| 2
 +
|  | 2
 +
| 2
 +
|  | 3
 +
|  | 4
 +
|  | 2
 +
| 2
 +
|  | 2
 +
| 2
 +
|  | 3
 +
|  | 4
 +
|  | 2
 +
| 2
 +
|  | 2
 +
| 2
 +
|  | 4
 +
|  | 5
 +
|  | 5
 +
|-
 +
|  | '''Maxi'''
 +
|  | 5
 +
|  | 5
 +
|  | 5
 +
|  | 5
 +
|  | 7
 +
|  | 4
 +
|  | 4
 +
|  | 6
 +
| 4
 +
| 5
 +
|  | 7
 +
| 4
 +
|  | 4
 +
| 5
 +
|  | 5
 +
| 4
 +
|  | 4
 +
| 4
 +
|  | 4
 +
| 5
 +
| 6
 +
|  | 4
 +
| 4
 +
|  | 4
 +
| 4
 +
|  | 4
 +
|  | 6
 +
|  | 4
 +
|  | 4
 +
|  | 4
 +
|  | 4
 +
|  | 5
 +
|  | 7
 +
|  | 5
 +
|  | 4
 +
|  | 4
 +
|  | 4
 +
|  | 6
 +
|  | 7
 +
|  | 7
 +
|-
 +
|  | '''City'''
 +
|  | 1
 +
|  | 1
 +
|  | 2
 +
|  | 2
 +
|  | 2
 +
|  | 3
 +
|  | 4
 +
|  | 5
 +
|  | 6
 +
|  | 7
 +
| 8
 +
| 8
 +
|  | 9
 +
| 9
 +
|  | 10
 +
| 11
 +
|  | 12
 +
| 13
 +
|  | 14
 +
| 15
 +
|  | 16
 +
| 17
 +
| 17
 +
|  | 17
 +
| 18
 +
|  | 18
 +
|  | 19
 +
|  | 19
 +
|  | 20
 +
|  | 20
 +
|  | 20
 +
|  | 21
 +
|  | 22
 +
|  | 22
 +
|  | 23
 +
|  | 23
 +
|  | 24
 +
|  | 24
 +
|  | 25
 +
|  | 25
 +
|}
 +
 +
<br>
 +
 +
<br>
 +
  
  
Строка 24: Строка 970:
 
{{enddiv}}
 
{{enddiv}}
  
−
[[Category:OptimizationProblems]]
+
[[Категория:OptimizationProblems]]

Версия 08:02, 17 ноября 2022

  • Есть L городов
  • Есть n рабочих.
    • Каждый работник живет в определенном городе.
  • Есть m рабочих центров, каждый из которых
    • расположен в определенном городе.
    • имеет минимальную и максимальную потребность в работниках.

Надо так назначить работников к производственным центрам, чтобы минимизировать полное расстояние, которое проезжают эти рабочие.

L 25
m 40

Сколько работников в каждом городе?

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
n 4 8 16 13 10 12 11 10 7 7 7 5 5 3 2 2 1 1 1 2 1 1 2 3 4

Расстояние между 25 городами (расстояния симметричные, представлены верхней треугольной матрицей).

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
1 0 21 23 18 19 12 12 25 72 25 4 25 25 25 18 67 67 67 67 67 25 19 12 12 25
2 0 0 25 5 13 4 4 12 5 12 19 12 12 12 12 75 75 75 75 75 12 13 4 4 12
3 0 0 0 13 15 19 19 4 9 4 13 4 25 4 25 55 55 55 55 55 4 15 19 19 4
4 0 0 0 0 35 13 13 19 39 19 15 19 12 19 12 25 25 25 25 25 19 12 13 13 19
5 0 0 0 0 0 15 15 13 45 13 12 13 12 13 4 12 12 12 12 12 13 12 15 15 13
6 0 0 0 0 0 0 35 15 23 15 4 15 4 15 19 4 4 4 4 4 15 4 12 12 15
7 0 0 0 0 0 0 0 12 22 12 19 12 19 12 13 19 19 19 19 19 12 19 12 19 12
8 0 0 0 0 0 0 0 0 10 4 13 4 13 4 15 4 15 15 4 13 4 13 4 13 4
9 0 0 0 0 0 0 0 0 0 19 15 19 15 19 12 19 12 12 19 15 19 4 19 15 19
10 0 0 0 0 0 0 0 0 0 0 12 13 12 13 4 13 4 4 13 12 13 19 13 12 13
11 0 0 0 0 0 0 0 0 0 0 0 15 4 15 19 15 19 19 15 4 15 13 15 4 15
12 0 0 0 0 0 0 0 0 0 0 0 0 19 29 13 12 13 13 12 19 12 15 12 19 25
13 0 0 0 0 0 0 0 0 0 0 0 0 0 43 15 4 15 15 4 13 4 12 15
13 12
14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 19 24 12 19 15 19 4 12 15 4
15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 36 4 13 4 13 19 11 78 19
16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 15 19 15 19 15 13 77 49 13
17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 32 13 4 15 12 29 15
18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 23 15 19 4 4 43 12
19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 25 13 19 19 9 4
20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 13 13 11 19
21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 15 12 13
22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 23 15
23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 34 20
24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11
25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Рабочие центры


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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
Mini 2 3 2 3 4 2 3 4 2 3 4 2 3 4 2 2 2 2 2 3 4 2 2 2 2 3 4 2 2 2 2 3 4 2 2 2 2 4 5 5
Maxi 5 5 5 5 7 4 4 6 4 5 7 4 4 5 5 4 4 4 4 5 6 4 4 4 4 4 6 4 4 4 4 5 7 5 4 4 4 6 7 7
City 1 1 2 2 2 3 4 5 6 7 8 8 9 9 10 11 12 13 14 15 16 17 17 17 18 18 19 19 20 20 20 21 22 22 23 23 24 24 25 25




Нужно дорабатывать

Источник — «https://discopal.ispras.ru/index.php?title=Optprob/Распределение_рабочих_по_производственным_центрам&oldid=21831»