Optprob/Планирование экскурсий — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показано 8 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
<!-- p35 -->
 
<!-- p35 -->
 
{{checked|}}
 
{{checked|}}
 +
 +
[[File:Планирование экскурсий_2023-12-23_04-13-02_image0.png|right]]
  
 
У нас есть группа из 60 экскурсантов, которые наняли услуги компании автобусных туров на следующие 3 дня.  
 
У нас есть группа из 60 экскурсантов, которые наняли услуги компании автобусных туров на следующие 3 дня.  
Строка 6: Строка 8:
 
* Есть шесть различных экскурсий, которые могут быть проведены.
 
* Есть шесть различных экскурсий, которые могут быть проведены.
 
* Каждый экскурсант выбрал максимум три экскурсии. Экскурсант может взять только одну экскурсию в день.
 
* Каждый экскурсант выбрал максимум три экскурсии. Экскурсант может взять только одну экскурсию в день.
−
* Автобусы компании имеют вместимость (количество мест). У компании 10 автобусов.  
+
Вот, какие экскурсии выбрал каждый экскурсант:
 +
{{WikiCutBegin|122 строк отношения «Экскурсант хочет Экскурсию»}}
 +
{| class=wikitable
 +
|-
 +
| Экскурсант
 +
| Экскурсия
 +
|-
 +
| 1
 +
| 1
 +
|-
 +
| 1
 +
| 3
 +
|-
 +
| 1
 +
| 5
 +
|-
 +
| 2
 +
| 2
 +
|-
 +
| 2
 +
| 4
 +
|-
 +
| 3
 +
| 6
 +
|-
 +
| 4
 +
| 2
 +
|-
 +
| 5
 +
| 1
 +
|-
 +
| 5
 +
| 5
 +
|-
 +
| 6
 +
| 4
 +
|-
 +
| 6
 +
| 6
 +
|-
 +
| 6
 +
| 3
 +
|-
 +
| 7
 +
| 1
 +
|-
 +
| 7
 +
| 4
 +
|-
 +
| 7
 +
| 5
 +
|-
 +
| 8
 +
| 3
 +
|-
 +
| 8
 +
| 5
 +
|-
 +
| 9
 +
| 2
 +
|-
 +
| 10
 +
| 1
 +
|-
 +
| 10
 +
| 3
 +
|-
 +
| 11
 +
| 1
 +
|-
 +
| 11
 +
| 4
 +
|-
 +
| 12
 +
| 3
 +
|-
 +
| 12
 +
| 5
 +
|-
 +
| 13
 +
| 6
 +
|-
 +
| 13
 +
| 4
 +
|-
 +
| 14
 +
| 2
 +
|-
 +
| 14
 +
| 6
 +
|-
 +
| 15
 +
| 2
 +
|-
 +
| 15
 +
| 4
 +
|-
 +
| 16
 +
| 4
 +
|-
 +
| 16
 +
| 5
 +
|-
 +
| 17
 +
| 2
 +
|-
 +
| 17
 +
| 6
 +
|-
 +
| 18
 +
| 2
 +
|-
 +
| 18
 +
| 6
 +
|-
 +
| 19
 +
| 1
 +
|-
 +
| 19
 +
| 4
 +
|-
 +
| 20
 +
| 6
 +
|-
 +
| 20
 +
| 2
 +
|-
 +
| 21
 +
| 1
 +
|-
 +
| 21
 +
| 3
 +
|-
 +
| 22
 +
| 4
 +
|-
 +
| 22
 +
| 6
 +
|-
 +
| 23
 +
| 6
 +
|-
 +
| 24
 +
| 1
 +
|-
 +
| 24
 +
| 3
 +
|-
 +
| 24
 +
| 6
 +
|-
 +
| 25
 +
| 2
 +
|-
 +
| 26
 +
| 2
 +
|-
 +
| 26
 +
| 4
 +
|-
 +
| 27
 +
| 4
 +
|-
 +
| 27
 +
| 5
 +
|-
 +
| 28
 +
| 3
 +
|-
 +
| 28
 +
| 5
 +
|-
 +
| 29
 +
| 6
 +
|-
 +
| 29
 +
| 3
 +
|-
 +
| 30
 +
| 1
 +
|-
 +
| 30
 +
| 4
 +
|-
 +
| 30
 +
| 5
 +
|-
 +
| 31
 +
| 6
 +
|-
 +
| 32
 +
| 2
 +
|-
 +
| 33
 +
| 1
 +
|-
 +
| 33
 +
| 3
 +
|-
 +
| 34
 +
| 2
 +
|-
 +
| 34
 +
| 4
 +
|-
 +
| 35
 +
| 4
 +
|-
 +
| 35
 +
| 6
 +
|-
 +
| 36
 +
| 6
 +
|-
 +
| 36
 +
| 2
 +
|-
 +
| 37
 +
| 1
 +
|-
 +
| 37
 +
| 3
 +
|-
 +
| 37
 +
| 5
 +
|-
 +
| 38
 +
| 4
 +
|-
 +
| 38
 +
| 5
 +
|-
 +
| 38
 +
| 6
 +
|-
 +
| 39
 +
| 2
 +
|-
 +
| 40
 +
| 3
 +
|-
 +
| 40
 +
| 5
 +
|-
 +
| 41
 +
| 2
 +
|-
 +
| 41
 +
| 6
 +
|-
 +
| 42
 +
| 2
 +
|-
 +
| 42
 +
| 6
 +
|-
 +
| 43
 +
| 3
 +
|-
 +
| 44
 +
| 4
 +
|-
 +
| 44
 +
| 5
 +
|-
 +
| 45
 +
| 1
 +
|-
 +
| 45
 +
| 4
 +
|-
 +
| 46
 +
| 2
 +
|-
 +
| 46
 +
| 6
 +
|-
 +
| 47
 +
| 2
 +
|-
 +
| 47
 +
| 4
 +
|-
 +
| 48
 +
| 4
 +
|-
 +
| 48
 +
| 6
 +
|-
 +
| 49
 +
| 6
 +
|-
 +
| 50
 +
| 2
 +
|-
 +
| 50
 +
| 6
 +
|-
 +
| 51
 +
| 2
 +
|-
 +
| 52
 +
| 3
 +
|-
 +
| 52
 +
| 5
 +
|-
 +
| 53
 +
| 1
 +
|-
 +
| 53
 +
| 3
 +
|-
 +
| 54
 +
| 3
 +
|-
 +
| 54
 +
| 5
 +
|-
 +
| 55
 +
| 6
 +
|-
 +
| 55
 +
| 2
 +
|-
 +
| 56
 +
| 1
 +
|-
 +
| 56
 +
| 3
 +
|-
 +
| 56
 +
| 5
 +
|-
 +
| 57
 +
| 1
 +
|-
 +
| 57
 +
| 4
 +
|-
 +
| 57
 +
| 5
 +
|-
 +
| 58
 +
| 2
 +
|-
 +
| 58
 +
| 4
 +
|-
 +
| 59
 +
| 4
 +
|-
 +
| 59
 +
| 6
 +
|-
 +
| 59
 +
| 3
 +
|-
 +
| 60
 +
| 4
 +
|-
 +
| 60
 +
| 5
 +
|-
 +
| 60
 +
| 6
 +
|}
 +
 
 +
{{WikiCutEnd}}
 +
 
 +
 
 +
 
 +
* Автобусы компании имеют вместимость (количество мест). У компании 5 автобусов.  
  
 
{| class=wikitable
 
{| class=wikitable
 
|-
 
|-
−
| <font color="#000000">Buses</font>
+
| Buses
−
| <font color="#000000">1</font>
+
| 1
−
| <font color="#000000">2</font>
+
| 2
−
| <font color="#000000">3</font>
+
| 3
−
| <font color="#000000">4</font>
+
| 4
−
| <font color="#000000">5</font>
+
| 5
−
| <font color="#000000">6</font>
+
−
| <font color="#000000">7</font>
+
−
| <font color="#000000">8</font>
+
−
| <font color="#000000">9</font>
+
−
| <font color="#000000">10</font>
+
 
|-
 
|-
−
| <br>  
+
| <br>
−
| <font color="#000000">60</font>
+
| 60
−
| <font color="#000000">40</font>
+
| 50
−
| <font color="#000000">60</font>
+
| 60
−
| <font color="#000000">60</font>
+
| 60
−
| <font color="#000000">35</font>
+
| 40
−
| <font color="#000000">70</font>
+
−
| <font color="#000000">60</font>
+
−
| <font color="#000000">60</font>
+
−
| <font color="#000000">60</font>
+
−
| <font color="#000000">60</font>
+
 
|}
 
|}
  
Строка 49: Строка 413:
 
| 5
 
| 5
 
| 6
 
| 6
−
| 7
 
 
|-
 
|-
 
| 1
 
| 1
 
| 0
 
| 0
−
| 1
 
 
| 1
 
| 1
 
| 0
 
| 0
 
| 0
 
| 0
 
| 0
 
| 0
−
| 0
+
| 1
 
|-
 
|-
 
| 2
 
| 2
Строка 66: Строка 428:
 
| 1
 
| 1
 
| 1
 
| 1
−
| 0
 
 
| 0
 
| 0
 
|-
 
|-
Строка 74: Строка 435:
 
| 0
 
| 0
 
| 0
 
| 0
−
| 1
 
 
| 1
 
| 1
 
| 0
 
| 0
Строка 85: Строка 445:
 
| 1
 
| 1
 
| 0
 
| 0
−
| 1
 
 
|-
 
|-
 
| 5
 
| 5
−
| 0
 
 
| 0
 
| 0
 
| 0
 
| 0
Строка 97: Строка 455:
 
|-
 
|-
 
| 6
 
| 6
−
| 0
 
−
| 0
 
−
| 0
 
−
| 0
 
−
| 0
 
−
| 0
 
−
| 0
 
−
|-
 
−
| 7
 
−
| 0
 
 
| 0
 
| 0
 
| 0
 
| 0
Строка 115: Строка 463:
 
|}
 
|}
  
−
<br>
+
* Однако автобус не должен охватывать более двух экскурсий за один день.
−
 
+
* Компания хочет спланировать экскурсии на 3 дня, чтобы использовать наименьшее количество автобусов
−
<br>
+
(минимизируем «автобусо-дни»).  
−
 
+
** При этом нужно найти назначение экскурсий и экскурсантов на рейсы автобусов
−
 
+
−
 
+
−
Однако автобус не должен охватывать более двух экскурсий за один день.
+
−
 
+
−
 
+
−
 
+
−
 
+
−
 
+
−
 
+
−
 
+
−
Компания хочет спланировать экскурсии на 3 дня, чтобы использовать наименьшее количество автобусов
+
−
(использование каждого автобуса в каждый день добавляется в объективную функцию). Мы должны установить
+
−
систему распределения экскурсантов между автобусами и экскурсий между автобусами, которая гарантирует, что все
+
−
экскурсии проводятся для всех экскурсантов.
+
  
 
{{enddiv}}
 
{{enddiv}}
  
−
[[Category:OptimizationProblems]]
+
{{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}}

Текущая версия на 13:46, 27 сентября 2024

Планирование экскурсий 2023-12-23 04-13-02 image0.png

У нас есть группа из 60 экскурсантов, которые наняли услуги компании автобусных туров на следующие 3 дня.

  • Есть шесть различных экскурсий, которые могут быть проведены.
  • Каждый экскурсант выбрал максимум три экскурсии. Экскурсант может взять только одну экскурсию в день.

Вот, какие экскурсии выбрал каждый экскурсант:


  • Автобусы компании имеют вместимость (количество мест). У компании 5 автобусов.
Buses 1 2 3 4 5

60 50 60 60 40

Один автобус в день может совершить несколько экскурсий в зависимости от близости между ними.

Эта информация будет собрана в бинарном атрибуте между экскурсиями (1: они могут быть выполняться одним и тем же автобусом, 0: нет).

Вблизи 1 2 3 4 5 6
1 0 1 0 0 0 1
2 0 0 0 1 1 0
3 0 0 0 0 1 0
4 0 0 0 0 1 0
5 0 0 0 0 0 0
6 0 0 0 0 0 0
  • Однако автобус не должен охватывать более двух экскурсий за один день.
  • Компания хочет спланировать экскурсии на 3 дня, чтобы использовать наименьшее количество автобусов

(минимизируем «автобусо-дни»).

    • При этом нужно найти назначение экскурсий и экскурсантов на рейсы автобусов

Источник — «https://discopal.ispras.ru/index.php?title=Optprob/Планирование_экскурсий&oldid=29773»