Задачи оптимизации на графах
Рассмотрение особенностей проведения расчетов временных характеристик. Знакомство с задачами оптимизации на графах. Наиболее распространенные способы построения сетевого графика, анализ проблем. Характеристика полного графа с известными длинами ребер.
| Рубрика | Математика |
| Вид | задача |
| Язык | русский |
| Дата добавления | 03.04.2014 |
| Размер файла | 501,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Задача 1
Дан полный граф с известными длинами ребер (табл.1). Найти а) минимальное покрывающее дерево; б) кратчайшие пути от вершины V1 ко всем остальным вершинам.
Таблица 1 - Исходные данные
А)
Постановка задачи: Рассмотрим связный граф G, длины ребер графа даны в таблице 1. Поставленная задача сводится к построению части G1 графа G, удовлетворяющего условиям:
1) G1 - связный;
2) G1 не содержит циклов;
3) G1 - содержит все вершины графа;
4) Сума ребер G1 минимальна по сравнению с другими частями, удовлетворяющими требованиям 1) - 3).
Решение: Составим таблицу 2 для удобства решения:
Таблица 2
|
Дуга |
Длинна |
Включение в дерево (+;-) |
1-ая группа вершин |
2-ая группа вершин |
|
|
1,5 |
5 |
+ |
1,5 |
- |
|
|
1,4 |
7 |
+ |
1,4,5 |
- |
|
|
4,5 |
7 |
- |
- |
- |
|
|
2,6 |
8 |
+ |
- |
2,6 |
|
|
4,6 |
9 |
+ |
1,2,4,5,6 |
- |
|
|
2,5 |
10 |
- |
- |
- |
|
|
5,6 |
10 |
- |
- |
- |
|
|
1,2 |
11 |
- |
- |
- |
|
|
2,4 |
12 |
- |
- |
- |
|
|
1,6 |
13 |
- |
- |
- |
|
|
3,6 |
15 |
+ |
1,2,3,4,5,6 |
- |
|
|
1,3 |
20 |
- |
- |
- |
|
|
3,4 |
21 |
- |
- |
- |
|
|
2,3 |
24 |
- |
- |
- |
|
|
3,5 |
24 |
- |
- |
- |
Искомое минимальное покрывающее дерево имеет вид:
Рисунок 1 - Минимальное покрывающее дерево
Длинна минимального покрывающего дерева равна 40.
Б) Вычислим кратчайший путь от вершины V1 к другим, для удобства составим таблицу 3.
Таблица.3
|
V1 |
V2 |
V3 |
V4 |
V5 |
V6 |
|
|
0+,1 |
||||||
|
11;1 |
20;1 |
7;1 |
5+;1 |
13;1 |
||
|
11;1 |
17;1 |
7+;2 |
13;2 |
|||
|
11+;1 |
17;1 |
13;2 |
||||
|
17;1 |
13+;2 |
|||||
|
17+;1 |
Покрывающее дерево имеет вид (рис.2):
Длинна покрывающего дерева равна 53.
Рисунок 2 - Покрывающее дерево
Задача 2
Построить сетевой график и провести расчет временных характеристик.
Таблица 4
|
Работы |
Предшествующие работы |
Время |
|
|
А1 |
- |
2 |
|
|
А2 |
А1 |
8 |
|
|
А3 |
- |
11 |
|
|
А4 |
А1 |
14 |
|
|
А5 |
А3, А4 |
5 |
|
|
А6 |
А1 |
15 |
|
|
А7 |
А5 |
25 |
|
|
А8 |
А2 |
13 |
|
|
А9 |
А2 |
20 |
|
|
А10 |
А6, А7, А8 |
17 |
|
|
А11 |
А9, А10 |
18 |
|
|
А12 |
А6, А7, А8 |
30 |
|
|
А13 |
А11, А12 |
23 |
|
|
А14 |
А5 |
18 |
|
|
А15 |
А13, А14 |
7 |
Построим черновой вариант графика (рис.3), основываясь на таблице 4:
Рисунок 3 - Черновой вариант сетевого графика
Произведем разбиение вершин на слои и введем коды работ (табл. 5 - 6).
Таблица 5
Таблица 6
Построим чистовой вариант сетевого графика (рис. 4):
Рисунок 4 - Чистовой сетевой график
Произведем расчет временных характеристик. Находим ранние и поздние сроки совершения событий, результаты вычислений занесем в таблицу 7.
Таблица 7
Полагаем, что tп(10) = 106, далее используем формулу для tп(i).
Имеем:
Определим критическое время:
Критический путь проходит через все вершины, для которых ri=0, его длина равна 106 обозначим его пунктирными стрелками (рис.4).
Вычислим ранние и поздние сроки начала и окончания работ по формулам (5) - (8) из методических указаний, результаты вычислений оформим в виде таблицы 8.
расчет временной сетевой график
Таблица 8
|
i, j |
tij |
tрн |
tро |
tпо |
tпн |
Rij |
rij |
|
|
1,2 |
2 |
0 |
2 |
2 |
0 |
0 |
0 |
|
|
1,3 |
11 |
0 |
11 |
11 |
0 |
0 |
0 |
|
|
2,4 |
8 |
2 |
10 |
28 |
20 |
18 |
0 |
|
|
2,5 |
14 |
2 |
16 |
16 |
2 |
0 |
0 |
|
|
2,6 |
15 |
2 |
17 |
41 |
26 |
24 |
24 |
|
|
3,5 |
5 |
11 |
16 |
16 |
11 |
0 |
0 |
|
|
4,6 |
13 |
10 |
23 |
41 |
28 |
18 |
18 |
|
|
4,7 |
20 |
10 |
30 |
58 |
38 |
28 |
28 |
|
|
5,6 |
25 |
16 |
41 |
41 |
16 |
0 |
0 |
|
|
5,9 |
28 |
16 |
44 |
99 |
71 |
55 |
55 |
|
|
6,7 |
17 |
41 |
58 |
58 |
41 |
0 |
0 |
|
|
6,8 |
30 |
41 |
71 |
76 |
46 |
5 |
5 |
|
|
7,8 |
18 |
58 |
76 |
76 |
58 |
0 |
0 |
|
|
8,9 |
23 |
76 |
99 |
99 |
76 |
0 |
0 |
|
|
9,10 |
7 |
99 |
106 |
106 |
99 |
0 |
0 |
Из таблицы 8 вытекает, что работам, лежащим на критическом пути, соответствуют резервы времени Rij и rij, равные нулю.
Размещено на Allbest.ru
...Подобные документы
Операции на графах позволяют образовывать новые графы из нескольких более простых. Операции на графах без параллельных ребер. Объединение графов. Свойства операции объединения т, которые следуют из определения операции и свойств операций на множествах.
реферат [106,0 K], добавлен 27.11.2008Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.
контрольная работа [466,3 K], добавлен 11.03.2011Способы решения задач дискретной математики. Расчет кратчайшего пути между парами всех вершин в ориентированном и неориентированном графах с помощью использования алгоритма Флойда. Анализ задачи и методов ее решения. Разработка и характеристика программы.
курсовая работа [951,4 K], добавлен 22.01.2014Общая характеристика распространенных проблем поиска величины максимального потока в сети при помощи алгоритма Форда-Фалкерсона. Знакомство с задачами по дискретной математике. Рассмотрение особенностей и этапов постройки дерева кратчайших расстояний.
контрольная работа [740,3 K], добавлен 09.03.2015Метод Форда-Беллмана для нахождения расстояния от источника до всех вершин графа. Алгоритмы поиска расстояний и отыскания кратчайших путей в графах. Блочно-диагональный вид и матрица в исследовании системы булевых функций и самодвойственной функции.
курсовая работа [192,1 K], добавлен 10.10.2011Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
курсовая работа [2,4 M], добавлен 08.10.2014Способы построения интерполяционных многочленов Лагранжа, основные этапы. Интерполирование функций многочленами Ньютона, способы построения графика. Постановка задачи аппроксимации функции одной переменной, предпосылки повышения точности расчетов.
презентация [204,5 K], добавлен 18.04.2013Поиск кратчайших путей для пар вершин взвешенного ориентированного графа с весовой функцией. Включение матрицы в алгоритм Флойда, содержащую вершину, полученную при нахождении кратчайшего пути. Матрица, которая содержит длины путей из вершины в вершину.
презентация [36,1 K], добавлен 16.09.2013Общее понятие, основные свойства и закономерности графов. Задача о Кенигсбергских мостах. Свойства отношения достижимости в графах. Связность и компонента связности графов. Соотношение между количеством вершин связного плоского графа, формула Эйлера.
презентация [150,3 K], добавлен 16.01.2015Рассмотрение эффективности применения методов штрафов, безусловной оптимизации, сопряженных направлений и наискорейшего градиентного спуска для решения задачи поиска экстремума (максимума) функции нескольких переменных при наличии ограничения равенства.
контрольная работа [1,4 M], добавлен 16.08.2010Кусторез как устройство, предназначенное для остатков травяной и кустовой поросли различного характера: особенности математической обработки данных, проведение экспериментальной оптимизации параметров. Анализ карты оптимизации потребляемой мощности.
курсовая работа [2,1 M], добавлен 19.03.2013Оптимизация как раздел математики, ее определение, сущность, цели, формулировка и особенности постановки задач. Общая характеристика различных методов математической оптимизации функции. Листинг программ основных методов решения задач оптимизации функции.
курсовая работа [414,1 K], добавлен 20.01.2010Математическая задача оптимизации. Минимум функции одной и многих переменных. Унимодальные и выпуклые функции. Прямые методы безусловной оптимизации и минимизации, их практическое применение. Методы деления отрезка пополам (дихотомия) и золотого сечения.
курсовая работа [2,0 M], добавлен 26.08.2009Теория графов. Параметры сетевого графика. Наиболее ранний из возможных сроков совершения того или иного события. Расчет основных временных параметров. Путь в сетевом графике. Опасность срыва наступления завершающего события. Частный резерв времени.
курсовая работа [3,3 M], добавлен 14.03.2009Знакомство с особенностями построения математических моделей задач линейного программирования. Характеристика проблем составления математической модели двойственной задачи, обзор дополнительных переменных. Рассмотрение основанных функций новых переменных.
задача [656,1 K], добавлен 01.06.2016Анализ теорем сопряженных функторов. Естественное преобразование как семейство морфизмов. Характеристика свойств рефлективных подкатегорий. Знакомство с универсальными стрелками. Рассмотрение особенностей метода построения сопряженных функторов.
курсовая работа [3,1 M], добавлен 27.01.2013Рассмотрение особенностей метода построения полного проверяющего теста для недетерминированных автоматов относительно неразделимости для модели "черного ящика" и разработка предложений по его модификации. Исследование условий усечения дерева преемников.
курсовая работа [1,3 M], добавлен 20.08.2010Изучение теории сетевого планирования. Оптимизация исходного сетевого графика по времени. Сетевое планирование изготовления ригелей. Приписывание относительных весов. Анализ графика распределения ресурсов (неравномерности) по времени выполнения заказа.
контрольная работа [145,1 K], добавлен 19.06.2013Поиск оптимальных значений некоторых параметров в процессе решения задачи оптимизации. Сравнение двух альтернативных решений с помощью целевой функции. Теорема Вейерштрасса. Численные методы поиска экстремальных значений функций. Погрешность решения.
презентация [80,6 K], добавлен 18.04.2013Понятие генетического алгоритма и механизм минимизации функции многих переменных. Построение графика функции и ее оптимизация. Исследование зависимости решения от вида функции отбора родителей для кроссинговера и мутации потомков, анализ результатов.
контрольная работа [404,7 K], добавлен 04.05.2015
