Реферат: Проблемы подготовки к экзаменам

где Gi - количество интервалов времени, в течении которых студент готовится к экзамену i,

ti0j - время начала j-го интервала подготовки студента к экзамену i

ti1j - время окончания j-го интервала подготовки студента к экзамену i

Суммарная эффект С от всех экзаменов выражается суммой всех Ci.

Суммарная ценность свободного времени в течении сессии будет выражаться как

L=L0*

где F - количество интервалов свободного времени

ts - длина интервала свободного времени s.

Наконец, суммарная ценность P, полученная студентом во время сессии выражается как

P=C+L (5)

Данное значение требуется максимизировать. Дополнительным условием по временам будет условие

#SUM s=1,F ts + #SUM i=1,N #SUM j=1,Gi ti1j-ti0j = l (6)

(6)

Также никакие интервалы не должны пересекаться (7)

На языке динамического программирования данная задача заключается в максимизации функции (5) при ограничениях (6) и (7).

III. Алгоритм решения задачи.

Общие зависимости.

Ограничение (7) делает задачу трудно решаемой в непрерывных величинах. Здесь же будет дан алгоритм приближенного решения методом назначений. Для использования этого метода следует перейти от понятия непрерывного времени к понятию дискретного. Введем величину дискретности времени. Разобьем интервал сессии длиной l на h частей. Длина каждого интервала будет равна dt=l/h. Далее заменим времена tiн и tik на соответствующие им tiн' и tiк', при этом для вычисления будем использовать формулу:

tiн'=(tiн-t0)/dt

tiк'=(tiк-t0)/dt

Полученное рациональное число будем округлять внутрь интервала: tiн' в большую сторону, tiк' в меньшую. Далее в задачу о назначениях введем h кандидатов и W+h работ - количество работ будем рассчитывать по формуле

Каждому i-ому экзамену будет соответствовать (tiк'-tiн') работ. Работы с индексом от W до W+h соответствуют отдыху (отсутствию учебы) в данный интервал времени.

Заполнение матрицы стоимостей задачи назначений.

Для работ, соответствующих отдыху : сxy, y>W cxy=L0*dt

сxy: y-> i.(в соответствии с номером работы y находим номер i соответствующего ей экзамена.

x < (tiн-t0): cxy=0

(tiн-t0) <= x <= (tiк-t0): cxy= Qix*Ii'/Qi0, Qix=U*dt*(1 - M(tiк' - x)

x > (tiк-t0): cxy=0

В большинстве случаев количество работ не будет равно количеству кандидатов. Если используемое программное обеспечение в явном виде не позволяет решать несбалансированные задачи о назначениях, то нужно добавить фальшивых кандидатов или работы.

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

Интерпретация полученного ответа.

График подготовки к экзаменам на основе полученного результата строится следующим образом:

Для каждого x-ого кандидата (x=1..h)

Определяем индекс y работы, на которую назначен данный кандидат x.

интервал времени (t0;t0+dt*x) должен быть посвящен

* Если y>W, то отдыху.

* Если нет, то по индексу y определяем индекс i экзамена, который соответствует y-ой работе. Данный интервал должен быть посвящен подготовке к экзамену i.

Замечания