Иванов, А.А. Автоматизация технологических процессов и производств

4 .4 . Оптимизация ИПС по производительности 103 Таблица 4.8. Матрица для подмножества [(4, 1)] / І 2 3 4 5 5 4 * 2 2 2 X 0 3 0 0 3 0 X 8 1 0 5 0 0 4 X 0 : S j 0 0 3 0 (см. табл. 4.8 и 4.9) отмечены звездочкой. Это означает, что наложен запрет на дугу (1, 4), поскольку дуга (4, 1) уже введена в расписание, а дуга (1,4) образует с ней контур (см. рис. 4.7). Таблица 4.9. Приведенная матрица для подмножества [(4,1)] І j 2 3 4 5 1 3 2 * 0 2 X 0 0 0 3 0 X 5 1 5 0 0 1 X Для приведенной матрицы подмножества [(4, 1)] приращения опенки снизу q будут равны: А(1,5) = 2; Д(2,3) = 0; Д(2,4) = 1; Д(2,5) = 0; Д(3,2) = 1; Д(5,2) = 0; Д(5,3) = 0. Наибольшее увеличение оценки снизу имеем у дуги (1, 5), кото­ рую вводим в расписание, и получаем последовательность обработки заготовок (по их номерам): 4, 1, 5 (см. рис. 4.7). Единицу в расписа­ нии учитываем один раз. Исключив 1-ю строку и 5-й столбец из приведенной матрицы подмножества [(4, 1)], получим матрицу для подмножества [(4, 1), (1, 5)] (табл. 4.10). Оценка снизу для подмножества [(4, 1), (1, 5)]: # = 0 + 0 = 0. Полученная матрица является приведенной, так как минималь­ ные элементы в строках и столбцах равны нулю. Найдем приращения Д(/,у): Д(2, 3) = 0; Д(2 ,4) = 5; Д(3, 2) = 5; Д(5, 2) = 0; Д(5, 3) = 0. Наи-