Оптимизация маршрута

В п. 2.2 работы было принято решение о замене поставщика ООО «Европейский хлеб» на ОАО «Славянский хлеб». Рассчитаем оптимальный маршрут.

Задачу решать с помощью теории графов, где вершины графа - перекрестки дорог, а дуги графа - дороги.

a) Определение ранних сроков совершения события

(2)

; ; ;

- равен максимальной продолжительности работы или сумме –х работ ведущих от начального события сетевого графика к данному –му событию.

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

Критический путь(L_КР) - самый продолжительный путь, ведущий от начального к конечному событию сетевого графика.

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

b) Определение поздних сроков свершения события (проводится строго в обратном порядке начиная с завершающего события).

(3)

; ; ;

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

c) Определение резервов времени событий.

(4)

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

Для событий, через которые проходит критический путь .

d) Определение критического пути.

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

Условия необходимые для работы на критическом пути:

1. Нулевые резервы времени начальных и конечных событий этой работы, т.е.

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

e) Длительность критического пути является максимумом работ от начального до конечного события сетевого графика.

L_КР= (5)

f) Полный резерв времени работы - это весь резерв, которым обладает работа при условии возможного раннего её начала и допустимого позднего её окончания.

(6)

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

или (7)

При расчетном принимают

h) Частный резерв времени первого вида – показывает, какая часть полного резерва может быть использована для увеличения , не влияя на ранний срок свершения начального события этой работы.

или (8)

i) Частный резерв времени второго вида – показывает, какая часть может быть использована для увеличения , не влияя на этой работы.

или (9)

Резервы времени определяются только у работ, которые не лежат на критическом пути (у лежащих на L_КР все резервы равны нулю).

Табличный метод

Параметры событий

Номер перекрестка	Ранний срок наступления	Поздний срок наступления	Резерв времени события
		Min(9-4;10-6;12-12)=0	0-0=0
	0+4=4	Min(10-1=9	9-4=5
	0+6=6	Min(23-5;16-0;12-2)=10	10-6=4
	0+12=12	16-4=12	12-12=0
	Max(12+4;6+0)=16	Min(23-7;24-3)=16	16-16=0
	16+7=23	Min(23-0;26-1)=23
	Max(16+3;23+0)=23	Min(27-2;26-2)=24	24-23=1
	Max(23+0;6+5)=23	26-3=23	23-23=0
	Max(23+3;23+1)=26	27-1=26	26-26=0
	Max(26+1;23+2)=27		27-27=0

Параметры работ

Дорога	Полный резерв времени работы	Свободный резерв времени работы	Частный резерв времени первого вида	Частный резерв времени второго вида
1-2	9-0-4=5	5-0-5=0	5-5=0	5-0=5
1-3	10-0-6=4	4-4-0=0	4-4=0	4-0=4
1-4	12-0-12=0	0-0-0=0	0-0=0	0-0=0
2-1	10-4-1=5	5-5-4=-4, т.е. 0	5-4=1	5-5=0
3-4	12-6-2=4	4-4-0=0	4-0=4	4-0=4
3-5	16-6-0=10	10-0-4=6	10-0=10	10-4=6
3-8	23-6-5=12	12-4-0=8	12-0=12	12-4=8
4-5	16-12-4=0	0-0-0=0	0-0=0	0-0=0
5-6	23-16-7=0	0-0-0=0	0-0=0	0-0=0
5-7	24-16-3=5	5-0-1=4	5-1=4	5-0=4
6-7	24-23-0=1	1-0-1=0	1-1=0	1-0=1
6-8	23-23-0=0	0-0-0=0	0-0=0	0-0=0
6-9	26-23-1=2	2-0-0=2	2-0=2	2-0=2
7-9	26-23-2=1	1-1-0=0	1-0=1	1-1=0
7-10	27-23-2=2	2-1-0=1	2-0=2	2-1=1
8-9	26-23-3=0	0-0-0=0	0-0=0	0-0=0
9-10	27-26-1=0	0-0-0=0	0-0=0	0-0=0