Файл: О.Н. Ванеев Моделирование систем.pdf

10

0.Принять в качестве вершины, заносимой в результирующую цепь (вершины ЗЦ), вершину N2.

1.Занести вершину ЗЦ в результирующую цепь. Если вершина ЗЦ является вершиной N1, то перейти к П5.

2.Выявить вершину из основной цепи (вершину О), в вектор смежности которой входит вершина ЗЦ.

3.Найти вершину О среди вершин, входящих в векторы смежно-

сти.

4.Принять вершину О в качестве вершины ЗЦ. Перейти к Э.1.

5.Переписать результирующую цепь наоборот.

6.Конец алгоритма.

Пример выполнения прямого хода алгоритма поиска "В глубину" приведен в прил. 1.

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

Алгоритм поиска "в ширину".

Исходные данные: множество дуг, N1 - начальная вершина цепи, N2 - конечная вершина цепи.

Прямой ход.

0.Все вершины заносятся в множество И (исследуемые вершины).

1.В качестве очередной просматриваемой (ОП) вершины берется начальная вершина N1. Вершина ОП заносится в основную цепь.

2.Вершина ОП заносится в основную цепь. Вершина ОП вычеркивается из И.

3.Выявляются все вершины множества И, смежные с ОП (ВВСОП). ВВСОП вычеркиваются из И и заносятся в вектор смежности вершины ОП.

4.Если среди ВВСОП нет N2, то ВВСОП заносятся в ОЦ, в качестве ОП берется очередная вершина из ОЦ, переход к П.3; иначе - конец прямого хода.

Обратный ход.

Обратный ход производится аналогично обратному ходу в алгоритме поиска "В глубину".

11

4.2.Второе задание

4.2.1.Содержание второго задания

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

Варианты исходных данных 1-10 даны в табл. 1 и 2. В табл. 1 даны номер рисунка, последовательность обработки поверхностей и состав оборудования, используемого для обработки. Номер варианта студенты выбирают по последней цифре шифра зачетной книжки (0 − вариант № 10). На деталях, изображенных на рисунках, обрабатываемыми являются пронумерованные поверхности, только эти поверхности необходимо учитывать при построении соответствий и в дальнейших действиях.

В табл. 2 заданы размеры деталей и данные о транспортных связях между используемыми рабочими местами.

Характеристики станков приведены в прил. 2. В работе под малым отверстием подразумевается отверстие, для которого не задан диаметр. Отверстия самого большого диаметра на заготовках деталей есть, поэтому сверлить их не нужно.

Для расчета вспомогательного времени принято, что на переустановку детали на одном станке, если она необходима, затрачивается 10 минут, на переустановку с одного станка на другой − 15 минут.

Рисунки для вариантов приведены на рис. 1, 2, 3. В таблицах используются следующие сокращения: ВФ – вертикально-фрезерный станок; ГФ – горизонтально-фрезерный станок;

ГОЦ − обрабатывающий центр с горизонтальным расположением шпинделя;

ВОЦ − обрабатывающий центр с вертикальным расположением шпинделя;

КСВ – координатно-сверлильный станок; ПРОТ − протяжной станок; РСТ − расточной станок.

12

13

14

4.2.2. Методические указания для выполнения второго задания

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

Решение многих технологических задач возможно на основе теории графов. В частности, задачу выбора оптимального состава и последовательности выполнения переходов можно представить как задачу поиска кратчайшего пути между начальной и конечной вершинами на графе возможного состава переходов. Граф возможного состава переходов (ГВСП) можно рассматривать как графовую модель задачи.

Построение графовой модели задачи, то есть ГВСП, включает нахождение множества возможных вариантов переходов, выявление возможных последовательностей выполнения пар переходов, определение весов дуг и вершин.

Вариант выполнения перехода определяется обрабатываемой поверхностью, станком, на котором производится обработка, используемым для обработки инструментом и выдерживаемыми режимами резания. При условии существования единственного варианта обработки поверхности на станке можно считать, что вариант выполнения перехода определяется парой <станок - поверхность>.

Установление множества возможных переходов удобно производить на основе построения соответствия <станок - поверхность>.

Наличие соответствия между какой-либо поверхностью и станком говорит о возможности обработки данной поверхности на данном станке, то есть о наличии варианта перехода.

Выявление множества дуг ГВСП производится с учетом заданных технологических ограничений. Данные ограничения возникают вследствие необходимости выдерживания принятого порядка обработки

15

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

ГВСП является ориентированным графом. Направление дуг в нем показывает направление технологического процесса. В общем случае данный граф может иметь несколько вершин-истоков и несколько вер- шин-стоков, то есть переходов, с которых может начинаться и заканчиваться обработка. Для применения стандартного алгоритма поиска пути должна быть одна начальная и конечная вершина. В противном случае необходимо ввести фиктивные начальные и конечные вершины: вершины S и T.

Пример графовой модели для обработки 1, 2, 3, 4 поверхностей некоторой детали на станках A, B, C при заданной последовательности обработки поверхностей 1 >3 >2 >4 изображен на рис. 3.

Рис. 3. Граф возможного состава переходов обработки поверхностей 1, 2, 3, 4 некоторой детали

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

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

Суммарная трудоемкость технологического процесса Т рассчитывается как сумма трудоемкостей отдельных операций Ti:

16

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

Расчет времени, затрачиваемого на выполнение переходов и на их смену, производится на основе данных о производительности заданных станков и данных о затрате времени на переустановку детали на одном станке и переустановку детали между отдельными станками.

Стандартные алгоритмы оперируют с графами, в которых имеют вес только дуги. Поэтому в сформированной графовой модели необходимо вес вершин привести к весу дуг, сохранив при этом характеристики путей, проходимых по графу. Данную операцию можно провести, рассчитав новый (приведенный) вес дуг по следующему правилу: приведенный вес дуги равняется сумме веса этой дуги на исходном графе и веса вершины, в которую она входит:

Рabп=Раb+Pb, (2)

где Pabп − приведенный вес дуги ab; Pab − вес дуги ab на исходном графе; Pb − вес вершины b на исходном графе.

Вычисление приведенных весов дуг целесообразно совмещать с построением матрицы смежности T для графа возможных вариантов переходов.

Матрица смежности T для ГВСП, приведенного на рис. 3, изображена на рис. 4.

Как уже отмечалось, критерием оптимальности технологического процесса могут быть показатели обеспечиваемой им трудоемкости, себестоимости и производительности обработки детали.

Задачи выбора маршрута с минимальной трудоемкостью и себестоимостью однотипны, их можно рассматривать как задачи поиска кратчайшего пути на ГВСП, где в качестве меры пути принимается суммарный вес пройденных дуг. Данная задача хорошо исследована и имеет алгоритм решения, известный как алгоритм Дейкстры.

17

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

Алгоритм поиска кратчайшего пути на взвешенном графе построен в виде пошагового пересчета расстояний от начальной S-й до всех вершин графа. Отдельный шаг алгоритма включает вычисление новых длин путей от начальной до каждой Vj-й вершины и сравнение их с длинами путей между этими же вершинами, принятыми на предшествующих шагах. Для дальнейшего рассмотрения в качестве длины пути принимается меньшая из двух сравниваемых величин. Новая длина пути от начальной до рассматриваемой вершины Vj вычисляется как сумма расстояния от вершины S до вершины, оказавшейся к ней ближайшей на предыдущем шаге (эта вершина будет обозначаться U), и расстояния между вершинами U и Vj, равного весу соответствующей дуги на ГВСП.

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

Формула пересчета расстояния от S-й до Vj-й вершины на i-м шаге будет выглядеть следующим образом: