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

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показано 6 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
<!-- p35 -->
 
<!-- p35 -->
 
{{checked|}}
 
{{checked|}}
 +
 +
[[File:Планирование экскурсий_2023-12-23_04-13-02_image0.png|right]]
  
 
У нас есть группа из 60 экскурсантов, которые наняли услуги компании автобусных туров на следующие 3 дня.  
 
У нас есть группа из 60 экскурсантов, которые наняли услуги компании автобусных туров на следующие 3 дня.  
  
* Есть семь различных экскурсий, которые могут быть проведены.
+
* Есть шесть различных экскурсий, которые могут быть проведены.
 
* Каждый экскурсант выбрал максимум три экскурсии. Экскурсант может взять только одну экскурсию в день.
 
* Каждый экскурсант выбрал максимум три экскурсии. Экскурсант может взять только одну экскурсию в день.
 
Вот, какие экскурсии выбрал каждый экскурсант:
 
Вот, какие экскурсии выбрал каждый экскурсант:
{{WikiCutBegin|400 строк отношения «Экскурсант хочет Экскурсию»}}
+
{{WikiCutBegin|122 строк отношения «Экскурсант хочет Экскурсию»}}
<pre>
+
Экскурсант Экскурсия
+
1 1
+
1 3
+
1 5
+
2 2
+
2 4
+
3 6
+
4 7
+
5 1
+
5 3
+
5 5
+
6 4
+
6 6
+
6 7
+
7 1
+
7 4
+
7 5
+
8 3
+
8 5
+
9 2
+
10 1
+
10 3
+
10 6
+
11 1
+
11 4
+
11 5
+
12 3
+
12 5
+
13 6
+
13 7
+
14 2
+
14 6
+
15 2
+
15 4
+
16 4
+
16 5
+
16 6
+
17 2
+
17 6
+
18 2
+
18 6
+
19 1
+
19 4
+
19 5
+
20 6
+
20 7
+
21 1
+
21 3
+
21 5
+
22 4
+
22 6
+
22 7
+
23 6
+
24 1
+
24 3
+
24 6
+
25 2
+
26 2
+
26 4
+
27 4
+
27 5
+
27 6
+
28 3
+
28 5
+
29 6
+
29 7
+
30 1
+
30 4
+
30 5
+
31 6
+
32 2
+
33 1
+
33 3
+
33 6
+
34 2
+
34 4
+
35 4
+
35 6
+
35 7
+
36 6
+
36 7
+
37 1
+
37 3
+
37 5
+
38 4
+
38 5
+
38 6
+
39 2
+
39 6
+
40 3
+
40 5
+
41 2
+
41 6
+
42 2
+
42 6
+
43 7
+
44 4
+
44 5
+
44 6
+
45 1
+
45 4
+
45 5
+
46 2
+
46 6
+
47 2
+
47 4
+
48 4
+
48 6
+
48 7
+
49 6
+
50 2
+
50 6
+
51 2
+
52 3
+
52 5
+
53 1
+
53 3
+
53 6
+
54 3
+
54 5
+
55 6
+
55 7
+
56 1
+
56 3
+
56 5
+
57 1
+
57 4
+
57 5
+
58 2
+
58 4
+
59 4
+
59 6
+
59 7
+
60 4
+
60 5
+
60 6
+
61 2
+
61 6
+
62 2
+
62 6
+
63 2
+
63 6
+
64 6
+
65 2
+
65 6
+
66 2
+
66 6
+
67 4
+
67 5
+
67 6
+
68 2
+
69 7
+
70 1
+
70 3
+
70 6
+
71 4
+
71 6
+
71 7
+
72 1
+
72 4
+
72 5
+
73 1
+
73 3
+
73 5
+
74 3
+
74 5
+
75 6
+
75 7
+
76 2
+
76 4
+
77 2
+
77 6
+
78 4
+
78 6
+
78 7
+
79 6
+
79 7
+
80 6
+
81 3
+
81 5
+
82 2
+
83 4
+
83 6
+
83 7
+
84 1
+
84 3
+
84 6
+
85 4
+
85 5
+
85 6
+
86 2
+
86 6
+
87 1
+
87 3
+
87 5
+
88 2
+
88 6
+
89 1
+
89 4
+
89 5
+
90 7
+
91 3
+
91 5
+
92 4
+
92 5
+
92 6
+
93 2
+
93 6
+
94 6
+
94 7
+
95 6
+
96 1
+
96 3
+
96 6
+
97 2
+
97 4
+
98 2
+
98 6
+
99 4
+
99 6
+
99 7
+
100 2
+
101 4
+
101 5
+
101 6
+
102 1
+
102 3
+
102 5
+
103 3
+
103 5
+
104 1
+
104 4
+
104 5
+
105 6
+
105 7
+
106 1
+
106 4
+
106 5
+
107 4
+
107 6
+
107 7
+
108 2
+
108 6
+
109 2
+
109 6
+
110 4
+
110 6
+
110 7
+
111 4
+
111 5
+
111 6
+
112 7
+
113 6
+
114 1
+
114 3
+
114 6
+
115 3
+
115 5
+
116 1
+
116 3
+
116 5
+
117 2
+
117 6
+
118 2
+
118 6
+
119 2
+
119 6
+
120 6
+
120 7
+
121 2
+
122 6
+
122 7
+
123 4
+
123 5
+
123 6
+
124 1
+
124 4
+
124 5
+
125 6
+
125 7
+
126 2
+
127 3
+
127 5
+
128 1
+
128 4
+
128 5
+
129 6
+
130 1
+
130 3
+
130 6
+
131 4
+
131 6
+
131 7
+
132 6
+
132 7
+
133 1
+
133 3
+
133 5
+
134 7
+
135 4
+
135 5
+
135 6
+
136 2
+
136 6
+
137 2
+
137 6
+
138 2
+
138 6
+
139 2
+
140 3
+
140 5
+
141 4
+
141 6
+
141 7
+
142 2
+
142 6
+
143 2
+
143 6
+
144 6
+
145 1
+
145 4
+
145 5
+
146 6
+
146 7
+
147 4
+
147 5
+
147 6
+
148 1
+
148 3
+
148 5
+
149 1
+
149 3
+
149 6
+
150 2
+
151 1
+
151 4
+
151 5
+
152 3
+
152 5
+
153 7
+
154 1
+
154 4
+
154 5
+
155 4
+
155 6
+
155 7
+
156 6
+
156 7
+
157 6
+
157 7
+
158 4
+
158 5
+
158 6
+
159 2
+
159 6
+
160 4
+
160 5
+
160 6
+
161 1
+
161 3
+
161 5
+
162 1
+
162 3
+
162 6
+
163 6
+
163 7
+
164 1
+
164 4
+
164 5
+
165 3
+
165 5
+
166 4
+
166 6
+
166 7
+
167 2
+
168 1
+
168 4
+
168 5
+
169 6
+
169 7
+
170 7
+
171 4
+
171 5
+
171 6
+
172 1
+
172 3
+
172 6
+
173 1
+
173 4
+
173 5
+
174 6
+
174 7
+
175 4
+
175 6
+
175 7
+
176 3
+
176 5
+
177 1
+
177 4
+
177 5
+
178 4
+
178 6
+
178 7
+
179 2
+
180 7
+
</pre>
+
{{WikiCutEnd}}
+
 
+
 
+
 
+
* Автобусы компании имеют вместимость (количество мест). У компании 10 автобусов.
+
 
+
 
{| class=wikitable
 
{| class=wikitable
 
|-
 
|-
| Buses
+
| Экскурсант
 +
| Экскурсия
 +
|-
 
| 1
 
| 1
 +
| 1
 +
|-
 +
| 1
 +
| 3
 +
|-
 +
| 1
 +
| 5
 +
|-
 
| 2
 
| 2
 +
| 2
 +
|-
 +
| 2
 +
| 4
 +
|-
 
| 3
 
| 3
 +
| 6
 +
|-
 
| 4
 
| 4
 +
| 2
 +
|-
 
| 5
 
| 5
 +
| 1
 +
|-
 +
| 5
 +
| 5
 +
|-
 
| 6
 
| 6
 +
| 4
 +
|-
 +
| 6
 +
| 6
 +
|-
 +
| 6
 +
| 3
 +
|-
 
| 7
 
| 7
 +
| 1
 +
|-
 +
| 7
 +
| 4
 +
|-
 +
| 7
 +
| 5
 +
|-
 
| 8
 
| 8
 +
| 3
 +
|-
 +
| 8
 +
| 5
 +
|-
 
| 9
 
| 9
 +
| 2
 +
|-
 
| 10
 
| 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
 
|-
 
|-
| <br>
 
| 60
 
 
| 40
 
| 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
 
| 60
 +
| 4
 +
|-
 
| 60
 
| 60
| 35
+
| 5
| 70
+
|-
 
| 60
 
| 60
 +
| 6
 +
|}
 +
 +
{{WikiCutEnd}}
 +
 +
 +
 +
* Автобусы компании имеют вместимость (количество мест). У компании 5 автобусов.
 +
 +
{| class=wikitable
 +
|-
 +
| Buses
 +
| 1
 +
| 2
 +
| 3
 +
| 4
 +
| 5
 +
|-
 +
| <br>
 
| 60
 
| 60
 +
| 50
 
| 60
 
| 60
 
| 60
 
| 60
 +
| 40
 
|}
 
|}
  
Строка 462: Строка 413:
 
| 5
 
| 5
 
| 6
 
| 6
| 7
 
 
|-
 
|-
 
| 1
 
| 1
 
| 0
 
| 0
| 1
 
 
| 1
 
| 1
 
| 0
 
| 0
 
| 0
 
| 0
 
| 0
 
| 0
| 0
+
| 1
 
|-
 
|-
 
| 2
 
| 2
Строка 479: Строка 428:
 
| 1
 
| 1
 
| 1
 
| 1
| 0
 
 
| 0
 
| 0
 
|-
 
|-
Строка 487: Строка 435:
 
| 0
 
| 0
 
| 0
 
| 0
| 1
 
 
| 1
 
| 1
 
| 0
 
| 0
Строка 498: Строка 445:
 
| 1
 
| 1
 
| 0
 
| 0
| 1
 
 
|-
 
|-
 
| 5
 
| 5
| 0
 
 
| 0
 
| 0
 
| 0
 
| 0
Строка 510: Строка 455:
 
|-
 
|-
 
| 6
 
| 6
| 0
 
| 0
 
| 0
 
| 0
 
| 0
 
| 0
 
| 0
 
|-
 
| 7
 
| 0
 
 
| 0
 
| 0
 
| 0
 
| 0
Строка 528: Строка 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 дня, чтобы использовать наименьшее количество автобусов

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

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