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

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

 

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

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

 

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

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

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

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

Выполнил: Костарева Надежда     Группа: 15 ЭБС   - 201   Проверил:  Рольщиков В.Е.

 

 

 

 

 

 

 

 

 

Челябинск

2012

 

 

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

Таблица 1

Таблица 2

1	2	3	4	5	6	7	8	9	10	11	V1	V2	V3	V4	V5	V6	V7	V8	V9
	1	1	1								3	3	3	3	3	3	3	1	0
				1	1						2	2	2	2	2	1	0	Х	Х
	1		1								2	2	2	2	2	2	2	0	Х
					1	1					2	2	2	2	1	1	0	Х	Х
							1	1			2	2	2	1	0	Х	Х	Х	Х
				1		1					2	2	2	2	1	0	Х	Х	Х
								1	1		2	2	1	0	Х	Х	Х	Х	Х
								1		1	2	1	1	0	Х	Х	Х	Х	Х
									1	1	2	1	0	Х	Х	Х	Х	Х	Х
										1	1	0	Х	Х	Х	Х	Х	Х	Х
											0	Х	Х	Х	Х	Х	Х	Х	Х

 

Вычислим  столбец V₁, каждый элемент которого есть сумма по соответствующей строке элементов матрицы смежности и припишем этот столбец справа к матрице смежности. Столбец V1 имеет ноль в строке 11. Значит вершина 11 не имеет потомков и является завершающей. Вершину 11 поместим в слой номер 1. Нумерация слоев потом будет изменена, так как в рассматриваемом методе разбивка по слоям идет с конца. Далее вычислим столбец V₂ , вычитая из столбца V₁ столбец 11 матрицы смежности (столбец 11 соответствует вершине, вошедшей в первый слой). Столбец V₂ припишем справа к получившейся матрице. Строку 11 далее не рассматриваем. В столбце V₂ имеется единственный нулевой элемент в 10 - ой строке, значит вершина 10 образует слой номер 2. Столбец V₃ находим, вычитая из столбца V₂ столбец 10 матрицы смежности. В столбце V₃ нулевые элементы стоят в 9 строке, значит вершины под номерами 9 образуют третий слой. Не рассматривая далее 9 строку, вычтем из столбца V₃ 8 столбец матрицы смежности. Продолжая, аналогично находим столбцы V₄ - V₈ . Перенумеруем слои в обратном порядке (римскими цифрами).

 

 

 

 

       I  II        III  IV     V         VI VII   VIII  IX

 

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

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

t₃=t₁+t(1;3)=0+5=5

Переходим к слою III. В нем находится вершина 2 и 4, в которые входят по две дуги (1;2); (3;2) и (1;4); (3;4). Тогда вершина 2 может  быть выполнена за время

t₂=max{(t₁+t(1;2)),(t₃+t(3;2)}=max{(0+5),(5+7)}=12

t₄= max{(t₁+t(1;4)),(t₃+t(3;4)}=max{(0+5),(5+7)}=12

Аналогично  находим :

   - в IV слое  t₆= max{(t₂+t(2;6)),(t₄+t(4;6)}=max{(12+10),(12+4)}=22

   - в V слое    t₅= max{(t₂+t(2;5)),(t₆+t(6;5)}=max{(12+10),(22+6)}=28

   - в VI слое   t₇= max{(t₄+t(4;7)),(t₆+t(6;7)}=max{(12+4),(22+6)}=28

t₈= (t₅+t(5;8)=28+3=31

   - в VII слое  t₉= max{(t₅+t(5;9)),(t₇+t(7;9), (t₈+t(8;9)}=

=max{(28+3),(28+9),(31+2)}=37

   - в VIII слое; t₁₀= max{(t₇+t(7;10)),(t₉+t(9;10)}=max{(28+9),(37+8)}=45

   - в IX слое    t₁₁= max{(t₉+t(9;11)),(t₁₀+t(10;11)}=max{(37+8),(45+4)}=49

 

Итак, время  выполнения проекта равно 49. Величина называется ожидаемым временем наступления события i. Расчеты осуществляются от слоя к слою, т.к. ожидаемое время вершины (события) из данного слоя зависит от времен выполнения работ, заканчивающихся в вершине и ожидаемых времен выполнения вершин предыдущих слоев.

Теперь, двигаясь назад из завершающей  вершины, находим дуги, на которых  получилось время  . Эти дуги составят критический путь или критические пути, если их несколько. В нашем примере t₁₁=49 получилось на дуге (10;11), t₁₀=45 на дуге (9;10), t₉=37 на дуге (7;9), (1;3),(3;2),(2;6),(6;7),(7;9),(9;10),(10;11) входящие в критический путь также являются критическими. Любое замедление в выполнении критических работ или в наступлении критических событий приведет к соответствующему замедлению выполнения всего проекта. У событий и работ, не являющихся критическими, есть некоторый резерв.

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

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

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

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

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

для некритических ³ .

Определение 17. Интервал [ , ] называется интервалом свободы, а его длина R(i) = - . называется резервом времени события i.

 

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

=t₁₁=49 R(11)=0

=t₁₀=45 R(9)=0

=t₉=37 R(10)=0

=(8;9)=37-2=35 R=35-31=4

=t₇=28 R(7)=0

=min(t₉-t(4;7), t₈)=min(37-4),(31)=31 R(5)=31-28=3

=t₆=22 R(6)=0

=min(-t(6;7)(t₆-(3;2))=min((28-6)(22-7))=15 R(4)=15-12=3

=t₃=5 R=0

=t₂=12 R=0

2.3. Резервы времени  работ. Определим сначала ранние и поздние сроки начала и окончания работ.

Определение 17. Ранний срок (i,j) начала работы (i,j)  совпадает с ожидаемым временем наступления события i, т.е.

(i,j) = .

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

Определение 18. Ранний срок (i,j) окончания работы (i,j) определяется равенством

(i,j) = + t(i,j)

Определение 19. Поздний срок (i,j) окончания работы (ij) определяется равенством

(i,j) = .

 

 

 

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

Определение 20. Поздний срок (i,j) начала работы (i,j) задается равенством

(i,j) = - t(i,j)

Перейдем к резервам времени  работ.

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

Полный резерв определяется по формуле

(i,j)= - - t(i,j) .

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

Определение 22. Пусть событие i наступило в ожидаемое время . Тогда свободным резервом R_c(i,j) работы (i,j) называется часть полного резерва, на которую можно увеличить продолжительность работы, не изменяя при этом раннего срока ее конечного события j. R_c(i,j) = - - t(i,j) .

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

Определение 23. Независимым резервом R_н(i,j) работы (i,j) называется величина, на которую возможна задержка работы (i,j) при условии, что начальное событие i наступает в предельно позднее время , а конечное событие j в наиболее раннее время , т.е.

R_н(i,j) = max{0;

- - t(i,j)} .

Выражение для R_н(i,j) определяется через максимум, т.к. величина - - t(i,j) может оказаться отрицательной. Если у некоторой работы (i,j) независимый резерв времени больше нуля (R_н(i,j)>0), то, увеличивая длительность исполнения работы в пределах этого резерва, мы не изменим резервы времени у других работ и событий.

Определение 24. Частным резервом R₁(i,j) работы (i,j) называется часть полного резерва, на которую можно увеличить продолжительность работы (i,j) при условии, что начальное и конечное события наступают в свои самые поздние сроки и . R₁(i,j)= - - t(i,j)

Рассчитаем все резервы  для графа на рис.5 . Резервы всех видов для событий и работ, лежащих на критическом пути, равны нулю. Рассчитаем резервы для события 2 и работы (1,2). Имеем :

• _{интервал} свободы   [t₂, ] = [12,12], R(2)=0;

R_n (1,2) =-t₁ t(1,2)=12-0-5=7

R_c(1,2)=t₂-t₁-t(1,2)=12-0-5=7

R_н(1,2)=t₂--t(1,2)=12-0-5=7

R₁(1,2)=--t(1,2)=12-0-5=7

Резервы для  события 5 и работы (5,8). Имеем

R_n (5,8)=-t₅-t(5,8)=35-28-3=4

R_c(5,8)=t₈-t₅-t(5,8)=31-28-3=0

R_н(5,8)=min(0; t₈--t(5,8)=min(0;31-31-3)=0

R₁(5,8)=--t(5,8)=35-31-3=1

 

 

 

 

 

 

 

 

Аналогичные расчеты, проведенные для других вершин, сведены в таблицу

Работа	Интервал	R	Rп	Rc	Rн	R1
(1;2) (1;3) (1;4)	0 0 0		7 0 10	7 0 7	7 0 7	7 0 10
(2;5) (2;6)	0 0		9 0	6 0	6 0	9 0
(3;2) (3;4)	0 0		0 3	0 0	0 0	0 3
(4;6) (4;7)	[15;12]                    3 3		6 12	6 12	3 9	3 9
(5;8) (5;9)	[31;28]                    3 3		4 6	0 6	0 8	1 8
(6;5) (6;7)	0 0		3 0	0 0	0 0	3 0
(7;9) (7;10)	0 0		0 8	0 8	0 8	0 8
(8;9) (8;11)	[35;31]                    4 4		4 16	4 16	0 12	0 12
(9;10) (9;11)	0 0		0 4	0 4	0 4	0 4
[10;11]	0		0	0	0	0