<<
>>

Сетевые задачи

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.

<< | >>
Источник: Исследование методов решения задач линейного программирования. Лекция. 2017

Еще по теме Сетевые задачи:

  1. 3.2. Математическое моделирование процессов тепломассообмена в сетевых трубопроводах систем теплоснабжения
  2. Сетевые игры и виртуальные миры
  3. 2.3. Задача календарного планирования при учете совмещения агрегированных операций
  4. 2.3. Основные компоненты системы календарно-сетевого планирова-ния
  5. Задача распределения объемов работ.
  6. 2.3.2. Интернет-проекты, поддержка местных сетевых инициатив в инновационном проектировании
  7. Сетевые организационные структуры
  8. 8.3. Организационный инструментарий.Сетевые матрицы
  9. Главные задачи в сетевом образовании в настоящее время
  10. 7. ПЕРВООЧЕРЕДНЫЕ ЗАДАЧИ ГОСУДАРСТВЕННОЙ ПОЛИТИКИ ОБЕСПЕЧЕНИЯ ПЕРЕХОДА К ИНФОРМАЦИОННОМУ ОБЩЕСТВУ
  11. 8.5. Транспортная задача в сетевой постановке
  12. 17.2. МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ
  13. СЕТЕВЫЕ ПРОТОКОЛЫ И УРОВНИ
  14. 8.4.7. ЭСКИЗНОЕ ПРОЕКТИРОВАНИЕ ИНФОРМАЦИОННОЙ ТЕХНОЛОГИИ РЕШЕНИЯ ЧАСТНЫХ ЗАДАЧ УПРАВЛЕНИЯ
  15. СЕТЕВЫЕ МОДЕЛИ
  16. СЕТЕВЫЕ РЕШЕНИЯ ФИРМЫ HIRSCHMANN