Экономико-математическое моделирование / Курсовая работа: Применение метода ветвей и границ для задач календарного планирования

Курсовая работа: Применение метода ветвей и границ для задач календарного планирования

d_A (s) = A (s) + + (23),

где J (s) — множество символов, образующих последовательность s.

За оценку критерия С(s) для варианта s можно принять величину

D(s) = max {d_A (s), d_B (s), d_C (s)} (24).

Тогда ход решения задачи трех станков можно представить следующей формальной схемой:

1) Нулевой шаг. Задание множества G⁽⁰⁾ , образуется всеми возможными последовательностями (s = 0).

Вычисление оценки для множества G₀ :

D(0) = max {d_A (0), d_B (0), d_C (0)} (25), где

; ; (26).

2) Первый шаг. ОбразованиемножествG₁ ⁽¹⁾ , G₂ ⁽¹⁾ , …, G_n ⁽¹⁾ , подмножествоG_k определяется всеми последовательностями с началом i_k (k, ...,n).

Вычисление оценок. Оценку для последовательности s_k определяют из соотношения (24), т. е. D(s_k ) = max {d_A (s_k ), d_B (s_k ), d_C (s_k )}; k = 1,…,n. (27).

Выбор варианта для продолжения. Из всех подпоследовательностей, построенных на предыдущем шаге, выбирают наиболее перспективную последовательность s_k с наименьшей оценкой, т. е. D(s_k ⁽¹⁾ )=minD(s_j ⁽¹⁾ ). (28)

Ветвление. Выбрав наиболее перспективный вариант последовательности s_k ⁽¹⁾ , развивают его построением всех возможных подпоследовательностей длиной 2 с началом s_k ⁽¹⁾ вида s_k ₊₁ ⁽²⁾ = (s_k ⁽¹⁾ , j), где j не входит в s_k .

Вычисление оценок производят в соответствии с соотношениями (21), (22), (23).

3) k-й шаг. Допустим, что уже проведено kшагов, в результате чего построены варианты s₁ ^(k) ,s₂ ⁽ ^k ⁾ ,…,s_k ⁽ ^k ⁾ , а именно подпоследовательности длиной k.

Выбираем самый перспективный вариант s_S ⁽ ^k ⁾ такой, что

D(s_s ⁽ ^k ⁾ )=minD(s_j ⁽ ^k ⁾ ).

Множество G_s ⁽ ^k ⁾ разбиваем на (n — k) подмножеств, каждое из которых образуется добавлением к последовательности s_s ⁽ ^k ⁾ некоторого элемента i_k ₊₁ такого, что i_k ₊₁ .

Оценка определяется в соответствии с соотношениями (21) — (24).

В результате строим дерево вариантов следующего вида: вершина О отвечает s = 0, вершины первого уровня G₁ ⁽¹⁾ , G₂ ⁽¹⁾ ..., G_n ⁽¹⁾ соответствуют последовательностям длиной 1, т. е. s₁ ⁽¹⁾ = 1, s₂ ⁽¹⁾ = 2,..., s_n ⁽¹⁾ = п и т. д. Каждая конечная вершина отвечает последовательности максимальной длины n.

Признак оптимальности. Если s_v ⁽ ⁿ ⁾ отвечает конечной вершине дерева, причем оценка наименьшая из оценок всех вершин, то s_v ⁽ ⁿ ⁾ — искомый вариант.