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

20

4.2.3.3.2. Приведение весов вершин к весу входящих в них дуг Привести по формуле (4) вес вершин к весу входящих в них дуг.

Результат приведения отобразить в виде взвешенной матрицы смежности. Пример построения взвешенной матрицы смежности приведен на рис. 2.

4.2.3.4. Поиск кратчайшего пути между начальной и конечной вершинами на ГВСП

4.2.3.4.1. Прямой ход Работу алгоритма Дайкстры необходимо оформить в виде матри-

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

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

Выявление вершины U, то есть вершины, ближайшей к началу на данном шаге, необходимо делать на основе значений, полученных в соответствующем столбце. Значение, соответствующее вершине, ближайшей к началу на данном шаге, необходимо выбелить (обвести). Необходимо также вычеркнуть из дальнейшего рассмотрения элементы строки, соответствующей данной вершине. Пример заполнения матрицы SL представлен на рис. 5. Матрица SL заполнена для данных из матрицы смежности, изображенной на рис. 4.

4.2.3.4.2. Обратный ход Оптимальный маршрут, полученный по алгоритму, выявляется на

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

21

	0	1	2		3	4		5		6	7		8		9		10	11
S	0`	--	----		----	---		---		--	---		---		---		----	--
A1	∞	8`	---		----	--		---		--	---		---		---		----	---
B1	∞	12	12`		--	--		---		--	---		---		---		----	----
A3	∞	∞	25		24	24		24`			---		---		---		----	----
B3	∞	∞		20	20	20`		--		--	---		---		---		----	----
C3	∞	∞	19		19`	--		---		--	---		---		---		----	--
A2	∞	∞		∞	∞	37		37		37	37		37'		---		----	-
B2	∞	∞		∞	∞	35		33		33	33'		---		---		----	-
C2	∞	∞		∞	∞	32		32		32'	----		-----		-----		----	--
B4	∞	∞		∞	∞	∞		∞		∞	44			43	43'		-----	-----
С4	∞	∞		∞	∞	∞		∞		∞	49		45		45		45	45
T	∞	∞		∞	∞	∞		∞		∞	∞			∞	∞		43'	-----
U	S	A1	B1		C3	B3		A3		C2	B2		A2		B4		T

Рис. 5. Матрица пошагового вычисления кратчайших расстояний до вершин графа

На приведенном примере обратный путь отображен с помощью стрелок на матрице SL. При этом выявлен следующий маршрут − T-B4- B2-B3-A1-S или в прямой последовательности S-A1-B3-B2-B4-T. Таким образом, для приведенного примера оптимальным будет маршрут, состоящий из двух операций: операции А и операции В. На первой операции будет выполняться переход по обработке первой поверхности, на второй операции будут обрабатываться поверхности 3, 2, 4.

5. УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ

5.1.Основная литература

1.Советов Б.Я. Моделирование систем: Учеб. для вузов по спец. "Автоматизированные системы управления" / Б.Я.Советов, С.А.Яков-

лев. – М.: Высш. шк., 1999. − 271 с., ил.

2. Бусленко Н.П. Моделирование сложных систем. – М.: Наука, 1986. − 399 с.: ил.

3. Робототехника и гибкие автоматизированные производства: В 9 кн. Кн. 5. Моделирование робототехнических систем и гибких ав-

22

томатизированных производств: Учеб. пособие для втузов / С.В. Пантюшин, В.М. Назаретов, О.А.Тягунов и др.; Под ред. И.М.Макарова. –

М.: Высш. шк., 1986. − 175 с.: ил.

4.Коршунов Ю.М. Математические основы кибернетики: Учеб. пособие. − М.: Энергия, 1972. − 376 с.

5.Филипс А. Алгоритмы оптимизации на сетях и графах / А.Фи-

липс, В. Гарсиа-Диас. − М.: Мир, 1988. − 258 с.

6.Липский В. Комбинаторика для программистов. − М.: Мир, 1988. – 135 с.

7.Егоров М.Е. Технология машиностроения. − М.: Высш. шк., 1976. − 487 с.

5.2.Дополнительная литература

1.Формирование оптимального маршрута обработки детали: Метод. указания к лабораторной работе по курсу "Основы математического моделирования" для студентов специальности 120100. / Сост.:

О.Н.Ванеев. − Кемерово: Кузбас. политехн. ин-т, 1993.

2. Выбор оптимальной последовательности выполнения переходов технологической операции: Метод. указания к лабораторной работе по курсу "Математическое моделирование процессов" для подготовки бакалавров по направлению Т29. / Сост.: О.Н. Ванеев. − Кемерово: Куз-

ГТУ, 1995.

3. Графовые модели размерных связей детали: Метод. указания к лабораторной работе по курсу "Математическое моделирование процессов" для подготовки бакалавров по направлению Т29. / Сост.: О.Н.Ванеев. – Кемерово: КузГТУ, 1997.

23

ПРИЛОЖЕНИЕ 1

Пример выполнения задания 1

Витвитский Евгений Владиславович В работе буквы И и Й будут рассматриваться как одна буква.

1.Найти множество букв И – вашем имени, О – отчестве, Ф - фа-

милии.

Ф={В,И,Т,С,К,И} И={Е,В,Г,Е,Н,И} О={В,Л,А,Д,И,С,О,Ч}

2.Найти множество А1 = И ∩ О ∩ Ф, А2= И О Ф, А2 =

=О \ И \Ф,

А1 = {В,И,Т,С,К,И} ∩ {Е,В,Г,Е,Н,И} ∩ {В,Л,А,Д,И,С,О,Ч} = = {В,И} ∩ {В,Л,А,Д,И,С,О,Ч} = {В,И }

А2 = {В,И,Т,С,К,И} {Е,В,Г,Е,Н,И} {В,Л,А,Д,И,С,О,Ч} =

={В,И,Т,С,К,Е,Г,Н} {В,Л,А,Д,И,С,О,Ч} =

={В,И,Т,С,К,Е,Г,Н,Л,А,Д,О,Ч}

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

Исходное слово - витвитскийевгенийвладиславович Для упрощения задания сокращаем количество букв до 9, удалив

буквы с наименьшей повторяемостью. Для этого рассчитываем повторяемость букв.

				24
	1	В	6	Таким образом наименьшая повторяемость букв
	2	И	8
				Г, Д, О, Ч, их удаляем
	3	Т	2
				ВИТВИТСКИЙЕВГЕНИЙВЛАДИСЛАВОВИ		Ч
	4	С	4
	5	К	1	Результирующее слово:
	6	Е	2
	7	Г	1	ВИТВИТСКИЙЕВЕНИЙВЛАИСЛАВВИ
	8	Л	2
				Отношения следования букв отображается для
	9	Н	1
				данного слова.
	10	А	2
	11	Д	1
	12	О	1
	13	Ч	1

Отношения следования, заданные перечислением: <ВИ> <ИТ> <ТВ> <ВИ> <ИТ> <ТС> <СК> <КИ> <ИИ> <ИЕ> <ЕВ> <ВЕ> <ЕН> <НИ> <ИИ> <ИВ> <ВЛ> <ЛА> <АИ> <ИС> <СЛ> <ЛА> <АВ> <ВВ> <ВИ>

И

С

В	Т	К

Е

Л

Н

А

Рис. П1. Графическое отображение отношения следования букв в исследуемом слове

25

4. Преобразовать полученные отношения в ориентированный граф.

При преобразовании были удалены петли <И-И>, <В-В>, а также кратные дуги <В,И>,<И,Т>,<Л,А>,

Таким образом, у графа будет следующее множество дуг { <ВИ> <ИТ> <ТВ> <ТС> <СК> <КИ> <ИЕ> <ЕВ> <ВЕ> <ЕН> <НИ> <ИВ> <ВЛ> <ЛА> <АИ> <ИС> <СЛ> <АВ> }

	В	И	Т	С	К	Е	Л	Н	А
В		1					1
И	1		1	1	1	1
Т	1			1
С					1		1
К		1
Е	1							1
Л									1
Н		1
А	1	1

	И
		С
В	Т	К
		Е

Л

Н

А

Рис. П2. Графическое отображение графа следования букв в исследуемом слове и матрица смежности для построенного графа

5. Поиск цепей от начальной вершины по алгоритму поиска "в глубину".

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

					26
Номер			И	ОП	Смежная
шага					вершина
1	{В,И,Т,С,К,Е,Н,Л,А }			В	И
2	{И,Т,С,К,Е,Н,Л,А }			И	Т
3	{	Т	,С,К,Е,Н,Л,А }	Т	С
4		{С,К,Е,Н,Л,А }		С	К
5		{ К,Е,Н,Л,А }		К	-
6			{ Е,Н,Л,А }	С	Л
7			{ Е,Н,Л,А }	Л	А
8			{ Е,Н,А }	А	-
9			{ Е,Н}	Л	-
10			{ Е,Н }	С	-
11			{ Е,Н }	Т	-
12			{ Е,Н }	И	Е
13			{ Е,Н }	Е	Н
14			{ Н }	Н	-

ОЦ	Вектор смежности
В	И
И	Т	Е
Т	С
С	К	Л
К	-
Л	А	-
А	-
Е	Н

Рис. П3. Пример выполнения поиска "в глубину"

Обратные ходы по матрице векторов смежности:

1.Н – Е – И – В

2.А – Л – С – Т – И – В

3.К – С – Т – И – В

4.Л – С – Т – И – В

Вершины С, Т, Е, И входят в состав выявленных цепей. Полученные пути можно отобразить на графе.

В	И С
	Т	К
		Е

Л

Н

А

Рис. П4. Цепи от начальной вершины до всех вершин графа

27

ПРИЛОЖЕНИЕ 2 Технологические возможности используемых станков

Наименование	Технологические возможности	Производитель-
оборудования		ность
Горизонтально-	Фрезерование плоских	5000 мм2/мин
фрезерный (ГФ)	поверхностей
Обрабатываю-	Обработка плоских поверхно-	2000 мм2/мин
щий центр с	стей концевой фрезой
вертикальным	Обработка плоских поверхно-	5000 мм2/мин
шпинделем	стей торцевой фрезой
(ВОЦ)
	Расфрезерование отверстий с	1500 мм2/мин
	круговой подачей при
	d > 80 мм
	Сверление	500 мм2/мин
	Сверление малых отверстий	0,5 отв./мин
Обрабатываю-	Обработка плоских поверхно-	5000 мм2/мин
щий центр с го-	стей торцевой фрезой
ризонтальным	Расфрезерование отверстий с	1500 мм2/мин
шпинделем	круговой подачей при
(ГОЦ)	d > 80 мм
	Сверление	0,5 отв./мин
	Сверление малых отверстий
Вертикально-	Обработка плоских поверхно-	10000 мм2/мин
фрезерный (ВФ)	стей торцевой фрезой
Расточной (РСТ)	Фрезерование открытых плос-	3000 мм2/мин
	костей при S < 50000 мм2
	Растачивание	3000 мм2/мин
	Сверление	600 мм2/мин
	Сверление малых отверстий	0,5 отв./мин
Протяжной	Протягивание отверстий	6000 мм2/мин
(ПРОТ)	D > 60 мм
Координатно-	Сверление	700 мм2/мин
сверлильный	Сверление малых отверстий	1 отв./мин
(КСВ)

28

ПРИЛОЖЕНИЕ 3

Пример оформления задания 2

Цель работы: изучение принципов построения графовых моделей технологических процессов и работы алгоритма поиска кратчайшего пути на взвешенном графе.

Дано.

Станки: ГФ, РСТ, КСВ, ПРОТ; нет пути между КСВ и ПРОТ; последовательность обработки поверхностей 1, 2, 3, 4, 5; деталь: n = 12.

Рис. П5. Деталь

1. Соответствие станок-поверхность.

29

2. Табличное представление соответствия.

	1	2	3	4	5
ГФ	*		*
РСТ	*		*	*	*
КСВ		*			*
ПРОТ				*

3. Выявление множества дуг.

Граф возможного состава переходов.

4. Нагружение графа возможного состава переходов. Расчет весов вершин:

PA1 = S1/Pгф = 350 · 150/5000 = 10,5 мин; S1 – площадь поверхности 1;

Pгф – производительность горизонтально-фрезерного станка

(прил. 2).

Аналогично:

PA3 = S3/Pгф= 10,5 мин;

PB2 = S2/Pрст = 4,71 мин; PB3 = S3/Pрст = 10,5 мин; PB4 = S4/Pрст = = 18,8 мин;

PB5 = S5/Pрст = 24 мин;

PС2 = S2/Pксв = 4,04 мин; Pc5 = S4/Pксв = 12 мин;