Optprob/Выбор внеклассных мероприятий — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- p23 --> {{checked|}} Школа хочет спланировать распределение внеклассных занятий среди учащих…») |
StasFomin (обсуждение | вклад) (Массовая правка: замена Категория:OptimizationProblems на {{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}}) |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
<!-- p23 --> | <!-- p23 --> | ||
{{checked|}} | {{checked|}} | ||
| + | |||
| + | [[File:Выбор внеклассных мероприятий_2023-12-23_02-51-24_image0.png|right|400px]] | ||
Школа хочет спланировать распределение внеклассных занятий среди учащихся. | Школа хочет спланировать распределение внеклассных занятий среди учащихся. | ||
| Строка 16: | Строка 18: | ||
A_k = 1 1 2 3 3 4 5 6 6 7 8 8 | A_k = 1 1 2 3 3 4 5 6 6 7 8 8 | ||
| − | |||
Максимум учеников в каждой группе: | Максимум учеников в каждой группе: | ||
| − | |||
M = 10 10 10 10 10 10 10 10 10 10 12 12 | M = 10 10 10 10 10 10 10 10 10 10 12 12 | ||
| − | |||
100 учеников уже запросили различные активности, не зная о расписании: | 100 учеников уже запросили различные активности, не зная о расписании: | ||
| − | + | {{WikiCutBegin| Тут длинная бинарная матрица 100×8}} | |
| − | {{WikiCutBegin}} | + | |
<pre> | <pre> | ||
S = | S = | ||
| Строка 131: | Строка 129: | ||
</pre> | </pre> | ||
{{WikiCutEnd}} | {{WikiCutEnd}} | ||
| − | |||
Занятия проводятся в течение 1 часа | Занятия проводятся в течение 1 часа | ||
| Строка 140: | Строка 137: | ||
D_h = 1 1 1 2 2 2 3 3 3 4 4 4 | D_h = 1 1 1 2 2 2 3 3 3 4 4 4 | ||
| − | |||
Расписание занятий уже фиксировано, матрицей 12×12. | Расписание занятий уже фиксировано, матрицей 12×12. | ||
| Строка 158: | Строка 154: | ||
0 0 0 0 1 0 0 0 0 0 1 0 | 0 0 0 0 1 0 0 0 0 0 1 0 | ||
</pre> | </pre> | ||
| − | |||
| − | |||
| − | |||
Есть мероприятия с двумя группами. | Есть мероприятия с двумя группами. | ||
У каждой группы свое расписание и свое максимальное количество студентов. | У каждой группы свое расписание и свое максимальное количество студентов. | ||
| Строка 167: | Строка 160: | ||
назначены общему числу студентов, принимая во внимание, что: | назначены общему числу студентов, принимая во внимание, что: | ||
* Ученик не может быть назначен в две группы с перекрывающимися видами деятельности. | * Ученик не может быть назначен в две группы с перекрывающимися видами деятельности. | ||
| − | * | + | * Ученику могут быть назначены только те виды деятельности, которые он запросил. |
| − | * Ученик не может заниматься более чем двумя видами | + | * Ученик не может заниматься более чем двумя видами активности в один день. |
| − | * Мы не можем назначить ученика в более чем одну группу по | + | * Мы не можем назначить ученика в более чем одну группу по одной и той же активности. |
| − | + | ||
| − | + | ||
{{enddiv}} | {{enddiv}} | ||
| − | + | {{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}} | |
Текущая версия на 11:59, 23 декабря 2023
Школа хочет спланировать распределение внеклассных занятий среди учащихся. Предлагаются следующие виды деятельности (8 активностей, 12 групп):
- Гимнастика (две группы)
- Музыка (одна группа)
- Баскетбол (две группы)
- Ремесла (одна группа)
- Рисование (одна группа)
- Английский язык (две группы)
- Французский язык (одна группа)
- Футбол (две группы)
Отображение групп на активности
A_k = 1 1 2 3 3 4 5 6 6 7 8 8
Максимум учеников в каждой группе:
M = 10 10 10 10 10 10 10 10 10 10 12 12
100 учеников уже запросили различные активности, не зная о расписании:
Тут длинная бинарная матрица 100×8
S =
1 1 0 0 0 0 0 0
1 1 0 0 0 0 1 0
1 1 0 0 0 1 1 0
0 0 0 0 0 0 1 0
0 1 1 0 1 1 0 0
1 1 0 1 1 0 0 0
1 1 0 1 0 1 0 0
1 1 0 0 1 1 0 0
0 1 0 0 1 0 0 0
1 1 0 0 0 0 1 0
1 1 0 0 0 0 0 0
1 1 0 0 1 1 1 0
1 1 0 0 1 0 0 1
1 1 0 0 0 0 0 0
0 0 0 0 1 1 0 1
1 1 1 0 1 0 0 0
1 1 0 1 0 0 0 0
1 1 0 0 0 0 1 0
1 0 1 0 0 0 1 0
1 1 1 0 0 0 0 0
1 1 0 0 0 1 0 0
1 1 0 0 1 0 0 0
1 1 0 0 1 1 0 0
0 1 0 0 1 0 0 0
0 1 0 0 1 0 1 0
1 1 0 0 1 0 0 0
0 1 1 0 0 0 0 0
1 1 0 0 1 0 1 0
0 0 1 0 1 0 0 0
1 0 1 0 0 0 0 1
1 1 0 1 1 0 0 0
1 1 0 1 1 0 0 0
1 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0
1 1 0 0 1 1 0 0
1 0 0 0 1 0 0 0
1 1 0 0 0 1 0 1
0 0 1 0 0 0 1 0
1 1 0 0 1 0 0 0
1 1 0 0 1 0 0 0
1 1 0 0 1 0 0 0
1 1 0 0 1 0 0 0
1 1 1 0 1 0 0 0
1 0 1 0 0 0 0 0
0 0 1 0 0 0 1 0
1 1 0 0 1 0 0 0
1 1 0 0 0 0 0 0
1 1 0 1 1 0 0 0
0 1 0 0 1 0 0 1
0 1 0 0 1 0 0 0
1 1 0 1 1 0 0 0
1 1 0 0 0 1 0 1
0 1 0 0 0 0 1 0
1 1 0 0 1 0 1 0
1 0 1 0 0 1 1 0
1 1 0 0 1 0 0 0
1 1 0 0 1 0 0 0
1 1 1 0 0 1 0 0
0 0 1 0 0 1 1 0
1 0 0 0 1 0 0 0
1 1 0 1 1 0 0 0
1 1 0 0 1 1 0 0
1 1 0 0 1 0 1 0
1 1 0 0 1 0 0 0
0 0 0 0 1 0 0 0
1 1 0 0 1 0 0 0
1 1 0 0 0 0 0 0
0 1 1 0 0 0 1 0
1 0 1 0 1 0 0 0
1 1 1 0 0 1 0 0
1 1 0 0 1 0 0 0
1 1 0 0 1 0 0 1
0 1 0 0 1 0 1 0
0 1 0 0 1 0 0 0
0 1 0 0 1 0 1 0
1 1 0 0 1 0 0 0
1 1 0 0 1 0 0 0
1 1 0 0 1 0 0 0
0 0 0 1 0 0 0 0
1 1 0 0 1 0 0 0
1 1 0 0 1 0 0 0
1 1 0 0 0 1 0 0
1 1 1 0 0 0 0 0
1 1 1 0 1 0 0 0
0 1 1 0 0 0 0 0
1 1 0 0 1 0 0 0
1 1 0 0 0 0 0 1
0 1 0 1 1 0 1 0
0 0 0 0 0 1 0 0
1 0 0 0 1 0 1 0
1 1 0 0 1 0 0 0
1 1 0 0 0 0 0 0
1 1 0 0 1 0 1 0
1 1 1 0 1 0 1 0
1 1 1 0 1 0 0 0
1 1 0 0 1 0 0 0
1 1 0 0 0 1 0 0
1 1 1 0 1 0 1 0
0 0 0 0 1 0 0 1
Занятия проводятся в течение 1 часа
- в понедельник, вторник, среду и четверг.
- в слоты «с 4 до 5 часов», «с 5 до 6» или «с 6 до 7 часов» пополудни — 3 слота в день, всего 12 слотов (h).
Для моделирование конкретное время неважно, т.е. есть 4 дня, и 12 часовых слотов, которые так отражаются на дни:
D_h = 1 1 1 2 2 2 3 3 3 4 4 4
Расписание занятий уже фиксировано, матрицей 12×12.
P_kh=1 0 0 0 0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 1
1 0 0 0 1 0 0 0 0 1 0 0
0 1 0 0 0 1 0 0 0 0 1 0
0 0 1 0 0 0 1 0 0 0 0 1
0 0 1 0 0 0 1 0 0 0 0 0
0 0 1 0 0 0 1 0 0 1 0 0
0 0 0 0 1 0 0 0 0 0 1 0
Есть мероприятия с двумя группами. У каждой группы свое расписание и свое максимальное количество студентов.
Мы собираемся распределить группы мероприятий ученикам с целью максимизации суммы мероприятий, которые назначены общему числу студентов, принимая во внимание, что:
- Ученик не может быть назначен в две группы с перекрывающимися видами деятельности.
- Ученику могут быть назначены только те виды деятельности, которые он запросил.
- Ученик не может заниматься более чем двумя видами активности в один день.
- Мы не можем назначить ученика в более чем одну группу по одной и той же активности.