3. Задачи сетевого программирования.

34. По данным таблицы 10 построить сеть.

Таблица 10.

Обозначение работы
Непосредст венно предшествующие работы	–	–	–
Продолжи тельность работы	3	6	4	5		1		9		6		8		5

35. В горной лесопарковой зоне расположено семь площадок для отдыха, соединенных тропами. Расположение площадок и длины троп указаны на рисунке 13. Найти кратчайший путь из в .

36. Комплекс работ представлен сетевым графиком (см. рис.14). Известна продолжительность (в днях) каждой работы и количество единиц ресурса, необходимо для выполнения работы в единицу времени, - интенсивность потребления ресурса (число в скобках). Построить линейный график и найти по нему критический срок, критические работы и резервы времени некритических работ. Построить шкалу потребления ресурса.

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

38. Найти кратчайший путь из в , из в для сетей, изображенных соответственно на: а) рис.15; б) рис.16.

39. Для местного аэропорта приобретается автокар. Через три года планируется установка механизированной погрузочной системы, после чего автокары станут ненужными. Тем не менее, может оказаться выгодным заменить автокар через год или два года или даже осуществить две замены (через год и через два года). В следующей таблице 11 приведены полные расходы (с учетом стоимости эксплуатации и выручкой от продажи), связанные с покупкой автокара в конце года i и его продажей в конце года j.

Год покупки (i)	Год продажи (j)
	1	2	3
0 1 2	4	8 5	15 11 6

Таблица 11.

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

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

41. Все площадки для отдыха (см. задачу 35) необходимо соединить телефонной сетью, причем телефонные линии должны проходить вдоль троп лесопарковой зоны. Спроектировать телефонную сеть с минимальной суммарной длиной линии.

42. Построить минимальные связывающие деревья (см. задачу 40) для сетей задачи 38.

43. Сформулировать задачу построения максимального потока как задачу линейного программирования.

44. Найти максимальные потоки из до , из до в сетях, изображенных соответственно на: а) рис. 17; б) рис. 18 (на дугах указаны их пропускные способности в каждом из направлений).

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

46. Информация о проекте задана перечнем работ, их продолжительностью выполнения (таблица 12). Построить сетевой график проекта, найти критическое время проекта и критический путь, если известно, что в i-ю работу можно вложить средства , где , при этом время выполнения работы уменьшиться до .

Таблица 12.

Работа	Каким работам предшест вует	Продол житель ность, мес.	Работа	Каким работам предшест вует	Продол житель ность, мес.
1	4, 5, 6	20	5	8	10
2	4, 5, 6	10	6	7	5
3	5, 6	8	7	8	5
4	8	20	8	–	10

47. Начальное условие как в задаче 46, полагая , определить размер вложенных средств в 1-ю, 4-ю и 8-ю работы так, чтобы время завершения всего комплекса работ не превышало 40 мес., а сумма вложений была минимальной.

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

49. Информация о проекте задана перечнем работ, их продолжительностью и последовательностью выполнения (таблица 13). Построить сеть проекта.

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

Таблица 13.

Работа	Каким работам предшест вует	Продол житель ность в днях	Работа	Каким работам предшест вует	Продол житель ность в днях
1	11, 15	15	9	5	10
2	1, 13	5	10	–	20
3	9, 14	5	11	5	10
4	10	10	12	1, 13	20
5	–	5	13	9, 14	10
6	3, 4	30	14	10	10
7	8, 2	10	15	9, 14	5
8	11, 15	20