Добровольная пожарная дружина г.Уэмперли.

Боб Бишоп является начальником добровольной пожарной дружины г.Уэмперли и водителем единственной пожарной машины. В дружине еще восемь членов и обычно, по крайней мере, шестеро откликаются на звон пожарного колокола. Боб - прагматик и не считает нужным выскакивать из дома, как только зазвонят в колокол. Он выходит в самый последний момент, когда ждать уже больше нельзя. Некоторые члены дружины живут в пригороде и поэтому обычно требуется не менее 15 минут, чтобы все собрались у пожарного депо.

Вопрос, на который Боб хотел бы получить ответ, звучит примерно так: "Сколько минут после сигнала тревоги можно оставаться дома, чтобы не прибыть к месту сбора последним."

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

Копией упомянутой схемы является рис.2.5. Узел 1 изображает дом Боба, а узел 14 - пожарное депо; узлы 2-13 - просто уличные перекрестки, а дуги - это отрезки между перекрестками. Стоимость каждой дуги представляет собой время, которое, по мнению Боба, потребуется ему, чтобы проехать данный отрезок пути.

[ Фиксированный внешний поток]

(стоимость)

Рис. 2.5.

Строительный кооператив.(СК)

Эта корпорация - одна из новых строительных фирм в городе. Недавно СК подписал контракт на строительство нового спортзала для колледжа. В контракте предусмотрены довольно большие штрафы за невыполнение работы в срок. Поэтому президент фирмы приказал плановому отделу выяснить, какие строительно-монтажные работы имеют решающее влияние на сроки окончания работ.

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

Этапы	Выполняемые работы	Требуемое число дней	Предшествющий этап
A	Подготовка стройплощадки		-
В	Укладка фундамента		А
С	Монтаж вертикальных стен		В
D	Монтаж крыши		С
Е	Укладка деревянного пола		В
F	Отделка внутренних стен		С
G	Установка сантехники		С
Н	Монтаж электропроводки		D
I	Установка баскетбольных щитов		D
J	Окраска и разметка площадки		E
К	Сборка системы отопления и кондиционирования		G, H
L	Монтаж внутренних беговых дорожек		Е
М	Строительство трибун		Е, F
N	Установка электрического табло		F
O	Оборудование буфета-бара		Е, F, G

[ Фиксированный внешний поток]

(стоимость)

Рис. 2.6.

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

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

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

Задача о максимальном потоке.

Переплетная фирма АСМЕ.

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

1) распаковать поступившие коробки с книгами;

2) сброшюровать листы;

3) обрезать страницы;

4) приклеить книжные корешки;

5) приклеить переплет;

6) оттиснуть заглавие на переплете;

7) упаковать готовые книги;

8) приклеить на коробки почтовые ярлыки;

9) погрузить коробки на грузовики.

Рис.2.7.

Этапы	Число рабочих мест	Производительность (число книг/день)
		10, 12
		10. 13
		7, 9, 3, 2
		22, 23
		15, 6, 4
		10, 15

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

ОРИЕНТИРОВАННЫЕ ГРАФЫ.