Методы оптимальных решений

МИНОБРНАУКИ РОССИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ  ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ 
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ЧЕЛЯБИНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

ФАКУЛЬТЕТ ЗАОЧНОГО И ДИСТАНЦИОННОГО ОБУЧЕНИЯ

КАФЕДРА МАТЕМАТИЧЕСКИХ МЕТОДОВ В  ЭКОНОМИКЕ

 

 

КОНТРОЛЬНАЯ РАБОТА

 

 

 

 

Направление «Экономика» Дисциплина «Методы  оптимальных решений»   Оценка

Выполнил: Группа: Проверил:  Рольщиков  В.Е.

 

 

 

 

 

 

 

 

Челябинск

2012

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

18. t(0,1)=5, t(0,2)=6, t(0,3)=3, t(1,3)=6, t(1,4)=5, t(2,3)=3, t(2,5)=6, t(3,5)=6, t(3,6)=1, t(4,3)=3, t(4,6)=3, t(4,7)=5, t(5,6)=3, t(5,8)=5, t(6,7)=3, t(6,8)=6, t(7,8)=3.

Решение:

В таблице 1 выписаны работы (дуги) и время их выполнения. В первую очередь, необходимо составить  и упорядочить сетевой график. Составим матрицу смежности (первые 8 столбцов таблицы 2, вместо нулей оставлены пустые места). Вычисление элементов столбцов V₀,...,V₇ будет описано ниже.

Таблица 1

Работа (i, j)	Время вып tij	Работа (i, j)	Время вып tij
(0; 1)	5	(3; 6)	1
(0; 2)	6	(4; 3)	3
(0; 3)	3	(4; 6)	3
(1; 3)	6	(4; 7)	5
(1; 4)	5	(5; 6)	3
(2; 3)	3	(5; 8)	5
(2; 5)	6	(6; 7)	3
(3; 5)	6	(6; 8)	6
		(7; 8)	3

 

Таблица 2

	0	1	2	3	4	5	6	7	8	V0	V1	V2	V3	V4	V5	V6	V7
0		1	1	1						3	3	3	3	3	2	1	0
1				1	1					2	2	2	2	2	1	0	х
2				1		1				2	2	2	2	1	0	х	х
3						1	1			2	2	2	1	0	х	х	х
4				1			1	1		3	3	2	1	1	0	х	х
5							1		1	2	1	1	0	х	х	х	х
6								1	1	2	1	0	х	х	х	х	х
7									1	1	0	х	х	х	х	х	х
8										0	х	х	х	х	х	х	х

  

Вычислим столбец V0, каждый элемент которого есть сумма по соответствующей строке элементов матрицы смежности и припишем этот столбец справа к матрице смежности. Столбец V0 имеет ноль в строке 8. Значит вершина 8 не имеет потомков и является завершающей. Вершину 8  поместим в слой номер 1. Нумерация слоев потом будет изменена, так как в рассматриваемом методе разбивка по слоям идет с конца. Далее вычислим столбец V1 , вычитая из столбца V0 столбец 8 матрицы смежности (столбец 8 соответствует вершине, вошедшей в первый слой). Столбец V1 припишем справа к получившейся матрице. Строку 8 далее не рассматриваем. В столбце V1 имеется единственный нулевой элемент в 7 - ой строке, значит вершина 7 образует слой номер 2. Столбец V2 находим, вычитая из столбца V1 столбец 7 матрицы смежности. В столбце V2 имеется единственный нулевой элемент в 6 - ой строке, значит вершина 6 образует слой номер 2. Столбец V3 находим, вычитая из столбца V2 столбец 6 матрицы смежности.. Получим столбец V3 . Продолжая, аналогично находим столбцы V4 – V7 . Перенумеруем слои в обратном порядке (римскими цифрами). Граф в

соответствии со слоями изображен  на рис. 1 .

  

 

 

 

 

  I          II                III               IV                     V                  VI                  VII               VIII

 

 

рис.1

 

 

 

Найдем критический  путь.

Начнем с  вычисления ожидаемого времени выполнения событий. Процесс вычисления будет идти по слоям от I-го к VIII .

В слое I находится  единственная вершина 0. Ей присваиваем время t₀=0, это начало выполнения проекта. Переходим к слою II. В этом слое также одна вершина 1, в которую входит единственная дуга (0;1). Следовательно, вершина 1 может быть выполнена за время

.

Переходим к  слою III. В нем находится две вершины, вершина 2 и 4. Вершина 2 может быть выполнена за время

t₂ = t₀ + t(0,2) = 0 + 6 = 6.

Вершина 4 может быть выполнена  за время:

t₄ = t₁ + t(1,4) = 5 + 5 = 10.

в IV слое:

t₃ = max {t₀ + t(0,3); t₁ +  t(1,3); t₄ + t(4,3); t₂ + t(2,3)} = max {3, 11, 13, 9} = 13

в V слое:

t₅ = max {t₂ + t(2,5); t₃ + t(3,5);} = max {12, 19} = 19

в VI слое:

t₆ = max {t₃ + t(3,6); t₄ + t(4,6); t₅ + t(5,6)} = max {14, 13, 22} = 22

в VII слое:

t₇ = max {t₄ + t(4,7); t₆ + t(6,7)} = max {15, 25} = 25

в VIII слое:

t₈ = max {t₇ + t(7,8); t₆ + t(6,8); t₅ + t(5,8)} = max {28, 28, 24} = 28

Время окончания  проекта равно 28.

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

Значит, критический  путь будет проходить по дугам:

 (7,8), (6,7), (5,6), (3,5), (4,3), (1,4), (0,1)

Выпишем в обратном порядке:

(0,1), (1,4), (4,3), (3,5), (5,6), (6,7), (7,8) – критический путь

Вычислим  резервы событий и работ.

Пусть T(i) -самое большое время на всевозможных путях из вершины i в завершающую вершину п. Тогда предельное время наступления события i определяется равенством

Для каждого  события i есть два граничных срока:

время  - ожидаемое время наступления события i;

время   - предельное время наступления события i.

Для критических  событий имеет место равенство   = ,  для некритических ³ .

Вычислим граничные  сроки     и резервы времени R(i) , двигаясь по слоям от последнего к начальному:

Видим, что не имеют резервов времени события 0, 1, 4, 3, 5, 6, 7, 8, которые и образуют критический путь.

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

Определим все  резервы событий и работ по формулам:

Ранний срок начала работы .

Ранний срок окончания работы .

Поздний срок окончания  работы .

Поздний срок начала работы .

Полный резерв работы .

Свободный резерв работы .

Независимый резерв работы .

Частный резерв работы .

 

Результаты  расчетов  запишем в  табл. 3

Работа	Время t(i,j)	Ранний срок начала	Ранний срок окончания	Поздний срок окончания	Поздний срок начала	Полный резерв	Свобод. резерв	Независимый резерв	Частный резерв
(0,1)	5	0	5	5	0	0	0	0	0
(0,2)	6	0	6	10	4	4	0	0	4
(0,3)	3	0	3	13	10	10	10	10	10
(1,3)	6	5	11	13	7	2	2	2	2
(1,4)	5	5	10	10	5	0	0	0	0
(2,3)	3	6	9	13	10	4	4	0	0
(2,5)	6	6	12	19	13	7	7	3	3
(3,5)	6	13	19	19	13	0	0	0	0
(3,6)	1	13	14	22	21	8	8	8	8
(4,3)	3	10	13	13	10	0	0	0	0
(4,6)	3	10	13	22	19	9	9	9	9
(4,7)	5	10	15	25	20	10	10	10	10
(5,6)	3	19	22	22	19	0	0	0	0
(5,8)	5	19	24	28	23	4	4	4	4
(6,7)	3	22	25	25	22	0	0	0	0
(6,8)	6	22	28	28	22	0	0	0	0
(7,8)	3	25	28	28	25	0	0	0	0