Автор работы: Пользователь скрыл имя, 07 Февраля 2013 в 18:59, контрольная работа
Задача №1
Исходные данные транспортной задачи приведены в таблице. Составить план перевозки однородного груза от пунктов производства к пунктам потребления с минимальными суммарными транспортными затратами.
Решение:
Найдем начальное решение методом минимального элемента. Если начальное решение окажется оптимальным, то задача решена. Если начальное решение окажется не оптимальным, используя метод потенциалов, будем последовательно получать решение за решением, причем каждое следующее, как минимум, не хуже предыдущего. И так, до тех пор, пока не получим оптимальное решение.
Задача №1
3
Задача №2
15
Задача №3
16
Задача №4
19
X 2 опт = |
190 |
0 |
0 |
0 |
20 |
||
0 |
100 |
0 |
0 |
30 | |||
0 |
0 |
0 |
0 |
60 | |||
0 |
30 |
65 |
45 |
0 |
Задача 2.
В туристической фирме составляют маршрут для туристов, которые должны проехать из пункта А в пункт В и по пути осмотреть все достопримечательности. Пункты и все дороги представлены следующей схемой:
х1 х2
х3
А х6
х5 х7
Требуется составить маршрут, чтобы туристы попадали в каждый пункт не более одного раза. Сколько маршрутов может быть при данной схеме дорог?
Решение.
В данной задаче маршрутов нет.
Задача 3.
На рисунке изображена транспортная сеть между населенными пунктами.
1. Постройте матрицу смежности и матрицу идентичности орграфа D.
2. Найдите кратчайшие маршруты между пунктами:
а) х1 и х8
b) х1 и х6
с) х4 и х8
d) х2 и х6
X8
X7
X11111111
X2
X4
X5
X6
X3
4
2 1 3
2 6 2
1 5
1 2 7 6
3 5
Решение.
1. Дан орграф D с вершинами х1, х2, х3, х4, х5, х6, х7, х8 и дугами а1, а2, а3, а4, а5, а6, а7, а8, а9, а10, а11, а12, а13, а14, а15, а16.
Орграф D содержит 8 вершин и 16 дуг, поэтому размер матрицы A(D) будет 8×8, а матрицы B(D)- 8×16.
Матрица смежности орграфа D – это квадратная матрица A(D) размера n×n ( n- число вершин) с элементами
aij =
1, если в орграфе D есть дуга из i-й вершины в j-ю
0, иначе
01100000
00111000
A(D)=
00011100
00001110
00000110
00000011
00000001
00000000
Матрица идентичности орграфа D – это матрица B(D) размера n×m (n- число вершин, m – число дуг) с элементами
bij =
1, если j-я дуга заканчивается в i-й вершине
-1, если j-я дуга начинается в i-й вершине
0, иначе.
-1-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0-1 0-1-1 0 0 00 0 0 0 0 0 0
0 1 1-1 0 0-1-1 00 0 0 0 0 0 0
B(D)=
0 0 0 1 0 1 0 0 0 0-1-1-10 0 0
0 0 0 0 1 0 1 0-1-1 1 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 1 0-1-1 0
0 0 0 0 0 0 0 0 0 1 0 0 1 1 0-1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
Маршруты, которые соответствуют данному решению:
(х1; х2; х3; х5; х6; х8) = 1+1+1+3+2=8;
(х1; х3; х5; х6; х8) = 2+1+3+2=8;
(х1; х2; х3; х6; х8)=1+1+4+2=8;
(х1; х3; х6; х8)=2+4+2=8;
(х1; х2; х5; х6; х8)=1+2+3+2=8.
Маршруты, которые соответствуют данному решению:
(х1; х2; х3; х6)=1+1+4=6;
(х1; х3; х6)=2+4=6;
(х1; х2; х5; х6)=1+2+3=6;
(х1; х3; х5; х6;)=2+1+3=6;
(х1; х2; х3; х5; х6)=1+1+1+3=6.
Маршруты, которые соответствуют данному решению:
(х4; х6; х8)=6+2=8;
(х4; х5; х6; х8)=3+3+2=8.
Маршруты, которые соответствуют данному решению:
(х2; х3; х6)=1+4=5;
(х2; х5; х6)=2+3=5;
(х2; х3; х5; х6)=1+1+3=5.
Задача 4.
Расширение участка дороги требует переноса воздушной электролинии (длиной 1700 футов). В следующей таблице приведены планы выполнения работ по замене электролинии. Постройте соответствующую сеть и найдите критический путь.
Процесс |
Предшествующий процесс |
Длительность, дн. | |
А |
Определение объема продаж |
- |
1 |
В |
Извещение пользователей о временном отключении электросети |
А |
0,5 |
С |
Подвоз материалов и оборудования |
А |
1 |
D |
Предварительные работы |
А |
1 |
Е |
Заготовка опор и материалов |
С, D |
3 |
F |
Доставка опор |
Е |
3,5 |
G |
Определение нового местоположения опор |
D |
0,5 |
H |
Разметка местоположения опор |
G |
0,5 |
I |
Земельные работы для установки новых опор |
H |
3 |
J |
Установка новых опор |
F, I |
4 |
K |
Ограждение старой линии |
F, I |
1 |
L |
Прокладка новых проводов |
J, K |
2 |
М |
Обустройство новой линии |
L |
2 |
N |
Натяжка проводов |
L |
2 |
О |
Подрезка деревьев |
D |
2 |
Р |
Отключение старой электролинии |
В, М, N, О |
0,2 |
Q |
Подключение новой электролинии |
Р |
0,5 |
R |
Уборка территории |
Q |
1 |
S |
Возврат материалов и оборудования |
I |
2 |
Т |
Завершение проекта |
R, S |
Рисунок 1
Решение задачи:
I этап. Строим сетевой график. Рисунок 1.
II этап. Вычисляем tp(i). При вычислении tp(i) перемещаемся по сетевому графику от исходного события 1 к завершающему событию 18.
tp (1) = 0
tp (2) = tp (1) + t (1, 2) = 0 + 1 = 1
tp (3) = tp (2) + t (2, 3) = 1 + 1 = 2
tp (4) = max { tp (2) + t (2, 4), tp (3) + t (3, 4)} = max {1 + 1, 2 + 0} = 2
tp (5) = tp (3) + t (3, 5) = 2 + 0,5 = 2,5
tp (6) = tp (4) + t (4, 6) = 2 + 3 = 5
tp (7) = tp (5) + t (5, 7) = 2,5 + 0,5 = 3
tp (8) = tp (7) + t (7, 8) = 3 + 3 = 6
tp (9) = max { tp (6) + t (6, 9), tp (8) + t (8, 9)} = max {5+3,5, 6+0} = 8,5
tp (10) = tp (9) + t (9, 10) = 8,5 + 1 = 9,5
tp (11) = max { tp (9)+t (9,11), tp (10)+t (10,11)} = max {8,5+4, 9,5+0}=12,5
tp (12) = tp (11) + t (11,12) = 12,5 + 2 = 14,5
tp (13) = tp (12) + t (12,13) = 14,5 + 2 =16,5
tp (14) = max { tp (2)+t (2,14), tp (3)+t (3,14), tp (12)+t (12,14), tp (13)+ + t (13,14) } = max {1+0,5, 2+2, 14,5+2, 16,5+0} = 16,5
tp (15) = tp (14) + t (14,15) = 16,5 + 0,2 = 16,7
tp (16) = tp (15) + t (15,16) = 16,7 + 0,5 = 17,2
tp (17) = max { tp (8)+t (8,17), tp (16)+t (16,17)} = max {6+2, 17,2+1}=18,2
tp (18) = tp (17) + t (17,18) = 18,2 + 0 =18,2
Критический путь равен 18,2 дн.
III этап. Вычисляем tn(i). При вычислении tn(i) перемещаемся от завершающего события 18 к исходному событию 1 по сетевому графику против стрелок.
tn (18) = tp (18) = 18,2
tn (17) = tn (18) – t (17,18) = 18,2 – 0 = 18,2
tn (16) = tn (17) – t (16,17) = 18,2 – 1 = 17,2
tn (15) = tn (16) – t (15,16) = 17,2 – 0,5 = 16,7
tn (14) = tn (15) – t (14,15) = 16,7 – 0,2 = 16,5
tn (13) = tn (14) – t (13,14) = 16,5 – 0 = 16,5
tn (12) = min { tn(14)-t(12,14), tn(13)-t (12,13)} = min{16,5-2, 16,5-2}=14,5
tn (11) = tn (12) – t (11,12) = 14,5 - 2= 12,5
tn (10) = tn (11) – t (10,11) = 12,5 – 0 = 12,5
tn (9) = min { tn(10)-t(9,10), tn(11)-t (9,11)} = min{12,5-1, 12,5-4}= 8,5
tn (8) = min { tn(17)-t(8,17), tn(9)-t (8,9)} = min{18,2-2, 8,5-0} = 8,5
tn (7) = tn (8) – t (7,8) = 8,5-3 = 5,5
tn (6) = tn (9) – t (6,9) = 8,5 - 3,5 = 5
tn (5) = tn (7) – t (5,7) = 5,5 – 0,5 = 5
tn (4) = tn (6) – t (4,6) = 5 – 3 = 2
tn (3) = min { tn(4)-t(3,4), tn(5)-t (3,5), tn(14)-t (3,14)} = min{2-0, 5-0,5, 16,5 - 2} = 2
tn (2) = min { tn(4)-t(2,4), tn(3)-t (2,3), tn(14)-t (2,14)} = min{2-1, 2-1, 16,5--0,5} = 1
tn (1) = tn (2) – t (1,2) = 1 – 1 = 0
IV этап. Вычисляем R(i) – резерв времени события i, то есть из числа, полученных на этапе III, вычитаем числа, полученные на этапе II.
R (1) = 0
R (2) = 1 – 1 = 0
R (3) = 2 – 2 = 0
R (4) = 2 – 2 = 0
R (5) = 5 – 2,5 = 2,5
R (6) = 5 – 5 = 0
R (7) = 5,5 – 3 = 2,5
R (8) = 8,5 – 6 = 2,5
R (9) = 8,5 – 8,5 = 0
R (10) = 12,5 – 9,5 = 3
R (11) = 12,5 – 12,5 = 0
R (12) = 14,5 – 14,5 = 0
R (13) = 16,5 – 16,5 = 0
R (14) = 16,5 – 16,5 = 0
R (15) = 16,7 – 16,7 = 0
R (16) = 17,2 – 17,2 = 0
R (17) = 18,2 – 18,2 = 0
R (18) = 18,2 – 18,2 = 0
V этап. У критических событий резерв времени равен нулю, так как ранние и поздние сроки их свершения совпадают. На данном сетевом графике критических путей несколько. Критические события 1, 2, 3, 4, 6, 9, 11, 12, 13, 14, 15, 16, 17, 18 и определяют критические пути:
A-D-E-F-J-L-M-P-Q-R-T
A-C-E-F-J-L-N-P-Q-R-T
Критический путь равен 18,2 дн.