Сетевые модели в инновационных проектах

МОСКОВСКИЙ УНИВЕРСИТЕТ МВД РОССИИ им. В.Я. КИКОТЯ РЯЗАНСКИЙ ФИЛИАЛ Кафедра экономической безопасности КОРОЛЕВ Г. И. МАТЕМАТИКА ЭКОНОМИКО – МАТЕМАТИЧЕСКИЕ МОДЕЛИ Тема 33. СЕТЕВЫЕ МОДЕЛИ В ИННОВАЦИОННЫХ ПРОЕКТАХ Лекция по курсу « МАТЕМАТИКА» Для специальности 38.05.01– Экономическая безопасность Рязань - 2017 СОДЕРЖАНИЕ Введение……………………………………………………………. 1. Основные понятия и определения сетевых моделей………….. 2. Последовательность и правила построения сетевого графика……………………………………………………………. 3. Временные характеристики сетевого графика и их расчет……………………………………………………………… 2 3 6 9 Введение Сетевое моделирование, как новая форма анализа, планирования, управления и контроля, начало интенсивно развиваться в конце 40-х - начале 50-х годов прошлого века. Это было связано с началом научно-технической революции, с необходимостью разработки и реализации крупных военных и экономических проектов, требовавших значительного времени и больших финансовых и материальных затрат. Это опытно-конструкторские и научноисследовательские работы по проектам ракетно-ядерного вооружения, проекты строительства крупных предприятий, гидроэлектростанций и пр. Неоценимую услугу ученым и конструкторам оказали сетевые модели при реализации советских космических программ и осуществлении крупнейших строек Сибири и Дальнего Востока. Сетевые модели хорошо себя зарекомендовали при минимизации стоимости различных комплексов взаимосвязанных работ, поисках кратчайших маршрутов при существующей сети дорог, для минимизации стоимости транспортировки различных грузов и при решении других задач. Особое значение сетевое моделирование приобретает при разработке и внедрении различных инновационных проектов. Сферы применения сетевых моделей непрерывно расширяются и в настоящее время они используются везде, где необходимо оптимальное планирование и эффективный контроль над проведением сложных комплексов взаимосвязанных мероприятий, в том числе и в правоохранительной сфере при проведении крупных административных и специальных мероприятий, при внедрении новых систем информационного обеспечения и др. 1. Основные понятия и определения сетевых моделей. Для построения сетевых моделей используется специальный математический аппарат, с помощью которого осуществляется управление комплексами мероприятий, направленных на достижение строго определенных целей. В сетевом моделировании объединяются графическое изображение модели (сете2 вой график) и аналитические методы расчета параметров модели. Особенностью этих моделей является присутствие в них времени, как основного параметра. Поэтому главная задача сетевого моделирования состоит в определении временных характеристик взаимосвязанных мероприятий: когда каждое мероприятие следует начинать, а когда завершать, каким резервом времени обладает каждая операция, в течение какого времени будет завершен весь комплекс мероприятий и т. д. Параллельно с этим решаются вопросы рационального распределения по проводимым мероприятиям различных ресурсов – материальных, финансовых, трудовых и других. Основными в сетевых моделях являются понятия события и операции (работы). Операция – это действие, которое необходимо выполнить для достижения определенного результата, а сам результат, полученный в итоге выполнения одной или нескольких операций, называют событием. Таким образом, сетевой график – это графическое изображение последовательностей операций и событий в соответствии с их логической взаимосвязью. На сетевых графиках события обозначаются небольшими кружочками, а операции – стрелками (рис. 1). Внутри круга проставляется номер события, а шифр операции определяется номерами событий, которыми начинается и заканчивается операция. Например, шифр операции 3-5 означает, что она начинается после наступления события 3 и завершается наступлением события 5. В сетевых моделях различают три вида операций. К первому типу относятся реальные мероприятия (действия), для осуществления которых необходимы затраты времени и ресурсов. Например, разработка плана проверки объекта, подготовка информации, закупка специальной техники, ремонтностроительные работы. Операции этого типа обозначаются на сетевом графике сплошными линиями. 3 3-5 Реальная операция 5 Рис. 1. К понятию событий и операций сетевого графика. Ко второму типу относятся так называемые операции-ожидания, требующие только затрат времени и не требующие затрат каких-либо ресурсов. Они характерны для различных технологических процессов производства (естественная сушка материалов, затвердевание бетона и пр.) и в правоохранительных органах встречаются в основном в процессе делопроизводства (документы «отлеживаются») и в практике служб тылового и хозяйственного обеспечения. На сетевом графике операции – ожидания обозначаются штрих пунктирными линиями (рис. 2.). 3 4 6 5 Операция - ожидание Рис. 2. Обозначение операции – ожидания. Третий тип составляют фиктивные операции, не требующие ни затрат времени, ни затрат ресурсов. Они указывают на логическую взаимосвязь событий, их зависимость одного от другого. Фиктивные операции обозначаются на сетевом графике пунктирными линиями (рис. 3.). 5 4 Фиктивная операция 7 6 Фиктивная операция Рис. 3. Обозначение фиктивных операций. Событие, как результат одной или нескольких операций, не имеет продолжительности и наступает только тогда, когда завершены все предшествовавшие ему операции. Если событие наступило, то могут быть немедленно начаты последующие операции. Существуют шесть разновидностей событий (см. рис. 4). Исходное событие это событие, не имеющее в данной сетевой модели предшествующих операций. С исходного события начинается сетевой график и в любой сетевой модели существует только одно исходное событие (на рис. 4 это событие 1). Завершающее событие это событие, не имеющее в данной сетевой модели последующих операций. Оно является конечной целью выполнения всего комплекса мероприятий. В сетевой модели может быть одно или несколько завершающих событий. В случае нескольких завершающих событий сетевая модель называется многоцелевой. Завершающим на рис.4 является событие 7. Промежуточное событие это любое событие, заключенное между исходным и завершающим событиями. Каждое из них является результатом выполнения одной или нескольких операций, и его наступление дает возможность начать выполнение последующих операций. На рис. 4 промежуточными являются события 2, 3, 4, 5 и 6. 4 Начальное событие это событие, которое непосредственно предшествует началу какой-либо операции. Если таких операций несколько, то это событие является начальным для всех них. Например, на рис. 4 событие 2 является начальным для операции 2 – 5, событие 4 – начальное для операций 4 – 5 и 4 – 6, а событие 1, являясь исходным, одновременно является начальным для операций 1 – 2 и 1 – 3. 2-начальное событие для операции 2-5 5-конечное событие для операций 2-5 и 4-5 2 5 2-4 - фиктивная операция 1-исходное событие 1 1-2-реальная операция 4 4-промежуточное событие 3 7 – завершающее 7 событие 6 3-6 – операция-ожидание 6-промежуточное событие Рис. 4. Разновидности операций и событий. Конечное событие это событие, которое непосредственно следует за данной операцией. Оно наступает только после завершения всех операций, для которых является конечным. Например, на рис. 4 событие 5 является конечным для операций 2 – 5 и 4 – 5, а событие 7, являясь завершающим, одновременно является конечным для операций 5 – 7 и 6 – 7. Смежные события это два события, связанные операцией. На рис. 4, например, смежными являются события 1 и 2, 3 и 4, 5 и 7 и т. д. Понятие смежных событий позволяет так определить символьное обозначение операций: шифр (символьное обозначение) операции соответствует номерам ее смежных событий. Очень важными для сетевого графика являются понятия путь и критический путь. Путем называют любую последовательность операций между исходным и завершающим событиями. Например, на рис. 4 последовательность операций (1–2) → (2–5) → (5–7) является путем. Путем является также и последовательность операций (1 – 3) → (3 – 4) → (4 – 6) → (6 – 7) и другие, включая пути через фиктивные операции и операции-ожидания. Критический путь это путь, имеющий наибольшую продолжительность по времени. Эту продолжительность называют длиной критического пути. Она характеризует продолжительность по времени всего комплекса мероприятий. Длина критического пути и совокупность входящих в него операций составляют основу для оптимизации разрабатываемых планов, координации и контроля за ходом мероприятий, поскольку на критическом пути лежат те операции, от которых зависят сроки выполнения всего комплекса мероприятий. 5 Знание критического пути позволяет руководителю выделить главное в комплексе мероприятий, сосредоточить основное внимание на критических операциях и усилить контроль за их выполнением. Управление комплексом мероприятий становится более конкретным и эффективным. 2. Последовательность и правила построения сетевого графика Моделирование начинается с тщательного анализа предстоящего комплекса мероприятий: устанавливается желательный срок завершения всего комплекса мероприятий; составляется перечень операций, необходимых для достижения цели; анализируется желательная и требуемая последовательность и параллельность выполнения операций. В результате анализа составляется полный перечень событий и операций, устанавливается последовательность их выполнения и продолжительность каждой операции. По результатам анализа и составленному перечню операций строится сетевой график. Если комплекс мероприятий очень сложен, сначала строятся первичные сетевые графики: общий перечень операций разбивается на группы, для каждой группы операций строится свой сетевой график, а затем все графики «сшиваются» в один. При построении общего сетевого графика происходит уточнение перечня событий и операций, выявляются излишние или недостающие звенья. Так в процедурах сетевого моделирования появляются первые корректирующие обратные связи, образующие локальные циклы моделирования. Составленный сетевой график рассчитывается вручную, если он содержит немного операций, скажем, 20-25 или на компьютере. В результате расчета находят ранние и поздние сроки наступления событий, начала и окончания операций, а также резервы времени для событий и операций. Результаты расчета анализируются как по временным характеристикам, так и по требуемым ресурсам, уточняется сам сетевой график. Уже на этом этапе, не прибегая к специальным методам оптимизации, можно найти возможности для сокращения общего времени проведения всего комплекса мероприятий или для более равномерного распределения ресурсов. Оптимизация сетевой модели может осуществляться по различным критериям: минимизации стоимости всего комплекса мероприятий при сохранении общего времени проведения операций; минимизации по времени при возможно меньшем увеличении стоимости проведения операций и т. д. Операции могут быть так распределены по времени проведения, что будет обеспечен расход ресурсов, не превышающий установленного уровня. На основе характеристик оптимальной модели составляется календарный план-график, в котором для каждого мероприятия определяется уже конкретный календарный срок его проведения. Затем формируются текущие планы мероприятий с указанием требуемых ресурсов и конкретных исполнителей. Планы доводятся до исполнителей и ставятся руководителем на контроль. Тщательное построение сетевого графика практически исключает пропуски операций, полнее показывает их взаимную увязку и сравнительную зна6 чимость. Такое целостное представление о плане мероприятий позволяет руководителю объективно проанализировать последовательность действий, оценить, почему на осуществление какого-либо мероприятия требуется именно столько времени, почему оно не может быть реализовано сразу и т. д. Разработка сетевого графика не представляет большой трудности, если хорошо изучены содержание и объем предстоящих операций. Но нужно иметь в виду, что существуют определенные правила построения графиков, нарушать которые нельзя. Они состоят в следующем. 1. Два смежных события могут быть связаны между собой только одной операцией. Часто при изображении параллельно выполняемых операций два смежных события ошибочно связывают двумя и более операциями (рис. 5,а). В этом случае одинаковый шифр имеют несколько операций, что вносит путаницу в расчет графика. Для правильного изображения параллельно выполняемых операций в график вводят дополнительные события и фиктивные работы. На рис. 5,б изображены уже четыре события вместо двух, завершающим является событие 4, а операции 2–4 и 3–4 являются фиктивными. 2 1 2 1 4 3 а) неправильно б) правильно Рис. 5. Правило смежных событий. 2. В сетевом графике не должно быть ни одного события, кроме исходного, которому не предшествовала хотя бы одна операция (рис. 6,а). Появление таких событий в графике возможно в результате каких-либо упущений при анализе комплекса мероприятий, когда часть операций оказывается не предусмотренной. В этом случае перечень операций уточняется и ошибка исправляется. Во многоцелевых графиках возможны случаи, когда комплекс мероприятий начинается с нескольких событий. Тогда одно из событий принимается за исходное, а другие связываются с ним фиктивными операциями (операция 1–2 на рис. 6,б). 2 2 3 1 5 3 1 5 4 4 а) неправильно б) правильно Рис. 6. Правило одного исходного события. 7 3. В сетевом графике не должно быть ни одного события, кроме завершающего, после которого не следует ни одной операции (событие 4 на рис. 7, а). Появление таких «тупиков» возможно из-за простой ошибки при построении графика либо в результате того, что операция 2–4 не нужна и ее необходимо убрать. Также может быть не замечена необходимость в последующей после события 4 операции. Во многоцелевых графиках такие события соединяются с завершающим событием фиктивной операцией (рис. 7, б). 4 2 1 2 5 4 5 1 3 3 а) неправильно б) правильно Рис. 7. Правило одного завершающего события. 4. Любая операция на сетевом графике обязательно должна начинаться после какого-либо события. На рис. 8,а операция, завершающаяся событием 2, не имеет начального события. Его необходимо ввести (событие 2 на рис. 8,б), разделив прежнюю операцию 1-3 на две. 1 3 1 2 4 3 2 а) неправильно б) правильно Рис. 8. Правило обязательности начального события. 5. Любая операция на сетевом графике обязательно должна заканчиваться событием. На рис. 9,а операция после события 2 не заканчивается другим событием, поэтому в график необходимо ввести дополнительное событие (событие 3 на рис. 9,б), которое делит прежнюю операцию 1-3 на две. 1 3 1 2 3 2 а) неправильно б) правильно Рис. 9. Правило обязательности конечного события. 8 4 6. На сетевом графике не должно быть замкнутых контуров (рис. 10, а и б). Такие ошибки обычно возникают при изображении графиков, в которых повторяются одноименные работы, например, цикличность операций при выработке решений, согласовании, уточнении и т. д. Не зря среди бюрократов бытует фраза: «Бумага пошла по кругу». Разработчик сетевого графика в данном случае путает пространственные (возвращение к тому же лицу или в то же подразделение) и временные характеристики комплекса мероприятий. Чаще всего оказывается, что возникающие по этой причине замкнутые контуры преобразуются в простую последовательность операций (рис. 10, в). 1 2 2 1 1 2 3 3 а) неправильно б) неправильно в) правильно Рис. 10. Правило недопустимости замкнутых контуров. При построении сетевого графика важно правильно пронумеровать события. Правильной является такая нумерация, при которой каждая операция начинается с события с меньшим номером (выходит из события с меньшим номером), а заканчивается событием с большим номером (входит в событие с большим номером). Другими словами, в шифре операции «а - b» должно соблюдаться условие b > a, где a – номер начального, а b - номер конечного для данной операции события. После анализа всего комплекса предстоящих операций и определения событий сетевого графика для его построения составляется таблица, в которой в первой строке указываются операции, а во второй – их продолжительности в днях или неделях. Таблица 1 Пример исходных данных для построения сетевого графика Операции 1-2 1-3 2-3 2-4 2-5 3-4 3-6 4-5 4-6 4-7 5-7 6-7 Продолжи – 5 8 6 8 10 12 9 6 7 14 5 10 тельность, дни 3. Временные характеристики сетевого графика и их расчет Все операции, входящие в сетевой график, имеют определенную продолжительность. Существуют три способа установления продолжительности операций: а) по действующим нормативам; б) по аналогии с ранее выполнявшимися операциями подобного типа; в) на основе мнения специалистов, то есть методом экспертных оценок. 9 Для сложного комплекса впервые выполняемых мероприятий обычно используют третий метод. Специалисты (эксперты) дают каждой операции три оценки продолжительности: tmin – минимальное время выполнения операции (оптимистическая оценка); tmax – максимальное время выполнения операции (пессимистическая оценка); tвер – наиболее вероятное время выполнения операции. По этим оценкам рассчитывается ожидаемое время выполнения операции: t min  4tвер  t max tож  6 Если оценка наиболее вероятного времени выполнения операции затруднена, ожидаемое время рассчитывается по двум оценкам: tож  3tmin  2tmax 5 Продолжительность выполнения каждой операции (в неделях или в днях) проставляется на сетевом графике над стрелкой, обозначающей эту операцию, и используется для расчета характеристик всего графика. Часто под стрелкой, обозначающей операцию, проставляют объем (величину) используемого для этой операции ресурса: количество исполнителей, стоимость выполнения операции и др. Чтобы не путать с продолжительностью операции, величину используемого ресурса указывают в круглых скобках (рис. 11). Продолжительность операции 12 4 (4) Объем ресурса 5 Рис. 11. Обозначения продолжительности и ресурса операции. Как уже говорилось, перед построением сетевого графика составляется перечень операций. Его не следует слишком детализировать, усложняя график, но нельзя и неоправданно укрупнять операции, так как операции, имеющие значительную продолжительность, трудно контролировать. Опыт использования сетевых моделей показывает, что в сетевую модель целесообразно включать операции продолжительностью не менее 3-х дней и не более 40 дней. Операции продолжительностью менее 3-х дней следует укрупнять, а операции продолжительностью более 40 дней необходимо делить на отдельные этапы с четкими промежуточными событиями для улучшения контроля за их выполнением. 10 Рассчитать параметры сетевого графика значит найти время наступления каждого события и резервы времени для событий и операций. При расчете учитываются два свойства сетевых графиков: а) любое из событий сетевого графика может наступить только тогда, когда завершены все предшествующие ему операции; б) любая операция, следующая за каким-либо событием, может быть начата только тогда, когда это событие произойдет. 1.Ранние сроки наступления событий. Для любого события существует минимально необходимое время для того, чтобы оно наступило. По первому свойству сетевых графиков это время определяется наиболее продолжительными операциями, предшествующими этому событию. Другими словами, поскольку к событию могут вести несколько путей, ранний срок наступления события это путь наибольшей длины от исходного события до данного. Ранние сроки рассчитываются по формуле: Tp(j) = max[Tp(i) + t i-j ], где i и j - смежные события; Tp(j)–раннее время (ранний срок) наступления события j; Tp(i) раннее время (ранний срок) наступления события i; t i-j – продолжительность операции (i - j); При наличии нескольких предшествующих событий, смежных с событием j, в скобках расчетной формулы находится столько сумм, сколько есть смежных событий, и из всех сумм выбирается максимальная. Полезно запомнить, что каждое событие имеет столько предшествующих ему смежных, сколько в него «входит» стрелок. Расчет ранних сроков осуществляется от исходного события к завершающему, то есть от начала графика к его концу. Для исходного (первого) события ранний срок его наступления всегда принимается равным нулю: Tp(1) = 0. Ранний срок наступления завершающего события называют критическим временем сетевого графика. Оно определяет продолжительность (длину) критического пути. 2. Поздние сроки наступления событий. Поздний срок наступления любого события определяется величиной пути минимальной продолжительности, ведущего к нему от завершающего события. Поздние сроки рассчитываются от конца сетевого графика к его началу, то есть от завершающего события к исходному. Для завершающего события полагают, что поздний срок его наступления равен раннему сроку его наступления. Расчет осуществляется по формуле: Tп(i) = min [Tп(j) – ti-j] В формуле в скобках за словом min записывается столько разностей, сколько событие i имеет последующих смежных событий. Для Tп(i) выбирается минимальное из значений этих разностей. Следует помнить, что любое событие имеет столько последующих смежных событий, сколько стрелок из него 11 выходит. Равенство нулю позднего времени наступления исходного события указывает на правильность расчета параметров графика. Для каждого события разность между поздним и ранним сроками его наступления называется резервом времени: R(i) = Tп(i) - Tр(i) События, для которых резерв времени равен нулю, лежат на критическом пути. Каждая операция имеет свое раннее и позднее время начала и окончания. Их расчет прост и понятен, если обратиться к рис. 12., где события i и j соединены операцией продолжительностью ti-j. Tp(i) Tп(i) ti-j Tp(j) i Tп(j) j Рис. 12. К расчету ранних и поздних сроков операций. 3.Раннее время начала операции. Операцию (i-j) можно начать в ее ранний срок только тогда, когда в свой ранний срок наступит предшествующее ей событие i. Таким образом, tрн(i-j) = Tp(i). 4.Позднее время начала операции. Этот срок необходимо определить так, чтобы операция (i-j) завершилась в поздний срок наступления последующего, j-го события c учетом продолжительности операции: tпн(i-j) = Tп(j) – ti-j. 5.Раннее время окончания операции. Раннее время окончания операции равно: tро(i-j) = Tp(i) + t(i-j) = tрн(i-j) + t(i-j). 6. Позднее время окончания операции. Этот срок должен соответствовать позднему времени наступления последующего события: tпо(i-j) = Tп(j). По рассчитанным временным характеристикам работ рассчитываются их резервы времени, используя которые можно регулировать как продолжительность всего комплекса мероприятий, так и использование выделенных кадровых, финансовых или материальных ресурсов. 12