Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение высшего образования

«КРЫМСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ имени В. И. Вернадского» Таврическая академия (структурное подразделение)

Выпускная квалификационная работа

Вероятностные сетевые модели



Введение

Разработка и внедрение в производство сетевых моделей начинается в серединеXX столетия. Потребность в реализации масштабных проектов с привлечением большого количества материальных и трудовых ресурсов вызвала необходимость в использовании проектногоподхода, моделирования. Это стало возможным благодаря развитию вычислительной техники. В конце 50-х в США были разработаны методы сетевого планирования и управления, такие какдиаграмма Гантта (Ganttchart), CPM (CriticalPathMethod- Метод определения критического пути), PERT (ProgramEvaluationandReviewTechnique - техникаоценки и анализа проектов), ставшие основой современных методик. Широкое внедрение ЭВМ поспособствовало развитию методов управления проектами (ProjectManagement).В настоящее время управление проектами с использованием сетевых моделей применяетсяво многих сферах деятельности.Существует множество настольных программных комплексов и приложений с web_интерфейсом, обладающих широкой функциональностью.

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

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

Основные задачи работы включают:

- анализ основных типов вероятностных моделейна основе описания, сравнения, формализации, классификации;

- освоение математического аппарата расчета временных параметров в сетях различных типов;

- исследование альтернативных сетевых моделей и методов их построения и оптимизации;

- построение альтернативных сетевых моделей для задач управления.

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

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



1. Управление проектами и сетевые модели

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

В числе основных источников, раскрывающих теоретические основы проектного управления, используютсяработы С. Баркалова и др. [2], авторского коллектива под редакцией М. Разу [14], М. Троцкого, Б. Гручи и К. Огонека[18],А. Галюка[3],А. Ивасенко, Я. Никоновой, А. Сизовой [10]. Р. Томаса[17]. Исторический обзор основан на работах Д. Филлипсаи А. Гарсиа-Диаса[21].На основе работ Д. Голенко-Гинзбурга, М. Троцкогои др.,Д. Филлипса и А. Гарсиа-Диаса, А. Притскера [24]изучены способы построения и анализавероятностных сетевых моделей, а также расчёт временных параметров проекта с использованием этих моделей.

1.1 Основные этапы развития сетевых технологий

Появлениеметодов и технологий сетевого планирования и управления (СПУ) непосредственно связано с коренными изменениями в сфере управления проектами (УП). Развитиеменеджмента и создание методологии проектного управления- длительный процесс. Основы современного менеджментаберут начало в конце XIX- начале XX века. В числе основоположников направления следует отметить социолога Макса Вебера, утверждавшего бюрократию как наиболее эффективный способ организации; Фредерика У. Тейлора и его последователей Р. Джилберта и Ральфа У. Бёрнса, выдвигавших идею научного инженерно-механистического менеджмента.В начале XXвека русский учёный А. Богданов предлагает применять системный подход к управлению производством, однако реализация этих идейначалась только к середине века, став основой методологии таких дисциплин как теория управления и системный анализ[14]. сетевой проектный управление высокотемпературный

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

При строительстве плотины Гувера в 1931-1936 гг. для управления расписанием впервые для проекта такого масштаба использовали диаграммы, изобретённыеинженером Х. Л. Ганттом, которые до сих порслужат основой для календарного планирования многих проектов благодаря своей наглядности.

Первым примером современного управления проектами стала реализация инициированного во время Второй мировой войны проектаManhattan, посвящённого созданию атомной бомбы. Американские учёные разработали для этогоособые методы планирования и управления выполнением работ. [18]

Ключевым моментом в становлении СПУ становится модернизация своих заводов компанией «E.I. duPontdeNemoursandCompany». Результатом проведённых исследований становится возникновение нового способа планирования:Уокер и Келли создали методику описания проекта, в которой применяются компьютерные вычисления. Методика получила название метода критического пути (МКП или CriticalPathMethod, CPM).В течение 1956 - 1958годов вВМС США при создании ракетного комплекса «Polaris» впервые был использованметодPERT (ProgramEvaluationandReviewTechnique - техника оценки и анализа проектов), предназначенный для управления временем и ресурсами [7].Применяя PERT-анализ, члены проекта создавали модель выполнения работ по постройке ракеты,структурируя логическую сетьиз последовательных взаимосвязанныхэтапов (событий).В дальнейшем метод и его модификации широко использовались в других экспериментальных, опытно-конструкторских и прочих научно-исследовательских проектах. Успех применения МКП и PERT обусловил их быстрое и широкое распространение.

Следующее десятилетие знаменательно разработкой американским ученым С. Эльмаграби методов расчета вероятностных альтернативных сетевых моделей (моделей с вероятностным типом событий) для управления научно-исследовательскими проектами и творческой деятельностью[12]. В 1962 году к логической PERT-сети добавили оценку ресурсов, появилась PERT/COST-методика (PERT-анализ с целью стоимостного прогнозирования).В 1966 году Аланом Притскером впервые была описана системаGERT (GraphicalEvaluationandReviewTechnique, метод графической оценки и анализа), применяемая для анализа и оптимизации альтернативных сетевых моделей[24].

Важным шагом для дальнейшего развития СПУ становится создание компьютерных программ и пакетов по управлению проектами. В них применяются как простейшие технологии (диаграмма Гантта, МКП), так и собственные разработки компаний, например, IBM, Lockheed Martin Corporation, P&G.70-е годы характерны развитием системного подхода к управлению и повсеместным внедрением СПУ, а также началом массового преподавания техники сетевого анализа в учебных заведениях. Из СПУ выделяется управление стоимостью, качеством, рисками, материальными запасами; развивается теория организационных структур [2].Таким образом, в большинстве случаев сетевые модели становятся многокритериальными.В это времяпоявляются некоммерческие организации и компании по управлению проектами. (PMI, IPMA, AIPM, ENAA).

В конце века применение УП распространяется на многие отрасли деятельности. Большой популярностью УП пользуется в социальной сфере, государственном управлении, международной торговле и научном сотрудничестве. Институт управления проектами выпустил первое издание Руководства к Своду знаний по управлению проектами (PMBOC), на основе которого множество компаний создало свои принципы УП[15]. Распространение компьютерных технологий позволило значительно упростить расчёты, благодаря чему СПУ распространилось на небольшие предприятия и проекты.

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

1.2 Основные понятия проектного управления

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

Любой проект в некоторой степени обладает ограниченностью, которую называют «тройственной». Это понятие опирается на три важнейших параметра проекта: время, стоимость и объём выполняемых работ. В этом ключе проект рассматривается как задача оптимизации с тремя основными ограничениями, где целевая функция -- качество реализации [3, 13].

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

Проекты можно классифицировать по многим характеристикам, например, по масштабу, срокам реализации, сложности, причине возникновения и другим параметрам[2, 10, 11, 13]. В частности, по основным сферам деятельности различают такие типы проектов:

- социальные;

- экономические;

- организационные;

- технические;

- смешанные.

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

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

- как форма воздействия на социально-экономическую систему;

- управление проектом в процессе формирования его результатов[6].

В [9, с. 107]представлена классификация проектного управленияпо конченой цели и внутреннему наполнению проекта (Таблица 1.1), хотя авторы подчёркивают, что любая классификация проектов, как и систем, носит весьма условный характер.



Таблица 1. Классификация проектного управления

		Содержание
		Неограниченное	Ограниченное
Цель	Терминальная	Мультипроектное управление	Терминальный проект
	Нетерминальная	Открытый проект	Развивающийся проект

С другой стороны, в [6] представлено чёткое структурирование целей по типам, а именно:

- требуемое конечное состояние проектируемой системы (монопроект);

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

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

Несмотря на различия втерминологии, группировка проектов по целям имеет общие черты с классами проектного управления по [14].

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

Всех участников проекта можно разделить на категории:

- управленческий аппарат заказчика проекта;

- управленческий аппарат исполнителя проекта;

- команды проектов[3].

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

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

- каскадная или «классический проектный менеджмент» - предполагает неизменность базовых задач;

- PERT-оценка продолжительности работ и PERT/COST-анализ материальных затрат;

- МКП - наглядный способ календарного планирования;

- PRINCE2 (стандарт УП в Великобритании);

- RWP (планирование методом набегающей волны);

- LEAN (от. англ. «бережливый») - концентрация на устранении потерь.

1.3 Структурная декомпозиция работ

Структура разбиения работ (WBS -Work Breakdown Structure) -одно из базовых средств УП, позволяющее решать проблемы организации работ, распределения ответственности, оценки стоимости, создания системы отчетности, эффективно поддерживать процедуры сбора информации о выполнении работ и отображать результаты в информационной управленческой системе для обобщения графиков, стоимости, ресурсов, работ и дат их завершения[11].

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

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

Ценность метода структурной декомпозиции работ состоит в том, что он:

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

- делит содержание проекта на понятные, ощутимые результаты;

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

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

Построение СРР включает в себя такие этапы:

- ответ на вопрос «Что должно быть сделано?». Для обеспечения согласованности между деревом работ и требованиями к проекту необходимо детально изучение документов, содержащих общее описание проекта (ТЗ, технический проект и пр.);

- определение основных промежуточных результатов;

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

- совершенствование дерева работ, пока оно не будет удовлетворять потребностям всех участников проекта[14].

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

1.4 Сетевое планирование и управление

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

Применение СПУ в экономических системах, включая календарное планирование, управление рисками, стоимостью, качеством проектных решений и другими ресурсами освещается в работах [10, 11]. Использование СПУ в научно-исследовательской работе и военном деле затронуто в [24]. Методология СПУ реализуется по принципам УП, которые стандартизированы PMI[15], IPMACompetenceBaseline, TenStep, IWURM, P2M, ГОСТ54869-2011[1]идругими.

Одним из первых методов календарного планирования сталаразработанная более 100 лет назад Генри Л. Ганттом схема представления работ на временной шкале, называемая диаграммой Гантта.

Диаграмма Гантта (ДГ) - ленточная диаграмма продолжительности работ, отображающая работы в виде горизонтальных отрезков. Состоит из двух частей - табличной и графической. В табличной описывается содержание работ, а в графической указывается их продолжительность. Продолжительность работ представляется в виде горизонтально вытянутого прямоугольника или линии. Левый край обозначает начало, а правый - окончание выполнения работы [3]. Ключевым понятием в диаграмме является «веха» (ключевая точка), то есть момент завершения одной или нескольких операций, имеющий принципиальную важность для выполнения проекта.

1.4.1 Классификация сетевых моделей

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

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

Согласно [18], в сетевых технологиях применяются сети трёх типов:

- работы представляются дугами, а события - узлами графа (ActivitiesonArrows, AoA);

- работы представляются узлами, а события - дугами графа (ActivitiesonNodes, AoN);

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

Похожая классификация вводится также в[9], где сетевые модели называют «ориентированными» (на операции, события, события и операции). Другие авторы ([23];[6];[17];[7]) не выделяют третий тип.

Конечно, сетевые модели обладают и другими важными параметрами. Например, в[9] кроме ориентированных на события и работы выделяются также следующие сети:

по количеству конечных целей:

- одноцелевые;

- многоцелевые;

по количеству исходных событий (операций):

- с одним исходным событием (операцией);

- с несколькими исходными событиями (операциями);

по степени неопределённости сети:

- детерминированные;

- стохастические;

по количеству операций:

- малого объёма (менее 1500);

- среднего объёма (от 1500 до 10000);

- большого объёма (более 10000).

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

Поскольку этот вопрос важен для дальнейшего изложения, приведем сравнительную таблицу классификации по Разу[14]и Голенко-Гинзбургу[4] (Таблица 2).

Таблица 2. Сравнительная классификация сетевых моделей

Оценка процессов	Оценка продолжительности	Классификация по Разу	Классификация по Голенко-Гинзбургу
Точная	Точная	Детерминированные СМ с точной оценкой продолжительности работ	Детерминированные СМ
Точная	Вероятностная	Детерминированные СМ с вероятностной оценкой продолжительности работ	Вероятностные СМ с детерминированной структурой
Вероятностная	Точная	Стохастические СМ	Альтернативные СМ
Вероятностная	Вероятностная

В дальнейшем будем ориентироваться на классификациюГоленко_Гинзбурга, предполагающую три основных типа сетевых моделей; детерминированные сетевые модели (ДСМ), вероятностные сетевые модели (ВСМ), альтернативные сетевые модели (АСМ).

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

Графическое представление модели и временная диаграмма удобны для наглядного представления небольшого количества работ, но с ростом числа работ (а в реальных задачах их десятки тысяч) это преимущество теряется. Поэтому для анализа и оптимизации используют матричную форму[8].

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

1.4.2 Детерминированная модель

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

Приведем требования к одноцелевой СМ с одним исходным событием:

- узлы пронумерованы в порядке выполнения, т. е. для каждой дуги ;

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

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

- отсутствуют циклы, т. е. замкнутые цепи, соединяющие узел с ним же самим [20];

- между смежными узлами может проходить только одна дуга;

- узлы строят последовательно (стрелки направлены слева направо - от начала к окончанию);

- следует избегать пересечения дуг на графике;

- фиктивные работы обозначаются пунктирной линией.

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

Таблица 3. Технологическая последовательность работ

Предшествующие работы ()	Данные работы ()
--	0,1
	0,2
	0,3
0,1	1,4
0,1	2,5
0,1	2,6
0,1	3,6
1,4	4,7
2,5	5,7
2,6 3,6	6,8
4,7 5,7	7,8

Построенный по этой таблице сетевой график приведён на Рис. 1

Рис. 1. Сетевой график типа «узел-событие»



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

Количество столбцов и строк в матрице равно количеству событий. Каждый столбец и строка нумеруются по порядку согласно количеству событий. Затем на пересечении каждой строки, соответствующей начальному событию, и столбцу, соответствующему последующему событию, ставится «1», а во всех остальных случаях - «0».

Наряду с понятиями работ и событий в сетевом моделировании очень важным является понятие пути.

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

Полный путь- это непрерывная последовательность работ между исходным и завершающим событием сетевой модели. Суммарная продолжительность работ, лежащих на пути, определяет длину пути[14]. Таких путей в сетевой модели может быть несколько.

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

Учитывая время выполнения работы,

Таблица 3 дополняется ещё одним столбцом под названием «Продолжительность» (Таблица 4).



Таблица 4. Технологическая последовательность работ с учетом продолжительности

Предшествующие работы ()	Данная работа()	Продолжительность
--	0,1	2
	0,2	2
	0,3	1
0,1	1,4	4
0,1	2,5	5
0,1	2,6	8
0,1	3,6	3
1,4	4,7	1
2,5	5,7	4
2,6 3,6	6,8	5
4,7 5,7	7,8	3

Рис. 2. Сетевая модель «узел-событие» суказанием временных параметров

Модель «узел-работа» (AoN) имеет существенные отличия от предыдущей. В узле содержится следующая информация (Рис. 3).

Рис. 3 Параметры, описываемые в узле модели «узел-работа»



На Рис.4 представлена модель «узел-работа», эквивалентная изображённой на Рис.5.

Рис. 4. Сетевая модель «узел-работа» с временными параметрами

Особенностью построения СМ «узел-работа» являются:

- добавление условных узлов «Начало», предшествующего всем узлам и «Окончание», следующего после всех работ (работы в этих узлах имеют нулевую продолжительность);

- работы можно нумеровать одним индексом;

- нет необходимости вводить фиктивные события, обозначающие логическую взаимосвязь событий;

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

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



.

Раннее начало данной работы равно максимальному из ранних окончаний предшествующих:

.

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

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

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

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



То есть полный резерв времени работ, который можно вычислить по любой из двух формул

для критических работ будет равен нулю.

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

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

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



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

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

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

1.4.3 Вероятностная модель

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

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

Очевидно, что в данном случае на распределение длительности работ накладывается ряд ограничений. Это распределение должно быть неотрицательным, унимодальным, конечным и непрерывным[4].Для расчёта продолжительности используют так называемые «экспертные» оценки длительности:

- наиболее вероятная (в формулах - m);

- пессимистичная (в формулах - b);

- оптимистичная (в формулах - a).

На основе многочисленных исследований, отмеченных в [3, с. 8], определено, что в качестве закона распределения можно использовать бета-распределение, которое удовлетворяет всем указанным условиям.

Функция плотности бета-распределения определяется на отрезке следующим образом:

где гамма-функция определяется по формуле

Расчёт коэффициентов бета-функции б и впроизводится по следующим формулам.



где a - оптимистичная продолжительность работы,

b - пессимистичная продолжительность работы,

m - наиболее вероятная продолжительность работы.

Правила вывода формул (1.16) и (1.17) описаны в [22].Следует отметить, что средняя продолжительность работы является математическим ожиданием случайной величины «длительность работы» и вычисляется по формуле

Дисперсия оценки продолжительности работы определяется так:

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

Согласно [4], формулы (1.18) и (1.19) «носят полуэмпирический характер». Голенко-Гинзбургом в качестве альтернативы методам расчётаPERTбыла предложена модель на основе двух оценок, которая значительно упрощает процесс расчёта и имеет ряд преимуществ перед технологией PERT[4, с. 17], а статистический анализ проекта в этом случае показывает несущественные изменения.

Плотность распределения определена следующим образом:

средняя длительность работы:

дисперсия:

Некоторые авторы предлагают различные альтернативы методу PERT, например метод А. А. Мешкова[5].

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



Но величина не всегда удовлетворительна, поэтому дополнительно выбирают директивную продолжительность [14],и оценивают вероятность завершения работы до предписанного срока :

где - функция плотности,

-продолжительность критического пути,

- директивная длительность критического пути,

- оптимистичная (наименьшая) продолжительность критического пути.

PERT-анализ обладает рядом недостатков, из-за которых вместо него выбирают альтернативные решения. Среди недостатков метода:

- субъективная оценка продолжительности работ;

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

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

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



1.4.4 Альтернативные сетевые модели

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

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

Существует три типа входных функций, которые представлены в Таблица 5.

Таблица 5.Типы входных функций узла

Тип	Описание входной функции	Логическая характеристика	Графическое обозначение
1	Узел выполняется, если выполнены все дуги, входящие в него	«И»
2	Узел выполняется, если выполнена любая из дуг, входящих в него	«ИЛИ»
3	Узел выполняется, если в данный момент выполнена одна и только одна из дуг, входящих в него	Исключающее« ИЛИ»

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

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

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

- создание сетевой модели на основе качественного описания системы (проблемы);

- сбор данных, необходимых для описания каждой дуги сети;

- получение эквивалентной функции из одной дуги между двумя узлами сети;

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

- вероятность реализации каждого узла;

- функция времени в замещающей сети;

- оценка полученных в предыдущих пунктах результатов.

- Для этапов 3 и 4 можно привести обобщение на всю модель:

- минимизация построенной сети;

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

В GERT-анализе для описания стохастической сети достаточно использовать два типа узлов: с третьим типом входной функции и первым типом выходной, и с третьим типом входной функции и вторым типом выходной. При этом допускается использование первого типа входной функции, если в вершину входит лишь одна дуга. Обоснование данного ограничения приведено в [24].

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

Рис. 6. Последовательные узлы.

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

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

Рис. 7. Параллельные дуги

Формулы расчета параметров:



Если же вторая дуга имеет входную функцию «ИЛИ», то время для эквивалентной дуги будет вычисляться иначе:

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

Рис.8 Петля

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

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

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

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

Метод PERTболее гибкий, так как включает в себя оценки, получаемые из статистических данных, что приближает сетевую модель к реальности. Однако результаты PERT-анализа являются смещёнными, тогда какGERT-моделирование приводит к несмещённым оценкам [25].

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

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

Обзор программных средств показал, что существуют популярные программы (MicrosoftProject, SpiderProject, ProjectLibre, GanttPro, LucidChart, EDrawMax и др.), автоматизирующие вычисления для МКП, PERT, способные строить диаграммы Гантта и отображать сетевые графики, а также создаватьсопутствующую информацию по различным параметрам модели.При этом наблюдается дефицит программного обеспечения для расчётов альтернативных сетей.

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



2. Прикладные задачи с использованием альтернативных сетевых моделей

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

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

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

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

2.1 Задача анализа времени производственного процесса

В качестве первого примера рассмотрим комплекс работ в задаче анализа времени производственного процесса по изготовлению и контролю качества деталей, приведенную в [24, с. 57], и исследуем еепутем построения сетевой модели.

Постановка задачи.На производственыной линии изготавливается деталь. Предполагается, что изготовление занимает четыре часа. Перед началом отделочных работ 25% деталей не проходят проверку, и им может потребоваться доработка. Время проверки предполагается распределенным в соответствии с бета-распределением со средней продолжительностью в один час. Доработка занимает три часа, и 30% переработанных частей не проходят проверку во второй раз. Вторая проверка доработанныхдеталей также распределяется в соответствии с бета-распределением со средней продолжительностью в полтора часа. При этом время проверок варьируется от 0 до 5 часов.

Детали, не прошедшие проверку, утилизируются. Если деталь проходит одну из инспекций, она отправляется на отделку, которая занимает 10 часов в 60%случаев и 14 часов в 40%случаев. Окончательная проверка, которая занимает один час, исключает 5 процентов деталей, которые затем утилизируются.

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

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

Основные составляющие производства: изготовление детали, проверка, отделка. СРР для задачи 1 представлена иерархическая структура работ по производству детали.

Сетевая модель. Для создания сетевой модели построим таблицу процессов в которой в первом столбце стоит наименование выполняемой работы, во втором - код работы. В столбцах «Вероятность» и «Время» указаны соответствующие этим работам параметры: время выполненияв часах и вероятность выполнения.Записи «в1» и «в2»в графе «Время» обозначают вероятностное время, заданное с помощью бета-распределения со следующими параметрами:

для в1,

для в2.

Значения , и получены с помощью формул(1.18), (1.16) и (1.17) соответственно.

Таблица 6. Взаимосвязи работ при производстве деталей.

Наименование работы	Код работы	Вероятность	Время выпол., час.
Изготовление детали	0,1	1	4
Первичная проверка (неудачная)	1,2	0,25	в1
Первичная проверка (успешная)	1,5	0,75	в1
Доработка детали	2,3	1	3
Проверка доработанной детали (неудачная)	3,4	0,3	в2
Проверка доработанной детали (успешная)	3,5	0,7	в2
Отделка (медленная)	5,61	0,4	14
Отделка (быстрая)	5,62	0,6	10
Окончательная проверка (неудачная)	6,4	0,05	1
Окончательная проверка (успешная)	6,7	0,95	1

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

По построенной сетевой модели сразу же можно определить вероятности исходов «4» и «7» с использованием теорем сложения и умножения вероятностей.

Оптимизация. Теперь оптимизируем сеть с помощью описанных впункте1.4.4 преобразований. Во-первых, сократим параллельные дуги (5,6¹ и 5,6²), и элементарные последовательности из двух дуг (



Таблица 7. Элементарные преобразования в сетевой модели

Сокращаемые дуги	Изменяемые дуги	Полученные дуги	Вероятности	Время
5,6i	5,61	5,6	1	11,6
	5,62
0,1	1,2	0,2	0,25	4+в1
	1,5	0,5	0,75	4+в1
2,3	3,4	2,4	0,3	3+в2
	3,5	2,5	0,7	3+в2
5,6	6,4	5,4	0,05	12.6
	6,7	5,7	0,95	12.6

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

Рис. Промежуточный этап оптимизации

Вероятности выполнения конечных узлов получились равными ранее вычисленным в (2.1) и (2.2), что свидетельствует о правильной минимизации сети.Подставив вместо в1 и в2 соответствующее и просуммировав, получим усреднённую оценку времени достижения одного из конечных событий. Таким образом, среднее время изготовления качественной детали составляет ~16.21 часа или 16 часов 13 минут, а вероятность этого исхода составляет ~87.9%.



2.2 Задача разработки оборудования для высокотемпературных систем

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

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

Структурные компоненты проекта. Проект может включать в себя следующие работы:

- исследование применимости электрического контроллера;

- исследование применимости пневматического контроллера;

- разработка контроллера переменного тока;

- разработка контроллера постоянного тока;

- исследование оптимальной AC / DC интеграции;

- экономический анализ электрического контроллера;

- экономический анализ пневматического контроллера;

- написание отчета.

Как показал ход анализа,в данном случае иерархическая структура работ СРР не будет так информативна, как алгоритм реализации проекта. Поэтому вместо СРР необходимо построить блок-схему (Рис. 2.5).

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

В проекте определены следующие события:

- техническое обоснование показывает, что электрическое управление высокотемпературной системой возможно / невозможно(1);

- регулятор переменного тока сочтён подходящим / неподходящим(2);

- регулятор переменного тока сочтён подходящим / неподходящим(3);

- достигнута оптимальная интеграция цепей переменного и постоянного тока(4);

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

- пневматическое управление признано осуществимым / неосуществимым(6);

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

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

- проект завершился неудачно(8);

- проект завершился успешно(9).

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

- проект завершён(10).



Рис. 8. Блок-схема разработки и внедрения контроллера

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

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

В полученной сетирезультат проверки работ (1,2) и (1,3) объединены в узле «1'». Обозначение событий для удобства изменено. Неудача в разработке контроллера постоянного тока при удачной разработке контроллера переменноготока обозначена «2».Неудача в разработке контроллера переменного тока при удачной разработке контроллера постоянного тока обозначена «3». Неудача в разработке двух контроллеров обозначена «23». Событие, когда оба контроллера разработаны имеет обозначение «23».

Преобразования первого этапа.



Сокращаемые дуги / узлы	Изменяемые дуги	Полученные дуги	Вероятности	Время
23	1', 23	1',81	0.16	3
	23,8
23	1', 23	1',82	0.24	3
	23,8
23	1',23	1',83	0.24	3
	23,8
1',81 1',82 1',83	1',81	1',8	0.64	3
	1',82
	1',83
1',23	23,4	1',4	0.36	2
1',4	4,5	1',5	0.36	7
0,1	1,1'	0,1'	0.7	8
	1,6	0,6	0.3	5

Полученная после преобразований сеть представлена на следующей иллюстрации (Рис. 2.7. Сетевая модель после преобразований):

Рис. 9. Сетевая модель после преобразований

Преобразования второго этапа.

Сокращаемые дуги	Изменяемые дуги	Полученные дуги	Вероятности	Время
0,1'	1',5	0,5	0.252	15
	1',8	0,81	0.448	11
0,5	5,8	0,82	0.0756	16
	5,9	0,91	0.1764	16
0,6	6,7	0,7	0.15	10
	6,8	0,83	0.15	6
0,7	7,8	0,84	0.09	11
	7,9	0,92

Страница:

•  1 
•  2 

курсовая работа "Вероятностные сетевые модели" скачать

Подобные документы

• Классификация сетевых технологий

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

• Сетевое планирование

  Сущность и назначение сетевого планирования и управления. Порядок и правила построения сетевых графиков. Понятие о пути. Временные параметры сетевых графиков. Анализ и оптимизация календарных сетей. Реконструкция, ремонт действующих промышленных объектов.
  
  курсовая работа [249,8 K], добавлен 11.08.2014
  

• Сетевое планирование многоэтапных операций

  Анализ системы планирования в ОАО "Металлург", разработка мероприятий по совершенствованию данной системы. Изучение понятия сетевого планирования, его роли в системе управления предприятием. Правила построения сетевых графиков и возможности их применения.
  
  курсовая работа [72,1 K], добавлен 17.11.2011
  

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

  Сетевое планирование и управление (нахождение критического пути) в социально-экономических процессах. Разработка программного обеспечения "Сетевое планирование и управления". Нахождение критического пути, оптимизация модели сетевого планирования.
  
  курсовая работа [1,3 M], добавлен 03.03.2012
  

• Виды сетевых структур

  Сетевая организация как одна из современных форм организации. Сетевые организации и их отличительные черты. Эволюция сетевых организаций. Связи в сетевой организации. Виды сетевых организаций. Перспектива развития сетевых организаций в России.
  
  реферат [90,2 K], добавлен 19.05.2012
  

• Модели стратегий в современных сетевых организациях

  Сущность и эволюция сетевых организаций. Ключевые стратегии роста предприятия. Описание основных идей школ стратегий по Минцбергу. Решение задачи средствами MS Access по начислению заработной платы путем накопления сумм, касающихся отдельных работников.
  
  курсовая работа [2,5 M], добавлен 12.09.2010
  

• Виды исследования систем управления

  Задачи, классификация и характеристика видов исследования систем управления: прогнозирование, планирование, контроль и диагностика с целью разработки долгосрочных мероприятий по совершенствованию организации, ее структуры, методов и моделей управления.
  
  курсовая работа [1,5 M], добавлен 05.02.2011
  

• Планирование работы управления образования

  Управление образованием как компонент муниципальной системы. Планирование как функция управления. Структура и содержание планов районного управления образованием, сетевое планирование. Анализ практики планирования работы районного управления образования.
  
  дипломная работа [92,3 K], добавлен 19.01.2012
  

• Планирование и прогнозирование в общей теории систем

  Процесс исследования систем управления - прогнозного, проектного и планового. Создание новой и изменение существующей системы управления. Основные сходства и различия прогнозирования и планирования. Распространение автоматизированных систем управления.
  
  курсовая работа [45,5 K], добавлен 20.07.2015
  

• Сетевое планирование и управление в менеджменте

  Теоретическое изучение сетевого планирования и управления, определение его сущности, изучение основных элементов сетевой модели. Характеристика элементов, моделирование, анализ построения и расчет параметров, необходимость оптимизации сетевой модели.
  
  курсовая работа [35,9 K], добавлен 10.12.2010
  

Другие документы, подобные "Вероятностные сетевые модели"

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