WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |

Рисунок 57 Рисунок Рассмотрим подмножество {(4,6)}. Включая дугу (4, 6) в контур, следует запретить вхождение в него дуги (6, 4) (рис. 58). Вычеркиваем 4 строку, 6 столбец и запрещаем В результате будет получена полностью приведенная переход (6, 4). В результате получится матрица, приведенная матрица:

на рисунке 59.

(4,6) 1 2 3 4 1 2 3 4 5 1 8 13 0 1 8 13 0 23 2 12 3 0 2 12 3 0 4 3 5 0 20 3 5 0 20 0 5 55 41 3 4 6 51 36 10 6 0 34 0 5 55 41 3 0 6 0 34 0 10 15 Рисунок 57 Так как в каждой строке и каждом столбце вновь по 1 2 3 4 5 1 2 3 4 (1,4) (1,4) лученной матрицы есть нулевой элемент, то = 70.

{(4,6)} 1 8 13 23 8 1 0 5 Невключение дуги (4, 6) в множество гамильтоновых 2 12 3 0 4 2 12 3 0 контуров приводит к матрице, приведенной на рисунке 60.

3 5 0 20 0 3 5 0 20 Полученную таким образом матрицу можно привести по 5 55 41 3 0 5 55 41 3 строке и 6 столбцу, в результате чего оценка увеличится на 6 0 34 0 15 6 0 34 0 24 и станет равной 94. На рисунке 61 приведено дерево реРисунок шений с оценками вершин на данном этапе.

Включение дуги (1, 4) потребует запретить переход Так как 70<94, то рассматриваем множество контупо дуге (6, 1) (рис. 65). Соответствующая матрица после выров, включающих дугу (4, 6). Выполняем оценку нулевых черкивания 1 строки, 4 столбца и замены элемента (6, 1) на элементов матрицы, приведенной на рисунке 62.

, приведена на рисунке. 66.

Рисунок Рисунок Рисунок Рисунок Эту матрицу следует привести по строкам и столбцам. Результат приведения показан на рис. 67.

(1, 4) 1 2 3 (1, 4) 1 2 3 2 9 0 2 12 3 4 3 5 0 3 5 0 5 52 38 5 55 41 3 6 34 0 6 34 0 Рисунок 62 Рисунок (1, 4) 1 2 3 2 4 0 Наибольшую оценку, равную 8, имеют два элемента, 3 0 0 поэтому выбираем любой из них, например, (1, 4). На рис. 5 47 38 приведено дерево решений на данном этапе.

6 34 0 Невключение дуги (1, 4) в контур приведет к увеличеРисунок нию оценки на 8 (рис. 64).

59 В результате получаем дерево решений, приведенное ний на данном этапе принимает вид в соответствии с рина рисунке 68.

сунком 69.

Невключение дуги (1, 2) приведет к увеличению оценки на 5 (рис. 71).

(1,2) (1,2) 1 2 3 4 5 1 2 3 4 1 5 15 1 0 2 12 3 0 4 2 12 3 0 3 5 0 20 0 3 5 0 20 5 55 41 3 0 5 55 41 3 6 0 34 0 15 6 0 34 0 Рисунок Включение дуги (1, 2) потребует запретить переход по дуге (2, 1) (рис. 72).

Рисунок 68 Рисунок Так как 78<81, следует использовать вариант невклю(1,2) 1 3 4 чения дуги (1, 4). Это означает возврат к матрице, приведен2 3 0 ной на рис. 64 справа. Выполняем оценку нулевых элементов 3 5 20 5 55 3 этой матрицы (рис. 70).

6 0 0 (1,4) 1 2 3 4 Рисунок 72 Рисунок 1 05 5 Соответствующая матрица после вычеркивания 1 стро2 12 3 03 ки, 2 столбца и замены элемента (2, 1) на приведена 3 5 00 20 на рисунке 73.

5 55 41 3 6 05 34 03 Эта матрица приведена по строкам и столбцам. В реРисунок зультате получаем дерево решений, приведенное на рисунке Наибольшую оценку получил элемент, расположен74. Так как 78<83, продолжаем решение задачи по ветке, ный в 1 строке и 2 столбце. Следовательно, дерево решевключающей дугу (1, 2).

61 в 3 строке и 5 столбце. Следовательно, дерево решений на данном этапе принимает вид в соответствии с рисунком 76.

Невключение дуги (3, 5) приведет к увеличению оценки на 9 (рис. 77).

1 3 4 5 1 3 4 (3,5) (3,5) 2 3 0 4 2 3 0 3 5 20 5 3 0 5 55 3 0 5 55 3 6 0 0 15 6 0 0 1 3 4 (3,5) 2 3 0 Рисунок 74 Рисунок 3 0 5 55 3 6 0 0 Рисунок Включение дуги (3, 5) потребует запретить переход по дуге (5, 3) (рис. 78).

Рисунок Соответствующая матрица после вычеркивания 3 строки, 5 столбца и замены элемента (5, 3) на приведена на рисунке 79.

(3,5) 1 3 (3,5) 1 3 2 3 2 3 5 55 5 55 Рисунок 6 055 6 0 Выполняем оценку нулевых элементов матрицы, приРисунок 79 Рисунок веденной на рисунке 73. Результат оценки показан на рисунке 75. Наибольшую оценку получил элемент, расположенный 63 Эта матрица приведена по строкам и столбцам. Следовательно, оценка длины контура в 78 единиц остается неизменной. Так как 78<78+8, продолжаем решение задачи по ветке, включающей дугу (3, 5).

Выполняем оценку нулевых элементов матрицы, приведенной на рисунке 79. Результат приведения показан на рисунке 80.

Наибольшую оценку получили два элемента (5 строка, столбец и 6 строка, 1 столбец). Следовательно, дерево решений на данном этапе принимает вид в соответствии с рисунком 82.

Невключение дуги (5, 4) приведет к увеличению оценки Рисунок на 55 (рис. 81).

(5,4) 1 3 4 (5,4) 1 3 2 3 0 2 3 5 55 5 0 6 0 0 6 0 Рисунок Включение дуги (5, 4) потребует запретить переход Рисунок 83 Рисунок по дуге (6, 3) (рис. 83). Соответствующая матрица после Приводя полученную квадратную матрицу порядка путем вычитания 3 из первой строки, получаем увеличение вычеркивания 5 строки и 4 столбца и запрета перехода по оценки на 3.

дуге (6,3) приведена на рисунке 85 слева.

(5,4) 1 3 (5,4) 1 2 3 3 2 6 0 6 Рисунок 65 В последней матрице выбор двух оставшихся дуг про- Задачи для самостоятельного решения изводится однозначно - это дуги (6, 1) и (2, 3). На рисунке 1. Найти решение задачи Беллмана-Джонсона для двух приведен полученный контур, а на рисунке 86 – дерево репоследовательных приборов. Длительности обслуживания шений. Длина полученного контура равна 81.

Анализируя полученное решение, приходим к выводу о приборами А и В приведены в таблице 10.

том, что оно оптимально, так как оценки всех остальных Таблица «оборванных» ветвей дерева решений не меньше полученного значения.

вариант к 1 2 3 4 5 6 7 8 9 tкA 1 5 4 5 4 2 4 3 5 2 tкB 2 1 2 4 3 4 1 3 2 tкA 2 2 4 5 5 4 3 1 2 1 tкB 5 3 4 5 2 1 4 3 1 tкA 3 3 1 5 3 3 3 1 5 3 tкB 5 3 4 4 4 4 2 1 1 tкA 4 1 2 3 1 1 2 1 4 5 tкB 4 3 1 4 3 3 3 4 1 tкA 5 2 1 3 3 4 1 2 3 3 tкB 4 3 3 4 5 3 1 4 4 tкA 6 4 5 1 2 3 2 4 4 4 tкB 3 3 3 4 3 1 2 1 1 tкA 7 4 4 2 5 5 5 5 4 5 tкB 4 1 1 5 1 3 5 1 1 tкA 8 2 5 5 2 3 2 5 4 2 tкB 5 4 1 2 3 3 4 4 2 tкA 9 3 5 3 1 2 5 3 3 5 tкB 1 3 2 4 5 1 2 2 2 tкA 10 5 4 1 2 1 5 1 3 2 tкB 2 5 3 5 3 3 2 5 4 Рисунок 67 Продолжение таблицы 2.3. 2.4.



tкA 11 2 4 3 1 4 5 4 3 1 22 30 14 41 34 64 57 52 1 tкB 3 3 1 3 3 5 1 5 2 23 17 11 19 29 37 40 3 68 32 27 47 31 49 29 3 33 9 tкA 12 1 2 2 5 3 1 3 4 3 9 54 44 17 3 48 35 29 44 tкB 4 4 2 1 1 5 3 5 2 62 48 13 7 36 49 64 4 8 13 47 16 23 32 43 3 69 16 tкA 13 4 4 3 5 5 4 1 3 3 tкB 2 2 5 5 2 3 3 3 5 2.5. 2.6.

60 31 66 7 15 9 67 42 40 tкA 14 3 5 5 4 1 4 1 3 5 7 23 4 37 58 47 66 31 6 tкB 2 5 2 5 3 5 3 3 1 32 43 18 5 12 1 4 9 43 4 31 56 50 9 19 69 4 47 tкA 15 1 4 5 4 1 4 1 1 4 50 37 58 34 11 31 46 68 10 tкB 2 2 4 3 5 1 3 1 5 12 43 38 60 48 69 39 7 15 tкA 16 2 4 1 2 3 5 3 4 2 2.7. 2.8.

tкB 5 1 3 2 2 1 4 4 5 17 53 29 34 16 65 60 59 3 tкA 17 5 2 2 1 1 5 5 4 4 35 41 20 37 45 61 34 70 70 41 4 65 38 59 30 29 44 16 tкB 1 5 5 3 4 3 5 4 1 40 29 46 15 40 58 41 10 28 tкA 18 5 2 2 4 4 1 1 5 1 33 4 49 50 25 55 58 38 12 49 11 8 35 24 24 57 56 15 tкB 5 1 5 3 2 3 3 2 4 tкA 19 1 5 4 1 3 4 5 1 1 2.9. 2.10.

tкB 22 54 52 41 52 27 28 4 3 1 2 1 4 1 1 3 3 5 17 52 35 36 28 58 14 70 6 tкA 20 4 1 2 1 5 1 4 1 5 4 62 63 35 41 68 19 10 43 37 63 7 36 68 4 43 22 33 tкB 5 4 5 1 5 5 1 4 1 19 34 17 64 10 47 44 58 69 65 34 62 3 26 50 9 35 2 2. Найти точное решение задачи коммивояжера методом ветвей и границ.

2.11. 2.12.

2.1. 2.2.

6 9 60 8 18 8 66 17 32 31 15 19 8 55 20 28 12 39 44 16 49 34 58 1 35 70 62 19 22 31 7 35 21 15 9 17 10 41 11 56 6 4 59 35 30 25 43 53 57 16 30 25 45 29 43 30 40 17 4 52 30 41 51 5 50 49 39 9 7 52 40 15 49 42 26 18 41 18 8 32 6 24 24 33 5 14 60 46 11 5 59 64 18 52 27 13 63 40 24 34 26 6 3 36 11 45 14 21 69 Решение. При построении сетевого графика необхо2.13. 2.14. димо следовать следующим правилам [4]:

41 13 10 5 31 26 54 63 8 1) длина стрелки не зависит от времени выполнения работы;

45 16 28 6 67 40 68 17 16 2) стрелка может не быть прямолинейным отрезком;

45 4 50 12 61 42 43 64 68 3) для действительных работ используются сплошные, а для 37 31 24 20 67 60 18 9 49 фиктивных – штриховые стрелки;

7 6 62 24 40 21 32 9 7 4) каждая операция должна быть представлена только одной 49 41 3 7 26 29 44 43 24 стрелкой;

2.15. 2.16.

38 3 6 26 34 14 9 16 35 55 5) между одними и теми же событиями не должно быть па14 5 33 24 24 38 39 57 7 раллельных работ, т.е. работ с одинаковыми кодами 9 39 49 50 5 3 5 53 31 (рис. 87);

16 57 53 43 25 6 33 49 22 35 7 31 22 19 26 24 50 43 55 8 19 15 31 34 24 5 25 2.17. 2.18.

1 53 60 48 33 2 45 3 43 2 9 32 9 27 1 38 22 21 45 38 24 39 38 53 9 39 58 Рисунок 87 Рисунок 3 22 39 50 10 60 32 24 26 6) следует избегать пересечения стрелок (рис. 88);

43 21 58 26 37 48 9 39 50 35 2 11 25 19 33 27 38 10 37 7) не должно быть стрелок, направленных справа налево;

4. Сетевое планирование и управление Пример 10. Построить сетевую модель программы опроса общественного мнения, которая включает работы, представленные в таблице 11. Найти критический путь.

Таблица Длительность Код Содержание работы работы работы (в днях) Разработка анкет A Распечатка анкет B 0,Прием на работу персонала C Обучение персонала D Выбор опрашиваемых лиц E Рассылка им анкет F Рисунок Анализ полученных данных G 71 8) номер начального события должен быть меньше номера Если в узел j входят несколько операций, то ранним конечного события; моментом события j является максимальная из сумм 9) не должно быть висячих (т.е. не имеющих предшест{Е + t }, где максимум берется по всем дугам (k, j). Ранk kj вующих событий), кроме исходного, и тупиковых событий ним началом операции (i, j) является ранний момент события (т.е. не имеющих последующих событий), кроме завершаюi. Для определения раннего окончания операции (i, j) следует щего (рис. 89);

найти сумму E + t.

i ij 10) не должно быть циклов (рис.90).

2) Вычислительный процесс для определения поздних моментов событий сетевого графика называется обратным проходом. Для обозначения поздних моментов принято использовать сокращение L (от английского слова late) и значок. Вычисления начинаются с последнего узла. Поздний момент его полагается равным раннему моменту (если поздРисунок ний момент завершающего события не задан). Поздний моПод временными характеристиками сетевого графика мент события i определяется как разность между поздним понимают:

моментом последующего события j и длительностью опера1) ранние и поздние моменты начала операций;

ции (i, j) (рис. 92). Если из узла i выходят несколько опера2) ранние и поздние моменты окончания операций;

ций, то поздним моментом является минимальная из разно3) резервы операций (полный, свободный, независистей {L - t }, где минимум берется по всем дугам (i, k).

k ik мый);

Поздним окончанием операции (i, j) является поздний мо1) Ранний момент события i – это наиболее раннее времент события j. Для определения позднего начала операции мя, когда возможно начало операций, исходящих из узла i.

(i, j) следует найти разность Lj - tij.

Вычислительный процесс для определения ранних моментов событий называется прямым проходом сетевого графика. Для обозначения ранних моментов принято использовать сокращение Е (от английского слова early) и значок. Для начального узла сетевого графика ранний момент полагается равным нулю. Ранний момент события j (j>1) определяется как сумма раннего момента предыдущего события Еi и длительности соответствующей операции (i, j) (рис. 91).





Рисунок п с н 3) Полный Rij, свободный Rij и независимый Rij резервы операции (i, j) вычисляются по формулам:

п Rij = L - E - t ;

j i ij с Rij = E - E - t ;

Рисунок j i ij 73 н менно. Завершающей работой проекта является анализ полуRij = max{0, E - Li - t }.

j ij ченных данных (G), который нельзя выполнить без предваНа рисунке 93 все виды резервов показаны схематично.

рительной рассылки анкет (F). В результате этих рассуждеПолный резерв используется, в основном, для устаний построим сетевую модель и пронумеруем события моденовления приоритетов операций. Свободный резерв испольли (рис.94). Нетрудно заметить, что критическим путем будет зуется, в основном, для выявления операций, задержка выпуть 123567.

полнения которых не повлияет на полные резервы последующих операций. Независимый резерв устанавливает операции, задержка выполнения которых не влияет на полные резервы ни предшествующих, ни последующих операций.

Рисунок Пример 11. Построить сетевую модель, включающую некоторую совокупность работ, связанных между собой отношениями предшествования:

1) A, B и C – исходные операции проекта;

2) A и B предшествуют D;

Рисунок 3) B предшествует E и H;

Критический путь – это полный путь максимальной 4) C предшествует G;

длины. Операции, лежащие на критическом пути, также на5) E и H предшествуют I и J;

зывают критическими.

6) C, D и J предшествуют K;

Из условия задачи известно содержание работ, но яв- 7) K предшествует L.

но не указаны взаимосвязи между работами. Поэтому для их Решение. В пункте 1) условия явно указано, что рабоустановления необходимо проанализировать смысл каждой ты A, B и C являются исходными, поэтому изобразим их конкретной работы и выяснить, какие из остальных работ тремя стрелками, выходящими из исходного события 1.

должны ей непосредственно предшествовать. Исходной (на- Пункт 2) условия означает, что стрелки работ A и B должны войти в одно событие, из которого выйдет стрелка работы D.

чальной) работой, начинающей сетевой график, в данном Но поскольку стрелки работ A и B начинаются в одном сослучае является «прием на работу» (С), поскольку все осбытии, то имеет место параллельность работ, которая недотальные работы должны выполняться уже принятыми на рапустима правилами построения сетевых моделей.

боту сотрудниками. Перед выполнением всех работ по опроДля ее устранения введем дополнительное событие 2, су общественного мнения необходимо обучить персонал (D).

в которое войдет работа B, а затем соединим события 2 и 3, в Перед тем как разослать анкеты (F), их надо разработать (A), которые входят работы A и B, штриховой стрелкой фиктивраспечатать (B) и выбрать опрашиваемых лиц (E), причем ной работы. В данном случае фиктивная работа (2,3) не соотработу с анкетами и выбор лиц можно выполнять одновреветствует никакой реальной работе, а лишь отображает логи 75 ческую связь между работами B и D. Дальнейшее построение Пример 12. Определить временные характеристики рассмотрим с помощью рисунка 95. сетевого графика, представленного на рисунке 96. Указать критический путь.

Согласно пункту 3) условия задачи, из события 2 выРешение. Для критических операций должны выполходят две стрелки работ E и H. Согласно пункту 4) условия няться следующие условия: а) ранний и поздний моменты задачи стрелка работы C должна войти в общее событие, из для начального и конечного узлов таких операций должны которого выйдет стрелка работы G. Проблема с параллельнобыть равны; б) критические операции не имеют резервов стью работ E и H (пункт 5 условия задачи) решается путем времени никакого вида.

введения дополнительного события 5 и фиктивной работы Ранее начало операций (1, 2), (1, 3) и (1, 4) равно 0.

(5,6). Для отображения в сетевой модели пункта 6) условия Событие 2 является начальным для работы (2, 5), а событие задачи введем стрелки работ D и J в событие 7, а связь рабо3 – для работ (3, 5) и (3 6). Так как событию 5 предшествуют ты C с работой K отобразим с помощью фиктивной работы две операции, выбираем максимальное из значений 4+2 и 5+6. Следовательно, ранние начало операции (5, 7) равно 11.

(4,7). Стрелку работы C нельзя напрямую вводить в собыАналогично, ранее начало операции (6, 7) равно 10. Ранний тие 7, потому что после нее должна следовать работа G, комомент наступления события 7 – это max{11+2, 10+5}=15.

торая с работами D и J никак не связана. Стрелка работы L Следовательно, проект может завершиться по прошествии не выходит из события 8, т.е. после окончания работы K в соотменее чем 15 единиц времени.

ветствии с пунктом 7) условия задачи.

Рисунок Начинаем расчет поздних моментов наступления событий. В соответствии с алгоритмом поздний момент настуРисунок пления события 7 равен раннему моменту, т.е. 15. Остальные значения приведены на рисунке 97 и в таблице 12. ВычислеПоскольку в условии не указано, что работы L, I и G ние всех остальных временных характеристик приведено в предшествуют каким-либо другим работам, то эти работы таблице 12. Из таблицы видно, что у проекта два критичеявляются завершающими и их стрелки войдут в завершаюских пути: 1467 и 1367. Длина критического щее событие 9.

пути равна 15.

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.