Основы математического моделирования

социально-экономических процессов

 

Лекция 1

Тема лекции: «Сетевые модели планирования и управления»

1. Методы сетевого планирования и управления. Автоматизированное управление проектами.  

2. Математические основы сетевых моделей.

3. Параметры сетевых моделей и методы их расчета.

1. МЕТОДЫ СЕТЕВОГО ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ. АВТОМАТИЗИРОВАННОЕ УПРАВЛЕНИЕ ПРОЕКТАМИ.  

1.1.  Особенности математического моделирования социально-экономических процессов.

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

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

состоит в том, чтобы распределить дневное задание между  рабочими таким образом, чтобы это задание было выполнено. При распределении дневного задания между рабочими мастер должен учитывать их квалификацию, технические характеристики станков, на которых они работают. Попытаемся построить математическую модель деятельности производственного участка.  В такой модели в качестве переменных естественно взять число деталей каждого из типов, которые должен выпустить каждый из рабочих. В модели должны быть выделены операции,  необходимые для изготовления каждой детали, указана  производительность рабочих в каждой из операций, описана технологическая последовательность операции и т. д. Эта информация позволяет построить ограничения, которым должны удовлетворять задания. Полученные ограничения могут отражать, например,  необходимость выполнения каждым рабочим полученного им задания в течение смены и т. д. Если считать, что производительность рабочего в каждой из операций фиксирована заранее, то сформулированная модель будет описывать технологические ограничения, которым должна удовлетворять деятельность  производственного участка. С помощью этой модели для любого варианта распределения заданий, удовлетворяющего сформулированным технологическим ограничениям, можно подсчитать затраты времени на выполнение плана выпуска деталей, а также другие  показатели деятельности участка за день. Однако если нас заинтересует вопрос о том, какие результаты будут получены на участке в действительности, ответить на него с  помощью сформулированной модели окажется невозможно: обычно существует огромное число вариантов распределения  заданий, укладывающихся в технологические ограничения. Для  ответа на поставленный вопрос необходимо построить модель, описывающую принятие решения мастером, то есть модель, учитывающую его опыт, интересы и цели, связанные с руководством производственным участком. Можно было бы, конечно, выбрать такой вариант распределения заданий, который привел бы к  наиболее эффективной загрузке оборудования или к наискорейшему выполнению задания. Однако на практике такой вариант  распределения заданий мог бы не удовлетворить мастера. Дело в том, что операции делятся на «выгодные» и «невыгодные» в смысле их оплаты. Поэтому мастер обязан следить за тем, чтобы все  рабочие получили в итоге такую зарплату, которую и сам рабочий, и мастер считали бы «нормальной». Понятие «нормальной»  зарплаты формализовать трудно. Кроме того, неизвестно, желает ли мастер получить дополнительное задание, которое придется  выполнять после основного. Может быть, мастер опасается, что в случае слишком быстрого выполнения основного задания будут снижены расценки на выполняемые операции. Ответ на эти вопросы зависит уже не от технологических факторов производства, а от факторов социально-психологических и организационных, в частности, от системы стимулирования эффективности  производства.

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

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

 

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

 

1.2. Методы сетевого планирования и управления (СПУ).

 

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

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

Особенность систем СПУ заключается в том, что деятельность всех коллективов исполнителей рассматривается в целом как единый комплекс взаимосвязанных и взаимозависимых операций, на­правленных на достижение общей конечной цели. Здесь исполь­зуется информационно-динамическая модель особого вида, так называемая СЕТЕВАЯ МОДЕЛЬ ЛОГИКО-МАТЕМАТИЧЕСКОГО ОПИСАНИЯ, позволяющая алгоритмизировать расчеты параметров этого процесса: продолжительности, трудоемкости, стоимости и т.д. Сис­темы рассчитаны на использование компьютерных систем обра­ботки исходных и оперативных данных для расчета контролируе­мых показателей и получения необходимых аналитических и отчетных сводок.

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

Методы сетевого планирования и управления (СПУ) концентрируют внимание руководителей на самых важ­ных работах комплекса, отсеивая второстепенные. Так, при сло­жившихся методах управления в поле зрения руководителя обычно находится до 70% работ, что, безусловно, затрудняет принятие им эффективных решений. Разработка СПУ позволила устано­вить, что практически лишь около 10% работ от всего комплекса существенно влияют на ход выполнения работ. При этом время, затрачиваемое руководителями на решение вопросов управле­ния, сокращается на 50-60%. Кроме того, все участники работ находятся в объективно равных условиях осведомленности, что оказывает влияние на успех завершения всего комплекса работ в намеченные сроки. В зависимости от масштаба проекта (комплекса работ) различают следующие системы СПУ:

 

- большие  – разра­ботки с числом событий в сети 10,5 тыс. – 12 тыс.;

- средние  – от 1,5 тыс. до 10 тыс.;

-  малые   –  до 1,5 тыс.

 

Преимущества методов сетевого планирования и управления (СПУ) заключаются в следующем.  Методология сетевого планирования и управления:

 

а) концентрирует внимание руководителей на небольшом числе работ и исполнителей;

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

в) позволяет в любой момент времени получать исчерпы­вающую информацию о проекте;

г) обеспечивает непрерывность управления ходом работ, своевременность принятия решений, оперативность вмешатель­ства;

д) позволяет рационально маневрировать выделенными ре­сурсами;

е) дает большую экономию времени, средств, энергии, мате­риалов и т.д.;

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

з) является теоретической основой автоматизированного управления проектами.

 

Работы по использованию и развитию СПУ ведутся с середины 20-го столетия и  получили широкое распро­странение в нашей стране и за рубежом; уже накоплен большой опыт и сложилась своя ис­тория. Первоначально методология СПУ была разработана в 1956 г. специалистами фирм «Дюпон» и «Ремингтон Ред» М. Уолкером и Д. Келли для проекта по модернизации заводов фирмы «Дюпон». Впечатляющим результатом ее использования является проектирование корпорацией «Локхид» ракетной системы «Поларис» для оснащения подводных лодок ВМС США В результате применения методов сетевого планирования работы были выполнены на два года раньше намеченного срока! При разработке ракетного вооружения «Поларис» в США был разработан метод PERT. В конце 50-х годов двадцатого столетия в США была разработана система CRM — метод критического пути — для управления строительны­ми работами. В России работы по применению методов и моделей СПУ начались с 1961 г. В процессе развития методов СПУ появились различные це­левые системы: ПУСК – планирование и управление созданием корабля; СУР — система управления разработками; АСОР — авто­матизированная система организации работ; ЦПК — централизо­ванное планирование и контроль и др. Одним из примеров успешного применения методов СПУ в России является использование данного метода при восстановлении храма Христа Спасителя в Москве.

 

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

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

 

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

 

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

 

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

 

 

1.3. Автоматизированное управление проектами.

 

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

 

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

 

1. Стандарт, разработанный Институтом управления проектами (Project Management Institute) принят в качестве национального стандарта в США (стандарт ANSI).
2. Стандарт по качеству в управлении проектами ISO 10006.

 

 

Отметим некоторые наиболее популярные системы управления проектами, теоретическим фундаментом которых являются методология сетевого планирования и управления (СПУ).

 

1. Управление проектами в среде Microsoft Оffice Project – комплексное решении корпорации Microsoft по управлению корпоративными проектами, которое позволяет управлять проектами любой сложности.

 

2. Spider Project Professional   –  пакет управления проектами, спроектированный и разработанный с учетом практического опыта, потребностей, особенностей и приоритетов российского рынка.

 

3. Программные продукты компании Primavera Inc:

 

Primavera Project Planner Professional – профессиональная версия, предназначенная для автоматизации процессов управления проектами в соответствии с требованиями PMI (Project Management Institute) и стандартами ISO. В первую очередь этот пакет предназначен для использования в составе корпоративной информационной системы, хотя вполне может работать и автономно, помогая решать задачи календарно-сетевого планирования, определения критического пути, выравнивания ресурсов, и других задач моделирования проектов, групп проектов, портфелей и программ.

 

Sure Track Project  Manager – этот пакет ориентирован на контроль выполнения небольших проектов или фрагментов крупных проектов.  Данный пакет может работать как самостоятельно, так и совместно с Project Planner в корпоративной системе управления проектами.

 

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

 

 

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

 

1. Создать иерархическую структуру работ (укрупненно описать проект).
2. Задать, какие составляющие стоимости будут использованы для финансового анализа и управления проектом.
3. Составить перечень операций (работ, задач) проекта и задать их характеристики.
4. Составить перечень ресурсов проекта и задать их характеристики.
5. Задать взаимосвязи (ограничения на порядок исполнения) операций проекта.
6. Назначить ресурсы на исполнение операций проекта.
7. Назначить стоимости операциям, ресурсам и назначениям проекта.
8. Задать ограничения на финансирование, поставки, сроки исполнения операций.
9. Составить расписание исполнения работ проекта с учетом всех ограничений.
10. Оптимизировать состав используемых ресурсов.
11. Определить бюджет и распределение во времени плановых затрат проекта.
12. Определить и промоделировать риски и неопределенности.
13. Определить необходимые резервы, стоимости и потребности в материалах для исполнения запланированных показателей с заданной надежностью.
14. Представить плановую информацию руководству и исполнителям.

В процессе исполнения проекта эти автоматизированные системы позволяют:

 

- вести учет;

- анализировать отклонения исполнения от запланированного;

- прогнозировать будущие параметры проекта;

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

- вести архивы проекта.

 

2.  МАТЕМАТИЧЕСКИЕ ОСНОВЫ СЕТЕВЫХ МОДЕЛЕЙ.

 

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

 

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

 

Основу научной дисциплины, называемой теорией  графов,  составляет совокупность  методов и представлений, сформировавшихся при решении конкретных задач. Теория графов зародилась в восемнадцатом столетии  в  городе  Кенигсберге (в настоящее время – город Калининград),  жителей которого интересовал вопрос: можно ли в их городе совершить прогулку по замкнутому маршруту, проходя по каждому из семи мостов один и только один раз?  Известный математик Леонард Эйлер математически сформулировал  и решил эту задачу. В девятнадцатом столетии в Англии возникла другая трудноразрешимая математическая  задача, имеющая прямое отношение к теории графов. Это задача о четырех красках: достаточно  ли четырех цветов для такой раскраски карты, нанесенной на плоскость или сферу, чтобы на ней не оказалось двух смежных областей одинакового цвета? Эта задача впоследствии была решена. В двадцатом столетии  теория графов прошла определенные стадии формирования и после 1930 г.  была признана самостоятельной дисциплиной.

 

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

 

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

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 1. Граф.

 

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

 

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

 

Граф называется связным, если любая пара его вершин связана (рис. 2).

 

 

 

 

 

 

 

 

 

 

Рис. 2. Связный граф.

 

Граф, изображенный на рисунке 3, несвязен.

 

 

 

 

 

 

 

 

 

 

Рис. 3. Несвязный граф.

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 4. Цепь.

 

Цепь, начальная и конечная вершины которой совпадают, называется циклом (рис. 5).

 

 

 

 

 

 

 

 

 

 

Рис. 5. Цикл.

 

Вершина называется четной, если в ней сходится четное число ребер, и нечетной, если число всех сходящихся в ней ребер нечетно.

Вершина A на рисунке 6 четна — в ней сходятся 4 ребра, а вершина B нечетна — в ней сходятся 5 ребер.

 

 

 

 

 

 

 

 

 

 

 

Рис. 6. Четные и нечетные вершины графа.

 

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

 

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

ТЕОРЕМА (Эйлер). В любом конечном связном графе, все вершины которого четны, существует цикл, в котором каждое ребро графа участвует ровно один раз.

Такой цикл называют эйлеровым циклом, а граф, все вершины которого четны (и, значит, существует эйлеров цикл), — эйлеровым графом.

 

 

Важный класс графов составляют так называемые деревья.

 

Деревом называется связный граф, который не имеет циклов (рис. 7).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 7. Дерево.

 

Число B вершин дерева и число P его ребер различаются на единицу: B = P+1.

 

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

 

Если на каждом ребре задается направление (т.е. каждая пара вершин, соединенная ребром, упорядочена), то граф называется ориентированным, в противном случае – неориентированным.

 

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

 

 

3.      ПАРАМЕТРЫ СЕТЕВЫХ МОДЕЛЕЙ И МЕТОДЫ ИХ РАСЧЕТА.

3.

 

3.1. Основные понятия сетевой модели.

 

Основой сетевой модели проекта (комплекса операций) является сетевой график (или просто сеть), который дает наглядное представление о проекте. Сеть состоит из  множества вершин (узлов) и множества ребер (дуг, звеньев),  соединяющих различные пары вершин. На каждом ребре (дуге, звене) может быть задано определенное направление (ориентация). На сетевом графике  вершины сети изображаются кружками, а ребра — линиями, их  соединяющими. Таким образом, СЕТЕВОЙ ГРАФИК ПРЕДСТАВЛЯЕТ СОБОЙ ГРАФ ВИДА «СЕТЬ».

 

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

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

 

ОСНОВНЫЕ ПОНЯТИЯ СЕТЕВОЙ МОДЕЛИ: СОБЫТИЕ, РАБОТА И ПУТЬ.

 

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

 

 

                    1

 

 

                      5                                               3                         4               6

 

            6                4                                      9                                             9

 

 

                    3              6                                               3                     5

 

7

 

                                 4                    0              

 

 

 

 

Рис. 8. Графическое представление сетевой модели (СМ).

 

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

 

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

 

Каждая работа имеет определенную продолжительность t (i,j). Например, запись t (2,5) = 4 означает, что работа (2,5) имеет продолжительность 4 единицы (например, время выполнения – 4 дня).

 

К работам относятся также  такие процессы, которые не требуют ни ресурсов, ни времени выполнения. Они заключаются в установлении логической взаимосвязи работ и показывают, что одна из них непосредственно зависит от другой; такие работы называются фиктивными и на графике изображаются пунктирными стрелками (см. рис. 8,  работа (6,7)).

 

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

 

СОБЫТИЕ СВЕРШАЕТСЯ В ТОТ МОМЕНТ, КОГДА ОКАНЧИВАЕТСЯ ПОСЛЕДНЯЯ ИЗ РАБОТ, ВХОДЯЩАЯ В НЕГО.

 

События обозначаются одним числом и при графическом представлении СМ изображаются кружком (или иной геометрической фигурой), внутри которого проставляется его порядковый номер (i = 1, 2, ..., N).

 

В сетевой модели (СМ) имеется начальное событие  (с номером 1), из которого работы только выходят, и конечное  событие (с номером N), в которое работы только входят.

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

 

 

Например, в  приведенной выше сетевой модели (рис. 8) путями являются:

L1 = (1, 2, 3, 8, 10, 11), L2 = (1, 2, 5,10, 11) и др.

 

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

 

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

 

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

 

Их несвоевременное выполнение ведет к срыву сроков всего комплекса работ.

Перед расчетом СМ следует убедиться, что она удовлетворяет следующим основным  требованиям.

 

ОСНОВНЫЕ ТРЕБОВАНИЯ,  ПРЕДЪЯВЛЯЕМЫЕ К СЕТЕВЫМ МОДЕЛЯМ.

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

- нумерация событий начинается с исходного события, которому присваивается № 1;

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

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

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

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

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

4. Отсутствуют циклы, т. е. замкнутые пути, соединяющие  событие с ним же самим.

 

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

 

3.2. Основные характеристики сетевой модели.

 

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

 

1)      Для событий рассчитывают три характеристики: ранний и поздний сроки совершения события, а  также его резерв.

1)

Ранний срок tр (j) свершения j-го события определяется величиной наиболее длительного отрезка пути от исходного до рассматриваемого события, причем  

t^р. (1) = 0, t^р. (N) = tкр = t(Lкр):

t^р. (j) = max _i {t^р. (i)+t (i,j)}; j=2, …, N.         (1)

 

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

t^п. (i) =  min _j {t^п. (j)   –  t (i, j)};  i= 2, …, N – 1. (2)

 

Этот показатель определяется «обратным ходом», начиная  с завершающего события, с учетом соотношения t^п. (N) = t^р. (N).

Все события, за исключением событий, принадлежащих критическому пути, имеют резерв R(i)> 0:

R(i) = t^п. (i) – t^р. (i).              (3)

 

 

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

 

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

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

2)

Ранний срок начала работы (i,j):      t^р.н. (i,j) =  t^р. (i);                             (4)

 

Ранний срок окончания работы (i,j):   t^р.о.  (i,j) =  t^р. (i) + t (i,j);              (5)

 

Поздний срок окончания работы (i,j):      t^п.о. (i,j) =  t^п. (j);                     (6)

 

 

Поздний срок начала работы (i,j):   t^п.н.  (i,j) =  t^п. (j) – t (i,j);                  (7)

 

Полный резерв времени работы (i,j):  R^п. (i,j) = t^п. (j) – t^р. (i)  – t(i,j);        (8)

 

Независимый резерв времени  работы (i,j):

R^н. (i,j)  = max{0; t^р. (j) – t^п. (i) – t(i,j)} =  max {0; R^п. (i,j) – R(i) – R(j)}. (9)

 

 

Полный резерв времени работы (i,j) – это максимальное время, на которое можно отсрочить начало или увеличить время выполнения работы t(i,j)без изменения общего срока выполнения всего комплекса работ. 

 

Другими словами, R^п. (i,j) показывает, на сколько можно увеличить время выполнения конкретной работы при условии,  что срок выполнения всего комплекса работ не изменится.

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

3)      Путь L_П характеризуется двумя показателями — продолжительностью и резервом.

 

Продолжительность t(L_П) пути L_П определяется суммой продолжительностей составляющих его работ.

Полный резерв R(L_П) времени пути L_П определяется как разность между длинами критиче­ского и рассматриваемого путей:

R(L_П)= t(Lкр) –  t(L_П).

 

 

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

 

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

3.3. Таблица расчета основных показателей сетевой модели.

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

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

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

Кпр	(i,j)	t(i,j)	tрн (i,j)=tр(i)	tро (i,j)	tпн (i,j)	tпо(i,j)=tп(j)	Rп	Rн
№1	№2	№3	№4	№5	№6	№7	№8	№9
0	(1,2)	6	0	6	0	6	0	0
1	(2,3)	5	6	11	12	17	6	0
1	(2,4)	3	6	9	6	9	0	0
1	(2,5)	4	6	10	11	15	5	5
1	(3,8)	1	11	12	17	18	6	0
1	(4,5)	6	9	15	9	15	0	0
1	(4,6)	4	9	13	17	21	8	0
1	(4,7)	7	9	16	14	21	5	0
2	(5,9)	3	15	18	17	20	3	0
2	(5,10)	9	15	24	15	24	0	0
1	(6,7)	0	13	13	21	21	8	0
1	(6,11)	5	13	18	28	33	5	0
2	(7,10)	3	16	19	21	24	5	0
1	(8,10)	6	12	18	18	24	6	0
1	(9,10)	4	18	22	20	24	2	0
4	(10,11)	9	24	33	24	33	0	0

 

Рис. 9. Таблица расчета основных показателей сетевой модели.

 

Перечень работ и их продолжительность запишем во второй и третий столбцы таблицы.  При этом работы следует последовательно записывать во втором столбце: сначала записывают работы, начинающиеся с номера i=1, затем с номера i=2 и т.д.

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

Например, для работы (5,9) в первом столбце  поставим цифру 2, так как во втором столбце  на номер 5 оканчиваются две работы: (2,5) и (4,5).

Для заполнения четвертого столбца таблицы необходимо рассчитать ранние сроки начала работ tрн (i,j) = tр (i) по формуле (4).

 

Для заполнения пятого столбца таблицы необходимо рассчитать ранние сроки окончания работ tро (i,j) = tр (i) + t (i,j) по формуле (5).

 

1. Для работ, имеющих цифру «ноль» в первом столбце, в 4-м столбце также заносятся нули:

tрн (1,j) = tр (1) = 0. Затем по формуле (5) в 5-й столбец записываем сумму tро (1,j) = tрн (1,j) + t (1,j).

В нашем случае только одна работа (1,2) имеет цифру «ноль» в первом столбце. Для нее в 4-м столбце записываем цифру «0», в 5-м столбце записываем сумму: 0 +  t (1,2) = 0 + 6 = 6.

 

2. Для работ, начинающихся с номера 2, для заполнения 4-го столбца просматриваем уже заполненные строки в 5-м столбце, содержащие работы, оканчивающиеся  на номер 2;  среди них находят максимальное значение  max _i {tрo (i,2)}; в силу формул (1) и (5) имеем:

t рн (2,j) = tр (2) =  max _i {tрo (i,2)}.

То есть в соответствующие строки четвертого столбца  для всех работ, начинающихся на номер 2, переносим цифру 6, взятую из 5-го столбца (так как имеется единственная работа (1,2), которая оканчивается на номер 2, и для нее в 5-м столбце мы уже вычислили tро (1,2) = 6). Таким образом,

tрн (2,3) = 6;

tрн (2,4) = 6;

tрн (2,5) = 6.

Затем для этих работ заполняем соответствующие строки 5-го столбца:

tро (2,3) = tрн (2,3) + t (2,3) = 6 + 5 = 11;

tро (2,4) = tрн (2,4) + t (2,4) = 6 + 3 = 9;

tро (2,5) = tрн (2,5) + t (2,5) = 6 + 4 = 10.

 

То есть эти значения  в столбце 5 получаются в результате суммирования соответствующих значений, стоящих в столбцах 3 и 4, согласно формулам (4) и (5).

 

3. Для работ, начинающихся на номер 3, для заполнения 4-го столбца, просматриваем в 5-м столбце работы, оканчивающиеся на номер 3.  В нашем случае таких работ только одна — (2, 3), мы видим, что tро (2,3) = 11.  Поэтому в 4-м столбце для работ, начинающихся на номер 3, проставляем число 11. Работ, которые начинаются на номер 3, у нас только одна – (3,8). Таким образом,

tрн (3,8) = 11.

 

Соответственно, tро (3,8) = 11 +1 = 12.

 

4. Работ, которые начинаются на номер 4, у нас три: (4,5), (4,6) и (4,7).

Находим работы, которые оканчиваются на номер 4;  такая у нас одна – (2,4). Для нее в 5-м столбце уже вычислено значение tро (2,4) = 9. Поэтому, в силу формул (1), (4), (5) имеем:

 tрн (4,5) = 9;

tрн (4,6) = 9;

tрн (4,7) = 9.

 

Поэтому   в силу формул (4), (5) находим:

tро (4,5) = 9 + 6 = 15 ;

tро (4,6) = 9 + 4 = 13;

tро (4,7) = 9 + 7 = 16.

 

5. Рассматриваем работы, которые начинаются на номер 5: (5,9) и (5,10). 

Находим работы, которые оканчиваются на номер 5: (2,5) и (4,5). Для этих работ в 5-м столбце мы уже вычислили tро (2,5) = 10 и  tро (4,5) = 15. Выбираем среди этих чисел 10 и 15 максимальное, то есть 15 и записываем это число в 4-й столбец для работ (5,9) и (5,10):

tрн (5,9) = 15;

tрн (5,10) = 15.

 

 

Поэтому   в силу формул (4), (5) находим:

tро (5,9) = 15 + 3 = 18 ;

tро (5,10) = 15 + 9 = 24.

 

Аналогично, заполняем оставшиеся строчки в 4-м и 5-м столбцах для работ (6,7), (6,11), … (10, 11).  Этот процесс повторяем до тех пор, пока не будет за­полнена последняя строка в столбцах 4-м и 5-м таблицы.

Столбцы 7 и 6 заполняются «обратным ходом», т. е. снизу вверх.

 

Для этого мы просматриваем строки, оканчивающиеся на номер последнего события; затем из столбца 5 выбираем макси­мальное значение, которое записываем в столбец  7 по всем строкам, оканчивающимся на номер последнего события.

 

В нашем случае таких работ две (6,11) и (10, 11): tро (6,11) = 18, tро (10,11) = 33. Число 33 записываем в столбец 7 для всех работ, оканчивающихся на номер 11.  то есть для работы (10,11), согласно формуле tп (N) = tр (N).  Затем для этих строк находим значение в столбце 6 как разность между значениями из 7-го столбца и 3-го столбца согласно формулам (6), (7):

t пн (i, j) = =  tП (j) – t (i,j) =  tпо (i,j) – t (i,j).

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

t пн (6,11) =  tпо (6,11) – t (6,11) = 33 – 9 = 24.

t пн (10,11) =  tпо (10,11) – t (10,11) = 33 – 5 = 28.

 

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

 

Для определения значений в 7-м столбце для этих строк (работы (5,10), (7,10), (8,10), (9,10)) просматриваем все строчки в столбце 6, лежащие ниже и начинающиеся с номера 10.

Среди них выбирается минимальное значение из столбца 6, которое переносится в столбец 7 по рассматриваемым  строкам.  В нашем случае она одна — (10,11), поэтому заносим во все строки указанных работ число  «24».  Процесс повторяется до тех пор, пока не будут заполнены все строки по столбцам 6 и 7.

Значения в строках столбца 8 вычисляются как разности  между соответствующими значениями в строках столбцов 6 и 4 (или столбцов 7 и 5), согласно формуле (8), с учетом формул (7) и (6).

 

Столбец 9 проще получить, воспользовавшись формулой (9), учитывая (8).

Например,  Rн (2,5) = max {0; Rп(2,5) – R(2) – R(5)}. Вычисляем:

 

Rп(2,5) – R(2) – R(5) = Rп(2,5) – (tп (2) – tр (2)) – (tп (5) – tр (5)) = Rп(2,5) + tр (2) + tр (5) – tп (2)  - tп (5) = 5 + 6 + 15 – 6 – 15 = 5.

Тогда Rн (2,5) = max {0; Rп(2,5) – R(2) – R(5)}  = max {0, 5} = 5.                          

 

Аналогично рассчитываем остальные элементы столбца 9.

 

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

Lкp = (1,2,4,5,10,11), tкp = 33 дня.

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

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

 

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

 

где t (Lmax) — длительность максимального из некритических путей, проходящих через работу  (i,j);

t`кр — продолжительность части критических работ, входящих в рассматриваемый путь Lmax.

 

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

 

В нашем примере  для работ критического пути (1,2), (2,4), (4,5),(5,10),(10,11) коэффициент напряженности К^н. = 1.

 

На основе этого коэффициента К^н. все работы сетевой модели могут быть разделены на три группы:

-  напряженные (K^н. (i,j) > 0,8);

-  подкритические (0,6 ≤  K^н. (i,j) ≤ 0,8);

- резервные (K^н. (i,j) < 0,6).

 

В результате перераспределения ресурсов, используя методы оптимизации, стараются МАКСИМАЛЬНО УМЕНЬШИТЬ ОБЩУЮ ПРОДОЛЖИТЕЛЬНОСТЬ РАБОТ, ЧТО ВОЗМОЖНО ПРИ ПЕРЕВОДЕ ВСЕХ РАБОТ В ПЕРВУЮ ГРУППУ.

3.3. Сетевое планирование в условиях неопределенности.

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

 

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

 

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

 

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

 

Такие оценки называются вероятностными (случайными), и их ожидаемое значение tож.(i,j)  оценивается по формуле:

tож.(i,j)  = (3 t_min(i,j) + 2 t_max (i,j))/5.

Для характеристики степени разброса возможных значений вокруг ожидаемого уровня используется показатель дисперсии S²:

S² (i,j) = (t_max(i,j) – t_min (i,j))² / 5² = 0,04 (t_max(i,j) – t_min (i,j))² .

 

 

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

Кроме обычных характеристик СМ, при вероятностном  задании продолжительности работ можно решить две дополнительные задачи:

1) определить вероятность того, что продолжительность  критического пути t_кp. не превысит заданного директивного  уровня Т;

2) определить максимальный срок выполнения всего  комплекса работ Т при заданном уровне вероятности р.

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

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

 

[1] Исследование операций. В 2-х томах. Т.1.  Методологические основы и математические методы. –  Под ред. Дж. Моудера, С. Элмаграби. –  Пер. с англ. – М.: Мир, 1981. – 712 с., ил.

 

[2] Фомин Г. П. Математические методы и модели в коммерческой дея­тельности: Учебник. — 2-е изд., перераб. и доп. — М.: Финан­сы и статистика, 2005. — 616 с: ил.

[3] Шелобаев С. И. Математические методы и модели в экономике,  финансах, бизнесе: Учеб. пособие для вузов. — М.: ЮНИТИ- ДАНА, 2001. - 367 с.

 

[4] Шикин Е. В., Чхартишвили А. Г. Математические методы и модели в управлении: Учеб. пособие. — 3-е изд. — М.: Дело, 2004. — 440 с. — (Сер. "Классический университетский учебник").

 

[5] Экономико-математические методы и прикладные модели: Учебное пособие для вузов/ В.В. Федосеев, А.Н. Гармаш,  Д.М. Дайитбегов и др.; Под ред. В.В. Федосеева. — М.:  ЮНИТИ, 1999. - 391 с.