7,9) (малюнок 8). В
Рисунок 8 - Граф ТП з максимальним потоком
Так як неможливо помітити останню вершину, можна зробити висновок, що потік, зображений на малюнку 8 є максимальним, тому що не можна знайти ще один шлях, який доходив би до кінцевої вершини і не містив би насичених дуг.
Підмножини непомічених вершин А = {9} відповідає розріз {(7,9), (8,9)} c пропускною здатністю рівної 6 +7 = 13.
Таким чином, мінімальним розрізом даної мережі є вузьке місце лінії, і, отже, реальна продуктивність обладнання вузького місця визначає максимальний потік і вихід придатних приладів з лінії.
4. ДОСЛІДЖЕННЯ ЗАВДАННЯ маршрутний ОПТИМІЗАЦІЇ НА ПРИКЛАДІ ТЕХНОЛОГІЇ ВИГОТОВЛЕННЯ ДРУКОВАНИХ ПЛАТ
.1 Технологічне забезпечення оптимальності керуючих програм
Під технологічним забезпеченням оптимальності керуючих програм розуміється розробка такого організаційно-технічного рішення, яке забезпечило б одержання максимального ефекту в процесі експлуатації обладнання з числовим програмним управлінням (ЧПУ).
Наочним прикладом одним із завдань, що вирішуються при технологічному забезпеченні керуючих програм, є мінімізація холостого пробігу виконавчого механізму (ІП). Такі холості переходи, як правило, мають місце в будь-якому технологічному обладнанні у разі багатоопераційної обробки деталей і вузлів ЕВА. p align="justify"> Наприклад:
В· обхід отворів на платі при роботі свердлильного верстата;
В· траєкторія переміщення різця при токарній обробці;
Розглянемо постановку задачі мінімізації холостого пробігу виконавчого механізму і її рішення методом гілок і меж.
.2 Формальна постановка задачі на прикладі роботи свердлильного верстата при виробництві друкованої плати
Нехай на друкованій платі необхідно просвердлити n-1 отвір. Поставимо у відповідність кожному i-ому отвору (i = 1, n-1) вершину xi повного неориентированного зваженого графа G (X, U), а також нуль верстата = x0. Веса ребер графа дорівнюють відстаням між центрами отворів. = {X1, x2, ..., xn} - безліч вершин графа = {u1, u2, ..., um} - безліч дуг графа (переходів між отворами).
Завдання полягає в тому, щоб знайти в графі гамільтонів цикл з мінімальним сумарною вагою ребер.
При вирішенні цього завдання використовується метод гілок і меж, як дозволяє отримати точні рішення без повного перебору варіантів.
Ідея методу полягає в побудові усіченого дерева перебору на підставі оцінки знизу значення цільової функції. При цьому спосіб обчислення оцінки повинен бути максимально простий, оскільки цим визначається час роботи алгоритму....
