Кафедра прикладной математики Курсовая работа по курсу Дискретная математика по теме Сетевые методы в планировании Группа ДИ 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. 1. Какое максимальное количество времени можно выделить для ее выполнения... По существу, это означает, что программу удается выполнить более или м...
Практическая реализация курсового проекта. Рис 4.1 Теперь перейдем ко второму этапу - обратному и прямому прохода... При прямом проходе вычисляем наиболее ранние возможные сроки наступлен... Начиная с завершающего события движемся в обратном направлении через к... Для i n-1,n-2 0 вычислить Limin Lj-dij, jijэA где минимум берется по в...
Заключение Максимальная потребность в ресурсах как на раннем, так и на позднем календарных планах равна 15, но на позднем календарном плане время использования максимума ресурсов составляет 1, а на раннем плане 8. Также из графиков видно, что наиболее равномерно ресурсы распределены на позднем плане. Поэтому наиболее оптимальной реализацией проекта будет поздний календарный план, тоесть когда мы возьмем наиболее поздние возможные сроки операций.
Список использованной литературы Таха Х. Введение в исследование операций т.1,2 М. Мир 1989 Ковалева Л.Ф. Математическая логика и теория графов МЭСИ 1977.