Методы и алгоритмы принятия решений в управлении учебным процессом в условиях неопределенности. Найханова Л.В - 93 стр.

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

Составители: 

Рубрика: 

93
U = {u}- множество ребер графа;
a
ij
– вес дуги u
ij.
Рассмотрим подграф G'(D',U') графа G, где:
D'⊆D, D'={d
i
, d
j
, d
k
}, где i, j, k – номера вершин подграфа;
U'⊆U, U'={u
ij
,u
ik
,u
jk
} – дуги подграфа, характеризуемые весами соответственно a
ij
,
a
ik
, a
jk
. Граф G'(D',U') представлен на рисунке 3.21.
d
i
d
j
d
k
a
ij
a
ik
a
jk
Рисунок 3.21 - Подграф из трех вершин
P
i
– множество модулей i-той дисциплины;
B
j
– базовые модули j-той дисциплины;
B
k
– базовые модули k-той дисциплины.
Пусть П – это множество модулей, которые входят в B
j
и B
k
, и наследуются от i-той
дисциплины.
П = P
i
∩B
j
∩B
k
.
(3.11)
Возможен один из вариантов значения множества П:
1)
П = ∅ - нельзя удалить дугу (d
i
,d
k
) – является существенной;
2)
П ≠ ∅. В этом случае необходимо скорректировать значение веса дуги (d
i
,d
k
)
следующим образом:
a'
ik
= a
ik
– |П| (3.12)
Из формул (3.11) и (3.12) следует, что величина a'
ik
может принимать только
неотрицательные значения. Если a'
ik
> 0, то дуга (d
i
,d
k
) менее существенная и удалять ее
нежелательно. Если a'
ik
= 0, то в данном случае дуга (d
i
,d
k
) – несущественная и ее можно
удалить.
Таким образом, с учетом тесноты и содержания междисциплинарных связей
необходимо переопределить понятие существенности связей:
Определение 3.8. Связь (i,k) называется несущественной в том случае, если (B
k
∩P
i
) ⊂
(B
j
∩P
i
), т.е. все модули, которые связывают дисциплины i и k, включены во множество
модулей, которые связывают дисциплины i и j.
Определение 3.9. Менее существенной называется связь (i, k), когда множество
модулей, которые связывают дисциплины i и k, частично включены во множество модулей,
которые связывают дисциплины i и j.
Определение 3.10. Существенной называется такая связь (i,k), у которой
(B
k
∩P
i
)
∩
(B
j
∩P
i
) = ∅, т.е. множество модулей, связывающих дисциплины i и k, не включено
во множество модулей, связывающих дисциплины i и k.
Несущественные связи в эквивалентных путях необходимо удалять. Менее
существенные связи нежелательно удалять. Существенные связи нельзя удалять.
Алгоритм обнаружения эквивалентных связей:
1.
Список А пуст;
2.
Найти пару (i,j)≠0 и сформировать список А ={k | (i,k) ≠0 и k
≠
j};
3.
Проверить наличие вершины j в списке А. Если она есть, то обнаружены
эквивалентные связи, иначе п. 4.
4.
Если список пуст, то повторить с п. 1 для следующей пары (i,j);
5.
Извлечь из списка первый элемент k. Добавить в конец списка элементы {l | (k,l) ≠0
и l∉А}. Далее п.3. 
           U = {u}- множество ребер графа;
           aij – вес дуги uij.
           Рассмотрим подграф G'(D',U') графа G, где:
           D'⊆D, D'={di, dj, dk}, где i, j, k – номера вершин подграфа;
            U'⊆U, U'={uij,uik,ujk} – дуги подграфа, характеризуемые весами соответственно aij,
aik, ajk. Граф G'(D',U') представлен на рисунке 3.21.
                                            a
                                                    dj     a
                                       ij             jk



                                  di                       dk
                                            aik


                            Рисунок 3.21 - Подграф из трех вершин

       Pi – множество модулей i-той дисциплины;
       Bj – базовые модули j-той дисциплины;
       Bk – базовые модули k-той дисциплины.
       Пусть П – это множество модулей, которые входят в Bj и Bk, и наследуются от i-той
дисциплины.
                                П = Pi∩Bj∩Bk.                                   (3.11)
       Возможен один из вариантов значения множества П:
    1) П = ∅ - нельзя удалить дугу (di,dk) – является существенной;
    2) П ≠ ∅. В этом случае необходимо скорректировать значение веса дуги (di,dk)
       следующим образом:
                                 a'ik = aik – |П|                               (3.12)

         Из формул (3.11) и (3.12) следует, что величина a'ik может принимать только
неотрицательные значения. Если a'ik > 0, то дуга (di,dk) менее существенная и удалять ее
нежелательно. Если a'ik = 0, то в данном случае дуга (di,dk) – несущественная и ее можно
удалить.
         Таким образом, с учетом тесноты и содержания междисциплинарных связей
необходимо переопределить понятие существенности связей:
         Определение 3.8. Связь (i,k) называется несущественной в том случае, если (Bk∩Pi) ⊂
(Bj∩Pi), т.е. все модули, которые связывают дисциплины i и k, включены во множество
модулей, которые связывают дисциплины i и j.
         Определение 3.9. Менее существенной называется связь (i, k), когда множество
модулей, которые связывают дисциплины i и k, частично включены во множество модулей,
которые связывают дисциплины i и j.
         Определение 3.10. Существенной называется такая связь (i,k), у которой
(Bk∩Pi)∩(Bj∩Pi) = ∅, т.е. множество модулей, связывающих дисциплины i и k, не включено
во множество модулей, связывающих дисциплины i и k.
         Несущественные связи в эквивалентных путях необходимо удалять. Менее
существенные связи нежелательно удалять. Существенные связи нельзя удалять.
         Алгоритм обнаружения эквивалентных связей:
     1. Список А пуст;
     2. Найти пару (i,j)≠0 и сформировать список А ={k | (i,k) ≠0 и k≠j};
     3. Проверить наличие вершины j в списке А. Если она есть, то обнаружены
         эквивалентные связи, иначе п. 4.
     4. Если список пуст, то повторить с п. 1 для следующей пары (i,j);
     5. Извлечь из списка первый элемент k. Добавить в конец списка элементы {l | (k,l) ≠0
         и l∉А}. Далее п.3.

                                              93

Страницы