Тема 27. Основы теории графов
3.1. Основные понятия
№3.1.1. Для графов, приведенных на рис.1., выполните следующие задания:
1) определите степени и полустепени вершин;
2) укажите содержащиеся в них:
а) контуры (циклы),
б) петли,
в) узлы,
г) висячие вершины;
3) определите, какие из графов являются:
а) ориентированными,
б) однородными,
в) полными,
г) мультиграфами.
1
. х2 х3 2. х2 х3
х1 х4 х1 х4
3
. 4.
х2 х4
х4
х1 х5 х1 х5
№3.1.2. По заданным полустепеням вершин постройте, если это возможно, ориентированный граф:
1) Р+(хi)=1, P_(xi)=1, i=1,…,4;
2) P+(x1)=P+(x2)=P_(x2)=P_(x3)=1,
P+(x3)=P_(x1)=2;
3) P+(xi)=i, P_(xi)=6-i, i=1,…,5.
№3.1.10. По данной матрице смежности постройте ориентированный граф и, если это возможно, неориентированный граф. Определите степени и полустепени вершин.
1
) 0
1 0 2) 0 1 1 3) 0 1 1 1 4) 0 1 1 1
1 0 1 1 0 0 0 0 0 0 1 0 0 0
1 0 0 1 0 0 0 1 0 1 0 1 0 1
0 1 1 0 1 0 0 1
Тема 28. Задача о коммивояжере
Литература: [4, 11]
Учебно-методическая литература: [6]
Тема 29. Задача об оптимальном потоке
Сети. Пропускная способность. Поток в сети. Минимальный разрез. Алгоритм Форда-Фалкерсона построения оптимального потока.
Литература: [4, 11]
Учебно-методическая литература: [6]
Тема 30. Задача о назначениях
3.3. Задача о назначении
№3.3.1. На должность президента, вице–президента и генерального менеджера АО «Оригинал» претендуют Иванов, Сидоров и Петров. В результате анкетирования акционеров АО, получена усредненная таблица, содержащая оценки (по десятибалльной шкале) соответствия претендентов предполагаемой должности. Определите оптимальное назначение претендентов на должности.
Вариант 1
-
Президент
Вице-през.
Менеджер
Иванов
9
7
8
Сидоров
7
8
9
Петров
8
9
6
Вариант 2
-
Президент
Вице-през.
Менеджер
Иванов
6
8
10
Сидоров
9
7
8
Петров
7
8
9
Литература: [4, 11]
Учебно-методическая литература: [6]
Тема 31. Задача сетевого планирования
3.4. Сетевой график
№3.4.1. Построить сетевую модель задачи планирования поставки товаров оптовым покупателям. Провести оптимизацию по критерию времени, определить критический путь и резервы времени, определить экономию.
|
Содержание работ |
Работа |
Длительность | ||||||
|
Коэффициент
|
Обозначение
|
Опорная
|
Варианты | |||||
|
1 |
2 |
3 |
4 |
5 | ||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
Отбор товара |
0,1 |
|
– |
2 |
4 |
5 |
6 |
3 |
|
Подготовка к отправке |
0,2 |
|
|
3 |
2 |
4 |
5 |
6 |
|
Выписка накладных |
0,3 |
|
|
1 |
2 |
3 |
4 |
3 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
Определение объема отгрузки |
0,4 |
|
|
1 |
2 |
3 |
4 |
3 |
|
Проверка цен |
0,5 |
|
|
1 |
2 |
2 |
2 |
2 |
|
Оформление счета |
0,6 |
|
|
1 |
2 |
4 |
3 |
2 |
|
Заказ автомашин |
0,7 |
|
|
3 |
1 |
1 |
2 |
2 |
|
Отправление счета покупателю |
0,8 |
|
|
1 |
4 |
4 |
3 |
3 |
|
Проверка товара по счету |
0,9 |
|
|
2 |
3 |
3 |
4 |
4 |
|
Оплата счета |
1,0 |
|
|
12 |
10 |
8 |
6 |
14 |
|
Погрузка товара и проверка количества |
1,1 |
|
|
2 |
3 |
3 |
4 |
4 |
|
Перевозка товара |
1,2 |
|
|
4 |
4 |
5 |
6 |
7 |
|
Выгрузка и сверка с документами |
1,3 |
|
|
4 |
4 |
5 |
4 |
5 |
Литература: [4, 11]
Учебно-методическая литература: [6]