Реферат: Сетевые методы в планировании
Курсовая работа
по курсу:
“Дискретная математика”
по теме:
“Сетевые методы в планировании”
Группа: ДИ 102
Студент: Шеломанов Р.Б.
Руководитель: Алферова З.В.
Москва 1998
Содеражание
Введение--------------------------------------------------------------------------- 3
Часть 1 Теоретическая часть к курсовому проекту------------------ 4
Глава 1 Теория графов--------------------------------------------------------------- 4
Глава 2 Календарное планирование сетевыми методами---------------- 8
Часть 2 Практическая реализация курсового проекта------------- 13
Задание----------------------------------------------------------------------------------- 13
Решение---------------------------------------------------------------------------------- 14
Заключение----------------------------------------------------------------------- 20
Список литературы ----------------------------------------------------------- 21
Введение
Для иллюстраций условий и решений многих задач люди пользуются графиками. По своей сути графики являются набором из множества точек и отрезков прямых соединяющих эти точки. Возникает вопрос: подчиняются ли графики каким-либо законам и обладают ли они какими-нибудь свойствами? Этот вопрос был поставлен Д. Кенигом, который впервые объединил все схематические изображения, состоящие из совокупности точек и линий, общим термином “граф” и рассмотрел граф как самостоятельный математический объект. Теория графов нашла свое применение в решении целого ряда экономических задач. Эту область приложения теории графов можно назвать: “Календарное планирование программ сетевыми методами”. Изучение именно этой области является основной целью моего курсового проекта.
Программа определяет совокупность взаимосвязанных операций которые необходимо выполнить в определенном порядке, чтобы достигнуть поставленной в программе цели. Операции логически упорядочены в том смысле, что одни операции нельзя начать, прежде чем не будут завершены другие. Операция программы обычно рассматривается как работа, для выполнения которой требуются траты времени и ресурсов. Как правило, совокупность операций программы не повторяется. До появления сетевых методов календарное планирование программ (т. е. планирование во времени) осуществлялось в небольшом объеме. Наиболее известным средством такого планирования был ленточный (линейный) график Ганта, задававший сроки начала и окончания каждой операции на горизонтальной шкале времени. Его недостаток заключается в том, что он не позволял восстановить зависимости между различными операциями (определяющие в значительной мере темпы реализации программы). В связи с повышением сложности современных программ потребовалась разработка более четких и эффективных методов планирования, обеспечивающих оптимизацию всего процесса осуществления программы. При этом эффективность интерпретируется как минимизация продолжительности выполнения программы c учетом экономических факторов использования имеющихся ресурсов.
Организационное управление программами стало новой областью теоретических и прикладных исследований благодаря разработке двух аналитических методов структурного и календарного планирования, а также оперативного управления программами. Эти методы, разработанные почти одновременно в 1957-1958 гг. двумя различными группами, получили названия метод критического пути (МКП) и метод оценки и пересмотра программ (ПЕРТ).
Метод критического пути был предложен фирмой Е. I. du Роnt de Nemours & Company для управления программами строительства, а затем был развит к обобщен фирмой Маuсhlу Associates. Метод ПЕРТ разработан консультативной фирмой по заказу военно-морского министерства США для календарного планирования научно-исследовательских и опытно-конструкторских работ программы создания ракет «Поларис».
В методах ПЕРТ и МКП основное внимание уделяется временному аспекту планов в том смысле, что оба метода в конечном счете определяют календарный план программы. Хотя эти методы были разработаны независимо, они отличаются поразительным сходством. Пожалуй, самым существенным различием первоначально было то, что в методе МКП оценки продолжительности операций предполагались детерминированными величинами, а в метод ПЕРТ — случайными. В настоящее время оба метода составляю единый метод сетевого планирования и управления (СПУ) программами.
Часть 1
Теоретическая часть к курсовому проекту
Глава1
Теория графов
Понятие графа
Графом G(X,U) называется совокупность двух объектов некоторого множества X и отображения этого множества в себя Г .
При геометрическом представлении графа элементы множества Х изображаются точками плоскости и называются вершинами графа. Линии, соединяющие любые пары точек x и y , из которых у является отображением х , называются дугами графа. Дуги графа имеют направление, обозначаемое стрелкой, которая направлена острием от элемента х к его отображению у .
Вершины и линии графа
Две вершины А и В являются граничными вершинами дуги, если А - начало дуги, а В ее конец.
Смежными называются различные дуги, имеющие общую граничную точку. Две вершины х и у смежны, если они различны и существует дуга, идущая от одной из них к другой .
Вершина называется изолированной, если она не соединена дугами с другими вершинами графа.
Если дуга U исходит из вершины х или заходит в х , то дуга U называется инцидентной вершине х , а вершины х инцидентной дуге U . Общее число дуг, инцидентной вершине х , являются степенью вершины х Р(х) . Вершины, степень которых Р(х)>2 , называются узлом, а со степенью Р(х)<2 - антиузлом.
Полустепень захода Р+ (х) вершины х - количество дуг, заходящих в данную вершину. Полустепень исхода Р- (х) - количество дуг, исходящих из данной вершины.
Последовательность линий на графе
Путь - последовательность дуг (U1 , U2 , ...Un ), в которой конец каждой предыдущей дуги совпадает с началом последующей. Путь может быть конечным и бесконечным.
Путь называется простым, если в нем никакая дуга не встречается дважды, и составным, если любая из дуг встречается более одного раза.
--> ЧИТАТЬ ПОЛНОСТЬЮ <--