[pic]

Кафедра прикладной математики

Курсовая работа по курсу:

“Дискретная математика”

по теме:

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

Группа: ДИ 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