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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
У нас есть группа из 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
 
| 60
 +
| 6
 +
|}
 +
 +
{{WikiCutEnd}}
 +
 +
 +
 +
* Автобусы компании имеют вместимость (количество мест). У компании 5 автобусов.
 +
 +
{| class=wikitable
 +
|-
 +
| Buses
 +
| 1
 +
| 2
 +
| 3
 +
| 4
 +
| 5
 +
|-
 +
| <br>
 +
|
 +
| 50
 
| 60
 
| 60
 
| 60
 
| 60
 +
| 40
 
|}
 
|}
  
Строка 462: Строка 411:
 
| 5
 
| 5
 
| 6
 
| 6
−
| 7
 
 
|-
 
|-
 
| 1
 
| 1
 
| 0
 
| 0
−
| 1
 
 
| 1
 
| 1
 
| 0
 
| 0
 
| 0
 
| 0
 
| 0
 
| 0
−
| 0
+
| 1
 
|-
 
|-
 
| 2
 
| 2
Строка 479: Строка 426:
 
| 1
 
| 1
 
| 1
 
| 1
−
| 0
 
 
| 0
 
| 0
 
|-
 
|-
Строка 487: Строка 433:
 
| 0
 
| 0
 
| 0
 
| 0
−
| 1
 
 
| 1
 
| 1
 
| 0
 
| 0
Строка 498: Строка 443:
 
| 1
 
| 1
 
| 0
 
| 0
−
| 1
 
 
|-
 
|-
 
| 5
 
| 5
−
| 0
 
 
| 0
 
| 0
 
| 0
 
| 0
Строка 510: Строка 453:
 
|-
 
|-
 
| 6
 
| 6
−
| 0
 
−
| 0
 
−
| 0
 
−
| 0
 
−
| 0
 
−
| 0
 
−
| 0
 
−
|-
 
−
| 7
 
−
| 0
 
 
| 0
 
| 0
 
| 0
 
| 0
Строка 527: Строка 460:
 
| 0
 
| 0
 
|}
 
|}
−
 
  
 
* Однако автобус не должен охватывать более двух экскурсий за один день.
 
* Однако автобус не должен охватывать более двух экскурсий за один день.

Версия 13:51, 27 ноября 2022

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

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

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


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

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=22026»