4.6.1.Метод повного перебирання

4.6.1.Метод повного перебирання

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

Початкова точка пошуку вибирається довільно. Область допусти­мих розв’язків має n координатних осей, на кожній з яких змінна вели­чина набуває послідовних значень. На координатній осі першої змінної , X1 матимемо ряд її послідовних значень

де перший індекс змінної вказує на належність до координатної осі, а другий — номер точки на цій осі.

Математична модель оптимізаційної задачі набуде такого вигляду:

де остання умова відображає дискретність задачі.

Значення функції мети визначають у кожній точці поля пошуку. З отриманих значень змінних вибирають ті, що забезпечують оптимальне значення функції мети. Число точок у просторі пошуку визначиться як

де n — число змінних або координат в області пошуку;  — число зна­чень по кожній з координат.

Якщо змінні булеві, які набувають значення 0 або 1, то кількість точок в області пошуку

Приклад 1. Нехай одну з двох деталей, вал або втулку можна об­робити на будь-якому з двох типів токарних верстатів — токарно-гвинторізному або токарно-револьверному. Токарну операцію можна оціни­ти часом обробки кожної деталі на кожному верстаті (табл. 4.11).

 

Для позначення події обробки j-ї деталі на і-му верстаті застосуємо булеву змінну, яка набуває двох значень:

Математична модель оптимізації з функцією мети (сумарний час об­робки обох деталей F), яку треба мінімізувати, набуде такого вигляду:

Умова  означає, що один тип деталі одночасно може оброб­лятися тільки на одному типі верстата. Можливі варіанти обробки двох типів деталей на двох типах верстатів та значення функції мети F для кожного з варіантів зведені в табл. 4.12.

У цьому прикладі вибір оптимального розв’язання зроблено пря­мим порівнянням значень функцій мети для всіх розглянутих варіантів, яких усього чотири. Якщо збільшувати кількість типів верстатів (N1) та кількість видів деталей (N2), то відбудеться різке зростання кількості точок розв’язань в ОДР за виразом N = N1*N2. Розглянемо складніший приклад оптимізації.

Приклад 2. Мінімізувати витрати часу на обробку трьох видів дета­лей на переналагоджуваному роботизованому технологічному комплексі (РТК) при таких характеристиках багатономенклатурного автоматизо­ваного виробництва:

РТК обробляє три види виробів, кожен з яких має річну програму випуску: N1, N2, N3;

РТК може одночасно обробляти лише один вид виробу;

Відомий час (табл. 4.13) переналагодження при переході від обробки i-го виробу до j-го, причому

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

Математична модель оптимізаційної задачі належить до перестановчих і матиме такий вигляд:

У цій моделі функція мети F являє собою сумарний час пере­налагоджень РТК, який необхід­но мінімізувати. Умова означає, що багаторазове перена­лагодження не розглядається, а умова вказує, що розгля­даються тільки два переналагод­ження РТК, без урахування вит­рат часу на початкове налагод­ження. Допустима послідовність переналагоджень задається орі­єнтованим графом (рис. 4.26). Оскільки видів виробу три, то граф має три вершини, номери яких відповідають виду виробу, що обробляється. Орієнтовані дуги графа відповідають переналагодженням РТК.

Оскільки існує три варіанти запуску в обробку першого виду дета­лі, (3-1) варіанти запуску другого виду деталей і так далі, то загальна кількість варіантів послідовності обробки становитиме: Послідовність обробки автоматично задає послідовність переналагод­жень, загальна кількість яких буде такою ж. Можливі варіанти послідов­ності переналагоджень РТК, що задані перестановчою моделлю, та зна­чення функції мети F для кожного варіанта, зведені в табл. 4.14.

Аналіз значень функції мети дає змогу визначити оптимальну по­слідовність обробки виробів: 3-2-1.

Розглянуті типи оптимізаційних задач легко алгоритмізуються і роз­в’язуються із застосуванням обчислювальної техніки, що стає необхід­ним під час розгляду задач більшої розмірності. При розв’язанні задачі про переналагодження РТК кількість варіантів послідовності переналагоджень різко зростає зі збільшенням видів деталей чи виробів, що оброб­ляються, наприклад, для чотирьох деталей N= 24, для п’яти N = 120, для шести N = 720.

Тому при розв’язанні оптимізаційних задач великої розмірності ви­користовують методи спрямованого перебирання варіантів. До цих методів належать метод “гілок та меж”, метод динамічного програму­вання та ін.