Optprob/Выбор внеклассных мероприятий — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 16: Строка 16:
  
 
   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| Тут длинная бинарная матрица 100×8}}
 
<pre>
 
<pre>
Строка 131: Строка 127:
 
</pre>
 
</pre>
 
{{WikiCutEnd}}
 
{{WikiCutEnd}}
−
 
  
 
Занятия проводятся в течение 1 часа  
 
Занятия проводятся в течение 1 часа  
Строка 140: Строка 135:
  
 
   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: Строка 152:
 
     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: Строка 158:
 
назначены общему числу студентов, принимая во внимание, что:
 
назначены общему числу студентов, принимая во внимание, что:
 
* Ученик не может быть назначен в две группы с перекрывающимися видами деятельности.
 
* Ученик не может быть назначен в две группы с перекрывающимися видами деятельности.
−
* ученику могут быть назначены только те виды деятельности, которые он запросил.
+
* Ученику могут быть назначены только те виды деятельности, которые он запросил.
−
* Ученик не может заниматься более чем двумя видами деятельности в один день.
+
* Ученик не может заниматься более чем двумя видами активности в один день.
−
* Мы не можем назначить ученика в более чем одну группу по одному и тому же виду деятельности.
+
* Мы не можем назначить ученика в более чем одну группу по одной и той же активности.
−
 
+
−
 
+
 
{{enddiv}}
 
{{enddiv}}
  
 
[[Категория:OptimizationProblems]]
 
[[Категория:OptimizationProblems]]

Версия 19:15, 17 ноября 2022

Школа хочет спланировать распределение внеклассных занятий среди учащихся. Предлагаются следующие виды деятельности (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 учеников уже запросили различные активности, не зная о расписании:

Занятия проводятся в течение 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

Есть мероприятия с двумя группами. У каждой группы свое расписание и свое максимальное количество студентов.

Мы собираемся распределить группы мероприятий ученикам с целью максимизации суммы мероприятий, которые назначены общему числу студентов, принимая во внимание, что:

  • Ученик не может быть назначен в две группы с перекрывающимися видами деятельности.
  • Ученику могут быть назначены только те виды деятельности, которые он запросил.
  • Ученик не может заниматься более чем двумя видами активности в один день.
  • Мы не можем назначить ученика в более чем одну группу по одной и той же активности.

Источник — «https://discopal.ispras.ru/index.php?title=Optprob/Выбор_внеклассных_мероприятий&oldid=21870»