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

4 .4 . Оптимизация ИПС по прои зводи тельности 101 Так как подмножества А и В имеют меньшее число элементов, чем множество U, то можно получить оценки снизу qA и qB более близкие к q , чем оценка снизу q. Оптимальный вариант обычно ока­ зывается в подмножестве с меньшей оценкой снизу (на рис. 4.6 это подмножество В). Подмножество В снова разбиваем на подмножества С и D и т. д., пока не придем к подмножеству, состоящему из одного элемента со значением q = q0. Этот элемент может рассматриваться как оптимальный. Пример составления оптимального расписания с помощью МВГ Пусть дана матрица i ху, в клетках которой заданы времена ttJ пе­ реналадок станка в единицах времени (табл. 4.6). Таблица 4.6. Исходная матрица переналадок станка І 1 2 3 4 5 ni . 1 X 7 7 2 4 2 I 1 - 6 X 2 4 1 1 L I l . 6 1 X 9 2 1 I 1 ..... 2 3 8 X 5 2 .?........ 6 1 2 5 X 1 Найдем оценку снизу начального множества, используя способ приведения матрицы по строкам и столбцам [9, 21]. Таблица 4. 7. Матрица, приведенная по строкам и столбцам і j 1 2 3 4 5 1 X 5 4 0 2 2 5 X 0 3 0 3 5 0 X 8 1 4 0 i 5 X 3 5 5 0 0 4 X Для этого из элементов каждой строки i вычитается наименьший элемент Л,. В результате получим сумму S/г, = 2+ 1 + 1+ 2 + 1=7, ко­