Предисловие научного редактора

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

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

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

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

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

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

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

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

Решению этой задачи посвящена настоящая монография. Она является продолжением монографии [2], где были определены базовые концепты медицинской картины мира, медицинского технологического процесса и развиты основы операторного подхода к его описанию и исследованию.

Ю. И. Журавлев, академик РАН

Предисловие авторов

Последовательное применение операторного подхода к описанию медицинских технологических процессов (МТП) [2] привело к моделям, которые принято называть моделями потоков работ. В большинстве случаев получение модели гораздо сложнее, чем её исследование. Одним из важнейших и самых надежных источников информации для получения модели являются реальные данные, возникающие в процессе лечения пациента и хранящиеся в соответствующих архивах. Эта информация обычно называется прецедентной. Именно задачам её использования для получения моделей лечебно-диагностических процессов посвящена настоящая монография.

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

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

Собственно исследование методов извлечения потоков работ (и описываемых пмп лечебно-диагностических процессов) из данных начинается с третьей главы. Глава посвящена изучению метрических характеристик множества медицинских технологических процессов, на котором вводятся понятия согласования п прецедентности МТП. Эти понятия используются для определения их релевантности.

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

на классы эквивалентности (по нозологическим формам), строится описание классов эквивалентности. Исследуются вопросы корректности и полноты описаний классов.

В пятой главе построенные модели применяются для описания МТП. Если в предыдущей главе рассматривались различные последовательности операторов, т. е. последовательности активных элементов лечебно-диагностических мероприятий п маршруты, образуемые ими, то здесь рассматриваются описания состояний пациента, условия применимости тех или иных мероприятий, манипуляции и ограничения. Исследуются причины возникновения тех или иных маршрутов в МТП.

В шестой главе рассматриваются методы извлечения потоков работ из данных. Для этого изучаются методы извлечения последовательностей работ, разбиение множеств последовательностей на классы на основе отношения релевантности, введённого в третьей главе. Рассматриваются методы извлечения из данных параллельных, итеративных, конкурентных и условных маршрутов в потоках работ. В завершение излагаются некоторые соображения об оптимизации МТП.

В приложениях приведены основные алгоритмы и описания программных средств извлечения описаний потоков работ из данных. В Приложении 1 онпсан метод разбиения множества рабочих последовательностей на классы эквивалентности. В Приложении 2 приведены основные процедуры извлечения рабочих последовательностей из данных и анализ их типов. Приложение 3 содержит алгоритм синтеза общего описания потоков работ. В Приложении 4 кратко описаны инструментальные средства построения моделей потоков работ.

Авторы считают своим приятным долгом выразить признательность проф. В. М. Хачумову, любезно предоставившему ряд материалов по моделям потоков работ.

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

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

Авторы

Введение

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

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

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

Для описания лечебно-диагностических процессов могут быть использованы известные общие методологии, модели и стандарты информационных процессов, включая модели потоков данных, модели потоков работ, методологии IDEFO, IDEF1X, IDEF3, языки программирования и моделирования.

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

ликвидация узких мест;

устранение избыточных этапов;

устранение дублирования;

сокращение времени выполнения задач;

определение мест и методов контроля процесса;

рост эффективности организации.

Моделирование системы процессов — абстрактное представление организации как системы взаимосвязанных и взаимодействующих процессов.

Для моделирования используются:

методы теории расписаний;

теория конечных автоматов;

методы теории систем массового обслуживания;

сети Петри и другие инструменты.

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

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

В следующей главе кратко описаны основные нринцины но- строения моделей потоков работ.

Глава 1

ПРИНЦИПЫ МОДЕЛИРОВАНИЯ потоковРАБОТ

Функции системы управления потокамиработ

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

Системы управления потоками работ обеспечивают поддержку лечебно-диагностических процессов в трёх основных областях и выполняют три типа функций.

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

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

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

Порядок построения модели

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

определить иерархическую подчиненность процессов и временную последовательность их взаимодействия (циклограмму) ;

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

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

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

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

Основными подходами к моделированию потоков работ являются:

моделирование на, основе потока, работ, существующего в лечебно-диагностической организации;

моделирование на, основе перспективной структуры процесса; такая модель должна, удовлетворять требованиям по целевым значениям показателей эффективности;

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

моделирование снизу вверх — формирование укрупненных процессов путем агрегирования детальных процессов.

Исследование адекватности модели проводится экспертами, которые проверяют соответствие модели реально существующему или создаваемому на, предприятии потоку работ.

Методы и задачи моделирования

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

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

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

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

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

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

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

задачи составления расписаний и календарного планирования;

задачи массового обслуживания;

задачи распределения;

задачи управления запасами;

задачи износа, и замены оборудования;

задачи разрешения конфликтных ситуаций.

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

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

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

(в частности их пропускная способность) при различных правилах формирования очередей.

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

задан объём работ, определённые ресурсы, т. е. фиксированные технологические возможности и количество материалов, — необходимо найти такой вариант использования ресурсов, который обеспечит минимальные затраты на, выполнение заданных работ;

заданы определённые материалы и оборудование (ресурсы) — необходимо определить, какая работа, даёт максимальный эффект при использовании этих ресурсов.

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

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

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

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

Проблемы применения моделей

Применяя модели, исследователь заменяет реальный объект его идеализированной копией, что сопряжено с искажениями. Важно учитывать, что реально содержание может быть искажено уже на первом этапе исследований — постановке проблемы (создания её концептуальной модели), при котором неверно может быть описано как существующее, так и желаемое состояние системы.

На этапе построения математической модели потеря адекватности связана, с представлением информации в форме, удобной для исследования, что не всегда, соответствует объекту исследования. Ограничение исходной информации при математическом моделировании происходит вследствие ограниченности математического языка, метода моделирования и собственно модели.

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

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

Свои ограничения и искажения накладывает и типизация — подгонка, задачи к конкретному классу. Типизация математических аспектов не позволяет рассматривать всё множество реальных факторов и связей, характеризующих задачи из этих классов. «Требуемая степень формализации в реальных задачах обычно не выполняется. Поэтому строгие математические результаты, полученные в теоретических исследованиях таких моделей, становились нестрогими в применениях» [4]. Результат, полученный для конкретного класса, оказывается

эффективным только в тех идеализированных условиях, в рамках которых разрабатывается теория этих классов задач.

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

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

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

В основу этого подхода легла, теория операторов специального вида, над дискретными множествами событий, представляющих активные части лечебно-диагностических мероприятий. Их описание и исследование составило основу операторной теории медицинских технологических процессов. Основные соображения этого подхода, изложены в части I настоящей монографии [2]. Здесь же мы сосредоточим внимание на, методах построения моделей такого рода, на, основе прецедентного подхода. Однако прежде рассмотрим особенности некоторых математических методов, которые обычно применяются в построении моделей потоков работ.

Глава 2

МОДЕЛИ ПОТОКОВ РАБОТ

Модели и методы теории расписаний

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

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

Теория расписаний представлена, набором типовых задач и методов их решения. Рассмотрим далее некоторые задачи, которые могут быть полезны при моделировании потоков работ и построении систем управления ими [5,6,7].

Расписания для одного ресурса. Рассмотрим постановку следующей простой задачи. Пусть имеются п независимых операций (работ), каждая из которых характеризуется временем ti (г = 1,2п) выполнения в системе. Необходимо найти оптимальный порядок прохождения всех работ через систему, минимизирующий среднее время обслуживания одной операции:

।72 к

к=Х г=1

Заметим, что общее время прохождения всех работ через си- 72

стему Т = ^Г ti является константой. Оптимальное решение 2=1

может быть найдено путем перебора, всех возможных порядков

прохождения работ через систему. Однако для данной задачи найдено простое решение: оптимальный порядок выполнения работ имеет место при выполнении условия й ^ О ^ • • • ^ ^п- Таким образом, решением задачи служит упорядочение работ по их длительности. Для этой цели можно использовать любой известный алгоритм сортировки, сложность которого и будет определять сложность задачи.

Если заданы дополнительно приоритеты р^ (i = 1,2,...,п) работ (чем приоритетней работа, тем больше величина, ррр то оптимальное решение задачи соответствует упорядочению работ по принципу

Йtn

PlР2Рп *

Рассмотрим теперь задачу оптимального прохождения взаимозависимых работ через систему. Пусть длительность выполнения кМ работы равна, Д. Если fc-я работа выполняется первой, то для подготовки системы, находящейся в исходном состоянии, к обслуживанию требуется t^ времени. Если работа, j выполняется непосредственно после гМ, то для перенастройки системы требуется время t^. Если fc-я работа, выполняется последней, то требуется До времени для возврата, системы в исходное состояние. Необходимо найти такую последовательность выполнения работ, при которой минимизируется общее время их прохождения через систему. Поскольку суммарное время выполнения п'--

всех работ ^ t^ = Т = const, то достаточно рассмотреть только

время, необходимое на перенастройку системы.

Эта, задача, имеет следующую графическую интерпретацию. Рассмотрим полный ориентированный граф (X,U^ где X = = {0, 1п^ —множество вершин, U — множество дуг. Каждой дуге (kj) припишем число (вес) Дд называемое также длиной дуги. Нулевая вершина, здесь соответствует начальному и конечному состоянию системы. Требуется найти такой контур, проходящий через каждую вершину только один раз, которому соответствует наименьшая длина, равная сумме длин его дуг. Задачу можно решить, используя все перестановки п задач. Для каждой перестановки вычисляется длина, пути на, графе. Этот алгоритм решения задачи называется исчерпывающим и имеет экспоненциальную сложность. Однако существуют алгоритмы с меньшей сложностью, которые дают хорошие, хотя не обязательно оптимальные решения. Таким алгоритмом является,

например алгоритм GTS [8], который осуществляет поиск на, графе, выбирая на каждом шаге дугу с минимальным весом. Алгоритм имеет квадратичную сложность О(п2).

Системы с многофазным обслуживанием. Рассмотрим теперь следующую задачу: пусть необходимо выполнить п работ, каждая из которых выполняется последовательно в пунктах А и В. Обозначим через Ар Bi время выполнения г-й (г = 1,...,п) работы в пунктах А и В соответственно. Требуется найти оптимальный порядок прохождения п задач через систему, минимизирующий общее время выполнения всех работ. Джонсон предложил ограничиться рассмотрением расписаний, в которых работы на, первой фазе (в пункте А) выполняются плотно без простоя до полного завершения [7]. Иначе говоря, работы в пункте А выполняются потоком без дополнительных

временных потерь и в заданном порядке.

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

в каждый такт времени оптимальное расписание таково, что

Фазы

№ работы

1

2

3

4

5

6

А

2

б

8

4

4

2

В

5

1

2

4

7

4

Таблица 2.1Таблица 2.1работа, г предшествует работе j^ если шпфА^ВД < тифАрВ^).

Таблица 2.1

Таблица 2.1

Рассмотрим пример. Пусть имеются шесть работ, которые первоначально выполняются в порядке, указанном в табл. 2.1. В таблице содержатся также длительности выполнения дан

ных работ на, пунктах А и В.

Построив диаграмму совмещения работ (рис. 2.1) с учётом возможных простоев, связанных с ожиданием освобождения

пункта, В, находим, что общее время Т выполнения всех работ

в порядке, представленном таблицей, равно 35.

Рис. 2.1. Диаграмма совмещения потоков работ

Рис. 2.2. Оптимальная диаграмма совмещения потоков работ

Фазы

№ работы

6

1

4

5

3

2

А

2

2

4

4

8

6

В

4

5

4

7

2

1

Таблица 2.2Таблица 2.2Производя сортировку работ в соответствии с алгоритмом Джонсона, находим оптимальный порядок выполнения работ (рис. 2.2, табл. 2.2). Для данного упорядочения работ Т = 27.

Таблица 2.2

Таблица 2.2

Задача для упорядочения работ на трёх пунктах сводится,

при определённых условиях, к задаче для двух пунктов путем объединения соответствующих работ, выполняемые в пунктах А п В плп пунктах В и С: соответствующие длительности работ при этом складываются. Класс задач, к которым применим алгоритм Джонсона, таким образом, ограничен. В случаях, когда и > 3 для решения используют, как правило, эвристические или приближенные методы.

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

(2Л)(2Л)Системы с многофазным циклическим обслуживанием. Периодические расписания наилучшим образом подходят для планирования многократного выполнения комплекса работ плп операций [9]. Пусть выполнение работ производится в соответствии с некоторой последовательностью работ (далее — алгоритмом) А, содержащей т работ (операций), среди которых могут быть одинаковые:

(2Л)

(2Л)

Л = ajlaj2...ajm.

Запись (2.1) показывает, что на Аэй фазе выполняется операция ajk. Алгоритм (2.1) назовем локальным алгоритмом (ЛА) обработки цифровой информации.

Пусть модель системы представлена набором Q элементов (исполнительных ресурсов, рабочих мест), настраиваемых на выполнение операций из набора элементов I типов,

соответствующих ЛА: {щ Щ2, • • • , QlY Здесь qj представляет набор kj одинаковых элементов, т. е. q = ^qjx, qj2 ..., qjk }, ^ kj = Q, 1 A kj ф pj. Пусть также tj — время, необходимое для выполнения операции aj элементом из набора qj. Если kj = Pj^ 3 — ^^ т0 имеется единственный способ закрепления

элементов за операциями ЛА при однократном использовании каждого из них. Если kj ф pj^ то существует множество возможных вариантов закрепления исполнительных ресурсов, характеризуемых многократным использованием в процессе реализации алгоритма.

ЛА назовем отмеченным локальным алгоритмом (ОЛА), если в (2.1) кроме выполняемых операций указаны закреплённые за ними элементы. ОЛА имеет следующий вид:

Л*(2.2)

Запись «^ означает, что элемент с номером ip из набора q^ выполняет операцию «дна k-й фазе реализации ЛА.

Однократное выполнение ОЛА назовем его циклом. Пусть алгоритм (2.2) выполняется многократно, причём начала циклов совпадают с моментами рх.ро,..., рх А ро А .... При многократной обработке будем оставлять неизменным порядок закрепления элементов за фазами ЛА, что является одним из необходимых требований обработки без прерываний. Указанное расписание назовем циклическим с периодом Т, если для всех его элементов выполняется соотношение pj + кТ = Pj^k- Будем говорить, что для циклического расписания с периодом Т имеет место совмещение вычислительных процессов, если хотя бы для одного элемента расписания выполняется Pj^x < Pj + ф, где ф — время (в тактах), необходимое для выполнения цикла ОЛА.

Рассмотрим далее задачу составления периодических расписаний для ЛА. Решение задачи начнём с разработки алгоритма оптимизации совмещения циклов.

Будем говорить, что для ОЛА существует совмещение Sn = Sn(Tx,... ,Tn^ если существуют совмещения б^фТь ... ,Tn^i), Sn-x(T2.... ,Тп) и при этом для к^ 1 выполняется одно из условий:

х 2/\ 2

1)^ + УТ>7п, 2) h п -Зк) + м " -гр >

7 = 1г=1г=1

Совмещение Sx(Tx) назовем максимальным, если не существует совмещения АДТД с Т < Тх- Для n > 1 совмещение Sn(Tx,..., Тп) назовем максимальным, если максимально совмещение Sn-x(Tx,... ,Тп_х) и не существует совмещения Sn(T\,..., Тп^х, Т) с Т < Тп. Пусть для алгоритма (2.2) дано сов

’п

мещение Sn = Sn(TA ... ,1^). Если обозначить t(Sn) = ^ТДп,

то очевидно 1 С t(Sn) А т. Если существует ПшД^) = t(A*Y п ^ оо, то нетрудно заметить, что ДЛ*) определяет среднее значение времени, необходимого для получения одного результата обработки в установившемся режиме работы системы, т. е. среднее значение времени однократного выполнения ОЛА. С достаточной степенью точности задачу отыскания ДЛ*)тш можно заменить задачей нахождения максимального совмещения. Более того, эти задачи обычно эквивалентны.

Покажем, что если совмещения Sn являются максимальными, то существует НтДАп) = ДА*), п оо, и имеется простой алгоритм нахождения этого совмещения.

Формализуем постановку и решение задачи максимального совмещения циклов. Для каждого элемента системы выпишем первоначально из ОЛА порядковые номера (фазы) закреплённых за ними операций. Если уд и ро — Две разные фазы закрепления элемента, то величину т = |уц — уф назовем сдвигом фазы. Таким образом, для всех элементов Дго типа можно выписать множество сдвигов фаз УД Л*), а всему варианту

ОЛА поставить в соответствие множество У (Л*) = |J УДА*) =

= {т1,...,тг} [9]. Введём далее множество G(A*) такое, что G(A*) = Ар\У(Л*), где Np = {1,... ,р + 1}, р = шах{т : т Е Е H(A*)Y Нетрудно убедиться, что множество сдвигов У (А*) определяет запрещенные шаги совмещения циклов обработки периодического расписания, а G(A*) — разрешенные шаги. Информация о множествах У (A*), G(A*) и длине локального алгоритма тп является достаточной для построения допустимых периодических расписании, в том числе оптимального.

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

Введём дополнительные операции и определения. Пусть дано совмещение ЗЦТх,..., ТД. Для тех s, 1 < s < к, для которых кк

+ ]О Tt тп введём обозначение gp =^ Введём

г=к™в^-Хг=к™8^-Х

операцию М0{д} = {х : .т = у — q > 0, у Е М^ где М С N, q Е N, N — множество натуральных чисел. Кроме того, пусть т(М) = min{t/ : у Е М}. Введём также вектор состояния Сто шага совмещения Рг.

С учётом сказанного, Алгоритм 1 построения периодического расписания сформулируем следующим образом.

Пусть для выбранного варианта ОЛА

ЩА*) = Щ, GX=NP\HX, Tx=m(G^, Рх = (1,Щ

Тогда существует совмещение Sy(Ty) и оно максимально.

Пусть

Я{ = Я10{Т1}, Но = Ну U Я^ Go = NP\H%

Тогда существует совмещение So (Ту, То) и оно максимально.

Пусть

n—1п—1

нЕ^^ще^т^, нп = нхин'п_ъ

k=li=k

Gn = Np\Hn, Tn = m(Gp, Pn = (l,gM--gG

Тогда существует совмещение Sn(Ty,... ,Тп) и оно максимально.

Процесс продолжается до такого п°, для которого найдётся такое fc°, 0 fc° п°, что Рпо = Рко. Тогда период циклического

П°—1

расписания будет равен Т = ^ Тр причём t(A*) = T/(nQ — kQ). i=k°

Теорема 2.1 [9]. Алгоритм 1 строит периодическое расписание с максимальным совмещением циклов.

Определение. Совмещение назовем равномерным с шагом Т, если Tt = const = Т.

При равномерном совмещении шаг равен периоду циклического расписания и минимальное Т может быть найдено как

Т = min{f : к • t Е Н(А*), t Е G(A*), к Е Я}.(2.3)

Из Алгоритма 1 непосредственно вытекает следующее важное следствие.

Следствие. Если Л^ и Л* — два варианта закрепления ПЭ за фазами ЛА, то ДА^) = t(A*), если ЩАу) = Н(А^); 1(А*) — среднее время получения результата в расписании с максимальным совмещением

Рассмотрим задачу оптимизации закрепления элементов. Пусть R = {Л*}, г = 1,..., г — множество всех вариантов закрепления за фазами вычислительного алгоритма (2.1), т. е. множество ОЛА.

В серии экспериментальных статистических исследований различных ОЛА вероятность Рц выполнения утверждения:

если |Я(ЛД| < |Я(Л$)| , (ЛД А$ Е Я),

то t^K^, (2.4)

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

Задача оптимального закрепления элементов заключается в нахождении такого ОЛА, для которого

ДА*) = шт{ДА*) |1 ^ j ^ г} .(2.5)

Так как закрепление элементов каждого типа производится независимо, то можно выделить множества вариантов закреп- I

ления Ri, г = 1,...,/, такие что |Я| = Ц \Ri\ = г. Каждому мно

жеству Ri соответствует набор Яг, Яг = {Яд,... ,НЙг^ причём Гг = |Яф

Можно показать, что задача (2.5) эквивалентна задаче минимального покрытия таблицы вариантов. Для её решения предложен эффективный алгоритм закрепления элементов за фазами ЛА, использующий эвристическое правило: вариант закрепления элемента f-ro типа с характеристикой Яд лучше или эквивалентен варианту с Н^^ если выполняется условие \Нр>\ — \НЙ\ — -\нг2\нЙ\^о.~~

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

Теория и модели массового обслуживания

Процессы функционирования крупных лечебно-диагностических учреждений могут быть описаны моделями систем массового обслуживания (СМО) — детерминированными, стохастическими, динамическими, дискретно-непрерывными [10,11]. Исследование характеристик таких моделей может проводиться либо аналитическими методами, либо путем имитационного моделирования. Для построения имитационных моделей в поддержку теории СМО разработаны и успешно используются модификации языка GPSS [12,13]. Имитационная модель отображает стохастический процесс смены дискретных состояний СМО в непрерывном времени в форме моделирующего алгоритма. При его реализации на ЭВМ производится накопление статистических данных по тем атрибутам модели, характеристики которых являются предметом исследований. По окончании моделирования накопленная статистика обрабатывается, и результаты получаются в виде выборочных распределений исследуемых величин плп их выборочных моментов. В общем виде СМО можно представить как совокупность последовательно связанных между собой входящих потоков требований (заявок, работ) на обслуживание, очередей, каналов (рабочих мест, оборудования, процессоров) обслуживания и выходных потоков требований (рис. 2.3).

Системы массового обслуживания в соответствии с данной структурой могут быть классифицированы следующим образом:

по входным потокам — детерминированные плп вероятностные (стационарные, нестационарные), ординарные плп неординарные (соответственно одна плп несколько заявок в одни момент времени), зависимые или независимые потоки;

по построению очереди — очереди типа FIFO (First In First Out), LIFO (Last In First Out), co случайной выборкой требований, с приоритетом и без приоритета;

по каналам обслуживания — одноканальные, многоканальные, однофазные, многофазные;

по выходному потоку — замкнутые (заявки после обслуживания вновь поставляют в систему), разомкнутые (число заявок неограниченно);

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

ОчередьОчередьМногофазныеканалыобслуживанияМногофазныеканалыобслуживанияВходной поток заявокВходной поток заявокВыходнойпоток заявокВыходнойпоток заявок

Очередь

Очередь

Многофазныеканалыобслуживания

Многофазныеканалыобслуживания

Входной поток заявок

Входной поток заявок

Выходнойпоток заявок

Выходнойпоток заявок

Рис. 2.3. Типовая структура СМО

В качестве основных показателей СМО могут быть использованы: вероятность простоя канала обслуживания; вероятность того, что в системе находится п требований; среднее число требований, находящихся в системе п в очереди; среднее число занятых каналов.

.2.1. Одноканальная детерминированная СМО. Пусть в систему поступают заявки через равные промежутки времени Аф, а обслуживание заявок происходит через равные промежутки времени Аф. Имеется одни канал обслуживания. Введём в рассмотрение следующие характеристики:

А = 1/А^п ~ интенсивность поступления заявок;

ц = 1/Аф — интенсивность обслуживания заявок;

р = Х/р — коэффициент загрузки системы (коэффициент использования).

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

Расчёт времени произведём следующим образом.

Очередь из п заявок будет исчерпана за время

И = Афп =

М

однако в систему поступит ?71 заявок:

Н Лпх = -— = -п = рп.

Afn ц

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

За это время поступает по заявок:

О9

По = -— = — рп = р^п.

На третьем шаге имеем:

П 9о

О = — р~, По = р п.

Процесс продолжается до выполнения условия tp^x A Afn, после чего очередь исчезает. Отсюда решаем следующую задачу:

т,П ПП 9ПL

Т =Ntj=—|— р-|— ух+ ...Н— р=

п( 1 — У'+1)п( 1 — У'+1)р ррр

п( 1 — У'+1)

п( 1 — У'+1)

lb , .9l х

= -(1 + у + 9?~ + ... + Д) =

Здесь используется формула суммы геометрической прогрессии.

При большом значении к, поскольку р < 1, можно пренебречь величиной <pkJrX. Тогда для упрощения расчётов принимаем

ц — х

Чем ближе интенсивность входного потока к интенсивности обслуживания, тем больше величина Т.

.2.2. Одноканальная разомкнутая система массового обслуживания с ожиданием. Пусть задана СМО, входной поток требований которой отвечает требованиям ординарности и стационарности и отсутствием последствий. Такой поток называется простейшим (пуассоновским) потоком.

Вероятность pn(t) поступления п заявок в систему за время t при нормальном распределении входных заявок определяется формулой

Рп(У = —j-e xt.

Здесь А — интенсивность поступления потока требований, которая определяется как среднее число поступлений требований в систему. Поток является стационарным, если вероятность поступления требований не зависит от начала отсчёта времени, а зависит только от продолжительности временного интервала наблюдения t. Для стационарного потока Xt является постоянной величиной на любом участке временной оси длиной t.

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

р — средней интенсивностью обслуживания заявок,

Ро ~ вероятностью простоя системы,

рп — вероятностью того, что в системе (в очереди и на обслуживании) находится п заявок в момент времени t,

Теист — средним временем ожидания требования в системе (т. е. средним временем пребывания требования в очереди и на обслуживании),

Д?ист — средним числом заявок в системе (в очереди и на обслуживании).

Работа СМО описывается системой обыкновенных дифференциальных уравнений вероятностей состоянии:

dtdt-Xp0(tH тГ-Xp0(tH тГdp\ (t)dtdp\ (t)dt-ApoC) + (A +ЛР1(С + №(Ц-ApoC) + (A +ЛР1(С + №(Ц

dt

dt

-Xp0(tH тГ

-Xp0(tH тГ

dp\ (t)dt

dp\ (t)dt

-ApoC) + (A +ЛР1(С + №(Ц

-ApoC) + (A +ЛР1(С + №(Ц

dp^

В установившемся состоянии ——— = 0 (г = 0,1,...,и

Тогда имеем систему алгебраических уравнений:

-Хр0 + //pi = 0,

Хр0 - (Л + р>\ + рр2 = 0,

Хрп-1 - (А + р>п + ррп+х = 0.

Решая систему алгебраических уравнений получаем:

Л

Pi = -Ро = РРо,

Р2 = Р2Ро,

Рп = РпРо-

Суммируя полученные значения для р^,р\,... ,рп, находим с использованием формулы суммы геометрической прогрессии п ’’

и с учётом равенства ^ Pt = 1 (ПРП оо и р < 1):

’г=0

Ро + РоР + РоР2 + . • • + РоРп =

— Ро( 1 + р + р“ + • • • + рп) —— Ро( 1 + р + р“ + • • • + рп) —Ро1 - рРо1 - р1,1,

— Ро( 1 + р + р“ + • • • + рп) —

— Ро( 1 + р + р“ + • • • + рп) —

Ро

1 - р

Ро

1 - р

1,

1,

откуда:

Ро = 1 -

Рп =

В установившемся СОСТОЯНИИ находим ТСИст И Лейстою

Мист = У1 Tipn = Pl + 2р3 + Зрз + ... + прп + ... =

72 = 1

= РоР + 2Ро Д + ■ • ■ + npwn + ■ • ■ =

= р0Щ 1 + 2р + Зр2 + ... + пр72-1

Поскольку

у + У + <У +... + р72 +=

PW = И количество заявок в очереди какPW = И количество заявок в очереди как

PW = И количество заявок в очереди как

PW = И количество заявок в очереди как

окончательно получаем:

Лейст =

Можно получить среднее часть NCHCT:

Лоч = — Лейст = у

грЛГСИСТ

^СИСТ — Д •

Моделирование потоков работ сетями Петри

При моделировании потоков работ часто используются сети Петри и методы их функционального анализа [14-—18]. Сети Петри — достаточно выразительное средство для моделирования потоков, в том числе синхронных и асинхронных.

Переход к сети Петри заключается в замене операторов алгоритма соответствующими операторами сети Петри и в «склеивании» этих операторов между собой. Склеивание происходит

по обрамляющим позициям. Таким образом, можно задать отображение алгоритма в сеть Петри и далее использовать её в качестве модели алгоритма.

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

Сеть Петри формально задаётся пятёркой:

>= (Р,Т,Г,Я,Мо), где

Р — непустое конечное множество позиций (мест),

Т — непустое конечное множество переходов,

F и Н — матрицы инцидентности, причём

F : Р х Т — отображение множества Р на Т,

н-тх Р — отображение множества Т на Р,

Мо — начальная разметка (маркировка) — вектор, который содержит информацию о количестве меток (фишек, маркеров) в соответствующих позициях (местах) сети.

Сеть называется fc-ограниченной, если количество меток в позиции не превышает величины к. Сеть является безопасной, если она fc-ограниченна и к = 1. Если метка при попадании в позицию не может её покинуть при данной разметке, то такая позиция является ловушкой. Сеть находится в состоянии тупика, если дальнейшее срабатывание переходов невозможно.

Классификация сетей Петри

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

Маркированные сети — сети, в которых каждая позиция имеет не более одного входа и не более одного выхода. С помощью них моделируют последовательно-параллельные процессы. МG-сети называют также синхрографами. Переход в синхрографе является потенциально живым, если он не входит ни в один пустой цикл (не содержит ни одной фишки). Синхрограф является живым, если каждый его цикл не пуст при начальной разметке. Живой синхрограф является безопасным тогда и только тогда, когда каждое его место входит в определённый цикл, содержащий ровно одну фишку.

Сети свободного выбора — сети, в которых каждая дуга, выходящая из позиции, является либо единственным выходом из нее, либо единственным входом в переход. FC-сети используются для описания процессов управления. Для сетей свободного выбора разработан механизм выявления ловушек и тупиков. Необходимым условием живости сети свободного выбора является то, что тупики должны содержать в себе ловушки. Следовательно, данная сеть живой не является. Путем сети называется последовательность переходов и позиций, связанных направленными дугами. Если начало и конец пути совпадают, то такой путь называется циклом. Критерием близости живой свободной сети является возможность её покрытия циклами.

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

Ординарные сети — сети, которые не имеют ограничений, кроме одного: кратность дуг должна быть не более единицы. Между узлами прокладывается ровно одна связь. Неординарная сеть может быть преобразована в ординарную. Для этого находят максимальную кратность дуг каждого места и производят размножение позиции в соответствии с установленной кратностью. Эти позиции соединяются друг с другом в кольцо, при этом дуги прорезаются своим переходом. Направление дуг является однонаправленным, так чтобы образовывался цикл. Далее восстанавливают связи данной размноженной позиции со всеми переходами. Алгоритм проведения связей жёстко не установлен, но связи проводятся так, чтобы они оставались ординарными.

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

2 Г. И. Назаренко, Г. С. Осипов

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

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

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

Приведённая классификация является неполной. В последнее время получили развитие новые типы сетей Петри, среди которых отметим вложенные сети Петри, которые существенно расширили возможности моделирования сложных систем [18].

Функционирование сети Петри. Маркировка сети ассоциируется с определённым состоянием моделируемой системы. При заданной начальной разметке Mq проверяется наличие переходов, которые могут сработать. Если такой переход один, то он срабатывает, если несколько — срабатывает один из них случайным образом. После срабатывания перехода система переходит в новое состояние, определяемое новой разметкой Мх и так далее. Сеть останавливается в двух случаях: все метки покидают систему; система переходит в тупиковое состояние, из которого нет перехода в другое состояние. Переход является живым при данной разметке Mq, если существует такая последовательность маркирования из Mq, которая приводит к срабатыванию данного перехода. Сеть является живой при данной начальной разметке, если жив каждый её переход.

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

Рис. 2.4. Пример сети Петри

Срабатывание перехода разбивается на два полутакта:

изъятие по одной фишке из всех входных позиций,

добавление по одной фишке во все выходные позиции, связанные с данным переходом.

Рассмотрим пример сети Петри (рис. 2.4) и опишем её.

Начальная разметка: Мд = (1010).

Матрица F (табл. 2.3), которая содержит «1» в клетке (iJY если есть дуга, направленная из позиции pi в переход tp и «0» — в противном случае.

Матрица Н (табл. 2.4), которая содержит «1» в клетке (гщЪ если есть дуга, направленная из перехода ^ в позицию рр и «0» — в противном случае.

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

М3М3МуМу10 1010 10тупиктупикКК1^101^10М4М5М4М5

М3

М3

Му

Му

10 10

10 10

тупик

тупик

К

К

1^10

1^10

М4

М5

М4

М5

Мз = Мг - цикл

Рис. 2.5. Граф достижимых маркирований

Символ ио означает возможность неограниченного возрастания числа меток в соответствующей позиции, следовательно данная сеть не является безопасной. В процессе функционирования сеть может вернуться в промежуточное состояние М2 (зацикливание) или остановиться при попадании в тупиковое состояние М3.

Алгебраический подход к описанию функционирования сетей Петри. Смена маркировок сети, т. е. функционирование сети Петри, может быть описано следующим уравнением [14]:

Мк = Мк_х + АТик_ъ A = H-FT, к = 1,2

Uk — управляющий вектор в к-й момент (такт) функционирования сети, размерность которого совпадает с количеством переходов в сети. Управляющий вектор для данной сети в на

чальном состоянии имеет вид Со = I т2 L причём д = 1 означа- \ /

ет готовность перехода С к срабатыванию, д = 0 — отсутствие готовности. Наличие нескольких единиц в векторе соответствует одновременному возбуждению соответствующих переходов и разветвлению процесса.

Элементы управляющего вектора можно определить следующим образом. Элементы вектора текущей разметки Mj сравниваются с соответствующими элементами столбцов матрицы инцидентности F, каждый из которых отвечает за состояние одного перехода. Если все элементы вектора текущего состояния не меньше соответствующих элементов г-го столбца матрицы F, то это означает возможность срабатывания г-го перехода и, следовательно, д = 1.

В нашем случае:

/ 0 \/0-1-10 \

и0= 0 , А = 011 -1 ,

\ 1 /\ 0 0 -1 1 /

/000\

дТ_-110

1-1 1-1 "

\0—11/

Далее получаем:

Мх = М0 + Ати0,

/Щ / 0 0 0\0,-1101 + -1 1 -1\о/ \ о -I I /

После чего определяется новый управляющий вектор, Ux =

/ ° \'

=1, и процесс повторяется.

\ 0 /

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

МХ=МО + Ати0,

м2 = мх+ Атих = Мо + Атф0 + и^,

к-1

Мк = M0 + AT^Ui = Mq + ATS.

?-о

Здесь S — вектор счёта срабатываний. Элемент вектора я^ указывает на число срабатываний перехода it в последовательности срабатываний, ведущих от начальной разметки Mq в разметку Л/Д.

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

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

Рис. 2.6. Раскрашенная сеть Петри

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

В качестве математического аппарата часто используются цветные (раскрашенные) иерархические сети Петри (рис. 2.6). Рассмотрим пример описания работы фрагмента вычислительной системы. Она содержит центральный процессор, три внешних устройства с1\,с1^,с1з и два канала ввода/вывода а и Ь. С каждым каналом связана фишка с соответствующим цветом (именем), представленным определённым символом. При этом внешнее устройство clx использует канал а, устройство Аз использует канал Ь, внешнее устройство с!^ — каналы а и Ь.

Условия срабатывания переходов заданы соответствующими таблицами. В сети имеются дополнительные фишки «,0,^,^ — эти фишки являются внутренними для моделируемой системы.

fl Plfl PlPl Рб f2 Р2Pl Рб f2 Р2Pl f5 Рб Рб P?Pl f5 Рб Рб P?Р2 Р? fa РзР2 Р? fa Рзdx^2 d^dx^2 d^3A73A70Aа а а аd\ ds ds dsa a b b0Aа а а аd\ ds ds dsa a b bP5 faP5 fa

fl Pl

fl Pl

Pl Рб f2 Р2

Pl Рб f2 Р2

Pl f5 Рб Рб P?

Pl f5 Рб Рб P?

Р2 Р? fa Рз

Р2 Р? fa Рз

dx

^2 d^

dx

^2 d^

3

A

7

3

A

7

0

A

а а а а

d\ ds ds ds

a a b b

0

A

а а а а

d\ ds ds ds

a a b b

P5 fa

P5 fa

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

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

Сети Петри, представляющие описание потоков работ (процесса в workflow-системе), выделяют в отдельный класс сетей Петри, WPN (Workflow Petri Nets), т.к. они обладают особыми свойствами, которые обусловлены ограничениями, накладываемыми на структуру потока работ. Объектно-ориентированные расширения сетей Петри (объектно-ориентированные сети Петри), позволяют интегрировать возможности workflow и UML для описания, анализа, моделирования и управления бизнес- процессами современного предприятия с использованием открытых стандартов представления информации. Моделирование позволяет описывать и верифицировать процессы, оценивать эффективность их выполнения с использованием стоимостного анализа, а также интегрировать описание процесса с моделью данных предприятия. Структура создаваемых в CASE-средстве сетей Петри соответствует основным ограничениям, возникающим при моделировании потоков работ в системах workflow.

Моделирование потоков работ конечнымиавтоматами

Теория автоматов — раздел теории управляющих систем, который изучает модели преобразователей дискретной информации, называемые автоматами. Теория конечных автоматов может быть с успехом использована для моделирования таких объектов, как вычислительные системы, технологические процессы, управляющие и организационные структуры. В общем случае её применение позволяет вычислять, компактно представлять, анализировать и прогнозировать процессы в динамических системах при сложных входных воздействиях [19,20,21].

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

Конечный автомат — это пятерка К = {Q, Л, 5, A, F^ где

Q — множество конечных состояний автомата;

А — алфавит автомата (конечное множество входных U, выходных V и промежуточных символов или букв);

— функция переходов, она задаёт отображение вида 5 : Q х х А -о Q (переход из одного состояния в другое под воздействием символов входного алфавита);

Л — функция выходов, её вид зависит от типа конечного автомата;

F — множество выделенных (распознанных) состояний. Данное множество является подмножеством множества Q.

Среди выделенных состояний могут быть, например, состояние ошибки или состояние нормального завершения процесса. Эти автоматы предназначены для решения задач, связанных, например, с разбором текста, распознаванием необходимой цепочки символов, анализом анкет, нахождением информации в базе данных и др. Под воздействием последовательности входных сигналов (букв алфавита Л) конечный автомат переходит из одного состояния в другое и оказывается в конечном состоянии, принадлежащем F, в случае распознания входной последовательности. Конечный автомат может быть представлен в виде графа, множество вершин которого соответствует множеству Q.

Рис. 2.7. Пример распознающего автомата

Рис. 2.8. Микропрограмма работы УА

Из вершины qi в вершину qj ведет дуга, помеченная символом алфавита, если есть соответствующая команда (буква алфавита), которая переводит автомат из состояния qt в состояние qj. Последовательность букв интерпретируется при этом как входное слово. Множество допустимых слов образует язык автомата.

Пример. Пусть алфавит состоится из цифр А = {0, 19}.

Построим конечный автомат, который распознаёт числа, кратные 3. Решение задачи представлено на рис. 2.7. Здесь q^ — начальное состояние автомата, Qq — выделенное состояние, соответствующее распознанию числа, кратного 3.

Управляющий автомат (УА) — это совокупность следующих элементов (рис. 2.8):

множества двоичных выходных сигналов V = {щпш}; если Pi = 1, то происходит запуск одного из блоков ОА;

множества входных сигналов U = {щгщ}, это осведомительные сигналы, которые поступают в УА из ОА; осведомительные сигналы сообщают УА, например, о переполнении, о готовности устройства ввода/вывода, о делении на ноль и т. п.;

множества внутренних состояний Q = {щ,..., qp^ (автомат с памятью);

микропрограммы работы, которая связывает сигналы U и V.

УА может быть представлен в виде автомата Мура или автомата Мили. Оба типа автомата могут быть использованы для интерпретации микропрограммы работы управляющего автомата.

Автомат Мура. Работа автомата Мура описывается функциями переходов и выходов:

+ 1) =

Vi(t) = А,- [</(£)], г = 1,..., т.

Здесь выход зависит от текущего состояния.

В качестве примера рассмотрим способ перехода от заданной микропрограммы (рис. 2.8) к графу автомата Мура. Каждой микрокоманде (прямоугольный блок на схеме) поставим в соответствие отдельное состояние автомата. Условие перехода от одной микрокоманды к другой (ромб на схеме) представляется в виде конъюнкции осведомительных сигналов, влияющих на переход. Каждая конъюнкция выписывается так, чтобы набор значений осведомительных переменных, обращающих конъюнкцию в «1», соответствовал условию перехода. При безусловном переходе конъюнкция заменяется на константу «1». Начало и конец микропрограммы отображаются одним и тем же начальным состоянием q^. Автомат ожидает возникновения сигнала и о = 1, после чего он начинает работать. Автомат вырабатывает в соответствии с заданной микропрограммой управляющие

Рис. 2.9. Граф автомата Мура

сигналы и получает осведомительные сигналы. При этом предполагается, что управляющий автомат является циклическим, т. е. может выполнять микропрограмму многократно.

На рис. 2.9 представлен граф автомата Мура, интерпретирующего заданную микропрограмму. Функции выхода автомата описываются булевыми функциями:

Р1 = Щ V фп Ро = q2V фп г3 = qx,

Г4 = q3, Р5 = q3, с6 = q^.

По заданным функциям может быть построена функциональная схема автомата.

Автомат Мили. Автомат Мили отличается тем, что его функции выхода в момент t зависят не только от состояния автомата, но и от набора значений входных осведомительных сигналов:

q(t+ 1) = 5[<ДЮ1 Д

t’iW = Xi^t^ux^un(t)], i =

Построим граф автомата Мили (рис. 2.10). Автомат Мили использует другие состояния, они определены на выходах. Начало и конец микропрограммы представляется начальным состоянием qo. Каждая дуга, выходящая из прямоугольника, отмечается меткой и символом состояния автомата. Исключение составляют дуги, идущие к конечной или начальной вершинаам, которые не отмечаются. Если несколько дуг с меткой входит в один блок графа, то они отличаются одинаковым состоянием. Условие перехода от одного состояния к другому соседнему

Рис. 2.10. Граф автомата Мили

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

Описание выходных сигналов автомата Мили:

= 9о01) Vq3 V д4(и2и3), ^’2 = 91Ю) V93 V 94(ЩЫ

Н = 9оЮ), V4 = 91 V 92,

г-s = 9i(u2) V99, г-6 = 94(wu3 V и2и3)-

Автомат Мили, построенный по микропрограмме управления, имеет число состояний, как правило, меньшее числа состояний эквивалентного ему автомата Мура. Однако у автомата Мили есть недостаток, препятствующий его использование в качестве УА. Этот недостаток связан с тем, что при смене сигналов на входе изменения на выходе сигналов могут произойти быстрее, чем произойдёт смена состояния автомата (эффект гонок). Недостаток устраняется введением элементов задержки.

При синтезе автоматов решаются задачи:

оптимального кодирования, минимизирующего число состояний автомата;

перехода от недетерминированного автомата к детерминированному автомату.

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

2.5. Моделирование потоков работ методамилинейного программирования

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

При поиске оптимального решения задачи линейного программирования достаточно ограничиться перебором базисных допустимых решений. Число базисных решений может быть достаточно велико для их перечисления прямым перебором за реальное время. Для решения ряда прикладных задач линейного программирования разработаны специальные решения, учитывающие особенности постановок задач данного типа и указанное свойство множества допустимых решений [10,22,23].

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

Основная задача линейного программирования (ЛП) имеет следующий вид (2.6)-(2.7):

F = ciЖ1 + Сохо + ... + спхп max, (2.6) при ограничениях:

Щ1Ж1 + 012^2 + ... + й\пХи + Х^х — Ьх,

«21*^1 “Ь «22 ^ 2 4" • • • 4" GXnFn 4" Жп_|_9 = 69,

(2.7) «ml^l 4" С1т9х2 4" • • • 4" ^mn-^n 4" ^n+m — Ьт,

^i, хайп ^ 0.

Здесь х^ (г = Х,...,п) — небазисные переменные; с?-, bj, ajj (г = X,... , п; j = X,... ,т) — заданные неотрицательные коэффициенты; хп^ххп^т — дополнительные (базисные) переменные.

В качестве базового метода рассмотрим решение задач ЛП с использованием симплекс-таблиц. Приведём задачу ЛП к виду (2.8)—(2.9), удобному для заполнения симплекс-таблицы, для чего выразим базисные переменные через небазисные переменные:

F = 0 — (—сгщ — Сохо — • • • — спхп) max, (2.8) при ограничениях:

«п+i = Ьх («пщ -j- G49T2 4" •• 4" О-Хп^п^

хп+2 = Ьа ™ («21Ж1 4" CI99X9 + •• + аапХп), (2.9) ^прт = Ьт («ml «4 4" «т2^2 4" ••4" О-тп^пУ

ХхМй, • Мп F 0.

Исходная симплекс-таблица 2.5 имеет следующий вид.

Таблица 2.5

«4

«'2

Tn

Х-п+Х

Ъ\

till

«12

«In

Хп+2

bi

«21

«22

«2п

^п+т

Ьт

«ml

«m2

«mn

F

0

Cl

С2

«п

Для решения задачи (2.8)-(2.9) используются алгоритмы последовательного преобразования симплекс-таблиц, в которых последовательно реализуются этапы получения опорного и оптимального решений.

Рассмотрим эту задачу на конкретном примере.

Пусть имеются заявки 3-х типов — А, В и С, которые проходят обслуживание на приборах 4-х типов. Известно время прохождения заявки каждого типа на каждом приборе. Известен

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

Исходные данные задачи занесены в табл. 2.6.

Таблица 2.6

Тип прибора

Затраты времени для заявок

Фонд времени

А

В

с

1

2

4

5

120

2

1

8

6

280

3

7

4

5

240

4

4

6

7

350

Прибыль

10

14

12

Введя дополнительные переменные, получим основную задачу ЛИ для решения. Перепишем условие задачи в виде, необходимом для формирования симплекс-таблиц:

F = 0 — (—10^1 — 14x2 — 12хз),ж 4 = 120 — (2т 1 + 4x2 + 5хз),х$ = 280 — (xi + 8хэ + 6x3),х^ = 240 — (7x1 + 4.^2 + 5хз),ху = 350 — (4xi + 6x2 + 7хз).

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

Таблица 2.7

• получение опорного пла-

bi

Х1

х2

х3

на;

Х4

120

2

4

5

• получение оптимального

Х5

280

1

8

6

плана.

Хв

240

7

4

5

Если столбец свободных чле

X/

F

350 0

4

-10

5

-14

7

-12

нов 1р положительный, то имеем опорный план. Если в последней строке (для критерия

нет отрицательных элементов, то имеем оптимальный план. В данном конкретном случае имеем опорный план.

Построение оптимального плана.

Находим любой из отрицательных элементов в последней строке, например (—12). Столбец, в котором расположен этот элемент, называется разрешающим столбцом. Для разрешающего столбца найдем отношение каждой строки, за исключением последней, к элементу столбца. Среди этих отношений находим минимальное положительное число. Строка, в которой расположен этот элемент, называется разрешающей строкой. Элемент Sr^ (г — номер строки, к — номер столбца) на пересечении разрешающей строки и разрешающего столбца называется разрешающим элементом.

Преобразуем таблицу по следующим правилам.

Для разрешающего элемента

Для всех элементов r-й строки, кроме разрешающего элемента,

s;3 = If j^k.

ОТк

Для всех элементов fc-ro столбца, кроме разрешающего элемента,

Для всех остальных элементов таблицы

О S^Spj • / 7 ' /

Необходимо выполнить обмен переменных, находящихся при разрешающем столбце и разрешающей строке, — в данном случае это жз, ж4 (табл. 2.8).

Таблица 2.8

bi

Т1

Т2

Х4

т3

24

2/5

4/5

1/5

Тб

136

-7/5

16/5

-6/5

т6

120

5

0

-1

х7

192

6/5

2/5

-7/5

F

288

-25/5

-22/5

12/5

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

Последующие этапы отражены в соответствующих симплекс- таблицах 2.9 и 2.10.

Таблица 2.9

bi

т6

т2

Х4

т3

72/5

-2/25

4/5

т5

848/5

7/25

16/5

-28/25

Ху

24

1/5

0

-1/5

х7

816/5

-6/25

2/5

-29/25

F

2054/5

25/25

-22/5

44/25

Таблица 2.10

bi

т6

т3

Х4

x<z

18

-1/10

5/4

7/20

Хь

112

3/5

-4

-56/25

24

1/5

0

-1/5

х7

156

-1/5

-1/2

-13/10

F

492

3/5

11/2

165/50

Выпишем оптимальное решение из последней таблицы: хо = 18, х^ = 112, хх = 24, Х7 = 156,

F = 492, х^ = тз = Х4 = 0.

Таким образом, заявки 3-го типа при оптимальном плане не обслуживаются. Кроме того, остаются неиспользованными 112 единиц ресурса прибора второго типа и 156 единиц ресурса прибора четвертого типа.

Решение задачи о назначении. Пусть имеется п работ (задач) и п кандидатов на их выполнение (персонала, процессоров, мест, машин). Пусть qj (i,j = 1,2п) — затраты (стоимость, время), связанные с назначением кандидата г на работу j. Введём переменные х^ (rj = 1,2,..., и) такие, что Xij = 1, если кандидат г назначен на работу j, и х^ = 0

в противном случае. Задача заключается в таком назначении (распределении), при котором суммарные затраты на выполнение всех работ минимальны.

Задача может быть сформулирована как задача ЛП:

и п

с = ^ф УУ CijXij min,2=1 j = l

П

причём 52 х^з — 52 хп = 1 Для всех ^j— 1,2,..., и, т. е. каждый 2=1

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

Есть специальный метод решения этой задачи, называемый

венгерским методом. Рассмотрим конкретный пример. Пусть

имеется 4 кандидата и 4 работы. Исходные данные задачи —

Кандидаты

Работы

1

2

3

4

1

3

7

5

8

2

2

4

4

5

3

4

7

2

8

4

9

7

3

8

Таблица 2.11Таблица 2.11величины затрат qj (i,j = 1,2,...,4) содержатся в табл. 2.11.

Таблица 2.11

Таблица 2.11

Метод основывается на том факте, что оптимальность решения не нарушается при увеличении или уменьшении элементов строки (столбца) таблицы на одну и ту же величину. Отсюда следуют все основные преобразования исходной таблицы.

Алгоритм решения задачи разби-

вается на несколько этапов.

Получение нулей во всех строках и столбцах матрицы.

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

Поиск оптимального решения.

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

отмеченными нулями х^ = 1, а для других х^ = 0. В противном случае переходим к следующему этапу.

Этап разметки строк и столбцов.

Отмечаем точкой строку, не содержащую ни одного отмеченного нуля.

Отмечаем столбец, содержащий перечёркнутый нуль в отмеченной строке.

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

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

Перестановка отмеченных нулей.

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

Результаты 1-го и 2-го (заключительного) этапов отражены в таблицах 2.12, 2.13.

делены полужирным шрифтом и подчёркнуты), для которого с =17.''

Транспортная задача

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

Обозначим через а^ (i = l,2,...,m) запасы ресурса на г-м пункте отправления и bj (j = 1,2,...,п) количество требуемого ресурса на j-м пункте назначения. Обозначим через Cij (г = 1,2,..., т; j = 1,2,..., п) стоимость доставки единицы

ресурса из г-го пункта отправления в j-й пункт назначения, а через х^з количество единиц ресурса, перевозимого из г-го пункта отправления в J-й пункт назначения. Тогда постановка задачи заключается в определении минимального значения функции:

т пт п

= 52 52 = 52 52min

2=1 7 = 12 = 1 7 = 1

т

при ограничениях ^ Fj = bj (количество ресурса, доставляемо-2=1'

П

го в j-й пункт); ^2 xij = °ч (количество ресурса отправленного j=i

из г-го пункта); х^ ^ 0 (г = 1,..., т; j = 1,..., п).

Если функции Fij = С{j X{j стоимости пересылки являются линейными функциями, то задача является задачей линейного программирования и может быть решена симплекс-методом. Для тп

её решения необходимо и достаточно, чтобы ^ аг = X bj- Если 2=1.7=1

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

Известны следующие особенности рассмотренной модели:

коэффициенты при неизвестных равны единице,

каждое неизвестное входит лишь в два уравнения системы,

исследуемые данные можно считать целочисленными (условие целочисленности).

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

Рассмотрим пример. Имеются 3 пункта отправления А?- (i = = 1,2, 3) и 4 пункта назначения (потребления) Bj (j = 1,... ,4). В табл. 2.14 указаны величины Cij (г = 1,2, 3; j = 1,..., 4), а также имеющиеся запасы и потребности (ёмкости).

1-й этап. Получение опорного решения методом минимального элемента.

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

F = 1 • 160 + 4 • 120 + 8 • 20 + 2 * 50 + 3 * 30 + 6 • 90 = 1530.

Таблица 2.14

Пункты отправления

Пункты назначения

В,

в2

В3

В4

Запасы

Ai

7

8

1

2

160

Аг

4

5

9

8

140

Аз

9

2

3

6

170

Потребности

120

500

190

ПО

470

Таблица 2.15

7

8

1 160

2

+

4 120

6

9

8 20

9

2 50

330 +

6 90

2-й этап. Получение оптимального решения методом узловых потенциалов.

Теорема 2.2. Если для некоторого опорного плана транспортной задачи существуют такие числа аь ад,..., ат\ Зг 3^ • • • Зп, что 3j ™ Q4 = Cij для заполненных клеток (x^j > 0) и З3 ™ Q4 ^ Cij для пустых клеток ^х^ = 0), то такой план называется оптимальным. Числа а^Зд называются потенциалами соответственно пунктов отправления и пунктов назначения.

Составим систему уравнений для заполненных клеток:

Зз ™ Q4 = Из = L

31 - «2 = СП = 4,

З4 — а2 = с24 — 8,

Зз «з = С32 = 2,

Зз ™ «з = С33 = 3, За - ад = с34 = 6.

Так как число заполненных клеток т + п — 1 = 6, а число неизвестных т + п = 7. то одно из неизвестных выбирают

произвольно. Пусть, например, aq = 0. Тогда: ад = — 2, «2 = “4, Зз = 1, Д = 4, З2 = 0, Зх = 0.

Для каждой свободной клетки определяются числа, такие что o^j = 3j ™ <^г ™ Cij. Если все сх^ отрицательны, то опорное решение является оптимальным. В противном случае необходимо перейти к новому плану. Для данного примера:

«п = Зх - «1 - сп = -7,

«12 = 02 ™ «1 ™ Q2 = “8,

а и = Д — ai — си = 2,

«22 = 02 ™ «2 “ с22 = “ L

«23 — 03«2 ” «23 = ™4,

«31 = 0Х — «3 ” С31 = “7.

Поскольку ан > 0, то имеющееся решение не является оптимальным.

Для перехода к новому плану рассматривают все свободные клетки, для которых а^ > 0 и из них выбирают клетку с максимальным значением cqj- Данную клетку следует заполнить. При этом следует изменить объёмы поставок в других клетках, связанных с данной клеткой циклом. Циклом называется замкнутая ломаная линия, вершины которой находятся в занятых клетках таблицы и в данной заполняемой клетке, а звенья располагаются вдоль строк и столбцов. Необходимо переместить ресурсы в пределах клеток цикла, для чего необходимо выполнить следующие действия.

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

В данную свободную клетку переносят меньшее из чисел Хр стоящих в минусовых клетках. Одновременно это число необходимо прибавить к соответствующим числам, находящимся в плюсовых клетках и вычесть из чисел, находящихся в минусовых клетках. Клетка, которая раньше была свободной, становится занятой, а минусовая клетка с минимальным числом становится свободной (пустой).

Таким образом, получаем новый опорный план, который следует проверить на оптимальность (переход к этапу 2).

В нашем случае необходимо заполнить клетку (1,4), так как «14 > 0. Соответствующая разметка клеток, образующих цикл, показана в табл. 2.15. В результате перемещения ресурса в количестве 90 единиц, получаем новое решение (табл. 2.16).

Таблица 2.16

7

8

1 70

2 90 +

4 120

5

+

9

8 20

9

2 50

3120 +

6

F = 70 + 2 • 90 + 8 • 20 + 3 • 120 + 2 • 50 + 4 • 120 = 1350.

Полученное решение лучше предыдущего. Проверяем его на оптимальность В результате получаем для заполненных клеток:

«1 = 0, «2 = ™6, ад = —2,

д=1, А = 2, А = 0, /31 =-2;

для пустых клеток:

«11 = -9,«12 = -8,«22 = 1,

одз — “2,«31 = —9,«34 = —2.

Поскольку полученное решение не является оптимальным, производим перемещение ресурса в количестве 20 единиц по новому циклу с заполнением клетки (2,2), так как «22 > 0 (табл. 2.17).

Таблица 2.17

7

8

1 50

2110

4 120

5 20

9

8

9

2 30

3140

6

F = 50 + 2 * 110 + 5 * 20 + 4 * 120 + 2 * 30 + 3 • 140 = 1330.

Можно легко проверить, что данный вариант является оптимальным.

Поиск кратчайшего пути

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

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

Пусть задана связная сеть G из п + 1 вершин и т ребер, представленная в виде ориентированного графа, в котором выделены две вершины — вход (нулевая вершина) и выход (вершина с номером и). Для каждой дуги заданы неотрицательные числа, называемые длинами дуг. Сеть представляется матрицей смежности Л, в которой:

Л(ц Д равно длине ребра между вершинами % и j;

A^j) = оо, если между вершинами г и j нет ребра;

А(г, %) = 0 для всех г = 0, 1,..., п.

Введём переменные тД, j^ такие что:

x^j) = 1, если дуга (цД входит в путь д = (ОЛьД,...

... Лп-ьД;

x(i,j) = 0, если дуга (цД не входит в путь щ гщ = = 0, 1,, п).

Тогда задачу о минимальном пути можно записать в виде задачи ЛП:

L(x) = ^^A(i, j)x(i, j) min,(2.10)

nn

5240,4 = 1, 524^0 = 1,(2.11)

33

k= l,2,...,n- 1.(2.12)

33

Для решения задачи (2.10Д(2.12) часто используют алгоритм Дейкстры [8], который признан одним из лучших. Рассмотрим принципы его построения.

Для определения кратчайшего пути помечают все вершины сети, указав в качестве начальной Vg и конечной W вершин пути первую и последнюю вершины сети.

Шаг 1. Определяются непосредственные расстояния (длиной в одно ребро) от заданной вершины Vg до всех остальных вершин.

Шаг 2. Выбирается наименьшее из них в качестве «постоянного» наименьшего расстояния (ребро между Vg и некоторой новой вершиной Уд).

Шаг 3. Это наименьшее расстояние добавляется к длинам ребер от новой вершины Уд до всех остальных связанных с нею вершин.

Шаг 4. Эта сумма сравнивается с предыдущим расстоянием от Vg до остальных вершин, и прежнее расстояние заменяется, если новое меньше.

Шаг 5. Новая вершина удаляется из списка вершин, до которых ещё не определены кратчайшие расстояния, и список укорачивается на один элемент.

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

В наихудшем случае задача отыскания кратчайшего расстояния от начальной вершины до конечной имеет ту же сложность, что и задача отыскания кратчайшего пути из начальной вершины во все остальные вершины. Задача о кратчайшем пути имеет в наихудшем случае сложность O((n + I)2).

2.8. Оценка критериев качества

Для оценки критериев качества (например качества работы подразделений) могут использоваться аддитивные критерии п'

F = ^ ^jFj^ в которых учитываются весовые коэффициенты Xj 1 = 1п

частных критериев F^ причём ^2 Aj = 1. Рейтинговую оценку критериев проводят эксперты по диагностической, лечебной и хирургической работе, которые оценивают каждый критерий определённым числом баллов, исходя из его важности. Ниже

рассмотрены два метода рейтинговой оценки критериев качества с помощью экспертов [24].

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

критерию. В дальнейшем удобно пересчитать эту таблицу, присваивая более важному критерию большее число у^ (г = \Д,... ,т\ з = 1,2,..., п\ Введём новые веса y^j = п — тур Теперь наиболее важный критерий имеет оценку п — 1, а наименее важный — нуль. Весовые коэффициенты в аддитивном критерии определяются таким образом:

т

' Угк

г=1 j=\

Степень согласованности результатов работы экспертов определяется коэффициентом

_125

т2 (п3 — п) ’

где п।т

S = ^^dj, ^7 = 9Ш(П+ 1) “ 52^’= 1’2,... ,п.

Значения w изменяются в пределах w Е [0, 1]. Если w = 1, то все эксперты дают одинаковые оценки. Если w = 0, то мнения экспертов несогласованны. В зависимости от величины

коэффициента w результаты оценки критериев либо принимаются, либо отвергаются.

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

Здесь а^ = 1, (i = 1,2,... ,n; j = 1,2,..., n; к = 1,2,,т), если г-й критерий предпочтительнее Дго критерия, а^ = 0 в противном случае.

Для каждого эксперта имеем такую таблицу, т. е. всего т таблиц. Далее происходит объединение таблиц в одну путем суммирования чисел, стоящих в соответствующих клетках:

т

ьи = 52

Определим весовые коэффициенты: п

Е

■ (А = 1.2

ЕЕ"-

В этом методе тоже надо определить степень согласованности экспертов: п п

2ЕЕЕ

г=1 J=1

v тЛ" п

а!

где С^. = —— — число сочетаний из и по г.

— г)!

Максимальное значение коэффициента согласия 7max = 1- Минимальное значение

{

1

для т четного, т — 1

для т нечётного.

т

Пример. Пусть имеются 3 эксперта и 4 критерия. Работа экспертов по ранжированию критериев показана в табл. 2.20. После пересчёта получаем табл. 2.21.

Таблица 2.201234142312314234231Таблица 2.201234142312314234231123410000210103100041110123410000210103100041110Таблица 2.22Таблица 2.22123410010230313200043230123410010230313200043230Таблица 2.24Таблица 2.24

Таблица 2.20

1

2

3

4

1

4

2

3

1

2

3

1

4

2

3

4

2

3

1

Таблица 2.20

1

2

3

4

1

4

2

3

1

2

3

1

4

2

3

4

2

3

1

1

2

3

4

1

0

0

0

0

2

1

0

1

0

3

1

0

0

0

4

1

1

1

0

1

2

3

4

1

0

0

0

0

2

1

0

1

0

3

1

0

0

0

4

1

1

1

0

Таблица 2.22

Таблица 2.22

1

2

3

4

1

0

0

1

0

2

3

0

3

1

3

2

0

0

0

4

3

2

3

0

1

2

3

4

1

0

0

1

0

2

3

0

3

1

3

2

0

0

0

4

3

2

3

0

Таблица 2.24

Таблица 2.24

В результате имеем вектор весовых коэффициентов

А = (1/18,7/18,2/18,8/18)

и степень согласованности экспертов

_ 12-37 _ 37 ~w 9(64 -4)40 ~ °’8 ‘

Работа 3-х экспертов по парному сравнению критериев отражена в таблицах 2.22+2.24 и сводной табл. 2.25.

Весовые коэффициенты А = (1/18,7/18,2/18,8/18) совпадают с коэффициентами, полученными по методу ранжирования.

Степень согласованности экспертов

2(3 + 3+1+3+1 + 3)15

' =Гб' = 9

на интервале 7min = - 7з, 7max = 1-

Глава 3

РЕЛЕВАНТНОСТЬ И ПРЕЦЕДЕНТНОСТЬ НАМНОЖЕСТВЕ МЕДИЦИНСКИХТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ

Прецедентность на множестве медицинскихтехнологических процессов

Напомним, что каждый элемент МТП, т. е. лечебное мероприятие, мы представляем как совокупность ограничений, императивов и операторов [2].

Ограничения Con описывают требования на продолжительность каждого этапа, наиболее важные показатели, требующие объективного исследования, критериальное подтверждение диагноза (если таковое существует), критерии перевода в другое отделение, критерии смены терапии, критерии выписки из стационара, критерии, которые являются условиями применения некоторого лечебного мероприятия.

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

С каждым ограничением связывается указание на этап, требования к которому задаются этим ограничением. Это указание может задаваться, например, временем t начала этапа — Con(t).

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

императивом, точно так же как и с ограничением, будем связывать указание на этап. Это указание может задаваться, например, временем t начала этапа — Imp(t).

Ограничения Con(t) включают: требования на продолжительность этапа L(t); наиболее важные показатели, требующие объективного исследования, P(i); критерии перевода в другое отделение Ktr; критериальное подтверждение диагноза Kds; критерии выписки из стационара К; критерии (условия) применимости оператора С.

Иначе говоря, Con(t) = (L(i)&P(i)&Ktr(i)&Kds&K&C). В дальнейшем мы будем заменять знак «&» запятой.

Императивы Imp(t) включают: указания по выбору специалистов Ch(t); манипуляции M(i); инструментальные и лабораторные исследования Rch(i), т. е. Imp(t) = (Ch(i), M(i), Rch(t)).

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

Множество всех элементов МТП обозначим через Е. Каждый элемент МТП е Е Е включает ограничения, императивы и некоторый оператор, т. е. представляет лечебное мероприятие. Через П(Е) обозначим множество МТП и через л (возможно с нижним индексом) — экземпляры МТП.

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

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

Метрики для классификации ситуаций

Многие задачи сводятся к сравнению текущего вектора признаков, характеризующих некоторое состояние или процесс, с эталонным (типичным) вектором той же размерности для выяснения степени близости или расстояния. В общем случае возникает задача парного сравнения текущего вектора с множеством векторов — например эталонов лечебно-диагностических процессов.

Рассмотрим образ в некотором пространстве признаков. В случае, если рассматривается /г признаков, имеем для каждого образа точку п-мерного пространства. Пусть в некотором /г-мерном пространстве заданы 3 точки — А, В, С.

К метрикам можно предъявить следующие требования:

d(A,B) У 0 (неотрицательность);

d(K, В) = 0 А = В (тождественность);

d(A, В) = d(B, А) (симметричность);

d(A, В) + <ЦВ, С) A d(A, С) (правило треугольника).

Заметим, что этим требованиям удовлетворяет расстояние в евклидовом пространстве:

^(A^,Aj) =

где Хк = (хХкМ2Ь --^пк) и Х3 = (xXj,xy, ...,xnj) — образы (точки евклидова пространства).

Если признаки принимают значения либо 1 либо 0 (т. е. являются бинарными величинами), то в качестве метрики используется мера Хемминга:

п

d(Xk,XjX = ^2\xik - xi3\ или d{Xk,Xj) = вирЩ - xi3\.i=i’

Близость образов можно определять с помощью мер близости, определённых несколько иным образом. Условия, которым они должны удовлетворять, таковы:

О А 7(А,В) А 1 (7(А,В) нормирован);

7(А,В) = 1 А = В;

7(А,В) = 7(В,А);

7(А, В) ^ 7(А, С), если <Х, В) ^ <Х, С).

3 Г. И. Назаренко, Г. С. Осипов

В качестве меры близости, например, может быть использован классический коэффициент корреляции:

В качестве меры близости может быть использована также мера Танимото-Джаккара:

К = n/nf,

где /г — число совпавших признаков, и1 — общее число признаков.

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

Евклидова метрика:

dik ='

Другая форма представления, для сравнения двух векторов:

Re(x1^x2) = (М - Х2)Т • С-М “ xsY(3.1)

Метрика Евклида, используемая для определения расстояния между точками пространства признаков щ, зд, удовлетворяет всем аксиомам расстояния; она удобна для определения расстояния между двумя точками, например между точкой наблюдаемых параметров и центром (выборочным средним) класса. Она не учитывает распределение точек в классе.

Мера сходства Хемминга:

где п^ — число совпадающих признаков у образцов Xi и Хр.

Вероятностная мера сходства:

где з — номер эталона, Х^г = 1,2,..., Ж) — элемент неизвестного входного образца, w^- — значение весового коэффициента, соответствующее математическому ожиданию г-го элемента (признака) фго эталона. Величина среднеквадратичного

отклонения а^ находится в результате экспериментов для каждого эталона.

Мера сходства Родаюерса-Танимото:

= niM + nk - Tlik), где nik — число совпадающих единичных признаков у образцов Х^ и Хр; гц п^. — общее число единичных признаков у образцов Х^ и Ху соответственно.

Метрика Махаланобиса:

В?м^ X) = (ж — Х^г С-Чх — т),(3.2)

где х — выборочное среднее класса X. Она представляет собой квадратичную форму, где С-1 — матрица, обратная корреляционной для рассматриваемого класса.

Элементы матрицы Ci вычисляются по формуле

где г, у — все возможные пары индексов измеряемых признаков, (i,j = 1,2,..., Ж). Выражения в скобках есть отклонения значений переменных х^ от соответствующего среднего N — количество объектов в классе. При г = к вычисляются среднеквадратичные отклонения, которые соответствуют дисперсиям параметров, а при г ^ к оценивается ковариация между двумя параметрами. Метрика Махаланобиса неприменима, если выборочная дисперсия хотя бы одного из параметров равна нулю.

Nd^k = ^M где 3k =7 = 1Nd^k = ^M где 3k =7 = 1Метрика Журавлева:

N

d^k = ^M где 3k =

7 = 1

N

d^k = ^M где 3k =

7 = 1

если |хд — хщ| < е, О, если \х^ — Хщ| Е.

Манхэттенская метрика:

N

7=1

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

Расстояние Чебышева:

dik = arg ^ахру - mV

где N — количество переменных (признаков), г и j — номера объектов.

Частично используется в нечётких нейронных сетях в виде минимаксных критериев. Недостаток — кластеры, полученные с помощью расстояния Чебышева, «склеиваются» друг с другом.

Метрика Брея-Кертиса:

N

В этом случае значения заключены между 0 и 1. Обычно перед использованием этой метрики данные стандартизуют. Данные после стандартизации должны быть неотрицательными.

Метрика Чекановского:a + сгк 2а + Ь + с*

Коэффициенты а, Ь, с, и d берутся из таблицы (матрицы) ассоциативности, построенной для двух объектов г и к, в которой 1 указывает на наличие признака у объекта, 0 — на его отсутствие. Проще всего рассмотреть эти коэффициенты, обратившись к таблице (матрице) ассоциативности размера 2x2:

О

lab.

О с d

Метрика Жаккара:

Как и в случае метрики Чекановского, коэффициенты а, Ь, cud берутся из таблицы ассоциативности.

Обобщённое расстояние Евклида-Махаланобиса рассмотрим, следуя [27,28].

Для определения расстояния от точки, координаты которой представляют собой параметры наблюдаемого объекта, до класса п сходных объектов обычно пользуются метриками Евклида и Махаланобиса. Каждая из этих метрик имеет свои преимущества и недостатки.

Метрика Евклида, используемая для определения расстояния между точками щ, тд,

Re(xXM^ = (М ™ Х<^Т • (-И ™ ^)>

удовлетворяет всем аксиомам расстояния, она удобна для определения расстояния между двумя точками, например между точкой наблюдаемых параметров и центром (выборочным средним) класса. Она не учитывает распределение точек в классе.

Метрика Махаланобиса не применима, если выборочная дисперсия хотя бы одного из параметров равна нулю:

Jim^ Rm^\ X) = сю.(3.3)

Метрика Махаланобиса совпадает с Евклидовой в случае, если класс представляет собой вектор реализаций нормированных (дисперсии Di = 1, г = 1,..., /г) независимых (ковариации Kij = 0, i,j = 1,..., п, г 7^ J) случайных величин. Если дисперсии больше 1, то расстояние Махаланобиса меньше Евклидова, если меньше, то R^ > R^. Проверка аксиом расстояния затруднена тем, что метрика используется для определения расстояния между разнородными объектами. Расстояние между двумя точками согласно (3.3) почти всегда бесконечно велико. Исключением является случай, рассмотренный ниже, который можно считать доказательством, что R2M(x,x) ^ 0.

Рассмотрим класс, состоящий из трёх точек: X = = {(0,0), (0, —А), (—А, 0)}. С помощью метрики Махаланобиса определим расстояние от точки х = (0,0) до класса X. При А, стремящемся к нулю, предел этого расстояния должен быть равен R^^x). Составим матрицу С-1:

2А2/9 -А2/9-А2/9 2А2/92А2/9 -А2/9-А2/9 2А2/9/ 6/А2 3/А2у 3/А2 6/А2/ 6/А2 3/А2у 3/А2 6/А2

2А2/9 -А2/9

-А2/9 2А2/9

2А2/9 -А2/9

-А2/9 2А2/9

/ 6/А2 3/А2

у 3/А2 6/А2

/ 6/А2 3/А2

у 3/А2 6/А2

Расстояние Махаланобиса составляет

(

Д \

0 + ж-

о + —

3 /

и не зависит от величины А. Таким образом, ^т^Д^т^А) = = R^M(x,x) = 2, что противоречит первой аксиоме расстояния.

Метрику Евклида, как и метрику Махаланобиса, можно представить в виде квадратичной формы, матрицей которой является единичная матрица:

= (ж-1 — x^E^xi -х^.

Метрика Махаланобиса может также использоваться и для измерения расстояния между двумя классами Xi и Х2. Для этого берут среднее взвешенное расстояний Махаланобиса от выборочных средних:

<(^1, ^2) — Г^АХ\> ^2) + (1 — 7)^м(х2, Xi).

Такая метрика неудобна, угак как если класс Xi состоит из единственной точки хц то №м^х\,Х^ Д R?M(x\, Х^. Рассмотрим обобщённую метрику Евклида Махаланобиса [8], определяющую расстояние между двумя классами Xi и Х2, в виде квадратичной формы

R^X\,X^ = Ц1 -bfAX -х2\

где Т| и щ — средние выборочные классов, матрица Л-1 является обратной матрицей произведения

Л=(С1+Е)(С2 + Е), (3.7)

(71 и (?2 — корреляционные матрицы для первого и второго классов соответственно. Для любых двух классов Xi и Х2, у которых Т1 = Х2, расстояние Д^(Х1,Х2) = 0. Если класс Xi представляет собой точку, то соответствующая ему корреляционная матрица состоит из нулей и мы получаем расстояние, аналогичное расстоянию Махаланобиса, с той разницей, что Rq(i*x, Х2) = R^(xx,X2) в случае, если дисперсия 0^=0, (г = 1,... 9?г). Если оба класса представляют собой точки, то Rq.s(x\,X2) = R^(х 1Д2)- Такая метрика удобна для решения задач распознавания образов, в которых некоторые параметры, описывающие наблюдаемые объекты, не изменяются. Рассмотрим, в качестве примера, задачу классификации объектов (табл. 3.1).

Видно, что данные по ту практически одинаковы, что затрудняет использование метрики Махаланобиса. Рис. 3.1. поясняет относительное расположение объектов. Каждый объект представлен точкой (хь хз) в пространстве только двух параметров.

Линии наилучшего приближения к множеству точек каждого класса построены по методу наименьших квадратов. Серые кружки соответствуют классу 1, чёрные — классу 2. Рассмотрим

Таблица 3.1

Объекты

Параметр ад

Параметр х^

Параметр хз

1 (класс 1)

16,7

13,46

5,15

2 (класс 1)

19,75

14,015

5,139

3 (класс 1)

17,1

14

6

4 (класс 1)

17.32

11,36

4,73

5 (класс 1)

22.69

13,46

5,15

6 (класс 2)

21.935

14,7

5,932

7 (класс 2)

21.94

14,7

6,36

8 (класс 2)

22

14,7

5,93

9 (класс 2)

21.19

14,7

5,93

10 (класс 2)

22,18

14,7

6,35

11 (класс 2)

22,183

14,698

6,433

12 (класс 2)

21,9

14,7

5,9

4.5-

41111!

15171921232527

Рис. 3.1. Относительное расположение объектов

в качестве примера произвольную точку А с координатами (20,828; 14; 6,1) трёхмерного пространства (в соответствии с размерностью табл. 3.1). Измерим для сравнения расстояния от заданной точки до классов с помощью различных метрик. Результаты измерений отражены в табл. 3.2.

Таблица 3.2

Расстояние

Класс 1

Класс 2

Евклида

5.768

1,4877

Обобщённое

1,3580

1,3590

Махал анобиса

5,3884

1218130,7445

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

Согласование прецедентов

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

Нахождение количественной оценки степени согласования должно основываться на соответствии элементов различных прецедентов. Это соответствие задаётся локальной функцией согласования.

Определение 3.1. Локальная функция согласования А : Е х Е R такова, что A(e, ej = г е R.

Согласование можно рассматривать как меру сравнимости элементов ei и е. Если элементы ei и е несравнимы, то локальная функция согласования на них не определена. Множество всех

элементов е, с которыми сравним элемент ei обозначим через О = {е| если A(e,ei) определена}. Содержательно сравнимость элементов означает, что они принадлежат одному и тому же типу или домену и тогда А(е, ej >0 может рассматриваться как «напоминание» о ei при обнаружении е; A(e,ei) = 0 означает, что напоминание о ei отсутствует, a A(e,ei) < 0 указывает, что е не может рассматриваться в качестве напоминания оег

Определение 3.2. Согласование между парой МТП описывается глобальной функцией согласования Л : ЩЕ) х ЩЕ) Д, (где R — множество рациональных чисел), такой что большее значение A^^ttj) соответствует большей степени согласования МТП.

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

Функция согласования для вектора признаков

В большинстве случаев медицинский технологический процесс может быть задан в виде пар ^е,я\ где е — лечебное мероприятие, as — состояние пациента — определённое подмножество из множества S фактов и признаков. Определение 3.2 можно переписать в этом случае в следующем виде.

Определение 3.3. Пусть П(Д) — множество прецедентов, заданных указанным выше образом; локальная функция согласования тогда имеет вид Ащ S х S R. Если ввести функцию ip — композиции локальных функций согласования, то можно записать

люь... ло, вь---<т) = лми-т ••• ДпЛ, ту

где Qi, щ — прецеденты.

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

мт---,дл■ шт е = i,-.., л-

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

Определение 3.4. Пусть {вцв2,еп} — множество элементов, таких что с каждым из них сравним некоторый элемент е (т. е. О = }е^| что А(е,е^) определена}).

Функцию Хе : R х ... х R R, такую что Хе = Хе(ф,..., anY где ai = f(aq(ei), Х(вр е)), aq(e) = 1 (если е 6 q) или aq(e) = О (в противном случае), будем называть функцией композиции.

Что касается функции /, то в простейшем случае можно считать, что она есть произведение а и А, т. е. щ = aq(e^ * А(ед е).

Предпочтения и глобальная релевантность

Введём теперь некоторую величину, которая будет характеризовать релевантность прецедента некоторому элементу или частичную функцию релевантности р : Е х П(Е) Д, так что г = р(е, тг).

Предпочтения служат для обнаружения таких прецедентов, которые могут оказаться наиболее подходящими для некоторого заданного прецедента. Можно полагать, что такую «предпочтительность» можно задать с помощью отношения предпочтения на множестве прецедентов, а запись 7V\aq7b2 означает, что xi предпочтительнее т?2 в смысле некоторого прецедента q.

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

В соответствии с этой гипотезой, сходство прецедентов будем описывать глобальной функцией релевантности, которую можно считать линейной формой частичных функций релевантности. Глобальную функцию релевантности обозначим через 1е\(х\уф Тогда геЦтгд^) = у(р(еьтг2),... ,р(еп,тг2)); где в\,... ,еп — элементы 7ц. Положим также, что

= геЦльд) > ге1(л2, q). Будем считать, что функция релевантности нормирована так, что для всяких л\ и Л2 геЦлц л2) 6 [0, 1].

Величину dist(7ri, Л2) = 1/ге1(тг1, Л2) будем называть расстоянием между прецедентами. Введём теперь понятие частичного прецедента, несколько модифицировав определение, приведённое в [4].

Определение 3.5. Частичным прецедентом для примера л = (..., он о^ 5, Ofc, оп,..ф где 5 — некоторая последовательность операторов из О, будем называть всякий пример лр, такой

что ге1(л, лр) ^ 0 и последовательность (од5р, о^ С сиР) где бр — некоторая подпоследовательность операторов из О.

Графически это выглядит следующим образом:

тг : ... > о^ > Oj > 5 > op > оп > ...

Яр : ... > о^ > Oj > 5Р > ор > оп > ...

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

Глава 4

ПОТОКИ РАБОТ В МЕДИЦИНСКИХДАННЫХ

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

Что подлежит анализу в ходе решения этой задачи?

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

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

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

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

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

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

В [5] были введены последовательные и параллельные потоки работ, однако не было рассмотрено устройство операторов, образующих потоки и условия возникновения тех или иных потоков. Оказалось, что во всех перечисленных задачах возникают и иные типов потоков работ.

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

Заметим, что высокая актуальность задачи построения моделей лечебно-диагностических процессов в клинической медицине связана с несколькими факторами, такими как существенный разрыв между знаниями, накопленными в теоретической медицине и их использованием в медицинской практике; постоянный рост стоимости лечения, следствием чего для большинства населения со временем окажется доступным лишь минимальный объём медицинской помощи, и ряд других.

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

Потоки работ как допустимыепоследовательности операторов

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

Обозначим множество заболеваний и патологических процессов через [/, а множество значений признаков, наблюдаемых, исследованных и измеренных в некотором состоянии, — как и ранее, через Р. С формальной точки зрения, элементы первого множества можно считать замкнутыми формулами логического (или какого-либо иного формального) языка первого порядка, элементы второго множества — одноместными атомарными формулами логического языка первого порядка.

Иначе говоря, заданы:

некоторое непустое множество U фактов, представленных множеством замкнутых формул логического языка первого порядка;

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

Кроме того (как показано в [2]), эти множества можно пополнить с помощью специальных процедур замыкания, основанных на качественных рассуждениях и вычислениях, однако сейчас этих процедур мы касаться не будем.

Задано также множество операторов, представляющих активные части лечебных мероприятий, т. е. действия, которые входят в те или иные лечебные мероприятия и изменяют в результате состояние пациента [2]. Таким образом, задано множество операторов О, действующих из 2и в 2и и из Р в Р, так что oS^n) = S(n + 1), где о е О, S(n) е 2L\ S(n + 1) 6 2и.

Каждому оператору поставлено в соответствие условие его применимости, т. е. задано отображение CON: О Р U 2^, так что CON(o) = сои, где о 6 О, сои е Р U 2и.

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

4-1. Потоки работ как допустимые последовательности операторов 79 формам. Каждый случай, т. е. запись обо всех лечебных мероприятиях, относящуюся к конкретному пациенту, будем называть примером или экземпляром. К примерам мы предъявляем следующие требования: для каждого мероприятия должно быть указано его наименование и время исполнения.

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

Итак, рассмотрим И (О) — семейство последовательностей вида си = (opOj,... ,о^ над множеством О операторов. Здесь kj,..., к — элементы N множества натуральных чисел и г < у < < ... < к. Можно считать, что с каждой последовательностью си связаны отображения ord : N 2^, так что ord(n) = я(п^ где s(n) е 2и, и lab^ : N -л О, так что lab(n) = оп, где оп 6 си. Первое отображение упорядочивает состояния пациента, второе — применяемые операторы.

На множестве И(О) задано некоторое отношение эквивалентности р, порождающее фактор-множество Qp множества Q(O). С содержательной точки зрения это отношение разбивает множество всех примеров на классы эквивалентности по нозологическим формам; т. е. в каждом классе содержатся примеры по одной и тоже нозологической форме (разумеется относящиеся к различным пациентам).

Нашей ближайшей целью является поиск полного описания каждого из классов эквивалентности, т. е. таких описаний, что каждый элемент из Q(O) удовлетворял бы описанию одного из классов.

Иначе говоря, задача состоит в том, чтобы опираясь на множества примеров, входящих в классы эквивалентности по прямому разбиению р, построить такие описания G({cu}) каждого из классов эквивалентности {си}, что каждый пример си, входящий в некоторый класс эквивалентности {си}, удовлетворял бы описанию G({cu}) этого класса. Точный смысл этих понятий будет введён несколько позже; пока же можно сказать, что понятие описание класса эквивалентности соответствует некоторому общему описанию множества всех примеров.

Далее мы намерены показать, что построенные описания являются полными, т. е. всякий новый пример, не принадлежащий Q(O), но сохраняющий разбиение р (т. е. пополняющий один из классов эквивалентности {cu} 6 Qp), удовлетворяет описанию G({cu}) этого класса эквивалентности. Иначе говоря, если cu 6 0(0), cut 0(0) и отношение р на 0(0) U {сиД порождает то же фактор-множество, что и на 0(0), то найдётся класс эквивалентности {cu}p 6 Ор, такой что сщ| = G({cu}).

Другими словами, задача состоит в том, чтобы построить описания каждого из классов эквивалентности, такие что каждый новый пример, даже не использованный при построении описания, но оказавшийся в какой-то момент в системе, удовлетворял бы описанию одного из классов. Это свойство классов и означает полноту описания каждого из них. Заметим, что эту задачу можно трактовать как задачу распознавания образов в её алгебраической постановке [1].

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

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

Маршруты в потоках работ

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

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

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

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

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

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

Итеративный маршрут соответствует повторению некоторой подпоследовательности операторов, пока не будут выполнены определённые критерии.

Введём ещё один тип маршрута, который назовем конкурентным. Конкурентный маршрут возникает тогда, когда существует тройка операторов, порядок выполнения которых в некотором подмножестве примеров обладает зеркальной симметрией по отношению к опорному примеру. Этот маршрут напоминает параллельный, однако отличие состоит в том, что переставляемые операторы (лечебные мероприятия) не соседствуют — между ними находится некоторый «неподвижный» оператор.

Уточним теперь определения маршрутов.

Определение 4.1. Будем говорить, что опорный пример си, а также все примеры си^ , для которых rel(cu, cu^) = 1, т. е. совпадающие с опорным, порождают последовательный маршрут.

Граф маршрута:

...OjOkOq.

Определение 4.2. Если среди множества примеров некоторого класса эквивалентности {gu}p найдутся cui, CU2,..., cun — частичные прецеденты для опорного примера си = (..., Oj, Oj, 5, Ok, оп,...) из того же класса, такие что если 5 = (on,om^, то di = ... = 5п = (ош,оп), будем говорить, что примеры cu, cui, CU2, ..., cun порождают параллельный маршрут.

Граф маршрута:

Ojоп >- от >■ Ok

Определение 4.3. Если среди множества примеров некоторого класса эквивалентности {си}р найдутся cui,cu2,... ,cun — частичные прецеденты для опорного примера си из того же класса, такие что если 5 = (on,om,op) (5 С си), то ф = ... = = Зп = (ор,от,оп) (5i С cui,...,5n С сип), будем говорить, что примеры cu, cui, CU2,..., cun порождают конкурентный маршрут.

Граф маршрута:

Определение 4.4. Если среди множества примеров некоторого класса эквивалентности {си}р найдутся cui,cu2,... ,cun — частичные прецеденты для опорного примера си из того же класса, такие что 51 = ... = 5П — некоторая последовательность операторов, не совпадающих с операторами из 5 (5 С cu, 5i С С cui,...,5n С сип), и если примеры cui,cu2,... ,cun не порождают параллельного или конкурентного маршрута, то будем говорить, что они порождают условный маршрут.

Граф маршрута:

Oi ^ Oj ^ Я ^ 0к ^ Oq

^Р

Определение 4.5. Если среди множества примеров некоторого класса эквивалентности {са}р найдутся ц)\, ио о,..., шп^ такие что ф = ... = Зп = (одф+1,..., Oj+k,Oj) (di С иох,... ,6п С С сап), то будем говорить, что примеры сап6^2, ^п порождают итеративный маршрут (число j + к будем называть длиной маршрута).

Граф маршрута:

^ 0.^ о.^х ^ ...^ °j^k^ 0.^ о.^х ^ ...^ °j^k

^ 0.^ о.^х ^ ...^ °j^k

^ 0.^ о.^х ^ ...^ °j^k

Замечание 4.1. В определениях 4.3-4.5 вовсе не обязателен выбор одного и того же примера в качестве опорного. Действительно, если са и cai — различные опорные примеры, то они также породят некоторый маршрут. Поскольку далее будет показано, что описанными типами маршрутов исчерпываются все маршруты в графе описания класса эквивалентности, то в качестве опорного примера можно выбрать любой из примеров са или сап

Теперь перейдем к уточнению понятия описание класса эквивалентности. Поскольку, в соответствии с предъявляемыми к классам эквивалентности требованиями, каждый элемент Q(О) должен удовлетворять описанию одного из классов, то описание каждого класса должно содержать все маршруты, порождённые содержащимися в классе примерами.

Таким образом, описание G({ca}) каждого класса эквивалентности {са} 6 Qp уместно считать графом, содержащим в качестве подграфов маршруты, порождённые всеми примерами са 6 {са}.

Построение описаний классов эквивалентности

Ближайшая наша задача состоит в том, чтобы для каждого из классов эквивалентности {са} из Qp построить его описание G({ca}) в виде графа, пример которого приведён на рис. 4.1.

Рис. 4.1. Пример описания класса эквивалентности (вершины графа обозначены целыми числами)

При этом построенному описанию должны удовлетворять все элементы класса {си}.

Понятно теперь, что это последнее обстоятельство означает, что для каждого примера из из класса {си} в графе G({cu}) должен найтись эквивалентный ему подграф.

Замечание 4.2. Будем считать, что примеры, содержащиеся в классах эквивалентности, удовлетворяют принципу частичной прецедентности. Это означает, что мы «закрепляем концы» примеров. Действительно, с содержательной точки зрения, трудно представить пример, в котором переставлены первый оператор с последним. Немного найдётся клиник, где лечение больного начинается с его выписки из клиники, а завершение лечения — с регистрации в регистратуре.

Перейдем далее к представлению графов посредством их матриц инцидентности. На множестве матриц инцидентности введём ассоциативную и коммутативную операцию покомпонентного сложения, сохраняющую единицу:

если А = \aij\ и В = \Ьг^ — матрицы инцидентности, то А + В = [ау] + \М, где [ay] + [by] = = max([ay], [by]).

Например, для последовательности oi, оо,..., о^ такая матрица будет иметь вид а^ = «23 = ... = ctk™\,k = 1; все остальные её элементы равны нулю.

Тогда для класса эквивалентности, содержащего лишь последовательности вида ... Oi —> Oj —> 7Г Ок oq ..., т. е. множество примеров, порождающих последовательный маршрут (см. Определение 4.1), матрица инцидентности (с точностью до перестановок строк и столбцов) будет иметь такой же вид: Щ2 = П2з = ... = акм,к = 1; все остальные её элементы равны нулю.

Определение 4.6. Описанием G({cu}) каждого класса эквивалентности {си} будем называть такую матрицу М({си}), для которой матрица инцидентности каждого из графов маршрутов, порождённых примерами класса {си} является субматрицей. (Матрицу А = [щф будем называть субматрицей матрицы В = [Ь^], если для каждого а^ найдётся Ь^, такой что ajj = bigY

Корректность и полнота описаний классовэквивалентности

Пусть {М} — множество матриц инцидентности всех примеров класса {си} и только их. Через М^ио^ обозначим матрицу инцидентности графа примера си^ (в дальнейшем фразу матрица инцидентности графа примера и)3 будем заменять фразой матрица примера u)jY

Теорема 4.1. M({cu}) = ^j М(сиД, где суммирование в указанном выше смысле выполняется по всем примерам си7- из класса {си}.

Доказательство. Пусть си — опорный пример. Тогда, в соответствии с определением 4.1, он (и все примеры, ему эквивалентные) порождают последовательный маршрут. Если иных примеров нет, то М = М(си) и М(си) является субматрицей матрицы М.

Если cui — пример, порождающий (по отношению к опорному примеру) параллельный маршрут, то, с одной стороны, М = M(cu) + M(cui), с другой — матрица графа параллельного маршрута окажется субматрицей матрицы М. Легко видеть, что действуя таким образом и далее, можно доказать теорему полностью.

Из теоремы следует, что если некоторый пример сам по себе или в паре с опорным примером порождает некоторый маршрут в графе, то, с одной стороны, матрица этого примера является субматрицей описания класса, с другой — матрица инцидентности порождённого примером маршрута оказывается субматрицей матрицы описания класса. Эта теорема, по-существу, обосновывает корректность процедуры построения описания класса.

Покажем теперь, что какой бы мы ни взяли пример из класса, он порождает один из маршрутов, определённых выше. Пусть М(аз) — матрица описания некоторого класса эквивалентности {си}.

Теорема 4.2. Для любого си, если си 6 {си}, си| = М(си).

Доказательство. Пусть S — симметрическая группа, действующая на множестве операторов из О. Будем полагать, что на О задан линейный порядок, и обозначим множество О с линейным порядком через О. Выделим в S следующие подгруппы подстановок:

G1 — тождественная подгруппа, оставляющая все элементы на своих местах;

G2 — подгруппа транспозиций, действующая на множествах из двух смежных операторов (в смысле порядка, заданного на О) и меняющая их местами; остальные элементы остаются при этом неподвижными; подгруппа состоит из подстановок а = О^О^ и а™1 = O^jOp аа^ = а™1 а = 1;

G3 — подгруппа инверсий, меняющая местами два элемента Ощ1 и 0^+1 с неподвижным элементом Ор ст = О^/О^Мг/О^ Ю = О^/О^.ОЦОг,

G4 — подгруппа n-трансляций, заменяющая О^.^ на Ощц на Ощ9, ..., О^ок на Oi+G Ощ2А + 1 вновь заменяется на Ow, ..., Owk на 0^к и т.д. и раз;

G5 — условная подгруппа, действующая на фрагмент из попарно смежных операторов и заменяющая операторы этого фрагмента некоторыми иными операторами из О.

Понятно, что подстановки из тождественной подгруппы, будучи примененными к опорному примеру из {си}, порождают примеры, совпадающие с опорным. Иначе говоря,

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

Пусть теперь си — произвольный пример из класса {си}, и пусть в примере си найдётся фрагмент, отличающийся от соответствующего фрагмента опорного примера расположением какого-либо оператора о. Если си о = (..., о^ о^ 5, Ор, оп,.. ф си = ,Oi,Oj,6\,Ok,on,..ф где си о — опорный пример, 5 = = (on,om), di = (om,on), то понятно, что пример си может быть получен из сид применением подстановок из группы G2, т. е. примеры cuq и си порождают параллельный маршрут.

Если для тех же примеров 5 = (on, от, ор)5i = (op,om,on), то пример си может быть получен из cuq применением подстановок из группы G3, т. е. примеры cuq и си порождают конкурентный маршрут.

Если для тех же примеров 8 = (oj,Oj+i,... ,о3^ь°3^м\Ь 5i = (oj,Oj+i,..., оз+^, Oj+ф то пример си может быть получен из сид применением подстановок из группы G4, т. е. примеры cuq и си порождают итеративный маршрут.

Если примеры cu о и си таковы, что 51 не может быть получен из 5 применением подстановок групп G1™G4 и 5i ф 5, то необходимо применить подстановки условной подгруппы.

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

Следствие. Всякий новый пример, не принадлежащий Q(O), но сохраняющий разбиение р (т. е. пополняющий один из классов эквивалентности {cu} 6 flp^ удовлетворяет описанию одного из классов эквивалентности.

Построение описаний для классов примеровметодами конструктивной индукции

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

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

Среди существующих методов описания классов примеров важное место занимают методы так называемой конструктивной индукции. Основой этого метода являются примеры и некоторые базовые знания, а результатом является общее описание множества примеров. Как примеры, так и само общее описание описываются своими свойствами, которые отделяют их от других описаний. Методы конструктивной индукции направлены на создание таких структур символьных данных, преобразования которых, да и сами структуры легко интерпретируемы пользователем и удовлетворяют так называемому принципу воспринимаемости [32].

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

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

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

индуктивных методов машинного обучения, таких как алгоритм TDIDT [33] или AQ [34]. Один из таких алгоритмов, TDIDT, будет рассмотрен ниже.

Алгоритм TDIDT. Алгоритм TDIDT представляет собой классический вариант top-down индукции и основан на методе «разделяй и властвуй». Результатом работы алгоритма, т. е. описанием пространства примеров, является дерево решений. Дерево решений разделяет области пространства примеров на подобласти таким образом, что каждая вершина дерева соответствует при этом подобласти пространства примеров. Корень дерева соответствует всему пространству примеров. Его потомки делят пространство примеров на непересекающиеся области. Этот процесс применяется к каждому листу дерева. Каждый такой лист (т. е. вершина дерева) помечается меткой, которая обозначает множество примеров, принадлежащих соответствующей области. Каждая внутренняя вершина класса (т. е. вершина, не обозначающая ничего, кроме самой себя) соответствует какому-либо атрибуту.

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

Алгоритм построения новых ветвей. Пусть S — полное множество примеров (экземпляров) из некоторого класса эквивалентности. Далее операторы о из множества О будем называть элементами (примеров).

Шаг 1. Выполнить поиск «лучшего» элемента од

Шаг 2. Произвести расщепление множества S на подмножества Si, S2,..., Sn, так чтобы все примеры из подмножества Sj имели одинаковые элементы Oj.

Шаг 3. Для каждого множества Sp если все примеры в Sj принадлежат одному и тому же классу С^ (имеющему ту же метку класса), создать лист дерева решений и пометить меткой этого класса. Иначе перейти к 1, положив S = Sj. Алгоритм заканчивает работу, когда все подмножества помечены, либо отсутствуют элементы, разделяющие непомеченные множества.

Что же такое «лучший» элемент?

Лучшим элементом естественно считать такой элемент, на котором некоторая функция даёт лучшую оценку. Основное требование к такой функции — выбор элемента ot должен увеличивать (по сравнению с исходной ситуацией) информацию о классах, помечающих обучающие выборки при разбиении рассматриваемого множества S на подмножества S\, So,. • •, Sn в соответствии с элементом оц

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

Пусть рр — вероятность того, что случайно взятый из Sj пример есть Сд. Она может быть оценена относительной частотой

где п^ — число примеров Ср в Sj и rij — число классов в Sj. Энтропия (по Шеннону) подмножества Sj вычисляется по следующей формуле:

=х1п2Рр.

к

Пусть элемент ср расщепляет множество S примеров на подмножества Sj. Тогда энтропия семейства подмножеств Sj^ порождённых значениями од есть

НМ^Р^хН^),

3

где P(Sj) — вероятность принадлежности некоторого примера

8а и оценивается отношением мощностей подмножеств Sj к мощности S:

Увеличение информации при таком расщеплении происходит благодаря уменьшению энтропии:

IG(SA) = H(S)-H(SM

где H^S) есть априорная (до расщепления) энтропия S.

Таким образом, алгоритм TDIDT выглядит следующим образом.

Использовать значение энтропии для поиска оптимального расщепления для каждого элемента.

Определить такой элемент, расщепление посредством которого максимизирует энтропию при делении множества примеров на два подмножества.

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

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

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

Один из наиболее известных подходов к сокращению был разработан И. Братко [35]. И. Братко предложил отсекать ветви таким образом, чтобы минимизировать полную ожидаемую ошибку классификации на новых примерах. Для этой цели ошибка классификации подсчитывается для каждого узла в дереве. В листьях дерева для оценки ошибки используются методы теории вероятности. Например, можно использовать формулу Лапласа.

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

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

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

Глава 5

ПРОЦЕССЫ И МАРШРУТЫ В НИХ

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

Операторы и их применимость

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

Напомним, что операторы из О действуют из 2и в 2и, т. е. из множества всех подмножеств множества U в себя и из Р в Р, где U — некоторое непустое множество фактов (например множество замкнутых атомарных формул логического языка первого порядка), а Р — множество свойств (в частности, ими могут быть одноместные атомарные формулы языка первого порядка).

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

Например, парадоксальный пульс — падение систолического давления на вдохе более чем на 10 мм. рт. ст. — признак, имеющий количественный характер; симптом Ллойда — боль в пояснице при глубокой перкуссии над почками — признак, имеющий качественный характер. Тогда каждый оператор о имеет вид:

/ Ф \

где Ф — семейство функций времени {/ь А> • • • >/п} из F, действующих из декартовых степеней множества Pi в Рх [2]; Р^ — множество значений неколичественных признаков, появляющихся в результате действия оператора о.

Возможны два механизма действия оператора о.

о : Гй Гб. так что

оР^п) = Р^п) U Р2<Щ + 1), либо оР2^п) = р2(г1 + 1),

где Р2(п + 1) — множество значений неколичественных признаков, появляющихся в результате действия оператора о.

о : (Pxf Рр так что:

/а(Р1(^),Р2(^)>,PkW) = ра(п + 1),

/у(Р1(п),р2(п),...,р^(п)) =рр(п+ 1),

Л (Pl W > Р2 (и) , .. . , Рк И ) = рх (п + 1) ,

где fa,fp,...Jx £ ф-

Замечание. Два различных механизма действия оператора о, X := X U Y и X := У, соответствуют двум различным видам операторов присваивания — добавляющим новые элементы в множество и заменяющим элементы множества. С содержательной точки зрения, речь идёт либо о появлении в новом состоянии новых признаков при сохранении имеющихся, либо об исчезновении в новом состоянии старых признаков и появлении новых. В различных приложениях используются различные виды операторов присваивания.

Таким образом, если s(n) U Pi (77) U Po(ti) (где Р\ (??) = рх (n) U ^Р2^п) U ... Upk(n)) назвать состоянием S(n) процесса S(n), то oS(n) = S(n + 1), т. е. операторы из семейства О играют роль операторов переходов.

Условия операторов. Рассмотрим теперь, какие же условия требуется наложить на множество операторов, чтобы они могли в совокупности явиться основой некоторого лечебно-диагностического процесса. Введём вначале понятие условия оператора.

В параграфе 4.1 было введено отображение CON : О —> Р U U 2L\ так что CON(o) = con (где о е О), con 6 Р U 2и. В нашем случае con Е Р, т. е. CON(o) ставит в соответствие каждому оператору о из О некоторое подмножество множества признаков. Приведем два примера таких условий.

При исчезновении свистящих хрипов и при сохранении ПСВ >80% от лучших или должных не менее 4 часов продолжить прием ^-агонистов каждые 3 4 наса.

Здесь выделенный полужирным шрифтом фрагмент курсива является условием применения оператора прием [Зо-агонистов каждые 3-4 'ааса.

Остаются свистящие хрипы, ПСВ 60 - 80% от лучших или должных; продолжить ингаляции ^-агонистов в прежних дозах каждый час; преднизолон внутрь 30 мг; осмотр пульмонологом для коррекции базисной терапии.

Выделенная полужирным курсивом часть текста — условие применения оператора продолжить ингаляции Дгагонистов в прежних дозах каждый час; преднизолон внутрь 30 мг; осмотр пульмонологом для коррекции базисной терапии. Это подмножество признаков будем называть условием оператора о и обозначать через с либо с(о).

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

Определение 5.1. Оператор о будем называть применимым к состоянию S(n), если с (о) С S(n).

Определение 5.2. Последовательность

7Г =Цк,Окр

будем называть процессом, если для каждых двух её элементов (cn, оп), (cn+i, on+i) оператор о7г+1 применим к состоянию S(n).

Множество всех примеров процессов обозначим через П(О). Если 9 — отображение из Q(O) в П(О), так что

9^01,Oj,,ок\) = оХс7,оДД.оД

(т. е. отображение, сохраняющее порядок), то легко видеть, что 9 — изоморфизм относительно упорядочения, а П(О) и П(О) — изоморфно упорядоченные множества. Таким образом, ЩО) — семейство последовательностей вида

7Г =(Cfc.Ofc))-

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

Отсюда следует, что определения 4.1-4.6 и теоремы 4.1 и 4.2 очевидным образом переносятся на множества примеров процессов.

Свойства операторов и типы процессов

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

Условные и итеративные маршруты. Наиболее простыми оказались причины возникновения условных и итеративных маршрутов. Появление условных маршрутов связано с тем, что возможны близкие в некотором смысле состояния процессов, к которым применимы различные операторы с близкими условиями. Если на к-м шаге некоторого процесса формируется состояние S\k), отличающееся от состояния S(k), то вместо оператора о становится применимым оператор ок условие которого

выполнимо в состоянии S/k). Появление итеративных маршрутов связано с наличием в примерах процессов некоторого критерия (условия), выполнение (или невыполнение) которого требует повторения некоторой предшествующей последовательности операторов.

Приведём примеры критериев.

Системные кортикостероиды, если нет ответа на лечение или больной недавно принимал стероиды.

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

Продолжить терапию в течение 2-х часов, ожидая улучшения. При неполном ответе (ПСВ 50 70%, SpO^ < 90%, в/в кортикостероиды (преднизолон 90 мг, солюкортеф 100 200 мг), эуфиллин в/в кап (.мониторинг эуфиллина)). При отсутствии улучшения — перевод в ОРИТ.

Понятно, что речь идёт о повторении терапии при выраженном улучшении. Если улучшение отсутствует, то повторение терапии прекращается.

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

Определение 5.3. Суперпозицией O1O9 операторов Oi и 09 называется оператор

Оз = / Ц У

такой что Ф3 = Ф1 • Ф2, где Ф1 и Ф2 — компоненты операторов Ф и 09 соответственно; Ф2 • Ф1 — композиция этих компонент, а Р( = Р( U Р/ Pl = Р( U Р/

Легко видеть, что имеет место

Лемма 5.1. Суперпозиция О\О9 применима к некоторому состоянию 8(п/ если c(oi) С 8(п/ c(oq) С S(n) U (ФуР^'/г)) U U РДп + 1)) и определены функции ФУфУР^п))) (где c(oi) — условие Op c(oq) — условие со).

4 Г. И. Назаренко, Г. С. Осипов

Отсюда и из определения последовательной маршрутизации следует

Теорема 5.1. Если в некотором классе эквивалентности {тг}р множества П(О) найдутся примеры, на которых определены суперпозиции (... (oi е Оэ) • 03) е ... е оп) и только они, то эти примеры порождают последовательный маршрут в описании класса С({тг}р).

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

Обратим внимание на Определение 5.1. Можно заметить, что в операторе Оэ • Oi присутствует член Ф2 • Ф1, ограничивающий возможность перестановок операторов, — из существования Ф1 • Ф2 вовсе не следует существование Ф2 • Ф1. Таким образом, вообще говоря, перестановка операторов возможна тогда, когда наборы функций Ф1 и Ф2 (которые можно рассматривать как векторы) ортогональны (будем записывать это Ф2 • Ф1 = 0) и разбивают множество признаков Pi на два непересекающихся подмножества. Далее, признаки, на которых определены как функции из Ф2, так и функции из Ф1, должны присутствовать в состоянии, к которому применяется суперпозиция. И, наконец, признаки очередного состояния, полученные с помощью применения семейства функций Ф1, не должны являться аргументами функций из семейства Ф2 и обратно. Это свойство пространства признаков будем называть сепарабельностью пространства признаков относительно операторов Оо и Оц

Вторым условием применимости операции суперпозиции является выполнение условий обоих операторов в одном и том же состоянии, т. е. если с(1) С S(n), то и с(2) С S(n). Это свойство ранее было названо применимостью. Сепарабельность пространства признаков относительно операторов Оэ и сц вместе с применимостью последних являются необходимыми и достаточными условиями коммутативности операторов Оо и Оц

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

При железодефицитной анемии на стационарном этапе лечения требуется выполнять

ежедневный пероральный прием препаратов Ее, ежедневное парентеральное (в/м) введение Ее, при этом порядок, выполнения лечебных .мероприятий не имеет существенного значения.

Изложенные соображения резюмирует следующая теорема.

Теорема 5.2. Если в некотором классе эквивалентности {тг}р множества П(О) найдутся примеры, на которых определены суперпозиции (... (<щ • 02) • 03)•...• оп), и для некоторых операторов О{ и Oj из этих примеров выполняются необходимые и достаточные условия коммутативности, то эти примеры порождают параллельный маршрут в описании класса С({тг}р).

Рассмотрим теперь, при каких условиях возможна конкурентная маршрутизация процессов. Пусть Ор Оэ и 03 — операторы, для которых имеет место

(О1 ео2) *о3) = (о3 • (о2 *О1)).

Это означает, что пространство признаков сепарабельно относительно операторов <щ и Оэ и операторов о1 и 03, где о1 = oi • Оэ. Можно показать, что и в этом случае пространство признаков сепарабельно относительно операторов Ор Оэ и 03.

Теорема 5.3. Если в некотором классе эквивалентности {тг}р множества П(О) найдутся примеры, на которых определены суперпозиции (... (сц • 02) • 03)•...• оп), и для некоторых операторов О;, Oj и о^ из этих примеров выполняются необходимые и достаточные условия попарной коммутативности, то эти примеры порождают конкурентный маршрут в описании класса

Таким образом, равенство нулю мультипликативного члена (разумеется вместе с применимостью операторов) позволяет применять в любом порядке (и даже одновременно) операторы Oi и Оэ и соответствующие им действия. Напротив, Ф1 • Ф2 ^ О означает, что действия, представляемые оператором Оэ, можно применять только после появления признаков, являющихся аргументами оператора Оэ в результате применения к некоторому состоянию S(n) действий, представленных оператором Ор

Глава 6

ВЫЯВЛЕНИЕ ПОТОКОВ РАБОТ ПОПРИМЕРАМ

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

В этой главе будут рассмотрены методы и основные процедуры обнаружения потоков работ в данных.

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

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

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

Процесс построения последовательности работ (в дальнейшем экземпляра) для текущего пациента включает следующие шаги.

Шаг 1. Прочитать об очередном лечебном мероприятии в базе данных.

Шаг 2. Если мероприятие проводилось ранее, то попытаться построить итеративный маршрут.

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

Шаг 4. Если итеративный маршрут не построен или лечебное мероприятие ранее не проводилось, то добавить лечебное мероприятие в текущий экземпляр.

Шаг 5. Перейти к шагу 1.

Разбиение экземпляров на классы и ихкластеризация

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

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

геЦтг], тг2) = ДрА Д, тг2)рДеп-тг2)),

Tri и л 2 — экземпляры, a eiеп — элементы лц Положим

{

1, если вг G Л2

0, если Л2,

а ф — линейная комбинация рг (г 6 {1,... щ}), нормированная на единицу; т. е.

Ге1(7Г1,7Г2) =

г

Здесь следует обратить внимание на то, что при вычислении релевантности принимается во внимание близость множеств элементов (или, иначе, лечебно-диагностических мероприятий) в сравниваемых экземплярах (последовательностях работ) и не принимается во внимание порядок элементов.

В практических экспериментах мы полагали, что два экземпляра Л1 и л2 релевантны, если ге1(лцЛ2) ^ 0,8. В этом случае они включаются в один кластер. Если текущий пример оказался таков, что для него геЦлц Л2) < 0,8, то создаётся новый кластер,

куда записывается текущий экземпляр; созданный кластер добавляется в список кластеров. Эта процедура выполняется в том случае, когда в базе данных созданы экземпляры для всех пациентов. Соответствующий алгоритм описан в Приложении 1.

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

То обстоятельство, что два элемента принадлежат отношению строгого линейного порядка, будем иногда обозначать символом «^». Параллельную маршрутизацию будем обозначать символом «^—>». Условная маршрутизация обозначается символом «П»- Итеративная маршрутизация, т. е. то обстоятельство, что последовательность элементов повторяется до выполнения некоторого критерия, например Kt, будет записываться следующим образом: (...) Kt, где в скобках — повторяемая последовательность операций, a Kt — критерий окончания повторения.

Медицинский технологический процесс в общем виде тогда может быть представлен следующим образом:

Ex Е2Еп,

где Е^ — этапы технологического процесса (г = 1,2,..., 7г).

Извлечение параллельных потоков

Параллельные маршруты в общем описании потока работ появляются в случае наличия транспозиции лечебных мероприятий в различных экземплярах. Например:

При синтезе обеих последовательностей строится параллельный маршрут следующего вида:

или в виде графа, в вершинах которого находятся операторы:

ОщОщОкОкОтОтOnOn

Ощ

Ощ

Ок

Ок

От

От

On

On

Извлечение итеративных потоков

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

При синтезе общего описания МТИ проверяется, для скольких пациентов построенна данная итерация. Если это число пациентов составит более 30% от общего числа пациентов, то итерация сохраняется, иначе нет.

Извлечение конкурентных потоков

Конкурентные потоки появляются в случае синтеза следующих экземпляров последовательностей работ:

(еде13е12),

(е12е13ед).

Представим синтез обеих последовательностей следующим образом:

[(ед > е12)е13].

На языке операторных графов конструкция выглядит следующим образом:

Ор >- от >- оп

Извлечение условных потоков

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

Заводится необходимый объект сои для построения условного перехода.

Находится лечебное мероприятие, начиная с которого общее описание МТП и экземпляр МТП текущего пациента совпадают. Назовем такое лечебное мероприятие точкой слияния.

В соответствующее поле объекта con записывается прочитанный элемент из общего описания МТП и все элементы, находящиеся между прочитанным элементом и точкой слияния.

В следующее поле объекта con записывается прочитанный элемент из экземпляра МТП текущего пациента и всё, что находится между прочитанным элементом и точкой пересечения.

Например:

(еи е13е12),

(ед -ч ейе12).

Результатом синтеза двух последовательностей будет конструкции следующего вида:

[ед (е13 П еп) е12], или в виде графа операторов:

Ог ^ Оз ^ 7Г ^ Ок ^ Oq

Некоторые замечания об оптимизации медицинских технологических процессов

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

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

Рассмотрим два процесса — Пт иП2, использующие общие ресурсы (приборы, оборудование, персонал) гх и г 2 соответственно.

П1 = епе12ein,

П2 = e2iе22е2т.

Пусть также rx(i,j) и r2(z,j) — затраты (например времени) при выполнении работы (ц j) с использованием ресурса гх и г2 соответственно. Требуется найти оптимальный план прохождения процессов через систему, минимизирующий общее время исполнения всех лечебных мероприятий Щд

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

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

Для двух мероприятий ец- и е2д выполняемых с использованием одного и того же ресурса гх вначале выполняется мероприятие, для которого гДцД = min(ri(l, j^n^, j)). Если это, например, мероприятие ец-, то затем выполняется сдвиг «хвоста» процесса П2 на гДЕ j) единиц и выполняется мероприятие e2j. Далее выбираются j + 1 мероприятия и процесс повторяется. При этом следует заботиться о том, чтобы ресурс 1 не простаивал.

Если два мероприятия ец- и 62j выполняются с использованием различных ресурсов, то они начинаются одновременно, при этом более длительное мероприятие обладает

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

Таким образом, следующий алгоритм А является оптимальным.

Шаг 1. Если ец- — текущее мероприятие процесса Пц a ед,; — текущее мероприятие процесса П2, и для их выполнения требуется один и тот же ресурс щ, то

Шаг 2. Выполняется мероприятие, для которого rx(i,j) = = min(ri(l J),ri(2J)).

Выполняется сдвиг оставшейся части процесса П2 на TxQiJ) единиц.

Выбираются j + 1 мероприятия, j := j + 1, переход к шагу 1.

Шаг 3. Иначе ец- и e^j начинаются одновременно; j := j + 1, переход к шагу 1.

Если все мероприятия исчерпаны, то алгоритм завершает работу.

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

Алгоритм А1. Рассматривается лишь фрагмент Щ с параллельной маршрутизацией и соответствующий ему фрагмент Пр

Шаг 1. Если eij — текущее мероприятие процесса Пу а е^ — текущее мероприятие процесса П2, и для их выполнения требуется один и тот же ресурс п, то

Шаг 2. Если для выполнения мероприятия e2?(j+i) процесса П2 требуется ресурс п, то выполняется инверсия е^ и е2?у+1у переход к шагу 4.

Шаг 3. Иначе выполняется мероприятие, для которого T\Vkp = min(ri(l, р,п(2,ру

Выполняется сдвиг оставшейся части процесса Щ на rx(ij) единиц.

Выбираются j + 1 мероприятия, j := 3 + 1, переход к шагу 1.

Шаг 4. Иначе exj и е^ начинаются одновременно; j := j + 1, переход к шагу 1.

Если все мероприятия исчерпаны, то алгоритм завершает работу.

П1 и П2 имеют параллельную маршрутизацию.

В этом случае можно использовать возможности оптимизации за счёт изменения порядка выполнения мероприятий на параллельных фрагментах процессов П) и П2.

Алгоритм А2. Рассматриваются лишь фрагменты Щ и П2 с параллельной маршрутизацией.

Шаг 1. Если exj и еру+р — текущие мероприятия фрагмента процесса П1 с параллельной маршрутизацией, требующие ресурса п, то

Шаг 2. Упорядочить мероприятия, переместив вперед е такое, для которого гх = min(ri(l,^фгфЕ j + 1)); иначе exj и еру+р начинаются одновременно; j := 3 + 1, переход к шагу 1.

Шаг 3. Если е — текущее мероприятие процесса Пр е2у — текущее мероприятие процесса П2, то, если для их выполнения требуется один и тот же ресурс и, то

Шаг 4. Упорядочить мероприятия, переместив вперед ei такое, что гх(вх) = min(ri (е), щ (e2j)); иначе е и е2у начинаются одновременно; j := j + 1, переход к шагу 1.

Шаг 5. Если для выполнения мероприятия е2 ^+р процесса П2 требуется ресурс п, то упорядочить мероприятия, переместив вперед е2 такое, что пЮ) = min(ri(ei),ri(e2i(j+1))); иначе в] и е2>у+1) начинаются одновременно; j := j + 2, переход к шагу 1.

Если все мероприятия исчерпаны, то алгоритм завершает работу.

Общий случай. Рассмотрим две рабочие последовательности, представляющие процессы с определёнными порядками выполнения лечебных мероприятий:

Ш = (оьо2О^1)

и

= <91-929ml 1 < п < m;

здесь ои Qj — операторы, представляющие лечебные мероприятия, г 6 (1,2n), j Е (1,2т).

Две рабочие последовательности назовем эквивалентными, если и только если их исполнение при любых одинаковых входах приводит к одинаковым результатам. Процессы си и cu i могут включать одинаковые операции, для выполнения которых могут использоваться общие ресурсы.

Введём тождественный оператор е, обладающий следующими свойствами: для любых операторов од и q^ процессов си и cut имеет место ощ ео^ о^ и qje eqj qj. Эта запись определяет отсутствие временного совмещения операций. Предполагается также, что количество ресурсов, реализующих тождественный оператор, не ограничено.

Оператор вида (cd), реализация которого заключается в одновременном выполнении операций end, назовем составным оператором. По определению полагаем (cd) = (de). С помощью введённых операторов можно записать следующие последовательности, называемые системами локальных процессов:

CCU1 = (oie)(o/re)(o/r+i</i)(оmQm--k^ (^Qm—k-X-XP-.^qn).

m — n + 1 ^ k ^ m — 1;

cu>2 = Де)... Де)(oHvh) • • • (oHnqP(ofc+n+ie) ... (ome),

0 k m — п;

сш3 = (eqxp.. (eq_kpoiq_k+iP.. (on+kqP(on+w^^ ...(ome),

1 — n ^ k ^ — 1.

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

Величина к, называемая сдвигом в системе локальных процессов си и cu i, равна числу тактов, на которое начало цикла процесса си опережает, при к > 0, или отстает, при к < 0, от начала цикла процесса сид

Если в системе локальных процессов указать закреплённые за операциями ресурсы, то получится система отмеченных локальных процессов сУ, оф, которая является допустимой только при выполнении следующих условий:

выполнение локальных процессов происходит без прерываний;

время выполнения всех операторов одинаково;

составные операторы не содержат одинаковых ресурсов.

В случае нарушения 2-го условия операция разбивается на элементарные промежутки времени (такты). Например, запись ио* = о1 о1 о1 и В* = g2g2 может означать 3 такта использования 1-го ресурса типа о и 2 такта использования 2-го ресурса типа q при условии равенства самих тактов. Заметим также, что если в системе находится только по одному ресурсу каждого типа, то верхние индексы можно опустить и формальная запись отмеченных локальных процессов совпадет с записью локальных процессов.

В дальнейшем ограничимся рассмотрением систем из 2-х локальных процессов. Каждому варианту системы отмеченных локальных процессов поставим в соответствие множество Нх(сио*) запрещенных сдвигов процесса ио* относительно процесса иф в прямом направлении (например вправо), а также множество сдвигов Н^сио*) — в противоположном направлении (влево). Здесь ЯфсиЛ) — множество сдвигов фаз, образуемых между фазами закрепления одноименных ресурсов, принадлежащих разным ОЛП (ио* и иф) и отсчитываемых с учётом выбранного направления сдвига. Понятно, что если за каждым оператором системы закреплены непересекающиеся множества ресурсов, то Н^(сио*) = 0, в противном случае Н^сио*) зависит от варианта взаимного упорядочения отмеченных локальных процессов.

Множествам запрещенных сдвигов поставим в соответствие множества разрешенных сдвигов Gt (си;*) и G^cuo*). Зафиксировав разрешенный сдвиг, можно определить формальные параметры полученной системы ЛП.

Будем рассматривать системы ЛП, отвечающие требованиям одного из видов параллелизма:

параллелизма множества объектов;

параллелизма независимых ветвей.

Уточним эти определения и изучим особенности составления расписаний для технологического процесса, принимая за критерий качества время реализации системы ЛП, обозначаемое t(cuo*Y

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

Системы локальных процессов являются идентичными, т. е. состоят из одних и тех же операций, выполняемых в одинаковом для всех ЛП порядке.

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

Порядок закрепления ресурсов за операциями одинаков для всех ОЛП.

Пусть технологический процесс реализует систему из 2-х одинаковых локальных процессов, состоящих из т операций. Всего имеется S ресурсов заданного состава, т. е. известны величины s^ г = 1,... J (st — количество ресурсов Тго типа, S = Y^^Y Требуется построить расписание технологического процесса, минимизирующее величину £(сси*) при выполнении перечисленных выше требований и использовании всех ресурсов. С учётом сказанного, задача составления оптимального распределения ресурсов формулируется следующим образом. Пусть g’1 и g2 — минимальные элементы множеств Gi(cu;*) и G2(ccu*) соответственно, тогда: £(ccu*) = т + min(g1,g2).

Рассмотрим в качестве примера следующую систему из двух ЛП при минимально необходимом количестве ресурсов каждого типа:

Л* = а а b с b с а а, В* = a a b c b с а а;

множество запрещенных сдвигов:

ЯфсЛ*) = Я2(сЛ*) = {О, 1, 2, 6, 7};

множество разрешенных сдвигов:

(Л(сЛ*) = О2(сЛ*) = {3,4,5,8}.

Таким образом, выполняем сдвиг ЛП Л* на 3 такта в любую сторону, причём /"(сЛ*) = 8 + 3 = 11.

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

локальные процессы (ветви) отличаются составом или порядком выполнения операций;

отмеченные локальные процессы отличаются порядком закрепления ресурсов за операциями ЛП.

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

Л* = a a b с b с a a, B* = caacbcb.

В этом случае получаем множество запрещенных сдвигов:

ЯДЛ*) = {0, 1,2,4}, Я2(сХ) = {0,2,4,5,6};

множество разрешенных сдвигов:

О](сЛ*) = {3,5}, G2(cT) = {1,3,7}.

Выбираем сдвиг влево на 1 такт, при этом общее время выполнения двух ЛП /(сЛ*) = 8.

Параллелизм смежных операций. Будем говорить, что система из трёх локальных процессов СЩ, и^ ^з отвечает требованиям параллелизма смежных операций, если входы сщ и си 2 являются независимыми, а выходы служат входами CU3. В этом случае все виды расписаний могут быть получены приписыванием CU3 к одному из процессов CU] или CU2 справа. Результаты приписывания обозначим соответственно си уз; си2д. Таким образом, достаточно рассмотреть систему из двух ОЛП при определённом ограничении на направления сдвигов, а именно си уз сдвигается относительно CU2 (вправо), a cui относительно ^2,3 влево.

Заключение

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

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

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

Исследованы условия порождения тех или иных экземпляров лечебно-диагностического процесса по описаниям классов. Разработаны алгоритмы и экспериментальные программные средства извлечения описаний лечебно-диагностических процессов из данных и построения описаний классов медицинских технологических процессов. Материалы книги являются теоретической основой систем мониторинга лечебно-диагностических процессов и управления ими в режиме реального времени.

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

Заключение113

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

Материалы монографии могут найти применение в исследовании причин отклонений реальных состояний пациентов от теоретических, в разработке методов корректировки последовательностей лечебно-диагностических мероприятий и методов синтеза экземпляров лечебно-диагностического процесса, как на основе описаний классов медицинских технологических процессов по нозологическим формам, так и на основе учёта индивидуальных особенностей пациентов.

Список литературы

Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики, вып. 33.— М.: Наука, 1978.'

Назаренко Г. И., Осанов Г. С. Основы теории медицинских технологических процессов. Часть 1. — М.: Физматлит, 2005.

Нестеренко А. К., Бездушный А. А., Сысоев Т. М. и др. Служба управления потоками работ по манипулированию ресурсами репозитория // Электронные библиотеки. 2003. Т. 6, вып. 5.

Журавлев Ю. И. Непараметрические задачи распознавания образов // Кибернетика. 1976, №6.

Теория расписаний и вычислительные машины / Под ред. Э.Г. Коффмана. — М.: Наука, 1984. — 336 с.

Танаев В. С., Шкурба В. В. Введение в теорию расписаний. — М.: Наука, 1975. — 256 с.

Конвей Р.В. Теория расписаний / Пер. с англ. Р.В. Конвей, В.Л. Максвелл, Л.В. Миллер — М.: Наука, Гл. ред. физ.-мат. лит., 1975. - 359 с.’

Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. — М.: Мир, 1981. — 368 с.

Хачумов В. М., Юмагулов М. Г. Об оптимизации метода совмещения вычислительных процессов в специализированных устройствах // Управление в сложных нелинейных системах. — М.: Наука, 1984. — С. 148-152.’

Кудрявцев Е. М. Исследование операций в задачах, алгоритмах и программах. — М.: Радио и связь, 1984. — 184 с.

Саати Г. А. Элементы теории массового обслуживания и её приложения. — М.: Советское радио, 1971. — 520 с.

Федосин С. А. Практикум по GPSS/PS. — Саранск, 2001.

Быков С. П., Храмов А. А. Разработка моделей в системе моделирования GPSS. - М.: МИФИ, 1998.

Слепцов А. И., Юрасов А. А. Автоматизация проектирования управляющих систем гибких автоматизированных производств / Под ред. В.Н. Малиновского. — К.: Техшка, 1986. — ПО с.

Методы параллельного микропрограммирования / Под ред. О.Л. Банд- ман — Новосибирск: Наука, 1981. — 180 с.

Котов В. Е. Сети Петри. — М.: Наука, 1984. — 160 с.

Питерсон Дснс. Теория сетей Петри и моделирования систем. — М.: Мир, 1984. — 264 с.

Ломазова И. А. Вложенные сети Петри: моделирование и анализ распределённых систем с объектной структурой. — М.: Научный мир, 2004. - 208 с.’’’

Каган Б. М. Электронные вычислительные машины и системы. — М.: Энергия, 1979. — 528 с.

Бауэр В. Введение в теорию конечных автоматов. — М.: Радио и связь, 1987.

Глушков В. М. Синтез цифровых автоматов. — М.: Физматгиз, 1962.

Монахов В. М., Беляева Э. С., Краснер Н. Я. Методы оптимизации. Применение математических методов в экономике. — М.: Просвещение, 1978.

Акулич И. Л. Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с.

Автоматизированное управление технологическими процессами: Учебное пособие/ Под ред. В.Б. Яковлева — Л.: Изд-во Ленингр. ун-та, 1988. — 224 с.’

Монахова Е., Бочкарев Л., Лукомский Л., Майоров А. Управление потоком работ. Rondo integrale de universale. Final, http:// www.russianenterprisesolutions.coni/mana/01 / 051 .html

BPML working draft March 25, 2002. http://www.bpmi.org/xnil. coverpages.org/bpnil.htnil

Хачумов В. M., Ксенофонтова Е. В. Образный анализ и диагностика сложных процессов // Доклады 11-й Всероссийской конференции “Математические методы распознавания образов” (ММРО-11, 23-29 ноября 2003 г., Пущино). — М.:, 2003. — С. 201-204.

Амелькин С. Л., Хачумов В. М. Обобщённое расстояние Ев- клида-Махаланобиса и его применение в задачах распознавания образов // Доклады 12-ой Всероссийской конференции “Математические методы распознавания образов” (20-26 ноября 2005 г.) — М.: МАКС Пресс, 2005. - С. 7-9.

Shapiro Robert A Comparison of XPDL, BPML and BPEL4WS. http://xnil.coverpages.org/Shapiro-XPDL.pdf

Маклаков С. Инструментальные средства создания корпоративных информационных систем // Компьютер Пресс. 1998. No 7-9.

Бездушный А. Н., Житсченко А. Б., Кулагин М. В., Серебряков В. А. Интегрированная система информационных ресурсов РАН и технология разработки цифровых библиотек / / Программирование. 2000. Т. 26, № 4. С. 177-185.' '

Марка Д. А., МакГоуэн К. Методология структурного анализа и проектирования SADT (Structured Analysis & Design Technique). — SofTecb, 1986. — http://asu.pstu.ac.ru/book/cadt/default.html

MedTrak. Система управления госпиталем, http://stariks.narod.ru/ Med _ Systems/MedTrak/MedTrak.htm

Michalski R. S. A theory and methodology of inductive learning // Machine Learning: An Artificial Intelligence Approach / Под ред. R.S. Michalski, J.G. Carbonell, T.S. Mitchell — Los Altos, CA: Morgan Kaufmann Publ. 1983. - V. I. P. 83-134.

Qinlan R. C4.5 Program for Machine Learning. — San Mateo: Morgan Kaufman Publ., 1993.

Michalski R. S., Mozetic I., Hong J., Lavrac N. The Multi-Purpose Incremental Learning System AQ15 and its Testing Application to Three Medical Domains // Proceedings of AAAI-86, Philadelphia, PA, 1986. — P. 1041-1045.' '

Jakulin A., Bratko I., Smrke D., Demsar J., Zupan B. Attribute Interactions in Medical Data Analysis / / Proceedings 9th Conference on Artificial Intelligence in Medicine in Europe (AIME 2003), Protaras, Cyprus / Под ред. M. Dojat, E. Keravnou P. Barahona. — P. 229-238

Приложение 1

Метод разбиения множества рабочихпоследовательностей на классы эквивалентности

В методе разбиения множества последовательностей работ (операторов) на классы эквивалентности используется структура данных MTPClass. Единственным полем данной структуры является массив экземпляров МТП, принадлежащих одному классу (для одной нозологической формы).

Опишем соответствующий алгоритм.

MTPClass

{

patients; // массив объектов Patient, у которых их частные МТИ совпадают

}

В структуру Place (она описана в алгоритме синтеза общего МТП) добавляется поле mtpclasses — массив классов похожих частных МТП.

Опишем процедуру разбиения на классы

DivideOnClassesO :

выбирается очередной пациент patient из списка patients;

если массив mtpclasses пуст, то создаётся объект mclass типа MTPClass, в mclass записывается patient, mclass добавляется в массив mtpclasses, переход к шагу 1;

count=0 — число совпадений;

ccount=0 — число совпадений в итерациях;

выбирается очередной объект mcl из массива mtpclasses;

выбирается первый пациент patient 1 из списка patients объекта mcl;

выбирается очередной блок block 1 из массива mmtp объекта patient;

выбирается очередной блок Ъ1оск2 из массива mmtp объекта patientl;

если blockl имеет тип Element, то:

если Ь1оск2 имеет тип Element, то:

если bockl=block2, то count=count+l, переход к шагу 6;

иначе переход к шагу 6;

если Ь1оск2 имеет тип Iteration, то:

выбирается очередной элемент el из списка blocks объекта Ь1оск2;

если blockl имеет тип Element, то:

если blockl=el, то ccount=ccount+l, переход к шагу 19;

иначе переход к шагу 19;

если blockl имеет тип Iteration, то переход к шагу 19;

выбирается очередной блок blockl из массива mmtp объекта patient;

переход к шагу 14;

если ccount составляет не менее 80% от общего числа blocks в итерации, то count=count+l, ccount=0, переход к шагу 6;

иначе ccount=0, переход к шагу 6;

если blockl имеет тип Iteration, то:

если Ь1оск2 имеет тип Element, то:

выбирается очередной элемент el из списка;

если Ь1оск2 имеет тип Element, то:

если Ь1оск2=е1, то ccount=ccount+l, переход к шагу 30;

иначе переход к шагу 30;

если Ь1оск2 имеет тип Iteration, то переход к шагу 30;

выбирается очередной блок Ь1оск2 из массива mmtp объекта pat i ent 1;

переход к шагу 25;

если значение ccount составляет не менее 80% от длины blocks объекта blockl, то count=count+l, ccount=0, переход к шагу 6;

иначе ccount=0, переход к шагу 6;

если Ь1оск2 имеет тип Iteration, то:

ввхбирается очередной элемент ell из списка blocks объекта blockl;

ввхбирается очередной элемент е12 из списка blocks объекта Ь1оск2;

если е11=е12, то ccount=ccount+l, переход к шагу 35;

иначе переход к шагу 35;

если значение ccount составляет не менее 80% от длинвх blocks объекта blockl, то count=count+l, ccount=0, переход к шагу 6;

иначе ccount=0, переход к шагу 6;

если значение count составляет не менее 80% от общего длины массива mmtp объекта patient, то patient 1 добавляется в mcl, переход к шагу 1;

иначе создаётся объект mclass типа MTPClass, в mclass добавляется patient 1, mlcass добавляется в список mtpclasses, переход к шагу 1.

Процедура закончит свою работу в тот момент, когда она обработает все экземпляры МТП пациентов в текущем медицинском подразделении. После её выполнения все экземпляры МТП будут разбиты на классы совпадения экземпляров МТП.

Приложение 2

Основные процедуры извлечения рабочихпоследовательностей из данных

Процедура Equal (проверяет равенство двух объектов):

Equal(objеct1,object2)

begin

если objl = obj2 то return true иначе return false

end

Процедура Concurrent (строит объект типа Concurrent):

Concurrent(cMTP[cgindex] ,cMTP [cgindex+1] , cMTP[cgindex+2],concurrent) begin

добавляется в поле union.first объект cMTP[cgindex] добавляется в поле union.first объект cMTP[cgindex+2] union.second=cMTP[cgindex+1]

end

Процедура add (добавляет объект в результирующий массив):

add (object)

begin добавляется объект object в result end

Процедура augment er (увеличивает index на число, равное count):

augmenter (index,count)

begin

index=index+count;

end

Работа процедуры make_parallel (строит объект типа Parallel) зависит от входных параметров:

make_parallel(cMTP[cgindex],cMTP[cgindex+1],parallel) begin

добавляется cMTP[cgindex] в список left объекта parallel

добавляется cMTP[cgindex+1]

в список right объекта parallel end

make_parallel(cMTP[cgindex],cMTP[cgindex+1], pMTP[index+2],parallel)

begin

добавляется cMTP [cgindex]

в список left объекта parallel

добавляется cMTP[cgindex+1]

в список right объекта parallel

добавляется pMTP[index+2]

в список right объекта parallel

end

make_parallel(cMTP}[cgindex],cMTP[cgindex+1], cMTP [cindex+2],parallel)

begin

добавляется cMTP[cgindex]

в список left объекта parallel

добавляется pMTP[cindex+2]

в список left объекта parallel

добавляется cMTP[cgindex+1]

в список right объекта parallel} end

make_parallel(cMTP[cgindex],cMTP[cgindex+1],

cMTP [cindex+2],pMTP[index+2],parallel) begin

добавляется cMTP[cgindex]

в список left объекта parallel

добавляется pMTP[cindex+2]

в список left объекта parallel

добавляется cMTP[cgindex+1]

в список right объекта parallel

добавляется pMTP[index+2]

в список right объекта parallel}

end

Процедура make_condition (строит объект типа Condition). Входные параметры:

cMTP — общий МТП;

рМТР — МТП текущего экземпляра класса Patient;

condition — объект Condition;

cind — выходной параметр, указывающий с какой позиции в общем МТП удалось найти одинаковое продолжение общего МТП и МТП текущего экземпляра класса Patient после условного перехода;

pind — выходной параметр, указывающий с какой позиции в МТП текщего экземпляра класса Patient удалосв найти одинаковое продолжение общего МТП и МТП текущего экземпляра класса Patient после условного перехода;

cgindex — указывает, с какой позиции в общем МТП начинается условный переход;

index — указывает, с какой позиции в МТП текущего экземпляра класса Patient начинается условный переход.

make_condition(cMTP,pMTP,condition,cind,pind, cgindex,index)

begin

arr [] ;

b;

b=search(cMTP,pMTP,cind,pind,cgindex,index);

если b=true to

begin

for (i=cgindex; Kcind; i++) arr[i-cgindex]=cMTP [i] ;

массив arr добавляется

в поле list объекта condition;

for (i=index; Kcind; i++)

arr [i-index]=pMTP[i] ;

массив arr добавляется

в поле list объекта condition;

end

иначе

begin

если экземпляр класса Patient нужно добавить в список t_patients, то добавляем текущий экземпляр класса Patient в список t_patients

иначе

begin

for (i=cgindex; Кдлина cMTP; i++) arr[i-cgindex]=сМТР [i] ;

массив arr добавляется

в поле list объекта condition

for (i=index; Кдлина pMTP; i++) arr [i-index]=pMTP[i] ;

массив arr добавляется

в поле list объекта condition end

end

end

Процедура search ищет место, начиная с которого общий МТП и экземпляр МТП текущего экземпляра класса Patient совпадают.

search(cMTP,рМТР,сind,pind,cgindex,index)

begin

res false;

for (i=cgindex; Кдлина cMTP; i++)

begin

for (j=index; дСдлина pMTP; j++)

begin

если cMTP[i] имеет тип Element то

begin

если cMTP [i]=pMTP[j]

begin

res=true;

break; // выход из цикла no j end

end

иначе

begin

если cMTP[i] имеет тип Iteration то

begin

res=search(cMTP[i].blocks,pMTP,cind,pind,0,j);

если res=true to break;

end

если cMTP[i] имеет тип Parallel то

begin

res=search(cMTP[i].left,pMTP,cind,pind,0,j);

если res=true to break;

иначе

begin

res=search(cMTP[i].right,pMTP,cind,pind,0,j); если res=true to break;

end

end

если cMTP[i] имеет тип Condition то

begin

for (h=0; Ь<длина cMTP [i].list; h++)

begin

res=search(cMTP[i].list[h],pMTP,cind, pind,0,j);

если res=true to break;

end

если res = true to break;

end

end

end

если res = true to

begin

cind=i;

pind=j;

return true;

end

end

return false;

end

Приложение 3

Алгоритм синтеза общего описания потоков работ

Задачей алгоритма является построение всевозможных маршрутов (потоков работ) на основе анализа экземпляров медицинских технологических процессов (МТП) конкретных пациентов. Алгоритм состоит из двух фрагментов: построение экземпляров МТП для пациентов и синтез общего описания потоков работ по каждой нозологической форме.

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

Построение экземпляров МТП

Каждый из этапов является структурированным множеством элементов. Например, для этапа Ei оно может иметь вид

[еп -> е12(е13 <—> ей) (е15 Ц. е16)].

Здесь у каждого элемента первый нижний индекс означает номер этапа, второй — номер в этапе.

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

В качестве этапов технологического процесса будем рассматривать места лечения больных. Опишем некоторые структуры, используемые в алгоритме. Разобьём этап технологического процесса на несколько блоков, где в качестве блока может выступать либо просто элемент е^, либо параллельная, либо условная, либо итеративная, либо конкурентная маршрутизация.

Тогда в записи можно выделить 4 блока:

еп;

е12;

Юз <—> ем);

Юб П еД.

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

В алгоритме используются следующие структуры данных:

Patient — структура используется для хранения данных о пациенте и МТП данного пациента.

Place — структура используется для хранения результатов синтеза общего МТП, процедур и правил работы алгоритма.

Element — используется для описания элементов МТП.

Parallel — используется для описания параллельной маршрутизации в МТП.

Condition — структура используется для описания условной маршрутизации в МТП.

Iteration — данная структура используется для описания итеративной маршрутизации в МТП.

Concurrent — структура используется для описания конкурентной маршрутизации в МТП.

Опишем указанные структуры более детально.

Структура Patient (пациент) содержит следующие поля:

D — id пациента;

mmtp — маршрут медицинского технологического процесса для данного пациента в конкретном месте лечения. По своей сути он является массивом блоков, о которых было упомянуто выше.

Структура Place — место лечения, содержит следующие поля:

name — название места лечения:

Id — id места лечения;

count — количество пациентов, проходящих лечения в данном месте лечения;

patients — идентификаторы всех пациентов, которые проходят лечение в данном месте лечения на данном этапе лечения;

t„patients — идентификаторы пациентов, для которых придётся ещё раз произвести синтез, если этого с первого раза сделать не удалось;

pmtp — промежуточный медицинский технологический процесс для данного места лечения;

fmtp — окончательный медицинский технологический процесс для данного места лечения;

places_to — места лечения, куда были направлены пациенты на следующем этапе лечения;

n_places_to — названия мест лечения, куда направили пациента для дальнейшего продолжения лечения; пациент может быть направлен на продолжение лечения в то место, где он уже проходил лечение и заново создаватв этот объект не нужно, поэтому MBi просто указываем на место далвнейшего лечения болвного и записываем его в уже созданный объект.

Структура Element (в качестве элемента этапа выступает оператор) имеет следующие поля:

Id — id лечебного оператора;

name — название лечебного оператора;

count — переменная, принимающая значение количества пациентов, для которых провели данное лечебное мероприятие; её значение учитывается при статистическом анализе во время синтеза обобщённого МТП из двух экземпляров МТП для двух пациетнов.

Структура Parallel соответствует параллельной маршрутизации и имеет следующие поля:

left — список блоков, которые идут «слева» от оператора <—> в упомянутом выше структурированном множестве элементов для текущего этапа лечения;

right — список блоков, которые расположены «справа» от оператора в упомянутом выше структурированном множестве элементов для текущего этапа лечения.

Примером может служить следующая последовательность:

[(ен е12)> (е13е14)].

Структура Condition соответствует условной маршрутизации и имеет поле

list — массив множеств блоков, которые получаются при объединении.

В качестве примера выступает следующая последовательность:

[(еп е12) П (е13ер)].

В данном случае list содержит два элемента (ец е12) и (ещ ер), каждый из которых состоит из двух блоков.

Структура Iteration соответствует итерационной маршрутизации и содержит следующие поля:

blocks — повторяемая последовательность блоков;

Kt — критерий окончания повторения;

count — количество пациентов, для которых проводилась данная итерация; это значение используется для статистического анализа при формировании окончательного МТП.

Введём ещё одну конструкцию Concurrent:

[(ен <—> е13)е12].

Она будет появляться при объединении конструкций (ец

€12 ^ е^) и (ei3 ^ ei2 ^ ец). Структура Concurrent соответствует этой конструкции и содержит следующие поля:

first — имеет тип Parallel;

second — имеет тип Element.

Работа алгоритма состоит из двух основных этапов:

построение экземпляров МТП для конкретных пациентов;

выполнение их анализа на релевантность и объединение их в общую структуру МТП.

Построение экземпляра МТП для конкретного пациента состоит из следующих шагов.

Шаг 1. Считывается название очередного лечебного мероприятия, проводимого с пациентом в данном месте лечения.

Шаг 2. Если название лечебного мероприятия не считано, то

Считывается место лечения, куда переводится пациент.

Добавляется название места в список n_places_to.

Ищется название места лечения среди уже пройденных мест лечения и в списке places_to.

Если поиск проведён успешно, то идентификатор пациента записывается в экземпляр МТП, но в новом месте лечения экземпляр МТП обнуляется; иначе создаётся новый объект типа Place, в него записывается идентификатор пациента, в новом месте лечения обнуляется его экземпляр МТП, добавляется новый объект Place в список places_to текущего места лечения.

Процедура запускается для очередного пациента.

Шаг 3. Проверяется, не проводилось ли данное лечебное мероприятие раньше.

Шаг 4. Если не проводилось, то создаётся объект типа Element, туда записывается название данного лечебного мероприятия, добавляется данный объект в список mmtp данного пациента, переход к пункту 1.

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

Шаг 6. Если замечено несовпадение, создаётся объект типа Element, в него записывается название текущего лечебного мероприятия, объект добавляется в список mmtp данного пациента, для считанных новых мероприятий проводится данная процедура с шага 3, переход к шагу 1.

Шаг 7. Если все лечебные мероприятия совпали, создаётся объект типа Iteration, в него записывается текущее лечебное мероприятие и все остальные из сохраненного списка, список очищается, указанные мероприятия удаляются из списка mmtp данного пациента, добавляется новый объект Iteration в список mmtp данного пациента, переход к шагу 1.

Иначе говоря, на шаге 7 выполнена замена в списке mmtp текущего пациента последовательности блоков Element на блок Iteration, т. к. указанная последовательность повторилась.

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

Синтез общего описания потоков работ

Вторая часть алгоритма также разбивается на две части:

построение промежуточного общего МТП путем объединения экземпляров МТП;

выполнение анализа на релевантность и построение результирующего МТП.

Входом процедуры объединения являются текущее общее описание МТП и экземпляр МТП очередного пациента.

Шаг 1. Заводится результирующий массив для блоков (будет использоваться для записи результатов объединения).

Шаг 2. Если общее описание МТП пусто, то в результат записывается экземпляр МТП пациента. Процедура для объединения общего описания МТП с экземпляром МТП следующего пациента.

Шаг 3. Определяется тип блока на очередном шаге объединения для экземпляра МТП.

Шаг 4. Если блок имеет тип Element

Определяется тип блока на очередном шаге для общего МТП.

Если он имеет тип Element, то сравнивается с элементом из экземпляра МТП пациента.

Если оба типа совпадают, то элемент записывается из общего описания МТП в результат, параметр count увеличивается на 1; переход к шагу 3.

Если типы элементов не совпадают, то

Оба несовпавших элемента сравниваются с тремя следующими элементами из экземпляра МТП и общего описания МТП и проверяется, не образуют ли они конкурентный маршрут.

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

Если не образуют, то проверяется на предмет наличия параллельного маршрута.

Если маршрут параллельный, то полученная структура записывается в результат; переход к шагу 3.

Если маршрут не является параллельным, то запускается процедура обнаружения условного маршрута. Если не удалось найти точку, в которой происходит объединение экземпляра процесса с общим описанием, то экземпляр добавляется в список t„patients.

Если блок из общего описания имеет тип Iteration, то процедура запускается для объединения части экземпляра пациента и параметра blocks у Iteration, после этого в результат добавляется результат выполненной процедуры; переход к шагу 3.

Если блок из общего МТП имеет тип Parallel (блок рО), то создаётся объект Parallel (например pl); в left или right находится элемент из экземпляра МТП пациента, объединяется фрагмент экземпляра МТП пациента с блоком; результат объединения записывается в соответствующее поле объекта pl; фрагмент экземпляра МТП объединяется с другим полем рО; результат записывается в соответствующее поле pl, pl добавляется в результат; переход к шагу 3.

Если блок из общего описания МТП имеет тип Condition (блок сО), то создаётся объект Condition (например cl).

Проводится поиск, в какой части поля объекта с0 находится нужный элемент. Объединяется часть МТП пациента с этой частью поля объекта сО. Записываются в с! все части до найденной части, результат объединения и то, что после найденной части. Добавляется с! к результату, переход к шагу 3.

Шаг 5. Если тип блока МТП пациента имеет тип Iteration

Определяется тип блока на очередном шаге для общего описания МТП.

Если он имеет тип Iteration

Если эти две итерации одинаковые, то итерация общего описания МТП записывается в результат, параметр count увеличивается на 1, переход к шагу 3.

Иначе, создаётся объект Condition, в left записывается итерация общего описания МТП, в right — итерация экземпляра МТП пациента, объект Condition добавляется в результат, переход к шагу 3.

Если тип блока общего МТП не Iteration, часть общего описания МТП объединяется параметром block блока экземпляра МТП пациента.

Шаг 6. Результат записывается в pmtp.

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

Далее строится результирующее описание для текущего места лечения.

Шаг 1. Для очередного блока из pmtp выполняются действия

Если тип Element, то добавить его в fmtp, переход к шагу 1.

5 Г. И. Назаренко, Г. С. Осипов

Если тип Iteration, то если значение count составляет более 30% от общего числа пациентов, проходивших лечение в данном месте лечения, то добавить его в fmpt. Иначе добавить в fmtp блоки из параметра blocks этого объекта. Переход шагу 1.

Если тип Parallel, то проверить значение count у первых элементов в списках left и right.

Если у первых элементов в списках left и right значения count больше 30% от общего числа пациентов, проходивших лечение в данном месте лечения, то весь блок добавить в fmtp.

Если у элемента значение count меньше 30% от общего числа пациентов, проходивших лечение в данном месте лечения, то ветвь отбрасывается, а все блоки добавляются в fmtp. Переход к шагу 1.

Шаг 2. Если тип Condition, то ветви, у которых значение count для первого блока будет 30% от общего числа пациентов, проходивших лечение в данном месте лечения, отбрасываются.

Шаг 3. Если осталась одна ветвь, то добавить значения блоков из этой ветви в fmtp. Если таких ветвей больше 1, то объект Condition с оставшимися ветвями добавить в fmtp.

Шаг 4. Если тип объекта Condit ion Concurrent, то проверить значение count у всех блоков внутри этого объекта. Если у одного из них значение count меньше 30% от общего числа пациентов, проходивших лечение в данном месте лечения, то он отбрасывается, а остальные добавляются в fmtp в порядке их следования в Concurrent. Иначе в fmtp добавляется весь объект Concurrent.

Далее очищается массив t_patients и запускается процедура построения общего описания МТП для всех мест лечения в списке places, to. Заметим здесь, что каждый этап медицинского технологического процесса связан с некоторым подразделением лечебно-диагностического учреждения. Понятие места лечения больного также связывается с подразделением лечебнодиагностического учреждения.

Разобьём этап технологического процесса на несколько блоков; в качестве блока может выступать либо просто элемент е^ либо параллельная, либо конкурентная, либо условная, либо итеративная маршрутизация. Все блоки выполняются последовательно.

Рассмотрим теперь вторую часть алгоритма.

Шаг 1. Для каждого пациента на каждом этапе лечения строится экземпляр МТП. Из базы данных извлекаются лечебные мероприятия, которые проводились с пациентом, после этого они упорядочиваются по времени их проведения и записываются в экземпляр МТП в том порядке, в котором они проводились для текущего пациента.

Шаг 2. Из экземпляров синтезируется общее описание МТП. Синтез общего описания заключается в последовательном применении правил построения структур Concurrent, Parallel и Condition. Если применимо правило для построения структуры Concurrent, то строится структура Concurrent. Иначе, если применимо правило построения структуры Parallel, строится структура Parallel. Иначе строится структура Condition.

Шаг 3. Если после выполнения процедуры синтеза список t_patients не пуст, то для этих пациентов ещё раз запускается процедура синтеза с указанием, что пациентов в список t„patients больше не добавлять.

Шаг 4. Из общего МТП отбрасываются те маршруты, которые проводились меньше чем для 30% пациентов.

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

Построение МТП для конкретного пациента в текущем месте лечения состоит из следующих шагов.

Шаг 1. Считывается название очередного лечебного мероприятия, проводимого с пациентом в данном месте лечения. Обозначим это лечебное мероприятие 1m.

Шаг 2. Если на данном этапе лечения с пациентом не проводилось иных лечебных мероприятий

Считывается место лечения place, куда направится пациент.

Добавляется название place в список n_places_to.

Ищется place среди уже пройденных мест лечения и в списке places_to.

Если place найдено, то идентификатор пациента записывается в place, но в новом месте лечения обнуляется его экземпляр МТП. Иначе создаётся новый объект типа place, записывается идентификатор

пациента, в новом месте лечения обнуляется его экземпляр МТП, добавляете новый объект place в список places_to текущего места лечения.

Выход.

Второй этап алгоритма заключается в синтезе общего МТП. Процедура синтеза make_sintez запускается для всех частных МТП. На вход процедуре синтеза подаётся общий МТП сМТР и экземпляр МТП рМТР очередного пациента.

Шаг 1. Заводится результирующий массив для блоков result. Он используется для записи объединения, cgindex используется как индекс блока в общем МТП, index — индекс МТП текущего пациента.

Шаг 2. Если общий МТП пуст, то в result записывается МТП пациента. Выход.

Шаг 3. Считывается очередной блок Ы из МТП пациента.

Шаг 4. Считывается очередной блок Ь2 из общего МТП.

Шаг 5. Определяется тип блока Ы на очередном шаге объединения для МТП пациента.

Шаг 6. Если Ы имеет тип Element

Определяется тип Ь2 для общего МТП.

Если блок Ь2 имеет тип Element, то сравнивается с Ы из МТП пациента.

Если Ь2 и Ы совпадают, то записывается элемент из общего МТП в результат с увеличением параметра count на 1; переход к шагу 3.

Если они не совпадают

Если правило MUnion применимо, то оно применяется, переход к шагу 3.

Если правило MSParallel применимо, то оно применяется, переход к шагу 3.

Если правило MLParallel применимо, то оно применяется, переход к шагу 3.

Если правило MRParallel применимо, то оно применяется, переход к шагу 3.

Если правило MBParallel применимо, то оно применяется, переход к шагу 3.

Если правило MCondition применимо, то оно применяется, переход к шагу 3.

Если блок из общего МТП имеет тип Iteration, то make_sintez (часть МТП пациента, параметра blocks для Iteration), в result добавляется результат выполненной процедуры и переход к шагу 3.

Если блок из общего МТП имеет тип Parallel (назовем данный блок рО), то создается объект Parallel pl, ищется, в left или right элемент из МТП пациента является первым элементом, res=make_sintez (часть МТП пациента, left/right); res записывается в нужное поле объекта pl. Результат make_sintez (МТП пациента, другое поле рО) записывается в нужное поле pl. В result добавляется pl. Переход к шагу 3.

Если блок из общего МТП имеет тип Condition (назовем данный блок сО), то создается объект Condition cl. Ищем, в какой части поля объекта сО первым находится нужный нам элемент. В с! записываются части до найденной части, результат make_sintez (часть МТП пациента, найденная часть поля объекта сО) и всё, что после найденной части. В result добавляется cl, переход к шагу 3.

Шаг 7. Если тип блока МТП пациента имеет тип Iteration.

Определяется тип блока на очередном шаге для общего МТП.

Если он имеет тип Iteration.

Если эти две итерации одинаковые, то записывается итерация общего МТП в результат с увеличением параметра count на 1, переход к шагу 3.

Иначе, создается объект Condition, в left запишется итерация общего МТП, в right — итерация МТП пациента, добавляется объект Condition в результат; переход к шагу 3.

Если тип блока общего МТП не Iteration, объединяется часть общего МТП с параметром block блока МТП пациента.

3. Описание основных процедур и правил

В алгоритме используются следующие основные процедуры. Правило MUnion используется для построения структуры Concurrent. Предусловие правила:

Equal(сМТР[cgindex],рМТР[index+2]),

Equal(сМТР[cgindex+1],рМТР[index+1]), Equal(сМТР[cgindex+2],рМТР[index]).

Список добавляемых фактов:

make_union(сМТР[cgindex],сМТР[cgindex+1], сМТР [cgindex+2],union), add(union), augmenter(cgindex,3), augmenter(index,3).

Процедура Equal(objectl,object2) проверяет, что onjectl равен object2. Процедура

make_union(cMTP[cgindex],сМТР[cgindex+1], cMTP [cgindex+2],union)

записывает cMTP[cgindex], cMTP [cgindex+1], cMTP[cgindex+2] в объект union. Процедура add (union) записывает объект union в result. Процедура augmenter(index,count) увеличивает значение index на величину count.

Правило MSParallel используется для построения структуры Parallel. Предусловие:

Equal(сМТР[cgindex],рМТР[index+1]), Equal(сМТР[cgindex+1],рМТР[index]).

Список добавляемых фактов:

make_parallel(сМТР[cgindex],сМТР[cgindex+1],parallel), Add(parallel), augmenter(cgindex,2) , augmenter(index,2).

Процедура

make_parallel(cMTP[cgindex],cMTP[cgindex+1],parallel)

записывает cMTP[cgindex], cMTP [cgindex+1] в parallel.

Правило MRParallel используется для построения структуры Parallel. Предусловие:

Equal(сМТР[cgindex],рМТР[index+2]), Equal(сМТР[cgindex+1],pMTP[index]).

Список добавляемых фактов:

make_parallel(сМТР[cgindex],сМТР[cgindex+1], рМТР[index+2],parallel),

Add(parallel),

augmenter(cgindex,2) ,

augmenter(index,3).

Правило MLParallel используется для построения структуры Parallel. Предусловие:

Equal(сМТР[cgindex],рМТР[index+1]),

Equal(сМТР[cgindex+2],рМТР[index]).

Список добавляемых фактов:

make_parallel(сМТР[cgindex],сМТР[cgindex+1], сМТР [cindex+2],parallel),

Add(parallel),

augmenter(cgindex,3), augmenter(index,2).

Правило MBParallel используется для построения структуры Parallel. Предусловие:

Equal(сМТР[cgindex],рМТР[index+2]), Equal(сМТР[cgindex+2],pMTP[index]).

Список добавляемых фактов:

make_parallel(сМТР[cgindex] ,сМТР[cgindex+1] , сМТР[cindex+2],рМТР[index+2] , parallel),

Add(parallel),

augmenter(cgindex,3),

augmenter(index,3).

Правило MCondition используется для построения структуры Parallel. Предусловие:

True.

Список добавляемых фактов:

make_condition(cMTP,pMTP,condition,cind, pind,cgindex,index), Add(parallel), augmenter(cgindex,cind), augmenter(index,pind).

Процедура

make_condition(cMTP,pMTP,condition,cind, pind,cgindex,index)

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

Приложение 4Инструментальные средства

Для поддержки создания служб и систем управления потоками работ существуют методологии, стандарты и специализированное программное обеспечение, образующие в комплексе инструментальные средства [27 30| разработчика.

Методологии

Методология — это совокупность методов, применяемых в жизненном цикле разработки процесса и объединенных одним общим подходом. В настоящее время получила распространение методология SADT (Structured Analysis and Design Technique) — методология структурного анализа и проектирования, которая породила целый ряд методов.

IDEF0 — метод функционального моделирования — позволяет описать бизнес-процесс в виде иерархической системы взаимосвязанных функций Методология IDEF0 представляет собой совокупность методов, правил и процедур, предназначенных для построения функциональной модели объекта какой- либо предметной области. Функциональная модель IDEF0 отображает функциональную структуру объекта, т. е. производимые им действия и связи между этими действиями. Методология IDEF0 может использоваться для моделирования широкого круга систем и определения требований и функций, а затем для разработки системы, которая удовлетворяет этим требованиям и реализует эти функции. IDEF может быть использована для анализа функций, выполняемых уже имеющейся системой, а также для указания механизмов, посредством которых они осуществляются.

IDEFIX — метод информационного моделирования — основан на концепции «сущность-связь» (entity-relationship).

IDEF3 — метод описания процессов — рассматривает последовательность выполнения и причинно-следственные связи между ситуациями и событиями для структурного представления знаний о системе.

IDEF4 — метод объектно-ориентированного проектирования сложных систем — описывает структуру, поведение и реализацию систем в терминах класса объектов.

IDEF5 — метод онтологического анализа систем — анализирует основные термины и понятия (словаря), используемые для характеристики объектов и процессов, границ применения, а также взаимосвязей между ними.

DFD (Data Flow Diagrams) — диаграммы потоков данных — методология структурного анализа, описывающая внешние по отношению к системе источники и адресаты данных, логические функции, потоки данных и хранилища данных, к которым осуществляется доступ. DFD — это способ представления процессов обработки информации, передачи и хранения данных (или материальных объектов).

CPN (Color Petri Nets) — раскрашенные сети Петри — методология создания динамической модели бизнес-процесса, позволяющая проанализировать зависящие от времени характеристики выполнения процесса и распределение ресурсов для входящих потоков различной структуры, над которыми выполняются формализованные операции (выборка, соединение и т. д.).

Стандарты

Одним из наиболее важных требований к системам управления потоками работ является следование стандартам и спецификациям, что даёт ряд преимуществ в системах управления:

формализацию описания потоков работ;

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

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

Следование ряду стандартов позволяет создавать автономные открытые workflow-системы, расширяет область и способы их применения для моделирования различных рабочих процессов.

На данный момент разработан ряд стандартов для описания реальных потоков работ, которые можно разбить на две категории:

графовые модели, отражающие древовидную структуру процесса;

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

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

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

WorkflowProcessDefinition — представляет собой контекст выполняющегося процесса, и его данные могут быть доступны всем остальным компонентам.

Activity — «действие» или «задание» процесса, представляющее собой этап, на котором происходит изменение содержания объектов процесса.

Transitioninformation — переходы между заданиями (могут быть условными и безусловными).

WorkflowRelevantData — оперативные данные, доступные всем компонентам процесса в ходе его выполнения.

Participant — участник процесса, производящий «действия» над объектами и осуществляющий переходы.

Application — внешнее приложение, используемое для выполнения «действий».

Спецификация XPDL имеет характерные особенности.

Рабочий процесс представляет собой направленный граф, узлами которого являются «действия», связанные между собой переходами. Переходы могут быть условными, причём условие проверяется на этапе выполнения конкретного «действия».

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

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

Является расширяемым стандартом.

Спецификация BPML, предложенная BusinessProcess- Managementlnitiative, является стандартом, реализующим блочную модель потоков работ. Элементарными блоками, из которых строится модель рабочего процесса в BPML, являются «действия» (Activity). Рабочий процесс не выделяется в виде отдельного объекта, а является специальным случаем агрегированного действия. В спецификации BPML выделяются следующие типы процессов:

вложенный процесс (NestedProcess);

процесс, обрабатывающий исключительные события (ExceptionProcess);

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

Для общения между процессами («действиями») в спецификации BPML используются сообщения (Messages) и сигналы (Signals). Двумя важными компонентами модели BPML являются системные ошибки (Faults) и расписания (Schedules). Системные ошибки приводят к завершению выполнения текущего задания, в результате чего управление передаётся специальным обработчикам. Расписания выполняют управляющие функции: в их задачу входит генерация специальных сообщений в определённые моменты времени, что позволяет осуществлять планирование запуска процессов.

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

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

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

Абстрактное понятие внешнего приложения (Application) в совокупности с поддержкой расширяемости стандарта даёт свободу выбора в реализации интерфейсов

для общения системы управления потоками работ с Web- сервисами, использующимися для выполнения «действий» процесса.

Существует ряд средств визуального проектирования (как графических, так и диалоговых), облегчающих процесс редактирования XPDL-описаний.

Более простой импорт описаний процессов на других XML- языках (преобразование их к направленному графу условных переходов между «действиями»), что способствует построению распределённых систем управления потоками работ.

Инструментальные программные системы

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

BPWin (бизнес-процессы и окна) - средство функционального моделирования, реализующее методологию IDEF0-IDEF3. BPWin помогает быстро создавать и анализировать модели с целью оптимизации деловых и производственных процессов. Посредством набора графических инструментов для отображения действий и объектов, BPwin позволяет легко построить схему процесса, на которой показаны исходные данные, результаты операций, ресурсы, необходимые для их выполнения, управляющие воздействия, взаимные связи между отдельными работами.

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

ORG-Master (система бизнес-моделирования) — многопользовательская среда моделирования и организации деятельности предприятия, поддерживающая системный и процессный

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

WPS (Work Flow system) — программное обеспечение и система технологий управления деловыми процессами, поддерживающая передачу документов по локальной сети и контроль выполнения функций, возложенных на сотрудников компании.

UML (Unified Modeling Language) — унифицированный язык моделирования, являющийся стандартным инструментом для создания программного обеспечения. UML удовлетворяет потребности при моделировании любых систем. Система описывается набором моделей, рассматривающих её с различных точек зрения. В UML все абстракции программной системы организуются в виде моделей, каждая из которых представляет относительно независимый аспект разрабатываемой системы. Для визуализации наборов этих абстракций можно использовать диаграммы. Модели, которые создаются с его помощью, могут быть непосредственно переведены на любой объектно-ориентированный язык программирования. Понятия, которые удобнее представлять графически, подставляются в UML, те же, которые лучше описывать в текстовом виде, выражаются с помощью языка программирования. UML позволяет непосредственно выполнять модели, имитировать поведение системы и контролировать действующие системы. В UML предусмотрены средства для графического представления систем и подсистем. Система и подсистема изображаются в виде пиктограммы стереотипного пакета.

Примером системы, объединившей последние достижения в области информационных технологий, служит интегрированная система управления госпиталем MedTrak [31]. Система, разработанная австралийской фирмой TrakHealth, позволяет управлять потоками амбулаторных пациентов, пациентов стационара и отделения скорой помощи, осуществляет управление ресурсами (людьми и оборудованием). В MedTrak учтены требования к информационным системам в части использования стандартов, протоколов ведения больных и поддержки принятия решений.

Язык моделирования GPSS

Одним из наиболее эффективных и распространенных языков моделирования сложных дискретных систем является в настоящее время язык GPSS (General Purpose System Simulator) [12,13]. Он может быть с наибольшим успехом использован для моделирования систем, формализуемых в виде систем массового обслуживания (СМО). Широкий набор компонентов этого языка позволяет конструировать сложные имитации модели с сохранением терминологии СМО. В качестве объектов языка используются аналоги таких стандартных компонентов СМО, как заявки, обслуживающие приборы, очереди и т.п. Достаточный набор подобных компонентов позволяет конструировать сложные имитационные модели, сохраняя привычную терминологию СМО.

GPSS работает с объектами, которые можно классифицировать следующим образом:

класс — транзакты и блоки, непосредственно связанные с транзакциями;

класс — объекты оборудования: устройства, накопители, логические ключи;

класс — вычислительные объекты: арифметические операции, переменные и функции;

класс — статистические объекты: очереди и таблицы;

класс — ссылочные объекты: ячейки и матрицы ячеек;

класс — создаётся пользователем.

Основным объектом является транзакт. Транзакт — это активный динамический объект, характеризуемый некоторым количеством атрибутов, называемых параметрами. Транзакты (процессы) продвигаются по маршруту и, проходя через другие объекты, подвергаются воздействию, которое меняет его атрибуты. Транзакты «создаются» и «уничтожаются» так, как это необходимо по логике модели в процессе моделирования. С каждым транзактом может быть связано произвольное число параметров, несущих в себе необходимую информацию об этом транзакте. Кроме того, транзакты могут иметь различные приоритеты. В начальный момент времени в GPSS-модели нет ни одного транзакта. В процессе моделирования симулятор генерирует транзакты в определённые моменты времени в соответствии с теми логическими потребностями, которые возникают в моделируемой системе. Подобным же образом транзакты

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

транзакт входит в блок, функцией которого является удаление транзакта из модели;

транзакт входит в блок, функцией которого является задержка транзакта на некоторое определённое в модели время;

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

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

Симулятор GPSS/PC помещает транзакты, в зависимости от условий в модели, в тот или иной список и переносит транзакты из списка в список, просматривает списки, выбирая следующий транзакт для обработки, корректирует таймер модельного времени после обработки всех транзактов в списке текущих событий.

Научное издание

НАЗАРЕНКО Герасим ИгоревичОСИПОВ Геннадий Семенович

ОСНОВЫ ТЕОРИИ МЕДИЦИНСКИХ ТЕХНОЛОГИЧЕСКИХПРОЦЕССОВ

Часть 2

Редактор Е.Б. ГугляОригинал-макет: О.А. КузнецовОформление переплета: А.Ю. Алехина

Подписано в печать 21.03.06. Формат 60x90/16.

Бумага офсетная. Печать офсетная. Усл. печ. л. 9.

Уч.-изд. л. 9,0. Тираж 500 экз. Заказ №

Издательская фирма «Физико-математическая литература»МАИК «Наука/Интерпериодика»

117997, Москва, ул. Профсоюзная, 90

E-mail: fizmat@maik.ru, fmlsale@maik.ru;

http://www.fml.ru

Отпечатано с готовых диапозитивовв ФГУП «Производственно-издательский комбинат ВИНИТИ»140010, г. Люберцы, Московская обл., Октябрьский пр-т, 403

УДК 51.7

ББК 32.81

Н 19

Назаренко Г. И., Осипов Г. С. Основы теории медицинских технологических процессов. Ч. 2. Исследование медицинских технологических процессов на основе интеллектуального анализа данных. - М.: ФИЗМАТЛИТ, 2006. - 144 с. - ISBN 5-9221-0677-5.

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

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

© ФИЗМАТЛИТ, 2006

ISBN 5-9221-0677-5ISBN 5-9221-0677-5© Г. И. Назаренко, Г. С. Осипов, 2006

ISBN 5-9221-0677-5

ISBN 5-9221-0677-5

ОГЛАВЛЕНИЕ

Предисловие научного редактора . . . . ..5

Предисловие авторов . . . 7

Введение . . . . . . 9

Глава 1. Принципы моделирования потоков работ . . . .11

Функции системы управления потоками работ. ..11

Порядок построения модели . . . 12

Методы и задачи моделирования . . . . 13

Проблемах применения моделей 16

Глава 2. Модели потоков работ 18

Модели и методах теории расписаншг . ..18

Теория и модели массового обслуживания . . . . ..26

Моделирование потоков работ сетями Петри 31

Моделирование потоков работ конечными автоматами. . . .40

Моделирование потоков работ методами линейного программирования. . . ..46

Транспортная задача . . . 52

Поиск кратчайшего пути . . . 57

Оценка критериев качества . . . 58

Глава 3. Релевантность и прецедентность на множе

стве медицинских технологических процессов ......63

Прецедентность на множестве медицинских технологических процессов . . . ..63

Метрики для классификации ситуаций 65

Согласование прецедентов ..72

Функция согласования для вектора признаков 73

Предпочтения и глобальная релевантность74

Глава 4. Потоки работ в медицинских данных. .......76

Потоки работ как допустимые последовательности операторов . . . . .. 78

Маршруты в потоках работ . . . 80

Построение описаний классов эквивалентности . .83

Корректность и полнота описаний классов эквивалентности 85

Построение описаний для классов примеров методами конструктивной индукции ..87

Глава 5. Процессы и маршруты в них. . .93

Операторы и их применимость. . . . 93

Свойства операторов и типы процессов . . 96

Глава 6. Выявление потоков работ по примерам. . . . . . 100

Построение последовательностей работ100

Разбиение экземпляров на классы и их кластеризация . . . . 101

Извлечение параллельных потоков. . . . 102

Извлечение итеративных потоков 103

Извлечение конкурентных потоков. . . . 103

Извлечение условных потоков . . . . 103

Некоторые замечания об оптимизации медицинских техно

логических процессов . . . . . . 104

Заключение . . . . . 112

Список литературы . . . . . 114

Приложение 1. Метод разбиения множества рабочих последовательностей на классы эквивалентности. . 116

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

Приложение 3. Алгоритм синтеза общего описания потоков работ 123

Построение экземпляров МТП . . .. 123

Синтез общего описания потоков работ 127

Описание основных процедур и правил .. 133

Приложение 4. Инструментальные средства. 136

Методологии 136

Стандарты . . . . .. . 137

Инструментальные программные системы . . . . .. 140

Язык моделирования GPSS . 142