Page 61 - 197_

а) б)
2 l 23 3 2 l 23 3

l 24 l 13 l 24 l 13
l 12 l 12 l 34

l 14 l 14

1 4 1 4

Рисунок 8.1 – До задачі визначення оптимальної

послідовності обробки отворів на верстаті з ЧПК
J
1 2 3 4
I
1 - 280 400 200

2 280 - 350 450
3 400 350 - 200
4 200 450 200 -  ,l якщо d i  d j
 ij
a ij  
l
 ij  t 3i V n , якщо d i  d j

J
1 2 3 4
I
1 - 380 400 300
2 380 - 450 450
3 400 450 - 300

4 300 450 300 -

Задача зводиться до послідовного формування планів
переходів, визначення суми l для кожного варіанту та вибору
ij
кращого  ij  min.
l
Для розв’язку задачі 1-го типу використовують динамічне

програмування, метод повного перебору, метод “гілок та
границь”, а також інші методи часткового перебору, що
грунтуються на скороченні перебору допустимих варіантів.
Якщо число отворів велике, то матриця оцінок має велику

розмірність - тоді отвори розбиваються на групи, кожна зі
своїми матрицями оцінок.

8.3 Задача 2-го типу[2]
Вона виникає, наприклад, під час синтезу структур операції

обробки на багатошпиндельних автоматах і напівавтоматах. По
суті це розподільча задача, її формалізація можлива введенням
булевих змінних.

61