ПОСТРОЕНИЕ СЕТЕВОГО ГРАФИКА

ВВЕДЕНИЕ

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

Методы сетевого планирования и управления (СПУ), разработанные в начале 50-х годов, широко и успешно применяются для оптимизации планирования и управления сложными разветвленными комплексами работ, требующими участия большого числа исполнителей и затрат ограниченных ресурсов. Для оптимизации сложных сетей, состоящих из нескольких сотен работ, вместо ручного счета следует применять типовые макеты прикладных программ по СПУ, имеющиеся в составе математического обеспечения ЭВМ.

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

Основная цель сетевого планирования - сокращение до минимума продолжительности проекта.

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

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

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

В данном курсовом проекте рассматриваются цель: определить минимальную стоимость комплекса производственных работ при заданной продолжительности его выполнения и других указанных условиях.

ПОСТРОЕНИЕ СЕТЕВОГО ГРАФИКА

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

Сеть представляет собой граф – фигуру, состоящую из точек и соединяющих их линий. Точки в этой фигуре называются вершинами графа, линии, которыми они соединены – ребрами (дугами). Модель СПУ представляет собой особый вид графов:

- во-первых, это связный граф, то есть любая его вершин связана между собой дугами;

- во-вторых, это конечный граф, то есть множество его ребер конечно;

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

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

Подготовка исходных данных для построения сетевого графика включает:

1. Определение начального и конечного событий;

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

3. Составление списка работ, соединяющих намеченные события;

4. Определение продолжительности выполнения каждой работы.

При построении сетевого графика для СПУ должны учитываться следующие правила:

1. График должен иметь только одно начальное событие и только одно конечное событие;

2. Ни одно событие не может произойти до тех пор, пока не будут закончены все входящие в него работы;

3. Ни одна работа, выходящая из какого-либо события, не может начаться до тех пор, пока не произойдет данное событие;

4. График должен быть упорядоченным.

Построение сетевого графика производится по первой таблице исходных данных.

В этой таблице в шапках по горизонтали и вертикали перечисляются все события, в остальной части таблицы приводятся работы.

Начальным событием – истоком I является «начало работ», а завершающим событием – стоком S – «готовность изделия». Поэтому нужно пронумеровать их соответственно числами 1 и 6.

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

Из этого события 2 (по горизонтали) выходят две работы-дуги, которые ведут к соответствующим событиям по вертикали. Их обозначим по порядку 4 и 5. Соответствующим событиям по горизонтали присвоим те же числа.

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

 I

 4\3 10\5

 I

 12\6

 5\2

6\4 S

S 9\6

 11\6

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

Используя полученную нумерацию событий в графике, изменим вторую таблицу исходных данных в задании