Контрольная работа по дисциплине Методы оптимальных решений Методические указания




Скачать 335.04 Kb.
НазваниеКонтрольная работа по дисциплине Методы оптимальных решений Методические указания
страница1/3
Дата публикации03.03.2013
Размер335.04 Kb.
ТипКонтрольная работа
skachate.ru > Информатика > Контрольная работа
  1   2   3
Факультет заочного и дистанционного обучения
Контрольная работа по дисциплине

Методы оптимальных решений

Методические указания
Методические указания содержат краткую теоретическую справку по теме “Нахождение критического пути; резервы времени событий и операций”, набор задач для практических занятий по соответствующему разделу. В работе приведены примеры решения задач.


Составитель канд. физ.-мат. наук, доцент В.Е.Рольщиков
Рецензент канд. физ.-мат. наук, доцент Т.Б.Бигильдеева


Челябинск 2012

^ ВВЕДЕНИЕ В СЕТЕВЫЕ МЕТОДЫ
1. Основные определения из теории графов

Алгоритмы сетевых методов основываются на теории графов. Приведем определения из этой теории, которые нам понадобятся в дальнейшем.

Определение 1. Ориентированным конечным графом называется пара множеств , где - множество вершин, а - множество дуг, каждая из которых соединяет некоторую пару вершин графа. На рисунке (см. рис.1) вершины обычно обозначаются кружочками или квадратами, а дуги - стрелками. Дуга обозначается также парой вершин, которые она соединяет, например . Здесь - начало дуги, а - конец дуги. Таким образом, дуга имеет направление от начала к концу, на рисунке направление дуги отмечается стрелкой.



2 4

2 4

1

1





3 5 3 5

рис.1. рис.2.

2 3
1 4 5 1 2
3
рис.3. рис.4.
Так в графе, изображенном на рис.1 имеется пять вершин и шесть дуг .

Ориентация дуги необходима, например, для изображения работы, так как она имеет начало и конец. Если ориентации нет или ее можно не учитывать, то говорят, что пара вершин соединена ребром (на рисунке изображается без стрелки). Так, если вершины графа есть станции АТС в городе, то телефонный кабель между двумя станциями можно представить ребром.

Определение 2. Граф называется неориентированным, если его вершины соединяются только ребрами.

Определение 3. Граф называется смешанным, если его вершины соединяются и ребрами и дугами.

На рис.2 и рис.3 приведены примеры неориентированного и смешанного графов соответственно.

Далее, если не оговорено особо, - ориентированный конечный граф.

Определение 4. Путь - это конечная последовательность дуг, в которой начало каждой следующей дуги совпадает с концом предыдущей.

Так в графе на рис.1 последовательность (1;2),(2;3),(3;5) есть путь. Последовательности (1;2),(3;5) и (1;2),(2;5) не являются путями. В первом случае конец первой дуги не является началом следующей, во втором случае в графе нет дуги (2;5), а есть дуга (5;2).

Определение 5. Замкнутый путь называется контуром.

В графе на рис.1 путь (2;3),(3;5),(5;2) - контур. В случае контура путь завершается в вершине, из которой начался.

В неориентированном графе путь называется цепью, а контур - циклом.

Обозначим - граф, который получается из заменой дуг на ребра. На рис.2 изображен граф для графа на рис.1.

Определение 6. Граф называется связным, если между всякой парой вершин в графе существует по крайней мере одна цепь.

Определение 7. Граф называется сильно связным, если между всякой парой его вершин существует по крайней мере один путь.

Граф на рис.1 является связным но не сильно связным, а граф на рис.4 - сильно связным.

Определение 8. Говорят, что граф антисимметричен, если из того, что следует, что обратной дуги нет, то есть .

Утверждение 1. Всякий граф без контура антисимметричен.

Обратное утверждение не верно. Так граф на рис.4 антисимметричен, но в нем есть контур. Отметим, что ребро заменяется двумя противоположными дугами, соединяющими те же вершины, что и ребро. Поэтому при наличии ребра всегда есть контур.

Определение 9. Если дугам ориентированного графа не приписаны веса, то длина пути есть количество дуг в этом пути.

Так путь (1;2),(2;3),(3;5) в графе на рис.1 имеет длину равную трем. В случае, когда дугам приписаны веса используются и другие определения длины пути.

Граф определяет бинарное отношение на множестве вершин графа (отношение между парами вершин из ) следующим образом. Вершина находится в отношении с вершиной , если . Это бинарное отношение можно записать в виде матрицы смежности , где , если , и , если . Матрицы смежности графов на рис.1 и рис.3 (с заменой каждого ребра на две противоположные дуги) имеют соответственно вид :

; .

На вершинах ориентированного связного графа без контуров определено еще одно бинарное отношение.

Определение 10. Говорят, что вершина предшествует вершине (краткая запись ), если существует путь ненулевой длины от к .

Так как в графе нет контуров, то при выполнении отношения не может выполняться (иначе из двух путей : от к и от к можно составить контур, содержащий вершины и ). Если в графе на рис.1 удалить дугу (5;2), то он станет связным без контуров. В этом случае можем записать 1 2, 1 3, 1 4, 1 5, 2 3, и т.д. (напомним, что здесь 1,2,3,4,5 - номера вершин и запись 1 3 означает, что существует путь ненулевой длины из вершины 1 в вершину 3) . Отношение обладает следующими свойствами :

1) асимметричность: из следует, что не выполняется ;

2) транзитивность: из и следует, что ;

3) иррефлексивность: любая вершина не находится в отношении с вершиной (т.е. сама с собой).

Определение 11. Иррефлексивное, транзитивное, а потому и асимметричное бинарное отношение называется строгим частичным порядком.

Порядок является частичным, так как не все пары вершин из графа находятся в этом отношении. Так в графе на рис.5 вершины с номерами 3 и 5 не находятся в отношении , т.е. не выполняется 3 5 и не выполняется 5 3, так как нет соответствующих путей.

Таким образом во всяком ориентированном связном графе без контуров можно установить отношение строгого частичного порядка. При этом, если , то вершина называется предком вершины , а вершина потомком вершины .

^ 2. Сетевые методы планирования

Для того, чтобы составить план работ по осуществлению больших и сложных проектов, состоящих из тысяч отдельных работ, необходимо описать этот проект с помощью некоторой математической модели. Одним из таких средств описания проекта является сетевая модель.

Сетевая модель представляет собой план выполнения некоторого комплекса взаимосвязанных работ, заданного в специфической форме сети, графическое изображение которой называется сетевым графиком (графом). Главными элементами сетевой модели являются события и работы.

Термин работа используется в широком смысле :

1) действительная работа (возведение стен, окраска труб и т.д.);

2) ожидание (процесс сушки, отвердения бетона и т.д.);

3) зависимость или фиктивная работа - логическая связь между двумя или несколькими работами.

Работы видов 1) и 2) имеют известную положительную длительность. Работы вида 3) имеют нулевую длительность.

Событие - момент завершения какого-либо процесса, отдельного этапа выполнения проекта.

Событие может являться частным результатом отдельной работы или суммарным результатом нескольких работ. Среди событий сетевой модели выделяют исходное (начальное событие, которому не предшествуют другие события и работы) и завершающее (событие, которое не предшествует ни одному событию и не является началом ни одной работы).

События на сетевом графике (графе) изображаются кружочками (вершинами графа), а работы дугами. Сетевая модель должна удовлетворять следующим правилам:

1. В сетевой модели должно быть ровно одно исходное и ровно одно завершающее событие.

2. В сети не должно быть контуров.

3. Любые два события должны быть непосредственно связаны не более, чем одной работой.

Составлением перечня работ по выполнению проекта, заданием их длительности, определением какие работы каким предшествуют занимаются специалисты по конкретным работам. Мы здесь будем рассматривать только составление сетевого графика и его исследование. Для исследования сетевого графика будем применять метод критического пути.

Перейдем к составлению сетевого графика. Нам понадобится упорядочить вершины графа. Для упорядочения вершин применяется метод разбивки графа на слои.

Разбить все вершины ориентированного связного графа без контуров на слои означает, что множество вершин графа нужно разбить на подмножества S(1), S(2),...,S(k), называемые слоями, удовлетворяющие следующим условиям :

1) все элементы данного слоя S(i) не имеют предков в следующих слоях S(i+1), S(i+2),..., S(k), элементы первого слоя не имеют предков, а элементы последнего потомков;

2) порядок вершин из одного слоя безразличен, т.е. не существует пути, соединяющего вершины одного слоя.

Разбиение на такие слои всегда существует.
  1   2   3

Похожие:

Контрольная работа по дисциплине Методы оптимальных решений Методические указания iconМетодические указания и задания по курсу «методы оптимальных решений»
Методические указания и контрольные задания по курсу “Методы оптимальных решений” для студентов заочного факультетов. – Спб: Изд-во...
Контрольная работа по дисциплине Методы оптимальных решений Методические указания iconМетодические указания по дисциплине «Методы оптимальных решений»
В работу должны входить все задачи, указанные в задании строго по варианту. Контрольная работа, содержащая не все задачи, а также...
Контрольная работа по дисциплине Методы оптимальных решений Методические указания iconКонтрольная работа по дисциплине:«Методы решений оптимизационных задач в экономике (мор-2)»
Методические указания по выполнению контрольной работы по дисциплине «методы решений оптимизационных задач в бизнесе»
Контрольная работа по дисциплине Методы оптимальных решений Методические указания iconКонтрольная работа по дисциплине «Методы оптимальных решений»
Номер варианта выбирается согласно порядковому номеру фамилии студента в списке группы!
Контрольная работа по дисциплине Методы оптимальных решений Методические указания icon«Методы оптимальных решений»
Контрольная работа выполняется по варианту, номер которого совпадает с последней цифрой номера в зачетной книжке
Контрольная работа по дисциплине Методы оптимальных решений Методические указания iconМетоды оптимальных решений
Теория: Принцип оптимальности, общая задача оптимального программирования. Получение оптимальных решений средствами ms excel
Контрольная работа по дисциплине Методы оптимальных решений Методические указания iconМетоды оптимальных решений, Часть 1 Учебно-методический комплекс...
Государственное образовательное учреждение высшего профессионального образования
Контрольная работа по дисциплине Методы оптимальных решений Методические указания iconМетодические указания и контрольные задания по дисциплине «Методы...
«Методы принятия управленческих решений» разработаны и подготовлены к в н., доцентом Фоломеевым Ю. Н. в соответствии с требованиями...
Контрольная работа по дисциплине Методы оптимальных решений Методические указания iconКонтрольная работа по методам оптимальных решений для студентов фнпо...
Вариант выбирается по последней цифре номера зачетной книжки. Контрольная работа оформляется в тетради или на листах формата А4 с...
Контрольная работа по дисциплине Методы оптимальных решений Методические указания iconМетодические указания по выполнению домашней работы по дисциплине...
Для студентов, изучающих дисциплину «Теория и методы принятия решений» предусмотрено написание домашней работы по проблемам, рассматриваемым...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница