Сетевые методы в планировании

    Дисциплина: Разное
    Тип работы: Курсовая
    Тема: Сетевые методы в планировании

    Кафедра прикладной математики
    Курсовая работа
    по курсу:
    “Дискретная математика”
    по теме:
    “Сетевые методы в планировании”
    Группа: ДИ 102
    Студент: Шеломанов Р.Б.
    Руководитель:
    Алферова З.В.
    Москва 1998
    Содеражание
    Введение
    --------------------------------------------------------------------------- 3
    Часть 1 Теоретическая часть к курсовому проекту
    ------------------- 4
    Глава 1 Теория графов
    ----------------------------------------------------- 4
    Глава 2 Календарное планирование сетевыми методами
    -------------- 8
    Часть 2
    Практическая реализация курсового проекта
    --------------- 13
    Задание
    --------------------------------------------------------------------- 13
    Решение
    -------------------------------------------------------------------- 14
    Заключение
    ----------------------------------------------------------------------- 20
    Список литературы
    ------------------------------------------------------------ 21
    Введение
    Для иллюстраций условий и решений многих задач люди пользуются графиками. По своей сути графики являются набором из множества точек и отрезков прямых соединяющих эти точки.
    Возникает вопрос: подчиняются ли графики каким-либо законам и обладают ли они какими-нибудь свойствами?
    Этот вопрос был поставлен Д.
    Кенигом, который впервые объединил все схематические изображения, состоящие из совокупности точек и линий, общим термином “граф” и рассмотрел граф как
    самостоятельный математический объект. Теория графов нашла свое применение
    в решении целого ряда экономических задач. Эту область приложения теории графов можно назвать: “Календарное планирование программ сетевыми методами”. Изучение
    именно этой области является основной целью моего курсового проекта.
    Программа определяет совокупность взаимосвязанных операций которые необходимо выполнить в определенном порядке, чтобы достигнуть поставленной в программе цели. Операции логически
    упорядочены в том смысле, что одни операции нельзя начать, прежде чем не будут завершены другие. Операция программы обычно рассматривается как работа, для выполнения которой требуются
    траты времени и ресурсов. Как правило, совокупность операций программы не повторяется. До появления сетевых методов календарное планирование программ (т. е. планирование во времени)
    осуществлялось в небольшом объеме. Наиболее известным средством такого планирования был ленточный (линейный) график Ганта, задававший сроки начала и окончания каждой операции на
    горизонтальной шкале времени. Его недостаток заключается в том, что он не позволял восстановить зависимости между различными операциями (определяющие в значительной мере темпы
    реализации программы). В связи
    с повышением сложности современных программ потребовалась разработка более четких и эффективных методов планирования, обеспечивающих оптимизацию всего процесса
    осуществления программы. При этом эффективность интерпретируется как минимизация продолжительности выполнения программы
    учетом экономических факторов использования имеющихся ресурсов.
    Организационное управление программами стало новой областью теоретических и прикладных исследований благодаря разработке двух аналитических методов структурного и календарного
    планирования, а также оперативного управления программами. Эти методы, разработанные почти одновременно в 1957-1958 гг. двумя различными группами, получили названия метод критического
    пути (МКП) и метод оценки и пересмотра программ (ПЕРТ).
    Метод критического пути был предложен фирмой Е.
    Роnt de Nemours Company для управления программами строительства, а затем был развит к обобщен фирмой Маuс
    lу Associates
    Метод ПЕРТ разработан консультативной фирмой по заказу военно-морского министерства США для календарного планирования научно-исследовательских и опытно-конструкторских работ
    программы создания ракет «Поларис».
    В методах ПЕРТ и МКП основное внимание уделяется временному аспекту планов в том смысле, что оба метода в конечном счете определяют календарный план программы. Хотя эти методы
    были разработаны независимо, они отличаются поразительным сходством. Пожалуй, самым существенным различием первоначально было то, что в методе МКП оценки продолжительности операций
    предполагались детерминированными величинами, а в метод ПЕРТ — случайными. В настоящее время оба метода составляю единый метод сетевого планирования и управления (СПУ)
    программами.
    Часть 1
    Теоретическая часть к курсовому проекту
    Глава1
    Теория графов
    Понятие графа
    Графом G(X,U)
    называется совокупность двух объектов некоторого множества X и отображения этого множества в себя Г.
    При геометрическом представлении графа элементы множества Х изображаются точками плоскости и называются вершинами графа. Линии, соединяющие любые пары точек x и y, из которых у
    является отображением х, называются дугами графа. Дуги графа имеют направление, обозначаемое стрелкой, которая направлена острием от элемента х к его отображению у.
    Вершины и линии графа
    Две вершины А и В являются граничными вершинами дуги, если А- начало
    дуги, а В ее конец.
    Смежными называются различные дуги, имеющие общую граничную точку. Две вершины х и у смежны, если они различны и существует дуга, идущая от одной из них к другой .
    Вершина называется изолированной, если она не соединена дугами с другими вершинами графа.
    Если дуга U исходит из вершины х или заходит в х, то дуга U называется инцидентной вершине х, а вершины х инцидентной дуге U. Общее число дуг, инцидентной вершине х, являются
    2 - антиузлом.
    Полустепень захода Р
    +(х) вершины х - количество
    дуг, заходящих в данную вершину. Полустепень исхода Р
    -(х) - количество дуг, исходящих из данной вершины.
    Последовательность линий на графе
    Путь - последовательность дуг (U
    1, U
    2, ...U
    n), в которой конец каждой предыдущей дуги совпадает с началом последующей. Путь может быть конечным и бесконечным.
    Путь называется простым, если в нем никакая дуга не встречается дважды, и составным, если любая из дуг встречается более одного раза.
    Путь, в котором ни одна из вершин не встречается более одного раза, называется элементарным путем.
    Гамильтонов путь - путь проходящий через все вершины, но только по одному разу,
    Эллеров путь - путь содержащий все дуги графа, при этом только по одному разу.
    Длинна пути - число дуг последовательности (U
    1, U
    2, ...U
    Ветвь - путь, в котором начальная и конечная вершины являются узлами. Дуга (x,y) называется замыкающей,
    если удаление ее не приводит к аннулированию пути из x в y.
    Контур - конечный путь, начинающийся и заканчивающийся в одной и той же вершине. Контур единичной длинны называется петлей.
    Ориентированный граф - граф, у которого вершины соединяются направляющими стрелками.
    Графы можно рассматривать с учетом или без учета ориентации его дуг.
    Разновидности графов
    Нуль-граф - граф (X,U), состоящий только из изолированных вершин.
    Однородный граф - если степени всех вершин графа одинаковы и P
    +(x)= P
    - (x) =0.
    Симметрический граф - граф, в котором две любые смежные вершины соединены только двумя противоположно ориентированными
    дугами.
    Антисимметрический - граф, в котором каждая пара смежных вершин соединена только в одном направлении.
    Полный - граф, в котором любая пара вершин соединена одинаковым числом дуг.
    Мультиграф - граф, в котором хотя бы две смежные вершины соединены более чем одной дугой. Наибольшее число дуг, соединяющих смежные вершины графа называется кратностью.
    Подмножества графов
    Подграфом графа
    G(X,U) называется граф G(A,U
    A), определяемый следующим образом:
    1. Вершинами A
    подграфа G(A,U
    2. Отображением каждой вершины подграфа является пересечение отображения той же вершины в графе G(X,U) со всем подмножеством вершин A подграфа G(A,U
    Частичным графом для графа G(X,U) называется граф G(X,U), в котором содержатся все вершины и некоторое подмножество дуг исходного графа.
    Частичный подграф - это частичный граф от подграфа.
    Фактором графа G(X,U) называется частичный граф G(X,U), в котором
    каждая вершина обладает полустепенями исхода и захода, равными единице,
    имеются одна заходящая и одна исходящая дуги.
    Базисным графом
    называется ориентированный частичный граф, образованный из исходного удалением петель и замыкающих дуг.
    Связность графа
    В общем случае граф может быть представлен несколькими отдельными графами, не имеющими общих дуг. Тогда граф G(X,U) называется несвязным, а каждый из составляющих его графов G
    1 , G
    2 ,...G
    n - компонентами связности. Граф называется
    связным, когда каждую его вершину можно соединить с любой другой его вершиной некоторой цепью.
    Операции над графами
    1. Объединение графов
    3,Гх
    3) = G
    1,Г1х
    2,Г2х
    , где
    2, а Гx
    3=Г1x
    Г2x
    Пример (Рис 1.1).
    Пересечение графов
    3,Гх
    3) = G
    1,Г1х
    2,Г2х
    , где
    2, а Гx
    =Г1x
    Г2x
    Пример (рис 1.2).
    4. Прямое (декартово) произведение графов.
    Прямым произведением множеств Х{x
    1.......x
    n} и Y
    называется множество Z, элементами которого являются всевозможные пары вида x
    i , y
    j , где x
    X, y
    Y. Обозначают:
    Z=X x Y.
    3,Гх
    3) = G
    1,Г1х
    2,Г2х
    2), где
    3=X1
    X2, а Гx
    3=Г1х1
    Г2х2
    Пример. (рис 2.3)
    1(X,Гх)=G
    1,Гх
    2(Y,Гy)= G
    2,Гх
    X={x
    Y={y
    Гх
    Гу
    1={y
    Гх
    2={x
    Гу
    2={y
    Гх
    x Y={x
    1, x
    2, x
    1, x
    2, x
    1, x
    Z={z
    Рис 2.3
    Расширение графа.
    Расширение графа - это превращение, линии, соединяющей любые две вершины графа в элементарный путь введением новых промежуточных вершин на этой линии.
    Сжатие графа.
    Сжатие графа - это превращение элементарного пути, соединяющего две любые вершины графа, в линию.
    Стягивание графа.
    Если граф содержит вершины Х
    1 и Y
    1 , то операцией стягивания называется исключение всех дуг между вершинами Х
    1 и Y
    и превращение всех вершин в одну общую вершину Х.
    Некоторые числа теории графов
    Пусть существует мультиграф с b вершинами,
    p ребрами, и R компонентами связности, тогда цикломатическое число мультиграфа определяется равенством:
    V= p-b+R
    Матрицы для графов
    Матрицей смежности графа G(X,Гх), содержащего n вершин называется квадратная бинарная матрица А(G)
    n x n , c нулями на диагонали. Чи...

    Забрать файл

    Похожие материалы:


ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены