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

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.Расчет весов дуг и вершин

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

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

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

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

Рис. 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, удалив

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

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

И

С

Е

Л

Н

А

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