Град 14452 шифр 01. На территории города имеется три телефонных станции А, б и В. Незадействованные емкости станций составляют на станции а q

• Название: На территории города имеется три телефонных станции А, б и В. Незадействованные емкости станций составляют на станции а q
• Дата: 13.10.2022
• Размер: 207.93 Kb.
• Имя файла: Град 14452 шифр 01.docx
• Тип: Задача; #731545
• страница: 4 из 4

Наибольшая сумма констант приведения равна (4+0) = 4 для ребра (1,2), следовательно, множество разбивается на два подмножества (1,2) и (1*,2*).

Нижняя граница гамильтоновых циклов этого подмножества:

i j	1	2	3	6	di
1	М	М	0	1	0
3	0	М	М	0	0
4	2	4	М	0	0
6	3	6	0	М	0
dj	0	4	0	0

В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.

i j	1	3	6	di
3	0	М	0	0
4	М	М	0	0
6	3	0	М	0
dj	0	0	0

Чтобы исключить подциклы, запретим следующие переходы: (4,1).

Поскольку нижняя граница этого подмножества (1,2) меньше, чем подмножества (1*,2*), то ребро (1,2) включаем в маршрут.

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

i j	1	3	6	di
3	0(3)	М	0(0)	0
4	М	М	0(0)	0
6	3	0(3)	М	3
dj	3	0	0

Наибольшая сумма констант приведения равна (0+3) = 3 для ребра (3,1), следовательно, множество разбивается на два подмножества (3,1) и (3*,1*).

Нижняя граница гамильтоновых циклов этого подмножества:

i j	1	3	6	di
3	М	М	0	0
4	М	М	0	0
6	3	0	М	0
dj	3	0	0

В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

i j	3	6	di
4	М	0	0
6	0	М	0
dj	0	0

Поскольку нижняя граница этого подмножества (3,1) меньше, чем подмножества (3*,1*), то ребро (3,1) включаем в маршрут.

В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (4,6) и (6,3).

В результате по дереву ветвлений гамильтонов цикл образуют ребра:

(1,2), (2,5), (5,4), (4,6), (6,3), (3,1),

Длина маршрута равна F(Mk) = 7+6+7+8+4+4=36.

Следовательно, маршрут почтальона, при котором затраты времени на его проход будут минимальными: А→Б→Д→Г→Е→В→А.

ЗАДАЧА 4.

На сетевом графике цифры у стрелок показывают в числителе - продолжительность работы в днях, в знаменателе - количество ежедневно занятых работников на её выполнение.

В распоряжении организации, выполняющей этот комплекс работ. Имеется 28 рабочих, которых необходимо обеспечить непрерывной и равномерной работой.

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



Решение.

Определим параметры сетевого графика по формулам:

1) ;

2) или ;

3) ;

4) или ;

5) ;

6) .

Расчет выполним в таблице.

		Раннее			Позднее			Резерв
(i,j)	Продолжительность t(i,j)	начало	окончание	начало		оконча ние	частный		полный
(1,2)	2	0	2	0		2	0		0
(1,3)	5	0	5	0		5	0		0
(1,4)	6	0	6	0		6	0		0
(2,5)	4	2	6	8		12	0		6
(3,5)	7	5	12	5		12	0		0
(3,6)	3	5	8	5		8	0		0
(4,6)	2	6	8	6		8	0		0
(5,7)	6	6	12	12		18	0		6
(6,7)	2	8	10	16		18	0		8

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

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

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

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


График загрузки можно интерпретировать в виде диаграммы:



В соответствии с графиком загрузки в течение интервала времени с 0 по 12 день для выполнения проекта требуется работа одновременно от 32 до48 человек. Таким образом, возникает необходимость снижения максимального количества одновременно занятых исполнителей с 48 до 28 человек.

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

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



По итогам корректировки график загрузки можно представить в виде диаграммы:



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