Тема: Сетевые модели (стр. 5 )

где nij —количество изделий, обрабатываемых как на станке i, так и на станке j, mij — количество изделий, обрабатываемых только на станке i или только на станке j.

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

Станок	Типы изделий
1	1,6
2	2, 3, 7, 8, 9, 12, 13, 15
3	3, 5, 10, 14
4	2,7,8,11,12,13
5	3,5,10,11,14
6	1,4,5,9,10
7	2,5,7,9,10
8	3,4,15
9	4,10
10	3, 8, 10, 14, 15

Сформулируйте данную задачу как сетевую.

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

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

5. Компания по прокату автомобилей разрабатывает план по обновлению парка своих машин на следующие пять лет (2000–2004 гг.). Каждый автомобиль должен проработать не менее 2–х и не более 4–х лет. В следующей таблице приведена стоимость замены автомобиля в зависимости от года покупки и срока эксплуатации.

	Стоимость замены ($) в зависимости от срока эксплуатации
Год покупки	1	2	3
2000	3800	4100	6800
2001	4000	4800	7000
2002	4200	5100	7200
2003	4800	5700	—
2004	5300	—	—

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

Рис. 3

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

Операция	Время (секунды)
Помещение ломтика хлеба в тостер	3
Поджаривание одной стороны ломтика	30
Переворачивание ломтика в тостере	1
Извлечение ломтика из тостера	3

8. Планирование производства. Компания продает некую продукцию, спрос на которую в следующие 4 месяца составит 100, 140, 210 и 180 единиц соответственно. Компания может удовлетворить любой помесячный спрос на продукцию и даже спрос на два и более месяца вперед. В последнем случае необходимо платить $ 1.20 за хранение единицы избыточно произведенной продукции в течение месяца. Покупная цена единицы продукции в следующие 4 месяца будет равна $15,$12, $10 и S14 соответственно. Стоимость переналадки оборудования для выполнения заказа составляет $200. Компания хочет разработать такой производственный план, чтобы минимизировать расходы на выполнение заказов, покупку продукции и ее хранение. Сформулируйте задачу как нахождение кратчайшего пути и найдите ее оптимальное решение.

9.Задача о рюкзаке. Путешественник, собираясь в путь, пытается поместить в свой рюкзак, объемом 5 кубических футов, наиболее необходимые в путешествии вещи. Имеется три вещи, объемом соответственно 2, 3 и 4 кубических фута, необходимость в которых оценивается (по 100–балльной шкале) в 30, 50 и 70 баллов. Сформулируйте эту задачу как сетевую, где необходимо определить самый длинный путь, и найдите ее оптимальное решение. (Совет. Узел в этой сети можно определить как пару [i, v], где i — номер выбираемой вещи, a v— свободный объем рюкзака, оставшийся после выбора i–й вещи.)

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

1.  Между городами 1 и 8.

2.  Между городами 1 и 6.

3.  Между городами 4 и 8.

4.  Между городами 2 и 6.

Рис. 4

11. Найдите кратчайшие пути между узлом 1 и всеми остальными узлами сети, представленной на рис. 5.

Рис. 5

12. Примените алгоритм Флойда к сети, показанной на рис. 6. Заметьте, что ребра (7, 6) и (6,4) ориентированы. Определите кратчайшие пути между следующими парами узлов.

1.  От узла 1 к узлу 7.

2.  От узла 7 к узлу 1.

3.  От узла 6 к узлу 7.

Рис. 6

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

Рис. 7

14. Найдите максимальный поток и значения потоков, проходящих через каждое ребро сети, показанной на рис. 8.

Рис. 8

15. Три нефтеперегонных завода транспортируют свою продукцию двум распределительным терминалам по сети трубопроводов, которая включает и насосные станции (рис. 9). Направления потоков в сети показаны стрелками, пропускные способности отдельных сегментов сети указаны в миллионах баррелей в день.

Рис. 9

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

Определите ежедневную потребность каждого распределительного терминала, соответствующую максимальной пропускной способности сети трубопроводов.

Определите ежедневную пропускную способность каждой насосной станции, соответствующую максимальной пропускной способности сети трубопроводов.

15. Пусть в сети из предыдущего упражнения (рис. 9) пропускная способность насосной станции 6 ограничена 60 миллионами баррелей в день. Найдите максимальную пропускную способность сети с учетом этого ограничения.

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

		1	2	3	4
Зернохранилища	1	30	5	0	40	20
2	0	0	5	90	20
3	100	40	30	40	200
	200	10	60	20

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

Существует ли при данных условиях схема транспортировки, обеспечивающая весь спрос птицеводческих ферм?

17. Пусть в задаче из предыдущего упражнения возможна транспортировка зерна между зернохранилищами 1 и 2, а также 2 и 3. Кроме того, возможна транспортировка между фермами 1 и 2, 2 и 3, 3 и 4. Максимальная пропускная способность в обоих направлениях указанных маршрутов составляет 50 тысяч фунтов. Как данные предположения скажутся на обеспечении пока неудовлетворенного спроса птицеводческих ферм?

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

Ребенок Ральф	Предпочтительные работы 3, 4 или 5
Мэй	1
Бен	1 или 2
Ким	1,2 или 5
Кен	2

Теперь родителям осталось найти такое распределение работ, которое в наибольшей степени учитывало бы предпочтения детей. Найдите максимальное количество таких распределений работ.

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

Фабрика	Тип игрушки
1	1,2,3
2	2,3
3	1,4
4	3,4

Ежедневные производственные возможности фабрик составляют 250, 180, 300 и 100 штук игрушек соответственно. Ежедневный спрос на игрушки четырех типов составляет 200, 150, 350 и 100 штук. Разработайте производственный план, максимально удовлетворяющий спрос на игрушки.

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

Общество	Студент
1	1,2,3
2	1,3,5
3	3,4,5
4	1,2,4,6

Приведем также распределение студентов по возможному принятию их в различные секции совета.

Секция	Студент
естественных наук	1,2,4
гуманитарных наук	3,4
инженерных наук	4,5,6

Каждый студент может быть принят только в одну секцию. Могут ли быть представлены в совете все четыре студенческих общества?