Первый шаг. Конструируем все возможные последовательности длиной 1

s₁ ⁽¹⁾ = 1; s₂ ⁽¹⁾ = 2; s₃ ⁽¹⁾ = 3 ; s₄ ⁽¹⁾ = 4 ; s₅ ⁽¹⁾ = 5.

Находим

d_A ⁽¹⁾ = A₁ + + = 14 + 3 = 17;

d_B ⁽¹⁾ (s = 0) = В₁ + + = 5 + 12 + 2 = 19;

d_C ⁽¹⁾ = С₁ + = 9 + 10 = 19 .

Откуда ∆ (1) = max {17, 19, 19} = 19.

Аналогично определяем ∆ (2), ∆ (3), ∆ (4), ∆ (5).

Второй шаг. Среди множества подпоследовательностей длиной 1, s₁ ⁽¹⁾ = 1, s₂ ⁽¹⁾ = 2,..., s₅ ⁽¹⁾ = 5 выбираем наиболее перспективную s = 1, для которой величина оценки-прогноза ∆ (s) оказывается наименьшей. Далее развиваем ее, конструируя возможные варианты длиной 2, т. е. (1.2), (1.3), (1.4), (1.5).

Для каждого из этих вариантов вновь определяем оценки по формулам (1) — (4).

Процесс вычислений продолжаем аналогично.

Процесс построения дерева вариантов приведен на рис. 1.

Каждой конечной вершине дерева вариантов будет отвечать полная последовательность s = i ₁ ,i _2, ,.i_n . Если для некоторой такой вершины величина оценки ∆ (s) не превосходит величины оценок для всех остальных вершин, то эта оценка определяет искомый оптимальный вариант. В противном случае разбиваем более перспективный вариант с наилучшей оценкой.

Конечная вершина определяет вариант (последовательность) = 3, 1, 5, 2, 4 с наилучшей оценкой ∆ = 20. Поэтому данный вариант является оптимальным.

Непосредственной проверкой убеждаемся, что время обработки всей последовательности деталей для этого варианта совпадает со значением оценки-прогноза и является минимальным:

Летература

1)Зайченко Ю. П., «Исследование операций», Киев «Высшая школа» 1975г.

2)Акулич И.Л., «Математическое программирование в примерах и задачах», Москва «В ысшая школа» 1993г.

3)Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. «Математическое программирование», Москва «В ысшая школа» 1980г.