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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
У нас есть группа из 60 экскурсантов, которые наняли услуги компании автобусных туров на следующие 3 дня.  
 
У нас есть группа из 60 экскурсантов, которые наняли услуги компании автобусных туров на следующие 3 дня.  
  
−
* Есть шесть различных экскурсий, которые могут быть проведены.
+
* Есть семь различных экскурсий, которые могут быть проведены.
 
* Каждый экскурсант выбрал максимум три экскурсии. Экскурсант может взять только одну экскурсию в день.
 
* Каждый экскурсант выбрал максимум три экскурсии. Экскурсант может взять только одну экскурсию в день.
 +
Вот, какие экскурсии выбрал каждый экскурсант:
 +
{{WikiCutBegin|400 строк отношения «Экскурсант хочет Экскурсию»}}
 +
<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 автобусов.  
 
* Автобусы компании имеют вместимость (количество мест). У компании 10 автобусов.  
  
 
{| 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>
+
| 6
−
| <font color="#000000">7</font>
+
| 7
−
| <font color="#000000">8</font>
+
| 8
−
| <font color="#000000">9</font>
+
| 9
−
| <font color="#000000">10</font>
+
| 10
 
|-
 
|-
 
| <br>  
 
| <br>  
−
| <font color="#000000">60</font>
+
| 60
−
| <font color="#000000">40</font>
+
| 40
−
| <font color="#000000">60</font>
+
| 60
−
| <font color="#000000">60</font>
+
| 60
−
| <font color="#000000">35</font>
+
| 35
−
| <font color="#000000">70</font>
+
| 70
−
| <font color="#000000">60</font>
+
| 60
−
| <font color="#000000">60</font>
+
| 60
−
| <font color="#000000">60</font>
+
| 60
−
| <font color="#000000">60</font>
+
| 60
 
|}
 
|}
  
Строка 139: Строка 552:
 
{{enddiv}}
 
{{enddiv}}
  
−
[[Категория:OptimizationProblems]]
+
[[Category:OptimizationProblems]]

Версия 15:44, 20 ноября 2022

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

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

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


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

60 40 60 60 35 70 60 60 60 60

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

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

Вблизи 1 2 3 4 5 6 7
1 0 1 1 0 0 0 0
2 0 0 0 1 1 0 0
3 0 0 0 0 1 1 0
4 0 0 0 0 1 0 1
5 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0




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




Компания хочет спланировать экскурсии на 3 дня, чтобы использовать наименьшее количество автобусов (использование каждого автобуса в каждый день добавляется в объективную функцию). Мы должны установить систему распределения экскурсантов между автобусами и экскурсий между автобусами, которая гарантирует, что все экскурсии проводятся для всех экскурсантов.


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

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