Расчет временных характеристик сетевых моделей

Найти максимальный поток в транспортной сети.

1.

Из вершины 1 нет маршрута по ненасыщенным ребрам в сток, т.е. по теореме Форда-Фалкерсона найденный поток максимален.

Решение задачи определяется матрицей X:

	-4
	-1
	-3
		-2
			-1	-1
		-2		-2
						-2
					-2		-4		-2

Величина максимального потока равна

F(X’)=8.

Задача 7.1.

i\j

Задача 7.2.

i\j

Задача 7.3.

i\j

Задача 7.4.

i\j

Задача 7.5.

i\j

Задача 7.6.

i\j

Задача 7.7.

i\j

Задача 7.8.

i\j

Задача 7.9.

i\j

Задача 7.10.

i\j

Пусть i - номер работы, t(i) - длительность выполнения работы i, i=1,2,3,4,5,6,7. Обозначим через K(i) - множество работ, непосредственно предшествующих работе с номером i (условие, определяемое технологическими требованиями на порядок выполнения работ). Требуется определить минимально возможное время, за которое можно выполнить все работы.

i	t(i)	K(i)
		O
		O
		{1,2}
		{3}
		{3}
		{4}
		{5,6}

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

К таким характеристикам относятся:

t(rn,i) - время самого раннего начала выполнения работы с номером i,

t(rk,i) - время самого раннего окончания выполнения работы с номером i,

t(pn,i) - время самого позднего начала выполнения работы с номером i,

t(pk,i) - время самого позднего окончания выполнения работы с номером i,

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

T(k) - время выполнения всех работ изделия.

Величина T(k) называется длиной критического пути, а критическим путём называют путь, соединяющий некоторую начальную работу - не имеющую предшествующих работ, и некоторую конечную работу - не имеющую последующих, т.е. от неё зависящих работ, суммарное время выполнения всех работ которого максимально.

Для расчета временных характеристик воспользуемся следующими рекуррентными соотношениями:

t(rn,i) = 0, если K(i) - пустое множество.

t(rk,i) = t(rn,i) + t(i),

t(rn,i)= max t(rk,j), где максимум берется по всем работам j из множества K(i).

t(pk,i) = t(rk,i), если работа i не имеет последующих,

t(pn,i) = t(pk,i) - t(i),

t(pk,i) = min t(pn,j), где минимум берется по тем работам j, которые принадлежат множеству K(i), т.е. по тем работам, от которых зависит работа с номером i.

r(i) = t(pn,i) - t(rn,i) = t(pk,i) - t(rk,i).

Работы критического пути это те работы, резервы времени которых нулевые.

Найденные временные характеристики приведем в таблице:

i	t(i)	K(i)	t(rn,i)	t(rk,i)	t(pn,i)	t(pk,i)	r(i)
		O
		O					0’
		{1,2}					0’
		{3}					0’
		{3}
		{4}					0’
		{5,6}					0’

Работы критического пути (2,3,4,6,7).

Длина критического пути T(k)=19.

Работа1,t(1)=3		Работа5,t(5)=3
	Работа3’ t(3)=2			Работа7’,t(7)=2
Работа2’, t(2)=5		Работа4’,t(4)=4	Работа6’,t(6)=6

Дата добавления: 2017-02-01