Шапорев С.Д. Дискретная математика - файл n13.doc

приобрести
Шапорев С.Д. Дискретная математика
скачать (1595.4 kb.)
Доступные файлы (14):
n1.doc1008kb.24.06.2000 17:47скачать
n2.doc580kb.29.02.2000 18:08скачать
n3.doc957kb.07.03.2000 15:50скачать
n4.doc492kb.24.06.2000 17:37скачать
n5.doc1198kb.19.04.2000 15:24скачать
n6.doc985kb.19.04.2000 21:35скачать
n7.doc771kb.07.05.2000 17:26скачать
n8.doc992kb.08.05.2000 16:38скачать
n9.doc217kb.08.05.2000 19:26скачать
n10.doc1581kb.26.03.2000 20:59скачать
n11.doc1011kb.31.03.2000 22:04скачать
n12.doc1025kb.31.03.2000 22:09скачать
n13.doc1691kb.05.04.2000 16:10скачать
n14.doc960kb.09.04.2000 12:05скачать

n13.doc





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

придется применить алгоритм Беллмана -

9(6) Мура.

-9(6) Этап 1. Шаг 1. .

9(7) -12(6) . Шаг 2. Ш, ,

7(11) 9(14) Да.

12(5) ,

(0) (0) 9(10) Шаг 3. Ш. Переход на второй шаг.

-10(11) 9(13) Вторая итерация. Шаг 2. Ш,

-13(7) ,

, нет корректировки очереди.

, Да. .

, Да. .

Шаг 3. Ш. Переход на второй шаг.

Третья итерация. Шаг 2. .

нет корректировки очереди,

нет корректировки очереди,

нет корректировки очереди,

,

нет корректировки очереди.

Шаг 3. Ш. Переход на второй шаг.

Четвертая итерация. Шаг 2. .

нет корректировки очереди.

Шаг 3. Ш.

Пятая итерация. Шаг 2. Ш, ,

.

Шаг 3. Ш.

Шестая итерация. Шаг 2. Ш, Ш.

Шаг 3. Ш. Конец первого этапа. Критический путь найден.

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

Тогда Кроме того два предыдущих потока дали Таким образом, минимальная стоимость всего потока равна


Глава 5. Элементы сетевого планирования.
§ 5.1. Критические пути, работы, резервы.
При планировании и управлении сложными комплексами работ используются их графические модели – сетевые графики. С математической точки зрения сетевой график – это связный орграф без петель и контуров. Основными понятиями сетевого планирования являются понятия работы и события.

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

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

Последовательность работ


Исходная

работа

Опирается на

работу

Продолжи-

тельность

работ



-

3



-

6



-

4





5





1





9





6





8


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

события . Работе предшест-

вует работа , поэтому дуга

на сети изображена вслед за дугой

.То же самое с дугами и .

Далее надо изобразить дуги и

. Работа опирается на работы

и . Итоговая работа опира-

ется на , и . На рисунках

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

Имея сеть работ некоторого проекта можно посчитать время выполнения всего проекта и различных его частей, состоящих из разного набора работ. Для этого введем еще несколько определений. Определим сначала минимальное время, за которое можно выполнить все работы комплекса. Для этого найдем продолжительность всех полных путей . В нашем случае таких путей четыре: Их продолжительности , , , . Наиболее продолжителен второй путь. Такой путь называют критическим. Этот путь определяет минимальное время выполнения всех работ комплекса. Минимальное время называют критическим сроком и обозначают . Итак, в рассматриваемом примере .

Все работы и события, лежащие на критическом пути, называют критическими, все остальные работы и события – некритическими. Задержка любой критической работы вызывает задержку выполнения всего комплекса. Следовательно, чтобы уменьшить время выполнения комплекса работ, надо сократить сроки критических работ. Некритические работы допускают некоторое запаздывание их выполнения без нарушения критического срока. Это запаздывание измеряется резервом времени событий и работ.

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

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

(5.1.1)

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

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

В нашем случае . Чтобы не нарушался критический срок, событие должно произойти в крайнем случае на восемь дней раньше, поэтому . Аналогично, . Таким образом, поздние сроки событий рассчитываются по формуле

(5.1.2)

где - множество работ, выходящих из события, - поздний срок свершения конечного события работы .

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


(5.1.3)

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

Зная сроки свершения событий, можно найти ранние и поздние сроки начала и окончания работы . Очевидно, что

(5.1.4)

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

(5.1.5)

Формулу (5.1.5) можно проиллюстрировать следующим рисунком.









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

(5.1.6)

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

Рассчитаем все резервы времени для событий и работ исходного примера.



2

3 10

7

1 3 5 6

0 0 6 6 15 15 23 23

0 0 0 0



4

7 9

2

Все расчеты проводятся в четыре этапа: 1) вычисляют ; 2) ; 3) ; 4) критический путь.

Этап 1. При вычислении перемещаются по сети от события к событию в порядке возрастания номеров. Именно, . Для события по формуле (5.1.1) Аналогично, Для вершин и формулу (5.1.1) необходимо применять в полном объеме, то есть , . Наконец, Получили критический срок. Итак,

Этап 2. При вычислении поздних сроков свершения событий перемещаются по сети от к в порядке убывания номеров. Так как , то исходное значение известно. Далее используем формулу (5.1.2).

Например, Аналогично, , Из события выходят две работы и , поэтому . Наконец. Из события выходят сразу три работы , и . Поэтому здесь Этап 3. Для вычисления резервов времени событий достаточно вычесть числа, записанные в правых и левых секторах кружков, друг из друга.

Этап 4. У критических событий резерв времени равен нулю. В нашем примере критическими являются события , , и . Они и определяют критические работы и критический путь 1-3-5-6.

Резервы времен работ сети вычисляются по формулам (5.1.4), (5.1.5) и (5.1.6). Например, , , ,

В заключение заметим, что критических путей на сети может быть несколько. Они могут включать в себя и фиктивные работы.
§ 5.2. Линейные графики.
Наряду с сетевым графиком при анализе и оптимизации комплекса работ применяется и линейный график. Построим его для нашего примера. На дугах исходного линейного графика проставлены в скобках интенсивности потребления ресурса. Найдем по этому линейному графику критический путь, критический срок, критические работы и резервы временно некритических работ. На первом рисунке слева изображен

исходный сетевой гра-

фик для того, чтобы яс-

нее были видны последо-

вательности работ. Вто-

рой рисунок - линейный

график. Он имеет две

шкалы – шкалу времени

и шкалу потребления ре-

20 сурса. Проанализируем

4 5 30 линейный график. Наи-

20 5 6 большей отметки време-

3 4 50 ни на нем соот-

3 5 ветствует работа (5, 6),

50 значение и явля-

2 5 ется критическим сро-

30 ком. Ясно, что будучи

1 4 заключительной работой

40 комплекса, работа (5, 6)

1 3 является критической.

50 Непосредственно ей

1 2 предшествует работа

(3, 5), а этой работе

0 5 10 15 20 (1, 3); обе эти работы

120 120 90 120 120 70 50 30 также являются крити-

ческими. Все остальные

шкала потребления ресурса работы – некритичес-

кие. Критические работы на линейном графике выделены жирной чертой.

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

Аналогично из линейного графика получим , , , . Для построения шкалы потребления ресурса в ходе работ, спроектируем на ось начальные и конечные точки работ. В полученных промежутках нужно просуммировать интенсивности всех работ, расположенных над этими промежутками. Например, для интенсивность равна 50+50+20=120 единиц.

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

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

Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации