Содержание к диссертации
Введение
1. Анализ методов и средств математического моделирования 10
1.1. Онтология математического моделирования 10
1.2. Методы построения концептуальных и математических моделей 16
1.3. Методы построения дискретных моделей системной динамики и динамических систем 21
1.4. Технология имитационного моделирования 27
1.5. Инструментальные средства имитационного моделирования 33
Выводы 38
2. Разработка и исследование графовых моделей многокомпонентных систем 39
2.1. Представление модели в виде маркированного орграфа 39
2.2. Представление модели в виде неориентированного маркированного графа 47
2.3. Формализованное описание маркированного гиперграфа 50
2.4. Формализованное описание нечетких маркированных графов 52
2.5. Раскрашенные и двудольные маркированные графы 55
2.6. Разработка программы моделирования маркированного графа 58
Выводы 63
3. Организация моделирования многокомпонентных систем на основе маркированных графов 64
3.1. Вычислительная модель для компьютерного моделирования динамических систем 64
3.2. Организация дискретно-событийного моделирования 71
3.3. Анализ адекватности имитационной модели сети массового обслуживания 78
3.4. Моделирование многокомпонентных динамических систем 81
3.5. Моделирование объекта системной динамики 88
Выводы 93
4. Решение задач на основе маркированных графов 94
4.1. Организация сетевого планирования 94
4.2. Решение задачи поиска кратчайшего пути 102
4.3. Моделирование многокомпонентных систем методом пространства состояний ... 107
4.4. Анализ структурных характеристик многокомпонентных систем 112
4.5. Модель конечного автомата в виде маркированного орграфа 118
Выводы 122
Основные результаты работы 123
Литература 124
Приложение 1
- Методы построения дискретных моделей системной динамики и динамических систем
- Представление модели в виде неориентированного маркированного графа
- Анализ адекватности имитационной модели сети массового обслуживания
- Моделирование многокомпонентных систем методом пространства состояний
Введение к работе
На сегодняшний день имитационное моделирование является мощным и
эффективным средством теоретического исследования и проектирования
технических, экономических, биологических и социальных систем. Широкое
применение имитационного моделирования обусловлено двумя причинами:
желанием разработчиков иметь в распоряжении количественные оценки
характеристик систем до завершения проектирования и экспериментального
исследования; сложностью выполнения оценок характеристик
многокомпонентных динамических систем аналитическими методами.
Существуют специализированные программные средства (Arena, Extend, ProModel, Vissim, Powersim, VenSim и др.), предназначенные для визуального моделирования многокомпонентных систем, и универсальные математические пакеты (MathCad, Matlab, Mathematica, Maple и др.). Графическая оболочка визуальных пакетов моделирования, как правило, скрывает от пользователя процедуру получения результатов модельного эксперимента. Однако выбор нужного для решения конкретной задачи численного метода и настройка параметров вычислительного эксперимента часто являются далеко не тривиальной задачей. При отсутствии в пакетах средств выбора метода и настройки параметров появляется опасность получения неправильных результатов.
К достоинствам математических пакетов следует отнести простой и удобный интерфейс, широкую библиотеку встроенных функций и численных методов, возможность символьных вычислений, графические средства представления результатов, а также возможность интеграции с программными средствами визуального моделирования. Кроме того, математические пакеты являются инструментальными средствами, позволяющими реализовать как аналитическое, так и имитационное моделирование несложных систем. К числу основных достоинств моделирования с помощью математических пакетов
следует отнести математическую прозрачность модельных представлений, которая особенно важна при моделировании новых неисследованных объектов.
Несмотря на перечисленные достоинства, широкое применение математических пакетов в имитационном моделировании в научных исследованиях и инженерной практике ограничено. Эти ограничения связаны с отсутствием способов построения моделей и программных средств организации имитационного моделирования многокомпонентных динамических систем. В связи с этим задача разработки способа построения моделей и программных средств для организации имитационного моделирования многокомпонентных динамических систем в среде математических пакетов является актуальной. При этом математические пакеты должны предоставлять пользователю средства для моделирования систем произвольной структуры и назначения, сокращать затраты времени на программирование вычислений при построении имитационной модели.
Методологической основой данной диссертационной работы являются исследования А. А. Самарского, СВ. Емельянова, Н. Н. Моисеева, О. Оре, К. Бержа, Ф. Харари, Л.Г. Лабскера, Р. Уилсона, Т. Саати, Н. Кристофидеса, В. Е. Котова, Дж. Питерсона, В. Н. Буркова, П. П. Макарычева и др.
Целью диссертационной работы являются теоретическое исследование и развитие методов, средств имитационного моделирования многокомпонентных динамических систем с применением математических пакетов.
Для достижения поставленной цели решены следующие задачи:
анализ существующих методов, алгоритмов, программных средств имитационного моделирования многокомпонентных динамических систем;
разработка вычислительной модели для организации имитационного моделирования динамики многокомпонентных систем в универсальных математических пакетах;
разработка и исследование способа построения имитационных моделей многокомпонентных систем на основе маркированных графов и оценка их адекватности;
разработка и исследование способа матричного описания маркированных графов и процедуры смены маркировки графа;
разработка алгоритмов решения задач сетевого планирования и поиска кратчайшего пути на основе представления сетевых моделей в виде маркированных орграфов;
разработка и экспериментальное исследование программного обеспечения моделирования сетей массового обслуживания, динамических систем и объектов системной динамики в среде математического пакета MathCad.
Методы исследования основаны на использовании основных положений теории математического, имитационного моделирования систем, теории случайных процессов, теории логики, теории графов, теории массового обслуживания, теории системной динамики и динамических систем, теории концептуального программирования, методов сетевого планирования и управления.
Научная новизна работы заключается в следующем:
разработана вычислительная модель для организации имитационного моделирования многокомпонентных систем, которая, в отличие от известных, содержит систему логических правил, формируемых с учетом структуры моделируемой системы и функций поведения ее разнородных компонентов;
предложены новые графовые модели структур многокомпонентных систем, которые, в отличие от известных, содержат маркеры в виде фишек, размещенных в вершинах или на дугах графа, продвижение которых в графе отражает динамику изменений значений сигналов компонентов в дискретном времени;
предложено матрично-векторное описание маркированных графов, которое обеспечивает задание структуры, начальной маркировки графа, условия активности вершин графа и процедуры смены маркировки;
предложен способ организации имитационного моделирования в математических пакетах, который отличается от известных способов организацией вычислений и продвижением модельного времени в процессе компьютерного эксперимента на основе маркированных графов;
предложены алгоритм решения задач сетевого планирования и алгоритм поиска кратчайшего пути, которые отличаются использованием маркированных графов при формализованном описании структуры сетевой модели.
Практическая значимость исследования. Полученные в диссертации теоретические и практические результаты позволяют расширить возможности моделирования многокомпонентных динамических систем в среде универсальных математических пакетов. Комплекс программ, разработанный в среде математического пакета MathCad, позволяет решать задачи имитационного моделирования динамических систем, объектов системной динамики и сетей массового обслуживания, а также задачи сетевого планирования и поиска кратчайшего пути на основе маркированных графов. Наличие библиотеки компонентов динамических систем позволяет ускорить процесс сборки модели из библиотечных элементов, что обеспечивает компонентный подход к имитационному моделированию систем на основе маркированных графов.
Реализация и внедрение результатов работы. Основные результаты по
разработке вычислительной модели, имитационных моделей
многокомпонентных динамических систем и комплекс программ для решения задач имитационного моделирования динамических систем в среде пакета MathCad внедрены в ОАО «Научно-производственное предприятие "Рубин"».
В ООО «СтройПенза» внедрена и успешно использована программа для решения задач сетевого планирования в среде математического пакета MathCad. С использованием программы выполнены расчеты временных характеристик сетевых проектов строительных работ.
Материалы диссертационной работы использованы при проведении лекционных и лабораторных занятий по дисциплине «Моделирование систем», изучаемой студентами специальности 230202.65 - «Информационные технологии в образовании» факультета вычислительной техники Пензенского государственного университета.
Основные положения, выносимые на защиту:
1) вычислительная модель для организации компьютерного
моделирования многокомпонентных систем, учитывающая структуру
моделируемой системы и функции поведения ее разнородных компонентов;
2) представление моделей структур многокомпонентных систем в виде
маркированных орграфов, содержащих в вершинах или на дугах маркеры,
обеспечивающие управление вычислениями в процессе модельного
эксперимента;
матричное представление маркированных графов, позволяющее описать логическую структуру графа, условие активности вершин графа и процесс смены его маркировки;
способ организации имитационного моделирования динамических систем, сетей массового обслуживания и моделей системной динамики на основе маркированных графов в среде универсальных математических пакетов;
алгоритм решения задач сетевого планирования и алгоритм поиска кратчайшего пути на основе маркированных графов.
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на следующих конференциях: Международной научно-технической конференции «Математические методы и информационные
технологии в экономике, социологии и образовании» (г. Пенза, 2001 г.); VII Международном семинаре «Синтез и сложность управляющих систем» (г. Москва,2001 г.); V Международной научно-технической конференции «Новые информационные технологии и системы» (г. Пенза, 2002 г.); Всероссийской научно-практической конференции «Социально-экономические аспекты современного развития России» (г. Пенза, 2003 г.); VII Международной научно-технической конференции «Новые информационные технологии и системы» (г. Пенза, 2006 г.).
Публикации. Основные положения диссертации опубликованы в 14 статьях и тезисах конференций. Среди них 1 статья в журнале из перечня ВАК.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 144 наименований и 8 приложений. Объем работы: 135 страниц основного текста, включающего 40 рисунков, 4 таблицы и 77 страниц приложений.
Методы построения дискретных моделей системной динамики и динамических систем
Для математического моделирования процессов и систем в самых разнообразных областях науки и техники широко используются дифференциальные уравнения. Методы построения дискретных моделей достаточно рассмотреть на примере моделей, представленных обыкновенными дифференциальными уравнениями (ОДУ) первого порядка. Эти методы легко переносятся на системы уравнений первого порядка и сравнительно просто обобщаются на случай уравнений высших порядков, нелинейных дифференциальных уравнений [14, 88, 113, 108].
Пусть на отрезке t0 t t требуется найти решение y{t) дифференциального уравнения j/ (t) + cny(t) = kx(t), которое при t = t$ удовлетворяет начальному условию у( о) = Уо- Условие существования и единственности решения поставленной задачи Коши при построении модели считается выполненным.
Метод Пикара [14, 108]. В общем курсе обыкновенных дифференциальных уравнений метод Пикара известен как метод последовательных приближений. Метод позволяет получить в аналитическом виде последовательность приближений ym(tn) = ym, m = l,2,...,k решению y(t) рассматриваемой задачи Коши по следующему правилу:
Однако метод Пикара редко используется при построении моделей без привлечения других методов вычислительной математики. Одним из существенных недостатков метода, препятствующих широкому применению, является необходимость выполнения операции интегрирования при осуществлении каждой итерации.
Метод рядов Тейлора [14, 113]. Более широкое распространение получил метод построения дискретных моделей, основанный на идее разложения в ряд решения задачи Коши [14]. Наиболее часто для этих целей используют ряд Тейлора. При этом приближённое решение ут (/) исходной задачи ищут в виде
Значения у (to),k = 2,3,...,m находят по формулам, полученным последовательным дифференцированием уравнения у - = f(t, y(t)). Для значений t, близких к 0, метод рядов Тейлора при достаточно большом т даёт обычно хорошее приближение к точному решению y(t) задачи Коши. Однако с увеличением расстояния {t - fy ) погрешность возрастает, и правило становится неприемлемым. Правило вовсе неприемлемо, если / выходит из области сходимости ряда Тейлора.
Метод матричных рядов Тейлора [14, 88, 113]. Система дифференциальных уравнений размерностью п, описывающая поведение объекта в непрерывном времени, задается в виде: строковые матрицы размерностью П; А - матрица размерности пхп; В - матрица-столбец размерности п; t є[0, оо).
Решение системы дифференциальных уравнений находится в виде: Y(0=Y(t0). ехр( - А t) +X(t) А 1 (Е - ехр( - А t)) В, где Е— единичная матрица размерности п х п.
Разностную аппроксимирующую схему получают в результате разложения функции exp(-A) в ряд Тейлора и определения шага дискретизации dt\
Аналого-дискретный метод решения [88]. Предположим, что модель компонента системы представлена в виде ОДУ первого порядка. Для построения дискретной модели находят аналитическое решение дифференциального уравнения: удовлетворяющее начальному условию y(t0) = Уц. Аналитическое решение ОДУ при x(t) = \(t) имеет следующий вид:
На отрезке интегрирования 0 t T вводится сетка ( Q={tn=n- At, п = 0, 1, 2, ...}, с шагом At. Если обозначить через уп = y(tn) сеточную функцию, то в этом случае имеем:
Аналого-цифровой метод обеспечивает построение дискретной модели, которая имеет высокую степень адекватности непрерывной модели [88]. На основе конечно-разностного уравнения может быть найдено z - изображение уравнения и дискретная передаточная функция:
Существует несколько способов построения системы ОДУ первого порядка. Пусть непрерывная модель объекта (компонента) представлена ОДУ второго порядка: случае первого способа вводятся следующие подстановки y{t) = у\ (t); = У2 (0 [88]. На основе введенных подстановок записывается система dt дифференциальных уравнений первого порядка:
Недостаток рассматриваемого способа заключается в том, что при решении системы уравнений и построении разностной схемы аппроксимации необходимо осуществлять операции дифференцирования или интегрирования.
При втором способе решается характеристическое уравнение [88]: где sj, s2 - корни характеристического уравнения {а\ = —s\ - s2, а0 =s} -s2). С использованием характеристических корней дифференциального уравнения исходное дифференциальное уравнение записывается в виде: На основе уравнения (1.2) составляется эквивалентная система ОДУ первого порядка
Представление модели в виде неориентированного маркированного графа
Универсальные математические пакеты (MathCad, Matlab, Mathematica, Maple и др.) являются инструментальными средствами, позволяющими реализовать как аналитическое, так и имитационное моделирование несложных систем. Среди достоинств математических пакетов следует отметить простой и удобный интерфейс, широкую библиотеку встроенных функций и численных методов, возможность символьных вычислений, графические средства представления результатов, а также возможность интеграции с программными средствами визуального моделирования [47, 105, 119, 133].
В пакетах "блочного моделирования" применяется графический язык иерархических блок-диаграмм. Основным «строительным» элементом в модели, представленной в виде диаграммы, является блок, который представляет собой систему типа «вход-выход-состояние». Блок может быть как простым, так и составным. Пакеты снабжены библиотекой блоков, содержат инструментальные средства для создания блоков и библиотек пользователя. В число основных элементарных блоков входят непрерывные, дискретные и гибридные блоки. К достоинствам этих пакетов следует отнести чрезвычайную простоту создания не очень сложных моделей. В то же время при создании сложных моделей пользователь должен строить довольно громоздкие многоуровневые блок-диаграммы, не всегда отражающие естественной структуры системы. Наиболее известными представителями "блочного моделирования" являются подсистема Simulink пакета Matlab и VisSim, которые позволяют моделировать системы: линейные, нелинейные, непрерывные, дискретные и гибридные [45, 47, 98, 138].
Существует множество пакетов, облегчающих разработку дискретно-событийных моделей и проведение экспериментов с ними. В первую очередь программное средство поддержки языка GPSS, который обеспечивает построение моделей в виде блоков и транзактов. Транзакты (заявки) отображают динамические объекты моделирования, а блоки — объекты, обрабатывающие эти заявки. Известны и другие инструментальные средства моделирования, использующие эту парадигму [20, 86, 87].
Транзактно-ориентированные системы моделирования блочного типа (Arena, Extend, ProModel, SimProcess и др.) позволяют создавать компьютерные модели реальных систем в различных сферах деятельности (производственных технологических операций, складского учета, банковской деятельности и т.д.). Имитационная модель в таких пакетах включает следующие основные элементы: источники, стоки, процессы и очереди. Модули, обрабатывающие объекты могут иметь различные состояния, например "ожидание" или "работа". При этом, каждому состоянию можно поставить в соответствие определенное изображение и, тем самым, анимировать имитационную модель. Инструментальное средство концептуального моделирования BPwin 4.0 поддерживает преобразование диаграмм IDEF3 в имитационную модель Arena, что позволяет эффективно оптимизировать моделируемые процессы [20, 86, 87].
Практическим воплощением нового подхода к объектно-ориентированному моделированию непрерывно-дискретных (гибридных) систем с использованием формализма гибридного автомата является пакет визуального моделирования Model Vision Studium (MVS). Основным «строительным» элементом описания в MVS является устройство (блок), который представляет активный объект, функционирующий параллельно и независимо от других объектов. В общем случае в описании устройства содержатся следующие элементы: входы, выходы, параметры, переменные состояния, поведение, локальная структура. Этот пакет основан на использовании активного динамического объекта и специальной формы наглядного представления гибридного поведения объекта в виде карты поведения [120].
Все присутствующие на рынке инструменты имитационного моделирования, как правило, разработаны для поддержки одного определённого подхода к моделированию. Использовать разные подходы, т.е. объединять системную динамику, дискретно-событийное и агентное моделирование в одной модели позволяет только отечественный инструмент моделирования AnyLogic. На сегодняшний день это единственное инструментальное средство, поддерживающее агентное моделирование.
AnyLogic разработан на основе достижений в области информационных технологий: объектно-ориентированный подход, визуальное проектирование, дружественный пользовательский графический интерфейс, платформонезависимый язык Java, агентные технологии, теория гибридных систем [61, 120, 144]. Главное достоинство AnyLogic - гибкость, позволяющая для решения одной и той же задачи на одной платформе выбирать как различные уровни абстракции, так и различные стили создания модели и комбинировать их для достижения целей моделирования. AnyLogic поддерживает языковые конструкции для задания поведения агентов, их взаимодействия, моделирования среды, а также имеет богатейшие анимационные возможности. Еще одним достоинством является открытость AnyLogic, т.е. имеется доступ к исходному коду модели, благодаря чему можно интегрировать модели, разработанные в AnyLogic, в другие приложения [144].
Для моделирования процессов системной динамики используются программные средства аналогового моделирования (Ithink и PowerSim), которые позволяют отображать динамику системы. Модели, созданные подобными инструментальными средствами, состоят из таких специфических логических структур, как уровни, стеки, потоки, преобразователи и соединители. Модели сложных систем, реализуемые в пакетах Powersim, Ithink получаются громоздкими и плохо читаемыми. В мощных системах, с целью расширения их функциональности присутствуют альтернативные концепции формализации.
Так, например, в системах Powersim, Ithink встроен аппарат дискретного моделирования, и, наоборот, в системах Extend, ProcessModel реализована поддержка непрерывного моделирования [16, 86].
В настоящее время наблюдается тенденция развития проблемно-ориентированных систем моделирования. Известны системы моделирования производственных систем различного назначения (Tomas, Sire и др.), медицинского обслуживания (MedModel), ориентированные на реинжиниринг (ReThink), телекоммуникации (Comnet) и др. Для этого в проблемно-ориентированные системы моделирования включаются абстрактные элементы, языковые конструкции и наборы понятий, взятые непосредственно из предметной области исследований [16, 87, 120].
В научно-технической литературе выделены современные тенденции в области имитационного моделирования, которые связаны с разработкой систем моделирования, интегрирующих различные подходы в описании динамических процессов, реализацией многопользовательского режима и взаимодействием имитационного моделирования со Всемирной паутиной. Несмотря на свою привлекательность, использование специализированных средств моделирования ограничено из-за ряда общих недостатков: недостаточная распространенность, необходимость дополнительного обучения пользователя и высокая стоимость систем моделирования [16, 87].
Анализ адекватности имитационной модели сети массового обслуживания
Для оценки адекватности имитационной модели выполнен расчет основных характеристик СеМО аналитическим методом [4, 5]. Граф схема аналитической модели трехзвенной системы «клиент-сервер» с двумя типами заявок, отличающимися маршрутами, представлена на рисунке 3.7. Вершины аналитической модели СеМО, представленной на рисунке 3.7, имеют следующую интерпретацию: Р\ - вероятность поступления в систему заявки первого типа; Р2 вероятность поступления в систему заявки второго типа; / " вероятность передачи заявки по каналу связи; Рц, /зз - вероятность передачи по каналу связи заявки первого типа; 32 34 " вероятность передачи по каналу связи заявки второго типа; Р4 вероятность обслуживания заявки сервером приложений (СП); Рщ% Аз вероятность обслуживания СП заявки первого типа; /] - вероятность обслуживания СП заявки второго типа; Р$ - вероятность обслуживания заявки сервером БД.
Система алгебраических уравнений, описывающая распределение финальных вероятностей аналитической модели СеМО, составляется на основе маршрутов заявок: Из решения системы уравнений (1) могут быть найдены все финальные вероятности СеМО: ph р2, р3, р4, Р5 Ръъ Р32 Рзз Р34 РА\ Р42 Р43 Путем объединения потоков двух типов заявок с использованием вероятностей, полученных при решении системы (3.12) вероятности обслуживания заявок для канала связи и сервера приложений определяются по следующим формулам: С учетом полученных вероятностей b , b2, Ь3, с\,с2 составлена следующая система алгебраических уравнений: Найдено решение системы уравнений (3.14) и получены финальные вероятности для узлов СеМО: Р\ р2 Ръ РА Р5 Используя значения интенсивностей поступления и обслуживания заявок в СеМО, а также найденные значения вероятностей можно найти основные характеристики работы СеМО, расчетные формулы для которых представлены ниже.
Среднее время обслуживания заявки Тоб в канале связи, сервере приложении и сервере БД определим соответственно как —, —, —. Hi № 3 Среднее время нахождения заявки в узле найдем по следующим формулам: Среднее время ожидания заявки в очереди определяется следующим выражением: Тож -Тс —Тоб Результаты аналитического и имитационного моделирования СеМО в среде математического пакета MathCad при интенсивностях поступления заявок Х\ = 2 (1/с), / = 4 (1/с) и интенсивностях обслуживания \х\ = 28 (1/с), [J-2 =100 (1/с), Цз =17 (1/с) соответственно в канале, сервере приложений и сервере БД приведены в таблице 3.2.
Моделирование многокомпонентных систем методом пространства состояний
Маркированные графы могут найти широкое применение в решении задач оптимизации. Рассмотрим решение задачи поиска путей минимальной или максимальной длительности между двумя вершинами графа. Для решения подобных задач широко применяют алгоритм Форда, Дейкстры и другие пошаговые алгоритмы определения кратчайшего расстояния между двумя вершинами [73, 13, 18].
Рассмотрим алгоритм решения задачи поиска кратчайшего пути, в основе которого, в отличие от известных алгоритмов, лежит использование маркировки дуг графа (сети). Предположим, что исходная сеть представляется в виде маркированного взвешенного орграфа G = ( !, D2,T,C,F,M0), где Т = {t\,t2 ...,tm} - множество весов дуг Wj графа, С = {с{,с2,...,ст} - множество весов маркеров mj,j = l,m, F(-) - функция, ставящая в соответствие каждому маркеру nij графа вес е., М0 = [ті,т2,...,т і - начальная маркировка дуг графа. Вес t(wj), j-\,m дуги орграфа равен заданной продолжительности пути по дуге w-. Веса маркеров ? vw,-) j = hm на начальном шаге к-0 выполнения маркированного орграфа принимаются равными нулю: c(w.)=0. На рисунке 4,5 представлен маркированный орграф (сетевая модель), в котором нужно найти маршрут и продолжительность кратчайшего пути от вершины 1 к вершине 12. На рисунке на дугах графа указаны их веса.
Для решения задачи поиска кратчайшего пути сетевой модели на основе маркированного орграфа разработан моделирующий алгоритм, который представлен на рисунке 4.4.
Как известно, кратчайшим путем между двумя вершинами считают путь в графе от одной вершины (начальной) до другой (конечной), вес которого минимален. Весом пути называется сумма весов дуг t{w.-), входящих в путь.
Выполнение маркированного орграфа осуществляется в процессе срабатывания активных вершин vt путем продвижения маркеров от начальной v{ до конечной vn вершины графа. Для начала выполнения маркированного орграфа, начиная с запуска исходной вершины vl5 необходимо в начальную маркировку ввести маркер m\w ,-)=1 на дуги Wj (EI(V{), входящие в начальную вершину vj. Если начальная вершина vj не содержит входящих дуг, то в маркированный орграф вводится дополнительная вершина v„+1 и дуга wm+l, wm+l el(vx), wm+l eO(vn+x). При этом исходная сеть, состоящая из п вершин и т дуг, представляется маркированным орграфом G, содержащим п + \ вершин и т + \ дуг. Дуга1 wm+l, входящая в исходную вершину графа vj, помечена маркером м+1 =1 и является фиктивной, т.е. с нулевой продолжительностью пути (/ш+1 =0).
При каждом к (А: = 0,1,2,...) запуске активной вершины vz-маркированного орграфа определяются веса маркеров, размещенных на выходных дугах активной вершины. При этом вес маркера на каждой выходной дуге определяется минимальным весом min \c\mjjj маркера из множества маркеров, размещенных на входных дугах активной вершины m\Wj)Gl\yi). В случае поиска максимального пути в графе вес маркера на каждой выходной дуге определяется максимальным весом max [суп,-)J маркера из множества маркеров, размещенных на входных дугах активной вершины myWjjElyVj):. Выбранный маркер с минимальным весом с[т.) помещается на выходные дуги Wj є 0{у;) активной вершины графа. При этом вес маркера суммируется с весом t\Wj) выходящих из вершины дуг: c\mjj=c\mj)+t\Wj), Wj eOyv ). Так, передвигаясь по дугам, маркер с минимальным весом суммирует веса пройденных им дуг. Вес с{ц ,-) маркера, дошедшего до конечной вершины v„ маркированного орграфа, показывает длину кратчайшего пути Ткр.
При запуске каждой разрешенной вершине v, графа присваивается метка, которая хранится в массиве меток вершин Skvli) размерности 2хп, 1 = 0,1, / = 1, п. Метка Яц вершины v,- состоит из двух элементов. Первый элемент #0 / метки указывает длину кратчайшего пути от начальной v\ до текущей вершины v;- маркированного орграфа, т.е. элементу «5 0, / присваивается значение веса выбранного маркера SQJ = min\c\mjjj. Второй элемент slt і метки вершины - номер предшествующей вершины выбранного маркера с минимальным весом. Начальные значения элементов массива Sk(Sn) принимаются равными -1: Бц =—1.
После того, как маркер с минимальным весом дойдет до конечной вершины vn маркированного орграфа, определяется маршрут маркера, т.е. номера пройденных им вершин. Маршрут находится по первой строке / массива S меток вершин, элементы которого указывают на предшествующие вершины передвижения маркера с минимальным весом. Маршрут определяется, начиная с конечной вершины vn графа и заканчивая начальной vj. Задача отыскания кратчайшего пути от начальной вершины vj до конечной vn имеет ту же сложность, что и задача отыскания кратчайшего пути из начальной вершины во все остальные вершины. Так, элементы нулевой строки s0j массива Sfs -) есть длины кратчайших путей из начальной вершины vj во все остальные вершины графа v,-, а по элементам 1-й строки можно найти номера вершин, принадлежащих кратчайшему пути Р . Метка о,« конечной вершины vn графа соответствует длине кратчайшего пути Т , если пути не существует, то SQ = — 1.
Для решения задачи поиска кратчайшего пути на основе маркированного орграфа в среде математического пакета MathCad разработана программа, позволяющая найти длину и маршрут кратчайшего пути сетевой модели, представленной маркированным орграфом. С использованием программы получены результаты поиска кратчайшего пути для графа, представленного на рисунке 4.5. Так, длина кратчайшего пути от вершины 1 до вершины 12 равна Г =11, а маршрут кратчайшего пути представлен вектором Р, элементы которого - номера вершин, принадлежащих критическому пути: Ркр =(l 4 7 8 6 9 11 12). В приложении 5 приведены листинги программы решения задачи поиска оптимального пути сети на основе маркированного графа в среде пакета MathCad.
