МО практики

Строится функция Лагранжа

Ф( X ,λ )= X 1 + X 2 + λ ( X 12 + X 22 - 1 )

Строим систему уравнений

	∂Φ		= 1 + 2 λ X1 = 0 ,	∂Φ		= 1 + 2 λ X 2 = 0 ,	∂Φ	= X12 + X 22 - 1 = 0 ,
	∂ X	1		∂ X	2		∂ λ
решение которой дает λ = ±1/				2 ,	X1 = X 2 = −λ .

3.2.Задания для самостоятельной работы.

1)f (X ) = x12 − x22 при условии 2x − y =3 ;

2)f (X )= x1 + x2 + x3 при условии x1x2 x3 =1;

3)f (X )= x1 + x2 при условии x12 + x22 = 2;

4)f (X )= x1 + x2 при условии 2x12 + x22 = 6;

5)f (X )= x1 + x2 при условии 3x12 + x22 =12 ;

6)f (X )= x1 + x2 при условииx1x2 =1

31

4 Практическое занятие №4

Сетевая модель, расчет основных параметров сетевого графика. 4.1 Построение сетевого графика

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

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

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

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

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

Различают три вида операций:
1) действительная операция (	) – процесс, требующий затрат

времени и ресурсов (разработка проекта, подвоз материалов, выполнение

монтажных работ и т. д.);
2) операция - ожидание (	) – процесс, требующий только затрат

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

32

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

При построении сетевых графиков необходимо соблюдать определенные правила:

1)в сети не должно быть событий (кроме исходного), в которые не входит ни одна дуга;

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

3)сеть не должна содержать контуров;

4)любая пара событий сетевого графика может быть соединена не более чем одной дугой. Если изобразить одновременно выполняемые три различные операции b , c , d с общими начальным и конечным событиями (Рис. 4.1), то возникает путаница из-за того, что различные операции имеют одно и то же обозначение (2,5). В этом случае рекомендуется ввести дополнительные события и соединить их с последующими фиктивными операциями (Рис. 4.2);

b

2	c	5

d

Рис. 4.1

5) номер начального события любой операции должен быть меньше номера ее конечного события.

33

Для отражения технологической или ресурсной зависимости в выполнении операций применяют фиктивные операции. Предположим, что операция c может выполняться после завершения операций a и b , а операция d – только

после завершения операции	b.
	3
b
2	c	5

d

4

	Рис. 4.2
Эта зависимость представлена на Рис. 4.3, из которого видно, что операция
c следует за операцией a	и фиктивной операцией (2,З).
	3
a			c
1			4
b			d
	2

Рис. 4.3

В свою очередь, операция (2,3) следует за операцией b . Тогда в силу транзитивности выполнение операции b предшествует выполнению операции c .

34

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

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

детерминированными. В случае отсутствия нормативных временных оценок определяются вероятностные оценки.

После составления списка операций приступают к процедуре построения сети.

Приведем пример построения простого сетевого графика. Рассмотрим проект, представленный с помощью следующей таблицы:

Таблица 4.1.

Описание составных работ проекта

Раб	Непосредственно	Время выполнения
ота	предшествующие работы
A	---	tA
B	---	tB
C	B	tC
D	A, C	tD
E	C	tE
F	C	tF
G	D, E, F	tG
	35

Анализ данных, приведенных в этой таблице, последовательности и взаимозависимости работ, позволяет построить сетевой график представленный на рис. 4.4.

Рис. 4.4

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

4.2 Расчет временных параметров сетевого графика

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

36

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

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

Следующий за событием путь - путь от данного события до завершающего.

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

Рассмотрим процедуру расчета параметров сетевого графика.

Пусть продолжительности выполнения операций tij известны (Рис. 4.5;

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

сетевого графика. Исходное событие означает момент начала выполнения комплекса операций, следовательно, t1 = 0. Событие (2) свершится, очевидно,

спустя 2 ед. времени после свершения события (1), так как				время выполнения
операции (1,2) равно 2. Следовательно,			t2 = t1 +t12 = 0 + 2 = 2 . Событию (3)
предшествуют	два пути: µ1 = (1−3)	и	µ2 = (1− 2 −3) .	Продолжительность
первого пути	равна 1 ед. времени,	а	второго – 2 ед. времени, так как

t12 +t23 = 2 +0 = 2 . Продолжительность второго пути можно найти добавлением к ожидаемому сроку свершения события (2) времени выполнения операции

(2,3), т. е. t2 +t23 = 2 +0 = 2 .	Поскольку событие (3)	может свершиться не
раньше момента окончания	всех входящих в него	операций, то

37

t3 = max(t1 +t13;			t2 +t23) = max(0 +1; 2 +0) = 2.
		2(2)		4		8(8)
						5	3
		2
	2
					6
0(0)								7	11(11)
		1	3
1				2(2)	3
						4		1
				2
			3				6	5(10)
						1
					4
					4(5)

Рис. 4.5

В событие (4) входят две дуги, исходящие из событий (1) и (3), для которых ожидаемые сроки свершения найдены. Следовательно, ожидаемый срок свершения события (4)

t4 = max(t1 +t14;								t3 +t34 ) = max(0 +3; 2 +2) = 4 .
Аналогично находятся ожидаемые сроки свершения событий (5), (6) и (7).
Значения ti ,			i =					приписаны соответствующим событиям.
						1,7
Общая формула нахождения ожидаемых сроков свершения событий имеет
вид:
t1 = 0;
t	j	= max (t		i	+t		ij	), j = 2,3,....n,
		>
		{(i, j)}
где		>			–			подмножество дуг сети, входящих в событие ( j).
		{(i, j)}

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

38

операций, входящих в событие (7), tkp =11 определила операция (5,7),

выполнение которой начинается после свершения события (5) и продолжается

3 ед. времени (t5 +t57	= 8 +3 =11) . Момент свершения	события (5) определила
операция (3,5), так	как t2 +t35 = 2 + 6 = 8 . В свою очередь момент свершения
события (3) определила операция (2,3), а события		(2)	– операция (1,2). Эти
операции на рис. 4.6 выделены жирной линией. Таким			образом, критический

путь µkp = (1− 2 −3 −5 −7) . Увеличение времени выполнения любой операции,

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

Начало выполнения операции (4,7) может быть отсрочено на 3 ед. времени. Отсюда следует, что для события (4), не лежащего на критическом пути, существует предельный (поздний) срок свершения. Обозначим предельный срок свершения любого события сетевого графика через ti*, i =1, n . Примем, что ожидаемый и предельный сроки свершения завершающего события (n)

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

t* =t	;
n n
t* =min(t* −t ), i =
			1,n−1,
i	<	j ij
{(i,j)}
<		– подмножество дуг сети, исходящих из события (i) .
где {(i, j)}
		39

В нашем примере t7* = t7 =11. Определим этот показатель для оставшихся событий. Из события (5) исходит одна операция, следовательно, t5* = t7* −t57 =11−3 = 8. Аналогично t6* =t7* −t67 =10. Из события (4) исходят три операции, поэтому

t4* = min(t5* −t45; t6* −t46; t7* −t47 ) = min(8 −3; 10 −1; 11−4) = 5 .

Аналогично t* = 2,	t* = 2	и t* = 0	(на Рис. 4.4 предельные сроки
3	2	1

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

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

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

Ri = ti* −ti .

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

(tijр.н =ti ); поздний срок окончания операции совпадает с поздним сроком свершения ее конечного события (tijп.о =t*j ); поздний срок начала выполнения операции равен разности между предельным сроком свершения ее конечного события и продолжительностью (tijп.н =t*j −tij );ранний срок окончания операции равен сумме ожидаемого срока свершения ее начального события и продолжительности (tijр.о =ti +tij ).

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

40