Рассмотрим задачу Class-Teacher Problem: m учителей ведут занятия у n классов, количество занятий, проводимых у класса учителем , равно . В каждый момент времени каждый учитель ведет не более чем у одного класса и каждый класс занимается не более чем с

Добавлена: 16.04.2026
Обновлена: 16.04.2026
Предмет: Теория управления
Автор: Кэмп

#Методы оптимизации и принятия решений
#Практикум по моделированию управленческих процессов

Рассмотрим задачу Class-Teacher Problem: m учителей ведут занятия у n классов, количество занятий, проводимых у класса учителем , равно . В каждый момент времени каждый учитель ведет не более чем у одного класса и каждый класс занимается не более чем с

Условие:

Рассмотрим задачу Class-Teacher Problem: m учителей ведут занятия у n классов, количество занятий, проводимых у класса $\mathfrak{i}$ учителем $\mathfrak{j}$ , равно $r_{i j}$ . В каждый момент времени каждый учитель ведет не более чем у одного класса и каждый класс занимается не более чем с одним учителем. Найти минимальное число временных периодов (p), необходимое для построения допустимого расписания, а также минимальное число аудиторий ( $\rho$ ) в расписании для $p$ периодов. Построить кратчайшие расписания для $\rho$ и $\rho-1$ аудиторий.\na) $n=4, m=4,\left(r_{i j}\right)=\left(

\begin{array}{llll}2 & 0 & 2 & 3 \\ 0 & 3 & 1 & 1 \\ 2 & 2 & 2 & 0 \\ 3 & 1 & 2 & 1\end{array}

\begin{array}{lllll}0 & 2 & 1 & 0 & 3 \\ 2 & 0 & 3 & 2 & 0 \\ 1 & 3 & 0 & 2 & 1 \\ 3 & 0 & 2 & 2 & 0\end{array}

Решение:

Дано

Случай a:
- Количество классов $n = 4$
- Количество учителей $m = 4$
- Матрица занятий $r_{ij}$ : $ r =

\begin{pmatrix} 2 & 0 & 2 & 3 \\ 0 & 3 & 1 & 1 \\ 2 & 2 & 2 & 0 \\ 3 & 1 & 2 & 1 \end{pmatrix}

Случай b:
- Количество классов $n = 4$
- Количество учителей $m = 5$
- Матрица занятий $r_{ij}$ : $ r =

\begin{pmatrix} 0 & 2 & 1 & 0 & 3 \\ 2 & 0 & 3 & 2 & 0 \\ 1 & 3 & 0 & 2 & 1 \\ 3 & 0 & 2 & 2 & 0 \end{pmatrix}

Найти

Минимальное число временных периодов $p$ для построения допустимого расп...

Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит

Попробуй решить по шагам

Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение

Какое из утверждений верно относительно минимального числа временных периодов (p) и минимального числа аудиторий (ρ) в задаче Class-Teacher Problem?

p определяется как максимальное значение среди сумм занятий для каждого учителя и каждого класса, а ρ — как максимальное количество занятий, проводимых одним учителем или в одном классе.

p определяется как максимум из отношения общей суммы занятий к числу классов и отношения общей суммы занятий к числу учителей, а ρ — как максимальный элемент в матрице занятий.

p определяется как сумма всех занятий, деленная на количество классов, а ρ — как сумма всех занятий, деленная на количество учителей.