Сетевые задачи
1 ЦЕЛЬ
Исследование методов решения сетевых задач.
2 ВЫПОЛНЕНИЕ РАБОТЫ
Задача№1. (Выставка)
Организаторы больших выставок часто вынуждены решать задачу: как организовать осмотр так, чтобы дать возможность в отведенное время ознакомиться с экспозицией наибольшему числу желающих.
Необходимо расставить 16 экспонатов так, чтобы предоставить возможность посещения наибольшего количества человек при условии:
1) вход и выход совпадают;
2) вход и выход разные.
Решение:
Задача №2.
Торговец, живущий в городе А намерен посетить города B, C, D. Расстояния между городами: AB=10, AC=25, AD=60, BC=15, BD=50, CD=35.
Необходимо найти кратчайший циклический маршрут.
Решение:
Рассмотрим следующие маршруты:
1. ABCDA→AB+BC+CD+DA=10+15+35+60=120
2. ACBDA→AC+CB+BD+DA=25+15+50+60=150
3. ABDCA→AB+BD+DC+CA=10+50+35+25=120
Кратчайшим является маршрут ABCDA или ABDCA.
Задача №3. (Строительство дорог)
Стоимость и строительство дорог соединяющих два любых города представлены в таблице.
| № | A | B | C | D |
| A | 0 | 12 | 14 | 13 |
| B | 12 | 0 | 7 | 10 |
| C | 14 | 7 | 0 | 11 |
| D | 13 | 10 | 11 | 0 |
AB+BC+DB=12+7+10=29
Задача №4. (Максимальный поток)
Задана сеть, каждое ребро которой имеет определенную ограниченную пропускную способность.
Определить максимально возможный поток в этой сети из узла 1 в 7.
Задача №5.
(Кратчайший маршрут)Дана сеть, каждое ребро которой помечено числом равное его длине.
Найти кратчайший путь из узла А к другим последующим узлам. Решение представить в виде таблицы.
| Узел | Кратчайший маршрут | Длина |
| А→B | AB | 30 |
| А→C | AC | 33 |
| А→D | ACD или ABD | 42 |
| А→E | ABE | 48 |
| А→F | ABDF или ACDF | 56 |
| А→G | ABEG | 67 |
| А→H | ABEH | 65 |
| А→I | ACDFI | 73 |
Задача №6. (Критический путь)
Задан цикл работ: A(3), B(6), C(12), D(9), E(11), F(3), G(5), H(7), I(3), в скобках – количество дней для выполнения данной работы. Необходимо найти критический путь и минимальное время необходимое для выполнения всего цикла, если известна последовательность выполнения следующих работ:
D→E,
F→D и G,
G→E,
H→G,
I→C и F.
Решение изобразим графически:
Минимальное время необходимое для выполнения всего цикла – 38 дней.
Задача №7. (Выбор университета и специальности)
Выпускник должен продолжить учебу в ВУЗе. Понимая, что вероятность успеха зависит как от выбора университета, так и от выбора специальности, он хочет оценить возможности получения диплома в технической области и области бизнеса.
Вероятности успешного поступления:
1) столичный Университет Бизнеса – 0,5
2) столичный Технический Университет – 0,6
3) Университет Бизнеса родного города – 0,8
4) Технический Университет родного города –0,85
Средний доход за год в течении первых 5 лет после окончания:
1)столичный Университет Бизнеса – 60000 руб
2)столичный Технический Университет – 55000 руб
3)Университет Бизнеса родного города – 42000 руб
4)Технический Университет родного города – 44000 руб
Если выпускник не получает высшего образования, то его средний доход составит 5000 руб
Предположим, что единственным критерием при принятии решения является доход.
Решение:
Построим дерево решений:
d1 – выбор столичного университета;
d2 – выбор университета родно города;
d3 – предпочтение бизнеса;
d4 - предпочтение технической специальности;
S1 – окончил столичный университет бизнеса;
S – не окончил;
S2 – окончил столичный технический университет;
S – не окончил;
S3 – окончил университет бизнеса родного города;
S – не окончил;
S4 – окончил технический университет родного города;
S – не окончил.
| узел4: | |
| узел5: | |
| узел6: | |
| узел7: |
Таким образом, очевидно, что оптимальным выбором является поступление в столичный Университет Бизнеса.
1.