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

102 Глава 4 . Оптимизация параметров ин те грированной системы торая дает некоторую оценку снизу. Эту оценку можно улучшить пу­ тем приведения матрицы по столбцам (аналогично приведению по строкам). Сумма наименьших элементов по столбцам у. 2ф = 0 + 0 + 1 + 0 + 0=1 . Уточненная оценка снизу: <7= 1А, + 2&, = 7+ 1= 8. В приведенной по строкам и столбцам матрице (табл. 4.7) берем только строки и столбцы, на пересечении которых есть ноль (т. е. ty = 0). Здесь это будут: (1, 4); (2, 3); (2, 5); (3, 2); (4, 1); (5, 2); (5, 3). Подсчитаем увеличение оценки снизу Д (i, j) сложением мини­ мальных чисел в строках и столбцах: Д(1, 4) = 2 + 3 = 5; Д(2, 3) = 0 + 0 = 0; Д(2, 5) = 0 + 1= 1 (ноль в пересечении не учитывается); Д(3, 2) = 1+0 = 1; Д(4, 1) = 1+ 5 = 6; Д(5, 2) = 0 + 0 = 0; Д(5, 3) = 0 + 0 = 0. Наибольшее увеличение оценки снизу получается для дуги (4, 1) (рис. 4.7). Рис. 4.7. Этапы построения контура с номерами заготовок: а —первоначальный; 6 —промежуточный; в —конечный Исключим 4-ю строку и 1-й столбец из приведенной матрицы и получим матрицу для подмножества [(4, 1)] (табл. 4.8). Оценка снизу для подмножества [(4, 1)]: q - 2 + 3 = 5. Приведенная по строкам и столбцам матрица для подмножества [(4, 1)] представлена в табл. 4.9. Клетки (4, 1) в последних матрицах