4, Выбор маршрута обработки детали методом динамического программирования

Реализацию рассмотренного алгоритма динамического программирования рассмотрим на примере оптимизации маршрута обработки отверстия. Возможные варианты маршрутов представлены в виде графа состояний на рис.7 .

Рис.7. Граф возможных маршрутов обработки заготовки.

На рис. 7 цифрами в квадратах обозначены возможные состояния заготовки в процессе обработки. Состояние 1 соответствует состоянию заготовки до обработки, 2, 3 и 4 ее состояниям после черновой обработки, которая может выполняться различными методами. Например, отверстие может обрабатываться черновым зенкерованием (состояние после обработки 2), черновым растачиванием (состояние 3) и обдирочным шлифованием (состояние 4). Цифрами 5, 6, 7 на рисунке обозначены состояния объекта после получистовой обработки, цифрами 8 и 9 – после чистовой, цифрой 10 состояние детали после обработки. Стрелками обозначены операции, цифры над стрелками определяют стоимость их выполнения. В качестве критерия эффективности примем себестоимость обработки детали, которая должна быть минимальной Рекуррентное соотношение для рассматриваемого случая будет аналогичным зависимости (48) при замене требования максимума на требование минимума. Оно справедливо для каждого из промежуточных состояний объекта производства. Роль входных переменных выполняет вид технологической операции.

В соответствии с приведенным ранее алгоритмом рассмотрим заключительную часть процесса обработки (первый этап анализа).

10-е состояние можно получить из 8-го и 9-го. Из 8-го пункта в 10-й имеется только один путь, он и будет являться оптимальным. Значение критерия эффективности J=1запоминаем. Аналогично из 9-го пункта в 10-й также один путь, он и является оптимальным с J=4.

На втором этапе рассматриваем возможные фазовые траектории перехода из состояний 5, 6 и 7 в состояние 10. Из 5-го состояния в 10-е можно попасть через 8-е и 9-е состояния. Рассчитаем критерии эффективности:

траектория 5-8-10 J=7+1=8

траектория 5-9-10 J=5+4=9

Оптимальной является траектория 5-8-10 со значением критерия эффективности J=8, она и запоминается.

Аналогично для 6-го и 7-го состояний имеем:

траектория 6-8-10 J=9+1=10;;

траектория 6-9=10 J=4+4=8, оптимальная, результат запомнить

траектория 7-8-10 J=7+1=8;

траектория 7-9-10 J=1+4=5, оптимальная, результат запомнить.

Таким образом, из пятого состояния оптимальной является траектория 5-8-10, из шестого – 6-9-10, из седьмого – 7-9-10.

На третьем этапе рассмотрим возможные фазовые траектории из 2-го, 3-го и 4-го состояний:

траектория 2-5-8-10 J=10+8=19, оптимальная, результат запомнить; оптимальность

траектории 5-8-10 доказана на предшествующем этапе;

траектория 2-6-9-10 J=12+9=21;

траектория 3-5-8-10 J=5+8=13;

траектория 3-6-9-10 J=10+9=19;

траектория 3-7-9-10 J=5+5=10, оптимальная, результат запомнить;

траектория 4-6-9-10 J=15+9=24;

траектория 4-7-9-10 J=13+5=18, оптимальная, результат запомнить.

Таким образом оптимальными траекториями являются: из состояния 2 – 2-5-8-10, из состояния 3 – 3-7-9-10, из состояния 4 – 4-7-9-10.

На четвертом этапе рассмотрим возможные фазовые траектории из 1-го состояния:

траектория 1-2-5-8-10 J=2+19=21;

траектория 1-3-7-9-10 J=5+10=15, оптимальная;

траектория 1-4-7-9-10 J=1+18=19.

Таким образом, оптимальным маршрутом обработки заготовки является маршрут, определяемый фазовой траекторией 1-3-7-9-10.