Методические указания для студентов механико-математического факультета (стр. 1 )

Министерство образования Российской Федерации

РОСТОВСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙУНИВЕРСИТЕТ

, ,

,

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

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

по курсу «Методы оптимизации»

для дневного и вечернего отделений

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

И СМЕЖНЫЕ ВОПРОСЫ

Часть 6

Ростов-на-Дону

2000

Методические указания рекомендованы к печати заседанием кафедры исследования операций механико-математического факультета РГУ: протокол № 11 от 4 июля 2000 г.

ОГЛАВЛЕНИЕ

11. Сетевое планирование…………………...………………………………..5

11.1.Построение сетевой модели………………...………………….…...5

11.2. Наиболее ранний возможный срок появления события……...…10

11.3. Наиболее поздний допустимый срок наступления события…....13

11.4. Резерв времени и критический путь……………………………...14

11.5. Оптимизация комплекса работ…………………………………...19

Индивидуальные задания………………………………………………..….29

Приложение 1………………………………………………………………..31

Приложение 2………………………………………………………………..33

Литература…………………………………...………………………………34

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

11. СЕТЕВОЕ ПЛАНИРОВАНИЕ

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

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

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

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

4.  Предполагается, что начатая работа продолжается без перерыва до завершения.

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

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

11.1. Построение сетевой модели

Для полного описания проекта необходимо :

1.  Задать список работ, входящих в проект, S={s1,s2,…,sn}, и длительность их выполнения t(si).

2.  Задать для каждой работы siÎS список непосредственно предшествующих ей работ Г-1(si).

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

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

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

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

i-е событие должно произойти до начала работы А. Аналогично, j-е событие не может произойти до завершения работы А.

Отношение предшествования между узлами является транзитивным. Если i-е событие предшествует j-му событию, а j-е событие предшествует k-му событию, то i-e событие предшествует k-му событию:

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

Неправильное представление предшествования.	Сетевая модель с фиктивной работой.

 

Рис. 1. Рис. 2.

Допустим, например, что фрагмент сетевой модели, показанный на рис. 1, соответствует такой последовательности выполнения работ: работа G следует за работами В и С, и работа Е следует за работой В (но не за работой С)]. Очевидно, что тогда схема на рис.1 является неправильной, поскольку она показывает, что как работа G, так и работа Е следуют за работами С и В. Чтобы получить правильное представление, необходимо ввести фиктивную работу, продолжительность которой равна нулю. Фиктивная работа обозначена штрихпунктиром. Правильное представление дано на рис. 2, где через X обозначена фиктивная работа. При необходимости фиктивные работы могут использоваться для изображения соотношений между работами, которые невозможно представить другим способом. Введение в проект фиктивных работ - это прием, позволяющий показать требуемое соотношение без изменения фактической продолжительности проекта.

Для иллюстрации построения сетевой модели рассмотрим следующий пример.

Пример 1.

Требуется построить сетевой график проекта. Информация о проекте представлена в таблице 1.

Таблица 1.

Работа si	Продол-житель-ность работы	Непосред-твенно предшеству-ющие работы
Обозна-чение	Описание	t(si)	Г-1(si)
A	Закупка деталей для узла 1	6	Нет
B	Закупка деталей для узла 2	4	Нет
C	Закупка деталей для узла 3	9	Нет
D	Изготовление узла 1	7	A
E	Изготовление узла 2	8	B
F	Изготовление узла 4	6	D, E
G	Изготовление узла 3	10	C, D
H	Сборка	4	F, G
I	Проверка и испытание	3	H

Сетевой график, соответствующий проекту, изображен на рис.3. В нем буквами X и Y обозначены фиктивные работы, наличие которых здесь обязательно. Действительно, если убрать дугу X, то получим сеть для проекта, в котором работе G непосредственно предшествуют работы E, D,C. Однако, это не соответствует проекту, описанному в таблице 1. Аналогичный результат получим, исключив фиктивную дугу Y: работе F будут непосредственно предшествовать работы E, D,C.

Сетевой график для примера 1.

Рис. 3.

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

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

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

События сети на рис.3 имеют правильную нумерацию.

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

Алгоритм правильной нумерации событий.

1.  Начинаем просмотр сети с начального события (узла, для которого Г-1(si)=Æ ), которому присваиваем номер 1 и считаем событием 0-го ранга. Полагаем i =0, k0=0.

2.  Вычеркиваем все дуги, исходящие из событий i-го ранга. Если таких дуг нет, переходим к шагу 4.

3.  События s¢, для которых Г-1(s¢)=Æ , объединяем в группу событий (i+1)-го ранга и присваиваем им в произвольном порядке номера ki+1,ki+2,ki+3,…,ki+1. Увеличиваем i на единицу и переходим к шагу 2.

4.  Работа алгоритма завершена. ·

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

11.2. Наиболее ранний возможный срок появления события

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