4.6.2.Застосування методу гілок та меж для структурної оптимізації технологічних систем
Метод ґрунтується на відкиданні деяких підмножин із ОДР, які при вивчених властивостях оптимального розв’язання можуть вважатися неперспективними.
Основна ідея алгоритму розв’язання полягає в тому, що процедура перебирання здійснюється спеціально, що дає змогу відкидати деякі розв’язки без безпосередньої перевірки, розглядаючи більш детально лише частину можливих розв’язків. Алгоритм працює таким чином. Нехай розв’язується задача мінімізації функції мети F. Задача запишеться так: мінімізувати F = F(Х) за умови, що — дискретна ОДР. Значення функції мети на першому кроці оптимізації задає верхню межу оцінки для всіх майбутніх допустимих значень, тобто далі нас будуть цікавити тільки ті допустимі розв’язки, в яких значення функції мети буде менше
На наступному кроці дискретна ОДР розбивається на підмножини, для кожної з яких можна знайти значення функції мети На цьому кроці визначається та підмножина що забезпечує мінімальне значення функції мети Розв’язання задачі представляється гамільтоновим шляхом графа, кожна вершина якого відповідає підмножині варіантів розв’язків задачі.
Розглянемо попередню задачу визначення оптимальної послідовності переналагоджень РТК, збільшивши її розмірність.
Приклад 3. Знайти оптимальну послідовність переналагоджень РТК, що обробляє вироби шести найменувань, тобто необхідно визначити, в якій послідовності потрібно запускати партії деталей шести найменувань, щоб сумарний час на переналагодження РТК був мінімальним. Час переналагоджень при переході обробки з i-го виду виробу на j-й позначимо і задамо у вигляді матриці переналагоджень (у годинах):
При застосуванні методу повного перебирання слід розглянути 720 варіантів. Покажемо, як метод “гілок та меж” зменшує обсяг обчислювальної роботи.
Спочатку визначимо нижню оцінку функції мети (сумарний час переналагоджень) будь-яким наближеним шляхом, наприклад вибором для кожного рядка матриці мінімального значення часу переналагодження. В матриці переналагоджень вибрані значення підкреслені, вони задають таку послідовність обробки виробів: 1—4—6—2—3—5— 1, а тривалість переналагоджень, яка являє собою нижню оцінку функції мети, становить: = 2,0 + 2,0 +1,5 + 3,5 + 3,5 + 1,5 = 14 год.
Цей розв’язок не є оптимальним. Для знаходження оптимального розв’язку застосуємо перетворення Гаусса-Жордана для вихідної матриці переналагоджень РТК. Визначимо в кожному рядку матриці мінімальний член і зменшимо елементи цього рядка на його величину. Отримаємо матрицю в кожному рядку якої з’явився нульовий член:
Визначаємо тепер стовпчики без нульових членів, вибираємо в кожному з них мінімальний член і зменшуємо елементи цього стовпчика на його значення. Отримаємо матрицю у кожному рядку і в кожному стовпчику якої є нульовий член:
Значення функції мети (тривалість суми часів переналагодження) в цій матриці зменшено на суму вирахуваних із кожного рядка і кожного стовпчика чисел. Ця сума визначає оцінку (вагу) початкової вершини графа розв’язань, задаючи мінімально можливе значення функції мети, менше значення якої не може існувати
Розбиття множини варіантів розв’язків може бути описано за допомогою графа розгалужень, кожна вершина якого задає підмножину можливих варіантів. Візьмемо якесь значення часу переналагодження яке відповідає дузі (ij) графа розв’язань. До першої підмножини А(ij) зарахуємо всі гамільтонові шляхи, що містять цю дугу. До другої підмножини А(ij) зарахуємо решту гамільтонових шляхів, тобто ті, які цієї дуги не містять. Вибір дуги графа (ij), яка покладена в основу розбиття множини розв’язків, здійснюється за допомогою двох правил:
Час переналагодження в матриці для цієї дуги дорівнює нулю: =0.
Внесок цієї дуги в сумарну тривалість переналагоджень буде максимальним. Позначивши оцінку цього внеску через визначимо його як суму найменших чисел в i-му рядку та j-му стовпці.
Наступні кроки розв’язання полягають у подальшому розгалуженні графа.
Виберемо першу дугу для побудови графа розгалужень. За матрицею знайдемо значення для всіх її нульових членів
Найбільше збільшення оцінки функції мети отримано для дуги (2,1). Позначаємо це на дереві дуги розгалужень (рис. 4.27). Щоб вилучити
шляхи підмножини які не проходять через виділену дугу (2,1), вилучаємо з матриці другий рядок та перший стовпчик. Отримаємо матрицю шляхів для підмножини А(2,1):
Оскільки дуга (2,1) вже залучена в оптимальний шлях, то треба накласти заборону на дугу (1,2) за допомогою знака бо ця дуга утворює замкнений цикл із залученою дугою (2,1) без інших вершин графа. Визначимо оцінку внеску решти дуг, що залишились у матриці
У дерево розгалужень залучаємо дугу (1,4), створивши підмножину В(1, 4) та підмножину (1,4). Для підмножини B(1, 4) отримаємо матрицю шляхом вилучення 1-го рядка та 4-го стовпчика:
Оцінка внеску решти дуг дає такі значення:
У дерево розгалужень залучаємо дугу (6, 2), створивши підмножини С(6,2) та (6 ,2). Підмножина С(6,2) задасться матрицею шляхом вилучення із 6-го рядка та 2-го стовпчика:
Оцінка внеску решти дуг дає такі значення:
У дерево розгалужень включаємо дугу (3, 5) та будуємо матрицю шляхом вилучення з попередньої матриці 3-го рядка та 5-го стовпчика:
Оцінка внеску решти дуг дає такі значення:
Максимальне значення оцінки виявилося однаковим для дуг (4, 3) та (5, 6), тому ці дві дуги залучаємо до гамільтонового шляху.
Результат застосування цього алгоритму дає таку послідовність дуг: (2, 1)—(1, 4)-(4, 3)-(3, 5)—
(5, 6)-(6, 2), які визначаються функцією мети (тривалість переналагоджень РТК):
що на одну годину менше значення = 14 год., отриманого на початковому кроці оптимізації.
Аналізуючи відкинуті раніше як безперспективні підмножини переконуємося, що їх оцінки знизу більші за 13,0. Тому ці підмножини не можуть містити коротшого від знайденого гамільтонового шляху.
Застосування методу “гілок та меж” дало змогу визначити без повного перебирання всіх можливих варіантів оптимальну послідовність обробки на РТК шести партій деталей: 2-1-4-3-5-6.
Застосування методу “гілок та меж” для оптимізації структури технологічної системи має деякі особливості, а саме: для математичного опису множини варіантів структури використовуються булеві змінні. Тоді варіант структури матиме вигляд
а функція його ефективності
де — ефективність j-го елемента при його входженні в i-й варіант структури; — булева змінна
Другою особливістю застосування методу “гілок та меж” для оптимізації структури технологічної системи є покрокове звуження області пошуку шляхом відсіювання безперспективних варіантів та конкретизації варіантів, що залишились.
На наступних кроках здійснюється розгалуження i-го варіанта структури, для якого (для задачі мінімізації). Цей варіант структури розробляється детальніше, виникають варіанти нової підструктури, для кожного з яких знову оцінюється ефективність:
Де
Процес розгалуження триває доти, доки повністю не визначиться оптимальний варіант структури. Якщо при оцінці варіантів є можливість точно визначити нижню межу оцінки функції мети на множині допустимих розв’язків, то знайдений варіант вважається оптимальним. Якщо ж оцінка варіантів є грубою чи наближеною, то одержане оптимальне значення може бути гіршим, ніж для деяких нерозгалужених підмножин. У цьому випадку проводиться додаткове розгалуження для вершин, які мають значення функції мети, близькі до підозрюваної на оптимальність. Розгалуження такої вершини здійснюється аж до рівня, коли оцінка ефективності погіршується порівняно з уже визначеним оптимальним розв’язком.