Применение метода ветвей и границ для задач календарного планирования
| Категория реферата: Рефераты по кибернетике
| Теги реферата: сочинение на тему онегин, решебник
| Добавил(а) на сайт: Flavija.
Предыдущая страница реферата | 1 2 3 4 5 6 | Следующая страница реферата
Таблица 1
|Длительность |Деталь |
|операций | |
| |1 |2 |3 |4 |5 |
|ai |2 |5 |1 |3 |3 |
|bi |3 |2 |1 |4 |5 |
|ci |4 |4 |2 |2 |2 |
Нулевой шаг. ( = 0.
(A(( = 0) = A(0) + [pic] + [pic] = 0 + 14 + 3 = 17;
(B(( = 0) = В(0) + [pic] + min cj = 0 + 15 + 2 = 17;
(C(( = 0) = С(0) + [pic]=14 .
Тогда
? (( = 0) = max {17, 17,14} = 17.
Первый шаг. Конструируем все возможные последовательности длиной 1
(1(1) = 1; (2(1) = 2; (3(1) = 3; (4(1) = 4; (5(1) = 5.
Находим
(A(1) = A1 + [pic] + [pic] = 14 + 3 = 17;
(B(1)(( = 0) = В1 + [pic] + [pic] = 5 + 12 + 2 = 19;
(C(1) = С1 + [pic]= 9 + 10 = 19 .
Откуда ? (1) = max {17, 19, 19} = 19.
Аналогично определяем ? (2), ? (3), ? (4), ? (5).
[pic]
Второй шаг. Среди множества подпоследовательностей длиной 1, (1(1) =
1, (2(1) = 2,..., (5(1) = 5 выбираем наиболее перспективную ( = 1, для которой величина оценки-прогноза ? (() оказывается наименьшей. Далее развиваем ее, конструируя возможные варианты длиной 2, т. е. (1.2),
(1.3), (1.4), (1.5).
Для каждого из этих вариантов вновь определяем оценки по формулам (1)
— (4).
Процесс вычислений продолжаем аналогично.
Процесс построения дерева вариантов приведен на рис. 1.
Каждой конечной вершине дерева вариантов будет отвечать полная последовательность ( = i1,i2,,.in. Если для некоторой такой вершины величина оценки ? (() не превосходит величины оценок для всех остальных вершин, то эта оценка определяет искомый оптимальный вариант. В противном случае разбиваем более перспективный вариант с наилучшей оценкой.
Конечная вершина определяет вариант (последовательность) [pic] = 3,
1, 5, 2, 4 с наилучшей оценкой ? = 20. Поэтому данный вариант является оптимальным.
Непосредственной проверкой убеждаемся, что время обработки всей последовательности деталей для этого варианта совпадает со значением оценки-прогноза и является минимальным:
[pic]
Летература
Рекомендуем скачать другие рефераты по теме: реферат на тему русские, реферат охрана.
Категории:
Предыдущая страница реферата | 1 2 3 4 5 6 | Следующая страница реферата
Главная