к правило, мають місце в будь-якому технологічному обладнанні у разі багатоопераційної обробки деталей і вузлів ЕВА. p align="justify"> Наприклад:
В· обхід отворів на платі при роботі свердлильного верстата;
В· траєкторія переміщення різця при токарній обробці;
Розглянемо постановку задачі мінімізації холостого пробігу виконавчого механізму і її рішення методом гілок і меж. br/>
.2 Формальна постановка задачі на прикладі роботи свердлильного верстата при виробництві друкованої плати
Нехай на друкованій платі необхідно просвердлити n-1 отвір. Поставимо у відповідність кожному i -ому отвору (i = 1, n-1) вершину x i повного неориентированного зваженого графа G (X, U), а також нуль верстата = x 0 . Веса ребер графа дорівнюють відстаням між центрами отворів.
X = {x 1 , x 2 , ..., x n } - безліч вершин графа
U = {u 1 , u 2 , ..., u m } - безліч дуг графа (переходів між отворами).
Завдання полягає в тому, щоб знайти в графі гамільтонів цикл з мінімальним сумарною вагою ребер.
При вирішенні цього завдання використовується метод гілок і меж, як дозволяє отримати точні рішення без повного перебору варіантів.
Ідея методу полягає в побудові усіченого дерева перебору на підставі оцінки знизу значення цільової функції. При цьому спосіб обчислення оцінки повинен бути максимально простий, оскільки цим визначається час роботи алгоритму. p align="justify"> Вихідними даними для алгоритму є матриця відстаней S .
Алгоритм:
) Приведення матриці відстаней S по рядках і стовпцях та визначення нижньої оцінки безлічі варіантів гамільтонових контурів.
В
де ci і qi - елементи приведення по рядках і стовпчиках відповідно, - довжина найкоротшого гамільтонового контуру в досліджуваному безлічі варіантів.
) Визначення оцінок на включення до шуканий гамільтонів контур для всіх В«нульовихВ» дуг.
) Включення дуг з максимальною оцінкою в ...
