загрузка...
 
4.6.2.Застосування методу гілок та меж для структурної оптимізації технологічних систем
Повернутись до змісту

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-го варіанта струк­тури, для якого  (для задачі мінімізації). Цей варіант струк­тури розробляється детальніше, виникають варіанти нової підструктури, для кожного з яких знову оцінюється ефективність:

Де

Процес розгалуження триває доти, доки повністю не визначиться оптимальний варіант структури. Якщо при оцінці варіантів є можливість точно визначити нижню межу оцінки функції мети на множині допусти­мих розв’язків, то знайдений варіант вважається оптимальним. Якщо ж оцінка варіантів є грубою чи наближеною, то одержане оптимальне зна­чення може бути гіршим, ніж для деяких нерозгалужених підмножин. У цьому випадку проводиться додаткове розгалуження для вершин, які мають значення функції мети, близькі до підозрюваної на оптимальність. Розгалуження такої вершини здійснюється аж до рівня, коли оцінка ефек­тивності погіршується порівняно з уже визначеним оптимальним роз­в’язком.



загрузка...