Пристрій для комбінаторної оптимізації розміщення об’єктів та трасування

Пристрій для комбінаторної оптимізації розміщення об'єктів та трасування, який містить комутатор, у якому усі контакти замикаються для випадку реалізації n! перестановок (n = k ) , а для 2 (19) 1 3 22623 варіант проекту (елемент комбінаторної множини) за критерієм мінімальних витрат на його реалізацію. В основу корисної моделі поставлено задачу створення пристрою з розширенням функціональних можливостей на випадок необхідності виділення з комбінаторної множини тільки того елементу, який відповідає оптимальному варіанту проекту та забезпечує мінімальні витрати на його реалізацію. Такого результату можна досягти, якщо у пристрій перебору сполучень, розміщень та перестановок, який містить комутатору, у якому усі контакти замикаються для випадку реалізації n! перестановок (n=k), а для реалізації сполучень Ck n та розміщень Ak розмикаються n-k контактів коn мутатора, починаючи з першого розряду, згідно з корисною моделлю, в нього введені блок обчислення функції мети за розміщенням, блок обчислення функції мети за трасами, блок обчислення загального значення функції мети, блок пам'яті, блок виділення мінімального значення функції мети, блок реєстрації, блок задання вихідної інформації, першу груп у ви ходів якого підключено до першої групи входів блоку обчислення функції мети за розміщенням, друга група виходів блоку задання вихідної інформації підключено до першої групи входів блоку обчислення функції мети за трасами, третій ви хід блоку задання вихідної інформації підключено до входу блока перебору сполучень, розміщень та перестановок, група виходів якого підключена до другого входу блоку обчислення функції мети за розміщенням та до другого входу блоку обчислення функції мети за трасами, вихід якого з'єднано з першим входом блока обчислення загального значення функції мети, другий вхід якого підключено до виходу блоку обчислення функції мети за розміщенням, вихід блоку обчислення загального значення функції мети підключено до першого входу блоку пам'яті, другий вхід якого з'єднано з першим виходом блока виділення мінімального значення функції мети, другий вихід якого підключено до першого входу блоку реєстрації, другий вхід якого з'єднано з першим виходом блоку пам'яті, другий вихід якого підключено до входу блоку виділення мінімального значення функції мети. Позитивним технічним результатом є те, що пристрій дозволяє знайти найкращий елемент комбінаторної множини розміщень об'єктів та трас між ними, який забезпечує мінімальні витрати на реалізацію відповідного проекту. На кресленні приведено схемну реалізації пристрою, де блок 1 задання вихідної інформації, блок 2 перебору сполучень, розміщень та перестановок, блок 3 обчислення функції мети за розміщенням, блок 4 обчислення функції мети за трасами, блок 5 обчислення загального значення функції мети, блок 6 пам'яті, блок 7 виділення мінімального значення функції мети, блок 8 реєстрації. У якості блоку 1 генерування елементів комбінаторної множини є [Авт.св. СССР №643883. 4 1979. Бюл. №3. Устройство для перебора сочетаний, размещений и перестановок. Левин Г.И.], решта блоків є стандартними. Пояснимо роботу пристрою (креслення). Попередньо з блоку 1 задання вихідної інформації до блоку 2 перебору сполучень, розміщень та перестановок вводиться інформація стосовно кількості n об'єктів, що розміщуються, та кількості m місць можливого призначення об'єктів, причому по одному на кожне місце. З блоку 1 задання вихідної інформації до блоку 4 обчислення функції мети за трасами задається матриця з'єднання об'єктів, кожний елемент якої вказує на наявність або відсутність зв'язку між об'єктами. Крім того задаються коефіцієнти для оцінки загальної вартості відповідних трас з'єднання об'єктів. З блоку 1 задання вихідної інформації до блоку 3 обчислення функції мети за розміщенням задаються коефіцієнти для оцінки загальної вартості розміщення об'єктів. Далі блоком 2 перебору сполучень, розміщень та перестановок здійснюється генерування елементів певної комбінаторної множини розміщень об'єктів. Кожний елемент цієї комбінаторної множини аналізується блоком 3 обчислення функції мети за розміщенням та блоком 4 обчислення функції мети за трасами. Далі у блоці 5 обчислення загального значення функції мети здійснюється оцінка загальних витрат на розміщення об'єктів та розташування трас з'єднання. Ці значення загальної вартості витрат на реалізацію проекту для кожного елементу комбінаторної множини запам'ятовуються блоком 6 пам'яті. Після чого у блоці 7 визначається мінімальне значення загальної вартості та у блоці пам'яті 6 відповідний елемент комбінаторної множини, який вказує на найкращий варіант проекту розміщення об'єктів та проведення відповідних трас між ними. Ця кінцева інформація фіксується блоком 8 реєстрації. За рахунок запропонованої апаратурної реалізації алгоритму розв'язання комбінаторних задач цього типу, витрати часу, у порівнянні з витратами часу на ПЕОМ, скорочуються у зв'язку з відсутністю етапу створення відповідного програмного забезпечення. Скорочення часу розв'язання задач оптимізації на пристрої також забезпечується паралельним виконанням окремих етапів алгоритму, наприклад, обчислення функції мети за варіантом розміщення об'єктів (блок 3) виконується паралельно з обчисленням функції мети за відповідною структурою трас (блок 4). Загальний час розв'язання задач оптимізації та витрати пам'яті в основному залежать від кількості n об'єктів, що розміщуються, кількості т місць призначення об'єктів та характеру матриці зв'язків між об'єктами. Точність розв'язання задач оптимізації за допомогою пристрою залежить від точності вихідних даних та точності виконання обчислювальних операцій цифровими блоками при розрахунку значення функції мети (блоки 3, 4, 5) та її оптимізації (блоки 6, 7). 5 Комп’ютерна в ерстка А. Рябко 22623 6 Підписне Тираж 26 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601