Задачи оптимизации на графах
Расчет временных характеристик чистового сетевого графика. Нахождение ранних и поздних сроков совершения событий. Определение критического времени пути. Построение графиков минимального покрывающего дерева. Составление таблицы результатов вычислений.
| Рубрика | Математика |
| Вид | задача |
| Язык | русский |
| Дата добавления | 03.04.2014 |
| Размер файла | 330,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://allbest.ru
Задача 1.
Условие: Дан полный граф с известными длинами ребер (табл.1). Найти а) минимальное покрывающее дерево; б) кратчайшие пути от вершины V1 ко всем остальным вершинам.
Таблица 1 - Исходные данные
|
Длины дуг |
|||||||||||||||
|
1,2 |
1,3 |
1,4 |
1,5 |
1,6 |
2,3 |
2,4 |
2,5 |
2,6 |
3,4 |
3,5 |
3,6 |
4,5 |
4,6 |
5,6 |
|
|
12 |
8 |
14 |
21 |
17 |
16 |
25 |
9 |
14 |
19 |
21 |
5 |
16 |
12 |
22 |
А) Постановка задачи: Рассмотрим связный граф G, длины ребер графа даны в таблице 1. Поставленная задача сводится к построению части G1 графа G, удовлетворяющего условиям:
1) G1 - связный;
2) G1 не содержит циклов;
3) G1 - содержит все вершины графа;
4) Сума ребер G1 минимальна по сравнению с другими частями, удовлетворяющими требованиям 1) - 3).
Решение: Составим таблицу 2 для удобства решения:
Таблица 2
|
Дуга |
Длинна |
Включение в дерево (+;-) |
1-ая группа вершин |
2-ая группа вершин |
|
|
3,6 |
5 |
+ |
3,6 |
- |
|
|
1,3 |
8 |
+ |
1,3,6 |
- |
|
|
2,5 |
9 |
+ |
- |
2,5 |
|
|
1,2 |
12 |
+ |
1,2,3,5,6 |
- |
|
|
4,6 |
12 |
+ |
1,2,3,4,5,6 |
- |
|
|
1,4 |
14 |
- |
- |
- |
|
|
2,6 |
14 |
- |
- |
- |
|
|
2,3 |
16 |
- |
- |
- |
|
|
4,5 |
16 |
- |
- |
- |
|
|
1,6 |
17 |
- |
- |
- |
|
|
3,4 |
19 |
- |
- |
- |
|
|
1,5 |
21 |
- |
- |
- |
|
|
3,5 |
21 |
- |
- |
- |
|
|
5,6 |
22 |
- |
- |
- |
|
|
2,4 |
25 |
- |
- |
- |
Искомое минимальное покрывающее дерево имеет вид (рис.1):
Рисунок 1 - Минимальное покрывающее дерево
сетевой график критический путь
Длинна минимального покрывающего дерева равна 46.
Б) Вычислим кратчайший путь от вершины V1 к другим, для удобства составим таблицу 3.
Таблица 3
|
V1 |
V2 |
V3 |
V4 |
V5 |
V6 |
|
|
0+,1 |
||||||
|
12;1 |
8+;1 |
14;1 |
21;1 |
17;1 |
||
|
12+;1 |
14;1 |
17;2 |
17;1 |
|||
|
14+;1 |
17;2 |
17;3 |
||||
|
17;2 |
17+;3 |
|||||
|
17+;2 |
Покрывающее дерево имеет вид (рис.2):
Рисунок 2 - Покрывающее дерево
Длинна покрывающего дерева равна 58.
Задача 2.
Условие: Построить сетевой график и провести расчет временных характеристик.
Таблица 4
|
Работы |
Предшествующие работы |
Время |
|
|
А1 |
- |
17 |
|
|
А2 |
- |
24 |
|
|
А3 |
- |
3 |
|
|
А4 |
- |
7 |
|
|
А5 |
А1, А2, А3 |
9 |
|
|
А6 |
А4 |
15 |
|
|
А7 |
А5, А6 |
30 |
|
|
А8 |
А5, А6 |
13 |
|
|
А9 |
А4 |
14 |
|
|
А10 |
А7 |
21 |
|
|
А11 |
А8, А9 |
19 |
|
|
А12 |
А10, А11 |
30 |
Построим черновой вариант графика (рис.3), основываясь на таблице 4:
Размещено на http://allbest.ru
Рисунок 3 - Черновой вариант сетевого графика
Произведем разбиение вершин на слои и введем коды работ (табл. 5 - 6).
Таблица 5
|
Слои |
Вершины |
|
|
1 |
1 |
|
|
2 |
2,3 |
|
|
3 |
4 |
|
|
4 |
5,6 |
|
|
5 |
7 |
|
|
6 |
8 |
Таблица 6
|
Работы |
Коды |
|
|
А1 |
1,3 |
|
|
А2 |
1,3 |
|
|
А3 |
1,3 |
|
|
А4 |
1,2 |
|
|
А5 |
3,4 |
|
|
А6 |
2,4 |
|
|
А7 |
4,5 |
|
|
А8 |
4,6 |
|
|
А9 |
2,6 |
|
|
А10 |
5,7 |
|
|
А11 |
6,7 |
|
|
А12 |
7,8 |
Построим чистовой вариант сетевого графика (рис. 4):
Размещено на http://allbest.ru
Рисунок 4 - Чистовой сетевой график
Произведем расчет временных характеристик. Находим ранние и поздние сроки совершения событий, результаты вычислений занесем в таблицу 7.
Таблица 7
|
i |
tp(i) |
tп(i) |
ri |
|
|
1 |
0 |
0 |
0 |
|
|
2 |
7 |
18 |
11 |
|
|
3 |
24 |
24 |
0 |
|
|
4 |
33 |
33 |
0 |
|
|
5 |
63 |
63 |
0 |
|
|
6 |
46 |
65 |
19 |
|
|
7 |
84 |
84 |
0 |
|
|
8 |
114 |
114 |
0 |
Полагаем, что tп(8) = 114, далее используем формулу для tп(i).
Имеем:
Определим критическое время:
Критический путь проходит через все вершины, для которых ri=0, его длина равна 114 обозначим его жирными стрелками (рис.4).
Вычислим ранние и поздние сроки начала и окончания работ по формулам (5) - (8) из методических указаний, результаты вычислений оформим в виде таблицы 8.
Таблица 8
|
i, j |
tij |
tрн |
tро |
tпо |
tпн |
Rij |
rij |
|
|
1,2 |
7 |
0 |
7 |
18 |
11 |
11 |
0 |
|
|
1,3 |
3 |
0 |
3 |
24 |
21 |
21 |
21 |
|
|
1,3 |
17 |
0 |
17 |
24 |
7 |
7 |
7 |
|
|
1,3 |
24 |
0 |
24 |
24 |
0 |
0 |
0 |
|
|
2,4 |
15 |
7 |
22 |
33 |
18 |
11 |
11 |
|
|
2,6 |
14 |
7 |
21 |
65 |
51 |
44 |
25 |
|
|
3,4 |
9 |
24 |
33 |
33 |
24 |
0 |
0 |
|
|
4,5 |
30 |
33 |
63 |
63 |
33 |
0 |
0 |
|
|
4,6 |
13 |
33 |
46 |
65 |
52 |
19 |
0 |
|
|
5,7 |
21 |
63 |
84 |
84 |
63 |
0 |
0 |
|
|
6,7 |
19 |
46 |
65 |
84 |
65 |
19 |
19 |
|
|
7,8 |
30 |
84 |
114 |
114 |
84 |
0 |
0 |
Из таблицы 8 вытекает, что работам, лежащим на критическом пути, соответствуют резервы времени Rij и rij, равные нулю.
Размещено на Allbest.ru
Подобные документы
Теория графов. Параметры сетевого графика. Наиболее ранний из возможных сроков совершения того или иного события. Расчет основных временных параметров. Путь в сетевом графике. Опасность срыва наступления завершающего события. Частный резерв времени.
курсовая работа [3,3 M], добавлен 14.03.2009Исследование функции на четность и периодичность. Нахождение вертикальных, горизонтальных (или наклонных) асимптот, а также экстремумов и интервалов монотонности. Определение интервалов выпуклости и точки перегиба. Построение графика исследуемой функции.
презентация [134,7 K], добавлен 21.09.2013Ознакомление с математическим аппаратом анализа временных рядов и моделями авторегрессии. Составление простейших моделей авторегрессии стационарных временных рядов. Оценка дисперсии и автоковариации, построение графика автокорреляционной функции.
лабораторная работа [58,7 K], добавлен 14.03.2014Составление математической модели задачи. Приведение ее к стандартной транспортной задаче с балансом запасов и потребностей. Построение начального опорного плана задачи методом минимального элемента, решение методом потенциалов. Анализ результатов.
задача [58,6 K], добавлен 16.02.2016Изучение теории сетевого планирования. Оптимизация исходного сетевого графика по времени. Сетевое планирование изготовления ригелей. Приписывание относительных весов. Анализ графика распределения ресурсов (неравномерности) по времени выполнения заказа.
контрольная работа [145,1 K], добавлен 19.06.2013Алгоритм построения минимального остовного дерева. Последовательность выполнения алгоритма Прима, его содержание и назначение. Процедура рисования графа. Порядок составления и тестирования программы, ее интерфейс, реализация и правила эксплуатации.
курсовая работа [225,0 K], добавлен 30.04.2011Характеристика полной группы событий как совокупность всех возможных результатов опыта. Способы определения вероятности событий в задачах разного направления. Нахождение вероятности количества нестандартных деталей. Построение функции распределения.
задача [37,9 K], добавлен 19.03.2011Вычисление и исследование предела и производной функции, построение графиков. Вычисление неопределенных интегралов, площади фигуры, ограниченной графиками функций. Нахождение решения дифференциального уравнения и построение графиков частных решений.
контрольная работа [153,6 K], добавлен 19.01.2010Определение вертикальной, горизонтальной и наклонной асимптот графиков функций. Точки разрыва и область определения функции. Нахождение конечного предела функции. Неограниченное удаление точек графика от начала координат. Примеры нахождения асимптот.
презентация [99,6 K], добавлен 21.09.2013Определение вероятности для двух несовместных и достоверного событий. Закон распределения случайной величины; построение графика функции распределения. Нахождение математического ожидания, дисперсии, среднего квадратичного отклонения случайной величины.
контрольная работа [97,1 K], добавлен 26.02.2012
