Рефераты / Кибернетика /

Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ

(1) (4). В результате строим дерево вариантов следующего вида: вершина О отвечает = 0, вершины первого уровня G1(1), G2(1)..., Gn(1) соответствуют последовательностям длиной 1, т. е. 1(1) = 1, 2(1) = 2,..., n(1) = п и т. д. Каждая конечная вершина отвечает последовательности максимальной длины п. Признак оптимальности. Если v(n) отвечает конечной вершине дерева, причем оценка наименьшая из оценок всех вершин, то v(n) искомый вариант, иначе переходим к продолжению варианта с наименьшей оценкой.

Пример 6. Рассмотрим задачу .трех станков, условия которой приведены в табл. 1: Таблица 1 Длительность операцийДеталь12345ai bi ci2 3 45 2 41 1 23 4 23 5 2Нулевой шаг. = 0. A( = 0) = A(0) + + = 0 + 14 + 3 = 17; B( = 0) = В(0) + + min cj = 0 + 15 + 2 = 17; C( = 0) = С(0) + =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 + + = 14 + 3 = 17; B(1)( = 0) = В1 + + = 5 + 12 + 2 = 19; C(1) = С1 + = 9 + 10 = 19 .

Откуда ? (1) = max {17, 19, 19} = 19. Аналогично определяем ? (2), ? (3), ? (4), ? (5).

Второй шаг. Среди множества подпоследовательностей длиной 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. Если для некоторой такой вершины величина оценки ? () не превосходит величины оценок для всех остальных вершин, то эта оценка определяет искомый оптимальный вариант. В противном случае разбиваем более перспективный вариант с наилучшей оценкой. Конечная вершина определяет вариант (последовательность) = 3, 1, 5, 2, 4 с наилучшей оценкой ? = 20. Поэтому данный вариант является оптимальным. Непосредственной проверкой убеждаемся, что время обработки всей последовательности деталей для этого варианта совпадает со значением оценки-прогноза и является минимальным:

Летература 1)Зайченко Ю. П., «Исследование операций», Киев «Высшая школа» 1975г. 2)Акулич И.Л., «Математическое программирование в примерах и задачах», Москва «В ысшая школа» 1993г. 3)Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. «Математическое программирование», Москва «В ысшая школа» 1980г.
Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ