СГУПС
,
МОДЕЛИ СЕТЕВОГО ПЛАНИРОВАНИЯ, АНАЛИЗА И УПРАВЛЕНИЯ
Методические указания и задания к курсу
«Математические методы и модели
в управлении»
Новосибирск
2011
УДК 658.012.2(084.21)(075.8)
Задания и методические указания предназначены для инженерных, экономических и других специальностей всех форм обучения с целью подготовки к практическим занятиям, выполнения контрольных работ и для использования в дипломном проектировании. Состав методических указаний полностью соответствует программе курса «Экономико-математические методы и модели в управлении», «Математика», «Информационные технологии в экономике».
Методические указания и задания рассмотрены и утверждены на заседании кафедры “Менеджмент на транспорте” 13 октября 2010 г..
Составители: доц., канд. экон. наук , доц.
Ответственный редактор: доцент кафедры “Менеджмент на транспорте”
Рецензент: докт. техн. наук, проф. кафедры “Высшая математика” СГУПС
© Сибирский государственный университет
путей сообщения, 2011
1 Сетевая модель и ее основные элементы
Сетевая модель представляет собой план выполнения некоторого комплекса взаимосвязанных работ (операций), заданного в специфической форме сети, графическое изображение которой называется сетевым графом (сетевым графиком). Существуют различные типы сетевых графов (СГ), но наиболее широкое применение получили так называемые вершинные и стрелочные графы.
Основными элементами стрелочного графа являются "работа" ("операция") и "событие". Различают несколько видов понятия "работа":
а) действительная работа — процесс, требующий затрат времени и ресурсов;
б) ожидание — процесс, который требует только затрат времени и не нуждается в использовании ресурсов (например, процесс сушки после покраски, твердение бетона и т. д.);
в) фиктивная работа (зависимость) — логическая связь между двумя или несколькими работами (событиями), не требующая затрат времени и ресурсов. Она указывает, что возможность одной работы непосредственно зависит от результатов другой. Действительная работа и ожидание в стрелочном сетевом графике отрабатываются сложной стрелкой, а фиктивная работа — пунктирной.
Событие — это момент времени, определяющий возможность осуществления начала или окончания данной работы или нескольких работ. Событие разграничивает работы плана. Оно является результатом выполнения предшествующей работы плана, а также необходимым условием начала последующей работы. Отсюда двойственный характер события: для всех непосредственно предшествующих ему работ оно является конечным, а для всех непосредственно следующих за ним — начальным. При этом предполагается, что событие не имеет продолжительности и свершается как бы мгновенно. На сетевом графике события изображаются кружками (вершинами графа). Среди событий сетевой модели выделяют два особых события: исходное и завершающее. Исходное событие не имеет предшествующих работ и является отдельным моментом начала работ. Завершающее событие не имеет последующих работ.
В вершинных сетевых графиках основным элементом является операция, представленная вершинами графа в виде прямоугольников. В качестве следующего элемента этого типа сетевых графов используются стрелки, показывающие зависимости между операциями, определяющие порядок их выполнения. Пример вершинного и стрелочного графов выполнения некоторого комплекса операций приведен на рис.1.
 |
В Е
А Б Д
Г
а) стрелочный граф
В
А Б Е
Г Д
б) вершинный граф
Рисунок 1. Пример вершинного и стрелочного графов выполнения некоторого комплекса операций
Сетевой график "работы–связи" в отличие от графика "события–работы" обладает известными преимуществами: не содержит фиктивных работ, имеет более простую технику построения и перестройки, включает только хорошо знакомое понятие "работа" без менее привычного понятия "событие".
Вместе с тем сети без событий оказываются значительно более громоздкими, т. к. событий обычно значительно меньше, чем работа (показатель сложности сети, равный отношению числа работ к числу событий, как правило, существенно больше единицы).
Поэтому эти сети менее эффективны с точки зрения управления комплексом. Этим и объясняется тот факт, что (при отсутствии в целом принципиальных различий между двумя формами представления сети) в настоящее время наибольшее распространение получили сетевые графики "событие–работа".
2 Порядок и правила построения сетевых графов
Первым шагом при составлении СГ является разбиение выполнения проекта на отдельные работы (операции), установление их логической взаимосвязи и взаимообусловленности.
При построении СГ необходимо соблюдать ряд правил:
1. Общее направление стрелок, отражающих работы (операции), должно быть слева направо, снизу вверх, сверху вниз.
2. СГ не должен иметь лишних пересечений стрелок.
3. В СГ не должно быть "тупиковых" событий (кроме завершающего, конечного), т. е. событий, из которых не выходит ни одна работа.
не верно верно
4. В СГ не должно быть "хвостовых" событий (кроме исходного, начального), которым не предшествует хотя бы одна работа.
не верно верно
 |
5. В СГ не должно быть замкнутых циклов, т. е. цепочек работ, которые возвращались бы к тому событию, из которого они вышли. Наличие таких циклов свидетельствует об ошибке в исходных данных или неправильном структурировании работ.
6. Если в СГ одно событие служит началом нескольких работ, заканчивающихся другим событием (т. е. при необходимости отобразить параллельные работы), то в этом случае вводится дополнительное событие и "фиктивная" работа.
не верно верно
7. В сети должно иметься одно исходное и одно завершающее событие.
8. При сложной взаимозависимости работ используются фиктивные работы.
а) Выполнению работы В предшествует окончание работы А, а выполнению работы Г — А и Б.
А В
Б Г
б) выполнению работы Г предшествует окончание работ А и Б, а выполнению работы Д — А и В.
Б Г
А
В Д
Пример 1.
На основе данных табл.1, отражающих последовательность выполнения операций построим стрелочный сетевой граф.
Таблица 1 - Исходные данные
Операция | А | Б | В | Г | Д | Е | Ж | З | И | К |
Непосредственно предшествующие операции | -== | А | А | Б | Б | Г | Д, Е | В, Г | Ж, З | З |
Операция А не имеет предшествующих, следовательно, она исходит из начального события. Операции Б и В зависят от окончания операции А.
Это показывается на графике следующим образом (рис.2).
Б
А В
Рисунок 2. Зависимость Б и В от А
Операции Г и Д имеют предшественником операцию Б, следовательно, они должны выходить из события, в которое входит операция Б (рис.3).
Д
А Б Г
В
Рисунок 3. Зависимость Д и Г от Б
Выполнение операции Е зависит от окончания операции Г. Операция З , в свою очередь, кроме операции Г зависит еще и от операции В. При подобной, сложной, взаимозависимости работ используем понятие "фиктивная работа" (рис.4). Действуя по аналогии, получим в итоге всех построений сетевой график.
 |
2 Д 5 Ж 7 И
Б
А Е
В З 6 К
4
Рисунок 4. Сетевой график задания
3 Упорядочение событий сетевого графа.
Под упорядочением событий итогового графа подразумевается нумерация, при которой для любой операции (работы) предшествующее ей событие расположено левее и имеет меньший номер по сравнению с завершающим эту работу событием. В качестве способа нумерации, обеспечивающего выполнение этого условия, можно использовать способ нумерации в зависимости от ранга события. При этом все события сетевого графа разделяются на ранги. К событиям одного ранга относятся такие, которые удалены от начального на одинаковое количество операций (работ), включая фиктивные. Так на рис. 5 событие нулевого ранга одно — № 0. Событие первого ранга № 1, второго — № 2, третьего — № 3. Событий четвертого ранга — два: № 4,5. Внутри одного ранга нумерация событий может быть произвольная, начиная с первого неиспользованного номера. Событие пятого ранга — № 6, шестого — № 7, седьмого — № 8. В результате подобной нумерации событий каждая операция получает код ( i-j ), где i — номер предшествующего операции события, j — номер последующего события.
4 Время выполнения операций
После того как структура сети точно установлена и изображена графически, необходимо получить оценки продолжительности каждой операции. Предположение о том, что эта величина может быть точно известна, в действительности выполняется редко, поскольку система сетевого планирования и управления (СПУ) обычно применяется для планирования проектов, не имевших в прошлом никаких аналогов. Чаще всего продолжительность операции по СГ заранее неизвестна и может принимать лишь одно из ряда возможных значений. Данная неопределенность сроков выполнения операций подвергает неопределенности общую продолжительность проекта. Выбор метода, позволяющего учесть эту неопределенность, зависит от типа проекта и природы неопределенности. Алгоритм, получивший наиболее широкое применение, называется методом оценки и пересмотра проектов (Project Evolution and Review Technique — PERT). При вычислении ожидаемого времени выполнения проекта этим методом используются показатели ожидаемого времени выполнения операций, которые являются случайными величинами, характеризующиеся своим законом распределения.
Практически во всех системах СПУ априори принимается, что распределение продолжительности работ обладает тремя свойствами:
а) непрерывностью;
б) унимодальностью, т. е. наличием единственного максимума у кривой распределения; в) двумя точками пресечения кривой распределения с осью ОХ, имеющими неотрицательные абсциссы.
Простейшим распределением с подобными свойствами является b–распределение, которое на основе анализа большого количества статистических данных (хронометраж времени реализации отдельных работ, нормативные данные и т. д.) можно использовать в качестве априорного для всех работ. Если это так, то распределение времени выполнения проекта в целом является нормальным.
Метод PERT может применяться при анализе конкретного проекта только в случае выполнения данной предпосылки.
Предположение о b–распределении продолжительности работы ( i–j ) позволяет получить следующие оценки ее числовых характеристик:
a) Среднее значение — ожидаемая продолжительность операции
(1)
где
t 0 ( i – j ) – оптимистическая оценка – минимально возможный период, в течение которого может быть выполнена данная операция (продолжительность операции при самых благоприятных условиях);
t HB ( i – j ) – наиболее вероятная оценка – наилучшая оценка периода времени, в течение которого может быть выполнена данная операция;
t n ( i – j ) – пессимистическая оценка – максимально возможный период времени, в течение которого может быть выполнена данная операция (время, которое потребовалось бы при самых неблагоприятных условиях).
Плотность
вероятности f(t)
 |
Срок выполнения
операции t
t0 tHB tn
Рисунок 5 Время и вероятность события
б) Дисперсия — мера степени неопределенности временных оценок операции
(2)
Пример 2:
На основе установленных временных оценок операций (табл. 2), определить ожидаемую продолжительность операций и степень неопределенности временных оценок.
Согласно формул (1,2) ожидаемая продолжительность операции
(0-1) составит:
недели,
а степень неопределенности временных оценок:
недель.
Результаты расчетов, произведенных аналогичным образом по всем операциям сетевого графа, приведены в табл.2.
Таблица 2 Результаты расчетов
Операция | Код операции | Срок выполнения операции, недель | s2 | |||
t 0 ( i – j ) | t HB ( i – j ) | t n ( i – j ) |
| |||
А | 0–1 | 3 | 4 | 5 | 4 | 4/36 |
Б | 1–2 | 2 | 2,5 | 6 | 3 | 16/36 |
В | 1–4 | 6,5 | 7 | 13,5 | 8 | 49/36 |
Г | 2–3 | 1 | 2 | 3 | 2 | 4/36 |
Д | 2–5 | 2,5 | 4,5 | 9,5 | 5 | 49/36 |
Е | 3–5 | 3 | 3,5 | 7 | 4 | 16/36 |
Ж | 5–7 | 1 | 1,5 | 5 | 2 | 16/36 |
З | 4–6 | 3 | 4,5 | 9 | 5 | 1 |
И | 7–8 | 2,5 | 3 | 9,5 | 4 | 49/36 |
К | 6–8 | 5 | 5,5 | 9 | 6 | 16/36 |
На основе полученных результатов можно сказать, что наибольшей неопределенностью временных оценок характеризуются операции В, Д, и И. Поэтому, при возможной оптимизации СГ необходим пересмотр временных оценок, что свидетельствует о высокой точности прогнозирования.
5 Анализ сетевого графа
5.1 Расчет временных параметров СГ
При анализе СГ особое значение занимает расчет временных параметров СГ (табл.3).
Таблица 3 Расчет временных параметров сетевого графика
Элемент сети, характеризуемый параметром | Наименование параметра | Условное обозначение параметра |
1. Событие 2. Работа 3. Путь | … … … |
Рассмотрим содержание и расчет указанных параметров.
1.Ранний срок Тр ( i ) наступления i-го события определяется продолжительностью максимального пути, предшествующего этому событию:
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 |
