Optprob/Планирование экскурсий

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

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

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

400 строк отношения «Экскурсант хочет Экскурсию»

Экскурсант Экскурсия
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

• Автобусы компании имеют вместимость (количество мест). У компании 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 дня, чтобы использовать наименьшее количество автобусов (использование каждого автобуса в каждый день добавляется в объективную функцию). Мы должны установить систему распределения экскурсантов между автобусами и экскурсий между автобусами, которая гарантирует, что все экскурсии проводятся для всех экскурсантов.

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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.