Метод ветвей и границ.

Метод ветвей и границ заключается в разбиении конечного множества, на котором ищется экстремум, на несколько подмножеств и в выяснении перспективности каждого из них. Если подмножество неперспективно, оно исключается из рассмотрения. Если в подмножестве может находиться экстремум, оно подвергается дальнейшему разбиению и исследованию. Разбиение и исследование продолжаются до тех пор, пока не будет выявлена единственная наилучшая точка. Исключение из рассмотрения неперспективных точек обуславливает направленность перебора. В большинстве задач дискретного программирования оценки перспективности подмножеств точек могут быть только приближенными. Если применяются излишне оптимистические оценки перспективности, перебор начинает приближаться к полному, увеличиваются потери на поиск. Если правила выбора перспективных ветвей излишне пессимистические, то снижается надежность определения экстремума.

Рассмотрим использование метода ветвей и границ для определения оптимальной последовательности фрезерования поверхностей.

Определение последовательности фрезерования отдельных поверхностей и их совокупностей является достаточно сложной задачей. Это обусловлено большим количеством факторов, влияющих на последовательность обработки и неясностью связей между факторами, затрудняющих выявление закономерностей построения последовательностей обработки.

Эту задачу трансформируем в задачу минимизации холостых перемещений инструмента. Такой подход возможен потому, что последовательность обработки будем искать в рамках установки, т.е. вопросы, связанные с определением поверхностей базирования и закрепления, решены.

Сокращение длины холостых перемещений является одним из резервов увеличения производительности труда. Под холостым перемещением понимается движение фрезы между двумя рабочими перемещениями. Одним рабочим перемещением может обрабатываться как одна, так и совокупность поверхностей (карман, колодец, контур) (рис. 3.2).

Все множество холостых перемещений для данной установки, имеющей n рабочих перемещений, можно представить в виде ориентированного графа_

G=(c, U),

у которого: с – множество вершин (множество рабочих перемещений); U – множество ориентированных дуг (наличие дуги указывает на возможность перемещения от одного рабочего перемещения к другому).

В реальных условиях граф G не является полным, так как существуют условия, запрещающие перемещения. К этим условиям можно отнести: расположение элементов базирующих и закрепляющих устройств; нежелательное изменение внутренних напряжений и перераспределение жесткости системы СПИД; выделение большого количества тепла, затрудняющего получение необходимой шероховатости и точности и т.д.

Задача минимизации холостых перемещений ставится в терминах дискретного программирования и формулируется следующим образом.

Минимизировать целевую функцию

n n

Σ Σ C_ij X_ij,

i=1 j=1

где С_ij=∞.

Через С_ij>0 обозначим расстояние между рабочими перемещениями i и j. С_ij=∞, если «прямого» маршрута между перемещениями i и j не существует. В некоторых случаях С_ij≠С_ji, т.е. начало обработки не совпадает с окончанием.

Булевы, перемещенные X_ij, определяются следующим образом:

	I, если цикл включает холостое перемещение от рабочего перемещения i к j ; 0, в противном случае.

 

X_ij=

 

Переменные удовлетворяют условиям:

, i є {1,2,…,n} (отход)

, j є {1,2,…,n} (подход)

X_ij – неотрицательные целые при любых i и j.