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

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

													Таблица 1
							Варианты заданий
Номер варианта				Номер				Последователь-					Используемое обору-
								ность обработки
				рисунка				поверхностей					дование
1, 2 ,3			1						1->2->3->4				ВФ, ГОЦ, РСТ
4, 5, 6, 7			2				1->2->3->4->5						ГФ, РСТ, КСВ, ПРОТ
8, 9, 10			3				1->2->3->4->5->6						ВОЦ, РСТ, КСВ
													Таблица 2
		Размеры деталей и дополнительные ограничения
№ ва-	Размеры поверхностей дета-										Кол-во
риан-				лей							малых		Ограничения
											отвер-
та	L1	L2		d1	d2			d3		L3
											стий
1	300	100		180	120			-		-	4		Нет пути между ВФ
													и РСТ
2	400	60		180	120			-		-	2		Нет пути между ВФ
													и РСТ
3	200	180		180	120			-		-	6		Нет пути между ВФ
													и РСТ
4	300	150		200	120			30		50	6		Нет пути между ГФ
													и ПРОТ
5	300	200		200	80			20		50	4		Нет пути между ГФ
													и ПРОТ
6	350	150		200	150			30		50	12		Нет пути между
													КСВ и ПРОТ
7	300	120		200	120			30		50	6		Нет пути между
													КСВ и ГФ
8	300	150		-	120			20		50	6
9	300	200		-	80			30		50	20
10	350	D2+		-	150			30		50	20
		50

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

T = ∑n	Ti .	(1)
i=1

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

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

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

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

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

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

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

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

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

17

S

A1

B1

A3

B3

C3

A2

B2

C2

B4

C4

T

S

∞

8

12

∞

∞

∞

∞

∞

∞

∞

∞

∞

A1

∞

∞

∞

17

12

11

∞

∞

∞

∞

∞

∞

B1

∞

∞

∞

12

10

15

∞

∞

∞

∞

∞

∞

A3

∞

∞

∞

∞

∞

∞

13

18

16

∞

∞

∞

B3

∞

∞

∞

∞

∞

∞

23

13

16

∞

∞

∞

C3

∞

∞

∞

∞

∞

∞

18

16

13

∞

∞

∞

A2

∞

∞

∞

∞

∞

∞

∞

∞

∞

10

12

∞

B2

∞

∞

∞

∞

∞

∞

∞

∞

∞

10

12

∞

C2

∞

∞

∞

∞

∞

∞

∞

∞

∞

12

17

∞

B4

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

0

C4

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

0

T

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

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

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

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

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

18

L(i,Vj)=min(L(i-1,Vj),L(i-1,U)+T(U,Vj)), (3)

где i − номер шага; Vj − номер вершины; L(i,Vj) − расстояние от начальной вершины до вершины Vj, вычисленное на i-м шаге; L(i-1,Vj) − расстояние от начальной вершины до вершины Vj, вычисленное на предшествующем (i-1-м) шаге; L(i-1,U) − расстояние от начальной вершины до вершины, ближайшей к ней, выявленное на предыдущем, i-1- м, шаге; T(U,Vj)) − вес дуги UVj по матрице смежности Т.

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

Данная задача в теории графов известна как задача поиска пути с самым узким широким местом. Ее можно рассматривать как разновидность задачи поиска кратчайшего пути. На каждом шаге алгоритма ее решения пересчитывается характеристика самого широкого места (в данном случае трудоемкость самой трудоемкой операции).

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

Э0. Все вершины помещаются во множество И (множество исходных вершин).

Устанавливается номер шага − 0 (i=0).

Вкачестве исходных расстояний от начальной вершины S до всех вершин записывается ∞. Для начальной вершины это значение устанавливается равным 0.

Вкачестве вершины U, то есть вершины, ближайшей к S, берем саму вершину S.

Э1. Устанавливается следующий номер шага (i = i + 1). Пересчитывается расстояние от начальной вершины до вершин

графа по формуле (3).

Э2. Выбирается вершина, ближайшая к началу. Данная вершина принимается в качестве вершины U. Вершина U вычеркивается из И.

Э3. Если И = О, то перейти к Э4. Найденный путь L(i,T) − искомый кратчайший путь между начальной вершиной и конечной.

Иначе переход к Э1.

Э4. Обратным ходом выявить полученный кратчайший маршрут. Э5. Работу алгоритма закончить.

19

4.2.3.Порядок выполнения второго задания работы

4.2.3.1.Выявление множества вершин графа возможного состава переходов

Для определения множества вершин необходимо графически построить соответствие <станок-поверхность> для заданной детали c учетом технологических возможностей станков, допустимых для использования при обработке (прил. 2).

Построенное соответствие представить в табличной форме.

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

4.2.3.2. Выявление множества дуг Дуги на ГВСП соответствуют возможным вариантам следования

отдельных переходов.

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

Выявленное множество дуг отобразить на ГВСП.

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

4.2.3.3. Нагружение ГВСП 4.2.3.3.1.Расчет весов дуг и вершин

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

Вес дуг рассчитывается на основе данных о времени, затрачиваемом при смене переходов.

Вес дуг и вершин отображается на формируемой ГВСП.