3.2 Варианты заданий
Определить максимальный поток из вершины s в вершину t для графа, изображенного на рис. 3.6, с пропускными способностями дуг с.
Рисунок 3.6 – Заданный орграф
1. c(e1)=15; c(e2)=4; c(e3)=12; c(e4)=10; c(e5)=5; c(e6)=3; c(e7)=7; c(e8)=10
2. c(e1)=30; c(e2)=8; c(e3)=12; c(e4)=20; c(e5)=10; c(e6)=8; c(e7)=14; c(e8)=20
3. c(e1)=20; c(e2)=6; c(e3)=8; c(e4)=15; c(e5)=7; c(e6)=4; c(e7)=11; c(e8)=15
4. c(e1)=21; c(e2)=7; c(e3)=9; c(e4)=16; c(e5)=9; c(e6)=6; c(e7)=13; c(e8)=17
5. c(e1)=22; c(e2)=8; c(e3)=10; c(e4)=17; c(e5)=10; c(e6)=7; c(e7)=14; c(e8)=18
6. c(e1)=18; c(e2)=10; c(e3)=8; c(e4)=15; c(e5)=13; c(e6)=2; c(e7)=16; c(e8)=15
7. c(e1)=12; c(e2)=3; c(e3)=12; c(e4)=13; c(e5)=14; c(e6)=8; c(e7)=7; c(e8)=19
8. c(e1)=51; c(e2)=10; c(e3)=15; c(e4)=4; c(e5)=13; c(e6)=10; c(e7)=6; c(e8)=21
9. c(e1)=50; c(e2)=9; c(e3)=16; c(e4)=5; c(e5)=14; c(e6)=9; c(e7)=7; c(e8)=22
10. c(e1)=15; c(e2)=4; c(e3)=12; c(e4)=10; c(e5)=5; c(e6)=3; c(e7)=7; c(e8)=10
11. c(e1)=22; c(e2)=12; c(e3)=4; c(e4)=11; c(e5)=22; c(e6)=5; c(e7)=9; c(e8)=14
12. c(e1)=7; c(e2)=21; c(e3)=6; c(e4)=13; c(e5)=16; c(e6)=23; c(e7)=32; c(e8)=8
13. c(e1)=9; c(e2)=31; c(e3)=16; c(e4)=6; c(e5)=11; c(e6)=14; c(e7)=7; c(e8)=11
14. c(e1)=3; c(e2)=21; c(e3)=12; c(e4)=20; c(e5)=33; c(e6)=11; c(e7)=7; c(e8)=15
15. c(e1)=2; c(e2)=41; c(e3)=22; c(e4)=11; c(e5)=7; c(e6)=4; c(e7)=20; c(e8)=15
16. c(e1)=13; c(e2)=7; c(e3)=14; c(e4)=11; c(e5)=31; c(e6)=15; c(e7)=8; c(e8)=3
17. c(e1)=1; c(e2)=6; c(e3)=17; c(e4)=18; c(e5)=5; c(e6)=22; c(e7)=31; c(e8)=12
18. c(e1)=10; c(e2)=41; c(e3)=23; c(e4)=7; c(e5)=8; c(e6)=9; c(e7)=11; c(e8)=14
19. c(e1)=1; c(e2)=5; c(e3)=13; c(e4)=17; c(e5)=24; c(e6)=19; c(e7)=7; c(e8)=17
20. c(e1)=15; c(e2)=3; c(e3)=2; c(e4)=1; c(e5)=13; c(e6)=8; c(e7)=22; c(e8)=15
21. c(e1)=10; c(e2)=7; c(e3)=12; c(e4)=10; c(e5)=3; c(e6)=4; c(e7)=17; c(e8)=10
22. c(e1)=8; c(e2)=16; c(e3)=7; c(e4)=8; c(e5)=5; c(e6)=2; c(e7)=3; c(e8)=12
23. c(e1)=12; c(e2)=4; c(e3)=8; c(e4)=11; c(e5)=3; c(e6)=4; c(e7)=7; c(e8)=15
24. c(e1)=6; c(e2)=8; c(e3)=12; c(e4)=14; c(e5)=7; c(e6)=5; c(e7)=17; c(e8)=15
25. c(e1)=9; c(e2)=6; c(e3)=3; c(e4)=11; c(e5)=7; c(e6)=2; c(e7)=20; c(e8)=7
4 Задача джонсона
4.1 Алгоритм решения
Задача 1. 10 деталей должны пройти последовательную обработку на двух машинах. Деталь, обработка которой на первой машине закончена, немедленно начинает обрабатываться на второй машине. Время обработки i-ой детали на первой машине ai и второй машине b i приведено в табл. 4.1. Найти такое расписание обработки деталей (работ), при котором суммарная продолжительность работ будет минимальна.
Таблица 4.1- Продолжительность обработки деталей на двух машинах
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
ai |
8 |
10 |
14 |
3 |
13 |
6 |
3 |
6 |
6 |
10 |
bi |
4 |
14 |
15 |
8 |
5 |
4 |
5 |
3 |
7 |
7 |
Алгоритм решения.
1. Найти
.
Если
,
то работу с соответствующим номером
запланировать первой, если
,
то работу запланировать последней.
2. Пометить столбец с запланированной работой и продолжить составление расписания для остальных работ.
3. Если для неких i, j выполняется равенство ai=aj или b i = bj и i<j, то вначале планируется очередность выполнения i-ой работы, затем – j-ой.
4. Если для неких i, j выполняется равенство ai= bj , то очередность выполнения работ определяется по первой машине.
Решение. Очередность выполнения работы будем обозначать номером в квадратных скобках.
Анализируя табл.4.1, видим, что минимальную продолжительность имеют работы номер 4 и 7 на первой машине и работа №8 на второй машине. Согласно п.4 алгоритма, вначале нужно определить очередность выполнения работ номер 4 и 7.
Согласно п.3 алгоритма, первой планируем выполнение работы №4 (ей присваивается первая очередь), затем – работы №7 (вторая очередь). Отметим это, занеся числа 1 и 2 в соответствующие ячейки второй строки табл. 4.2. Помечаем соответствующие столбцы. Работу №8 планируем последней; занесем число 10 во вторую строку табл. 4.2.
Следующими для планирования очередности являются работы номер 1 и 6, продолжительность выполнения которых на второй машине равна 4. Поскольку число 4 относится ко второй машине, очередность этих работ должна определяться с конца расписания. Согласно п.3, вначале определяем очередность работы №1: она будет выполняться перед последней работой (очередь 9), затем – работы №6 (очередь 8).
Далее последовательно определяем выполнение работ №5 (очередь 7), №9 (очередь 3), №10 (очередь 6), №2 (очередь 4) и №3 (очередь 5).
Таблица 4.2 - Очередность выполнения работ на двух машинах
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
[i] |
9 |
4 |
5 |
1 |
7 |
8 |
2 |
10 |
3 |
6 |
Джонсон показал, что описанный выше
алгоритм позволяет решить задачу
составления оптимального расписания
и для трех машин с продолжительностью
выполнения i-ой работы
соответственно ai,
bi,
ci,
при условии, что для любого i
выполняется одно из двух условий:
или
.
В этом случае задача сводится к задаче
двух машин, с продолжительностью работ
на них соответственно ai,+
bi
и bi
+ci.
Задача 2. 7 деталей должны пройти последовательную обработку на трех машинах. Продолжительность обработки приведена в табл. 4.3.
Таблица 4.3 - Продолжительность обработки на трех машинах
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
ai |
8 |
3 |
7 |
9 |
5 |
8 |
6 |
bi |
4 |
4 |
7 |
5 |
7 |
7 |
3 |
сi |
9 |
10 |
12 |
13 |
10 |
11 |
10 |
Анализ приведенных значений показывает, что условие применимости алгоритма выполняется (все ). Результат решения задачи приведен в табл. 4.4.
Таблица 4.4 - Очередность выполнения работ на трех машинах
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
ai +bi |
12 |
7 |
14 |
14 |
12 |
15 |
9 |
bi +сi |
13 |
14 |
19 |
18 |
17 |
18 |
13 |
[i] |
3 |
1 |
5 |
6 |
4 |
7 |
2 |
Для иллюстрации расписания работ и определения их суммарной продолжительности используется диаграмма Ганта; порядок ее построения понятен из рис. 4.1, где периоды вынужденного простоя машин выделены штриховкой.
Из диаграммы следует, что время простоя второй машины
время
простоя третьей машины
,
Рисунок 4.1-Диаграмма Ганта
а суммарная продолжительность всех работ
.