1.3 Существующие методы проектирования сетей DWDM
Несмотря на постоянное снижение стоимости волоконно-оптических компонентов, строительство новой или модернизация уже существующей ВОЛС остаются весьма дорогостоящими мероприятиями. Поэтому ошибки, допущенные на этапе проектирования линии, могут в дальнейшем резко увеличить стоимость работ в целом и затянуть сроки ввода линии в эксплуатацию. Таким образом, правильный расчет параметров всех компонентов ВОЛС является одной из важнейших задач при проектировании ВОЛС.
Проектирование и оптимизация сети DWDM – это интерактивный процесс, требующий учета всех ограничений системы:
− Расстояние и вносимые потери на отрезках сети;
− Типы и число услуг, которые должны быть предоставлены в каждой точке, подключенной к сети.
На основании этих требований при проектировании сети DWDM необходимо оптимально расположить оборудование в различных узлах сети таким образом, чтобы снизить общую стоимость проекта. При использовании оптических мультиплексоров ввода/вывода (OADM) в различных точках сети, число и тип устройств, установленных в каждом узле, необходимо оптимизировать при проектировании таким образом, чтобы снизить общую стоимость сети.
Решение всех немалых, а так же сложных задач, начиная от выбора оптимального способа прокладки ВОЛС, до определения конфигурации активного оборудования (коммутационно-распределительных устройств) целиком и полностью ложиться на плечи специалистов телекоммуникационных компаний. Подбор способа прокладки оптических сетей зависит от особенностей местности, в которой осуществляется строительство. Кабель может прокладываться в грунте, по стенам зданий и внутри помещений, в каналах кабельной канализации, а также посредством подвески к столбам воздушных линий электропередачи. Кроме того, огромное значение имеют условия прокладки оптической сети – в зависимости от этого выбирается вид кабеля. Поэтому требования к квалификации специалистов выполняющих расчеты ВОЛС с учётом всех вышеперечисленных моментов и соблюдение правил оптической сварки максимально высоки. Учесть все, сидя с калькулятором и множеством справочников, становится все сложнее и сложнее в связи с постоянным развитием элементной базы и повышением требований к объему и точности полученных результатов. Поэтому вопрос о создании программы, способной учитывать все требования построения новых сетей и модернизации старых, стоит весьма остро. На данный момент существует не так много программ, которые могут облегчить процесс проектирования ВОЛС, но все они либо ограничены графикой, либо ограничены возможностями расчета, либо выполняют функцию дополнительного программного обеспечения к общеизвестным программам оформления документации (AutoCAD, Visio).
Примером такой программы является программа EnergyCS Line. Программный комплекс EnergyCS Line, в пользу которого и был сделан выбор, предназначен для проектирования механической части воздушных линий электропередач, а также для проектирования волоконно-оптических линий связи с подвеской на воздушных линиях электропередач (ВЛ).
Проектирование ВЛ предполагает выполнение следующих операций:
− расчет стрел провисания проводов и тросов в различных режимах;
− расстановку опор по трассе;
− проверку габаритов над или под пересечениями;
− получение монтажных таблиц для стрел провисания и тяжений;
− расчет механических нагрузок на опоры и их фундаменты;
− получение спецификаций материалов и оборудования для сооружения линий электропередач и др.
Проектирование ВОЛС с помощью инструментов программы представляет собой дополнительную задачу, тесно связанную с расчетом проводов и тросов. Ее решение может организовываться в двух режимах: проектирование ВОЛС как продолжение проектирования ВЛ и проектирование ВОЛС с подвеской на существующей линии электропередач.
Проектирование ВОЛС включает:
− ввод данных о существующей линии, таких как положение опор на трассе, параметры проводов, описание пересечений (необходимо только для проектирования ВОЛС с подвеской на опорах существующей линии);
− определение условий подвески волоконно-оптического кабеля (ВОК), его способа крепления к опорам, размещение относительно траверс и стойки;
− размещение соединительных и, возможно, ответвительных муфт;
− определение строительных длин ВОК;
− проверку габаритов пересечений, если это критично для данного способа подвески ВОК;
− проверку дополнительной нагрузки на опоры, связанной с подвеской ВОК;
− формирование таблиц монтажных натяжений и монтажных стрел провисания;
− формирование спецификации кабелей, арматуры и материалов.
Недостатком данного программного средства является его узкая направленность (возможно проектирование только воздушных линий связи), комплекс позволяет спроектировать только механическую часть сети ВОЛС.
Другим примером программного средства автоматизации проектирования ВОЛС является PLS-CADD. PLS-CADD интегрирует в себе следующие ступени проектирования: моделирование местности, инженерные решения и расчеты, подготовка выходной документации. PLS-CADD это трехмерная среда для структурного моделирования воздушных линий электропередачи, позволяющая использовать в качестве геоподосновы любые геоференцированные данные инженерных изысканий, в том числе данные воздушно-лазерного сканирования, фотограмметрии, карт материалы, профили с геологией. Совместимость с современными геоинформационными приложениями является визиткой карточкой PLS-CADD и представляет собой мощный инструмент для визуализации и интерактивного редактирования модели воздушной линии связи. Участок или вся трасса линии, расстановка опор и их геометрия могут быть изменены путем набора простых операций на любой стадии работы с моделью. PLS-CADD позволяет моделировать пересечения с другими воздушными линиями электросвязии, отпайки, разветвления любой конфигурации.
Важным преимуществом PLS-CADD является совместимость со всевозможными графическими редакторами. Программа позволяет пользователю смоделировать любой сочетание гололедно-ветровых климатических условий (включая неравномерное распределение гололеда в пролете) с учетом различных национальных стандартов. Помимо этого, положение провода включая его ветровое отклонение может быть отражено графически для любого из расчетных климатических условий. Легкость и быстрота использования инструментов моделирования подвески проводов в PLS-CADD позволяет инженеру за считанные минуты проанализировать целый набор всевозможных внешних воздействий на участок линии, в то время как ручной расчет этих режимов мог бы занять несколько часов, а возможно и дней.
Недостатком PLS-CADD является то, что программа не производит механические расчеты модели проектируемой волоконно-оптической сети, так же здесь нельзя говорить и об оптимизации эксплуатационных расходов (подбор оборудования сети с заданными техническими характеристиками). PLS-CADD является скорее отличным средством визуализации полученной модели сети, чем инструментом для расчетов проектирования ВОЛС.
Еще одним примером программного средства автоматизации проектирования ВОЛС является nanoCAD ЛЭП – это одна программа, одна среда проектирования, не разделенная модулями или промежуточными файлами. Это единое решение, работающее с единой целостной моделью проекта непосредственно в графической среде nanoCAD. Комплекс позволяет решать следующие основные задачи:
− работа с базой данных оборудования, изделий и материалов;
− расстановка опор:
а) ручная расстановка опор на профиле и на плане;
б) атоматическая расстановка опор на профиле и на плане;
− расчеты ВЛ на основе требований ПУЭ-7, ПУЭ-6:
а) механические расчеты провода, троса, ВОК;
б) нагрузки на опоры и фундаменты;
в) расчет мест установки гасителей вибрации;
г) расчет числа изоляторов;
д) расчет вырубки просеки;
− расчет и оформление переходов ВЛ;
− формирование выходной документации:
а) автоматическая оформление расстановки опор на продольном разрезе профиля;
б) автоматическая оформление планов;
в) автоматическое оформление переходов;
г) автоматическая генерация табличных документов.
Данный программный продукт имеет определенный ряд недостатков:
− возможно проектирование только наземных объектов связи (не производится проектирование по канализационным объектам строительства электросвязи);
− отсутствует функция обеспечивающая оптимизацию расхода кабеля в сети;
− программа не имеет привязки к карте местности, на которой производится проектирование сети ВОЛС, расчеты производятся лишь на плане участка, для которого осуществляется проектирование сети.
Что касается разработанных программных комплексов для решения задач сетевого анализа с применением ГИС технологий, следует отметить программу Network Analyst (ESRI), которая предлагает дополнительные функции к ArcView GIS для анализа линейных сетевых тем, таких как дороги, линии коммуникаций, городские улицы, реки и др. С помощью Network Analyst решается задача поиска ближайшего пункта обслуживания а также выполняется определение зон обслуживания(доступности). Одной из стандартных функций модуля является выдача маршрутного листа передвижения. Network Analyst удобен и прост в эксплуатации, но решает только несколько задач сетевого анализа и работает только со специально подготовленными данными.
Более широкий набор функций по работе с сетями предоставляет Network Engine от ESRI. Этот программный пакет предназначен для создания функций сетевого моделирования, нахождения пути (маршрута) и отслеживания сетевой топологии. С его помощью можно моделировать любые сети, в том числе абстрактные. Но он оптимизирован для целей задания, сохранения, прокладки и анализа сетей, представляющих собой объекты реального мира, такие как улицы и магистрали, железные дороги, электрические, газовые или телекоммуникационные сети, водопроводы и системы канализационного стока, или обычные водотоки. Подобные географические (то есть имеющие пространственное протяжение и/или привязку) сети обычно рассматриваются как логический граф, основанный на реальных сетевых объектах.
Что касается программных продуктов для решения транспортных задач в среде MapInfo, то следует обратить внимание на ChronoVia – модуль для поиска оптимальных путей в сети, и ChronoMap – модуль для построение зон транспортной доступности. Программы работают практически с любыми данными дорожной сети в векторном формате MapInfo Professional. Кроме того, есть возможность определить правила для сети, что позволяет приблизить математическую модель к реальным дорожным условиям. Чем больше правил позволяет определять программное обеспечение, тем корректней получаемый результат.
ChronoVia предназначен для вычисления маршрутов от начального пункта через промежуточные пункты до пункта прибытия. Оптимизирующие функции позволяют определить наилучший маршрут с точки зрения времени, расстояния или транспортных расходов, а также оптимизировать последовательность остановок (задача коммивояжера). Остановки могут быть указаны непосредственно на карте или взяты из таблицы MapInfo, например, как результат геокодирования адресного списка клиентов, которым необходимо осуществить доставку товара.
Построение зон транспортной доступности в ChronoMap обладает большим числом настроек. Зоны могут строиться по одной или многим точкам с минимизацией расстояния, времени или транспортных издержек, с учётом категории транспортных средств и всех характеристик сети. Полезной особенностью является построение зон доступности, как от точки, так и к точке. Имеется широкий выбор настроек для оформления карты.
Большинство программ данного класса оперирует скоростными характеристиками сегментов уличной сети, и как правило это максимальная скорость движения для данного класса дороги. При этом не учитывается, какое транспортное средство передвигается по этой дороге. В данных программных продуктах вводится понятие транспортного средства, имеется библиотека различных транспортных средств. Пользователь может выбрать из библиотеки, которая в случае необходимости может быть расширена, транспортное средство (автомобиль, велосипед, грузовик, трактор и т.д.) для движения по маршруту.
Ниже приведена сравнительная таблица 1.2 программных средств проектирования сетей связи.
Таблица 1.2 – Сравнительная таблица программных средств проектирования сетей связи
|
Название |
Функции |
Недостатки |
|
EnergyCS Line |
расчет стрел провисания проводов и тросов в различных режимах; расстановку опор по трассе; проверку габаритов над или под пересечениями; получение монтажных таблиц для стрел провисания и тяжений; расчет механических нагрузок на опоры и их фундаменты; получение спецификаций материалов и оборудования для сооружения линий электропередач и др. |
узкая направленность (возможно проектирование только воздушных линий связи), комплекс позволяет спроектировать только механическую часть сети ВОЛС |
|
PLS-CADD |
моделирование местности, инженерные решения и расчеты, подготовка выходной документации |
не производятся механические расчеты модели проектируемой ВОЛС, так же нет функции оптимизации эксплуатационных расходов |
|
nanoCAD |
работа с базой данных оборудования, изделий и материалов; ручная расстановка опор; расчеты ВЛ на основе требований ПУЭ-7, ПУЭ-6; расчет и оформление переходов ВЛ; формирование выходной документации |
возможно проектирование только наземных объектов связи; отсутствует функция обеспечивающая оптимизацию расхода кабеля в сети; программа не имеет привязки к карте местности, на которой производится проектирование сети ВОЛС, (расчеты производятся лишь на плане участка) |
|
Network Analyst |
анализ линейных сетевых тем, таких как дороги, линии коммуникаций, городские улицы, реки и др; решение задачи поиска ближайшего пункта обслуживания; выдача маршрутного листа передвижения |
решает только несколько задач сетевого анализа и работает только со специально подготовленными данными |
Ознакомившись с данными программными продуктами для решения транспортных задач, можно отметить общую закономерность: никто из производителей не раскрывает вопрос, какие алгоритмы решения задач реализованы в программах.
Основываясь на анализе существующих системах автоматизированного проектирования сетей DWDM можно сделать следующие выводы: необходимо создание программного средства с полноценным математическим аппаратом, обеспечивающим максимальную близость рассчитываемых и реальных значений в проектируемой сети, позволяющем максимально оптимизировать эксплуатационные расходы и значительно снизить капиталовложения на проектирование современных городских сетей, а так же обладающем удобным графическим инструментом.
Задача автоматизации процесса проектирования сетей FTTH усложняется еще и тем, что FTTH-сети требуют совершенно иных подходов к проектированию ВОЛС в районах городской застройки, нежели классические сети, строящиеся по технологии FTTB для нужд Ethernet или кабельного телевидения. Здесь не подходит ни одна стандартная топология, такая как «кольцо» или «звезда». Это связано с тем, что классические сети проектируются «от центрального к домовым узлам» независимо от количества домовых узлов в районе или кластере. В FTTH-сетях необходимо учитывать максимальное количество подключаемых абонентских устройств к каждому порту линейного терминала, таким образом FTTH-сети проектируются «от квартир к центральному узлу». Таким образом, не смотря на то, что технология FTTH подразумевает топологию сети «звезда», в действительности FTTH-сети требуют особенной, новой топологии построения.
1.4 Структурные модели DWDM сетей на основе теории графов
Теория графов служит математической моделью для всякой системы, содержащей бинарное отношение. В теоретико-графовых терминах формулируется большое число задач, связанных с дискретными объектами. Они являются универсальной структурной моделью различных физических систем, при изучении которых на первый план выступает характер соединений различных ее компонентов, т.е. связи и отношения между объектами (электрическими, механическими, пневматическими, химическими, биологическими, биофизическими, социологическими и др.). Они используются в задачах проектирования и конструирования, анализе надежности сетей связи, электронных схем, коммуникационных сетей, при решении транспортных задач о перевозках, планировании и управлении, при составлении оптимальных маршрутов доставки грузов, при моделировании сложных технологических процессов, генетике, психологии, социологии, экономике и т.д. Преимущество графов следует из того, что они однозначно описывают структуру системы, на их основе просто записываются канонические уравнения, фиксируются физические свойства и причинная зависимость между переменными. Их особенностью является геометрический подход к изучению объектов, т.е. представление в виде диаграмм.
В инженерной практике рассматриваются технические системы, которые представляют собой комплекс взаимосвязанных технических средств, обеспечивающих преобразование массы, энергии и информации. Существенным элементом при этом является установление отношений между входами и выходами технических средств. Комплекс этих отношений и образует систему.
Выделяют два типа отношений: отношения преобразования и отношения связей. Отношения преобразования включают отношения переработки (информации, массы, с изменением свойств материала (внутренней и внешней структуры), преобразование энергии) и отношения перемещения (изменение положения предмета по отношению к другим предметам). Отношение связи – это то, что объединяет функциональные элементы технической системы в одно целое.
Они бывают только жесткими, т.е. не изменяющимися, в процессе функционирования системы. Через связи проходит интенсивный обмен веществом, энергией и информацией с окружающей средой и между элементами технической системы. Отношения связи отражают все взаимоотношения в технической системе и не обладают собственной материальной основой.
Прикладные задачи порождают графы, в которых между вершинами существует определенная зависимость, а ориентация дуг имеет первостепенное значение. Например, задача построения наилучшей схемы административного подчинения по критерию минимального количества непосредственных связей (минимуму непосредственных подчиненных и непосредственных начальников), задача построения определенной схемы связи в электрических сетях по критерию минимального количества контактов, задача выбора при обработке деталей наилучшего порядка, который должен удовлетворять определенной технологии и др.
При решении подобных задач приходится, имея допустимую схему связей объектов, выделить из нее какую-нибудь часть связей, удовлетворяющую определенным критерием. В качестве элементов (вершин) могут выступать некоторые узловые коммуникации (населенные пункты, магазины, склады, пункты электроснабжения и т.д.). Каждая связь (дуга) между вершинами характеризуется определенной величиной (временем, некоторыми затратами на строительство коммуникаций, длиной пройденного пути и т.д.). Требуется, не теряя связности графа, найти один из вариантов сети, для которой достигается минимум суммарных весов дуг. Аналогичные задачи могут встречаться при проектировании строительства сетей транспортных, газовых, воздушных, сети коммуникаций для передачи информации, при составлении графика выполнения работ и т.д.
В математических терминах сеть представляется как граф. Граф − пара множеств G=P,E, где P- множество N узлов (вершин или точек) P1,P2,…,PN, а E - множество ребер (соединений или линий), которые соединяют два элемента из P.
Рисунок 1.3 – Иллюстрация графа с N=5 вершинами и n=4 ребрами.Графы обычно представляются как множество точек, каждая из которых соответствует вершине. Две такие точки соединены линией, если соединены соответствующие вершины, как показано на рисунке 1.3. Множество вершин: P=1,2,3,4,5. Множество ребер:E={1,2},{1,5},{2,3},{2,5}.
Теория графов возникла в восемнадцатом веке в работе Леонарда Эйлера, чья ранняя работа в основном касалась маленьких графов с высокой степенью регулярности. В двадцатом веке теория графов стала более статистической и алгоритмической. Особенно большим источником идей являлось изучение случайных графов, т. е. графов, в которых ребра распределены случайным образом. Сети со сложной топологией и неизвестными принципами организации часто оказываются случайными; таким образом, теория случайных графов широко используется в изучении сложных сетей.
Теория случайных графов изучает свойства вероятностного пространства, связанного с графами с N вершинами, при N→∞. Многие свойства таких случайных графов могут быть определены с использованием вероятностных доводов. В этом отношении Эрдеша-Реньи использовали определение, что почти каждый граф обладает свойством Q, если вероятность обладания свойством Q приближается к 1 при N→∞.
В математической литературе конструирование случайного графа часто называется эволюцией: вначале имея множество из N отдельных вершин, граф развивается с последовательным добавлением случайных ребер, как показанно на рисунке 1.4. Графы, полученные на разных этапах этого процесса, соответствуют все большим и большим вероятностям соединения p, и наконец, при p→∞, получается полный граф.
Рисунок 1.4 – Иллюстрация процесса изменения графа
Ученые начали интересоваться сетевыми структурами, когда Интернета еще не существовало, зато существовали транспортные и энергетические сети, социальные и экологические системы, сети промышленных предприятий. Для формалистов-ученых было важно, что все они устроены похожим образом и хорошо описываются теорией графов. Граф — это структура, состоящая из вершин (узлов), соединенных связями (дугами). Возьмем, к примеру, сеть аэропортов. Узлами в ней являются аэровокзалы, а дугами — рейсы. Другой пример — сеть автодорог: узлы — города, связи — дороги. Понятно, что количество узлов в этих графах будет постоянно возрастать. Поскольку новые узлы добавляются непредсказуемым образом, то для изучения случайного графа применяется теория вероятностей.Важной характеристикой, которая может быть получена для случайного графа, служит вероятность того, что узел связан с другими k узлами. Эта величина называется распределением связности. Имеющиеся сети можно разделить на два класса, один из которых характеризуется экспоненциальным распределением связности, а другой — показательным. Основываясь на форме графа, американский физик Альберт Ласло Барабаши назвал сети с показательным распределением бесступенчатыми (scale-free). Оказалось, что бесступенчатые сети обладают некоторыми полезными свойствами. В экспоненциальных сетях каждый узел связан примерно с одинаковым числом других узлов. В бесступенчатых же сетях количество связей у различных узлов неодинаково: имеются сильно связанные фрагменты сети и менее связанные. Если попытаться изобразить структуру сети, то получится приблизительно такая картинка, как на рисунке 1.5. Красным цветом обозначены узлы сети, имеющие наибольшее число связей, зеленым — те, которые связаны с красными, черным — все остальные. Если часть узлов вывести из строя, то работоспособность сети, вообще говоря, может измениться. В такой ситуации бесступенчатые сети демонстрируют более высокую устойчивость, чем экспоненциальные. Если переложить эти рассуждения на язык Интернета, то выведение из строя отдельных узлов сети не должно повлиять на работу сети в целом. А значит, в научных исследованиях Барабаши речь идет, ни много ни мало, о безопасности и надежности Сети.
Рисунок 1.5 – Графы экспоненциальной (слева) и бесступенчатой сетей
Основываясь на теории случайных графов можно не только наглядно представить структурные схемы сетей DWDM, но и проанализировать их с наиболее достоверной точностью.
Рисунок 1.6 – Пример применения графов на карте п.Ростоши
На рисунке 1.6. наглядно изображен пример организации прокладки кабеля между узлами (абонентами).
Большое практическое значение имеет группа задач, связанных с выполнением комплекса работ при наличии ограничений на порядок их выполнения, длительность каждой работы, выделяемые ресурсы и т.п. С такими задачами приходится сталкиваться при решении вопросов календарного планирования и оперативного управления, как в производстве, так и в сфере обслуживания населения.
Задачи подобного рода разнообразны, и их исследование проводится в рамках различных научных дисциплин. В теории сетевого планирования основное внимание уделяется определению порядка выполнения сложных разработок, включающих в себя большое число взаимосвязанных работ, требующих многочисленных исполнителей и значительных материальных затрат. В теории упорядочения рассматриваются вопросы установления порядка выполнения большого комплекса однородных работ с помощью одного или нескольких специализированных устройств, машин, приборов. В теории массового обслуживания разбираются задачи назначения приоритетов в обслуживании поступающих заявок некоторыми устройствами, приборами и т.п. Существует некоторое сходство формальных моделей этих видов задач. Целенаправленную деятельность можно рассматривать как некоторый протекающий во времени процесс, заключающийся в реализации (выполнении) определенной совокупности работ. Выполнение работ стеснено целым рядом ограничений и условий, которые можно разбить на две группы.
Ограничения 1. Эти ограничения описывают взаимную зависимость выполнения работ. Ограничение 2. Они связаны с ограниченным объемом ресурса, который может быть выделен на выполнение совокупности работ.
Особенности задач первого типа состоят в том, что жесткие ограничения 1 в таких задачах в значительной степени предопределяют порядок выполнения отдельных работ и число возможных вариантов расписания здесь не очень велико.
Однако варианты всегда возможны и среди них могут найтись такие, при которых окажется минимальным время выполнения подпрограммы, наиболее рациональное распределение ресурсов и т.п. Для решения задач этого типа широко применяются методы сетевого планирования и управления (СПУ). В задачах второго типа ограничения на очередность выполнения отдельных работ незначительны, что не означает, что порядок выполнения работ здесь безразличен. От порядка выполнения работ зависит распределение ресурса по шагам. На переход от одной работы к другой тратится время, может потребоваться переквалификация персонала, переналадка или замена оборудования и т.п. Поэтому и здесь стоит задача составления расписания работ в определенном смысле наилучшего. В задачах этого типа приходится рассматривать очень большое число различных комбинаций порядка выполнения работ и давать оценку каждой комбинации. Такие задачи получили название комбинаторных задач на составление расписания или задач упорядочения.
Сетевые методы широко применяют для рационального планирования крупных разработок, включающих в себя выполнение целого комплекса взаимосвязанных работ, например сооружение строительных объектов, разработка новых технических систем и изделий, проведение крупных ремонтов и реконструкций, изготовление и сборка крупных изделий (самолетов, судов, космических кораблей) и т.п. Эти методы основаны на наглядном представлении выполняемого комплекса работ в виде ориентированного графа, дуги которого изображают выполняемые работы, а вершины – события, представляющие собой завершение отдельных работ.
Последовательность дуг в таком графе определяет порядок, в котором выполняются работы. Таким образом, сетевой граф – это построенная без масштаба графическая схема последовательности выполнения взаимосвязанных работ.
Первый шаг в построении сетевого графика состоит в расчленении всего комплекса на отдельные работы или операции. Каждая работа связана с затратами времени, следовательно, имеет начало и конец, которые должны легко определяться.
Одновременно с перечнем работ определяются ограничительные условия на их выполнение: длительность каждой работы, средства на ее выполнение, интенсивность, перечень непосредственно предшествующих работ, выполнение которых является необходимым для начала данной работы.
С целью упорядочения работ удобно приписывать отдельным работам вес, отражающий степень их важности, что в значительной степени предопределяет порядок выполнения работы. Одним из способов упорядочения работ является приписывание работе веса, равного сумме числа непосредственно следующих за ней работ и вес этих работ. Конечные работы принято считать одинаково важными и приписывать им вес условно равный единице.
Сетевой граф должен удовлетворять определенным условиям:
− ни одно событие не может произойти до тех пор, пока не будут закончены все входящие в него работы;
− ни одна работа, выходящая из данного события, не может начаться раньше этого события.
Поскольку ни одна последующая работа не может начаться раньше, чем будут закончены все предшествующие ей работы, то на сетевом графе не должно быть контуров. Кроме того сетевой граф должен содержать только одно начальное и одно конечное событие, в противном случае его всегда можно преобразовать к нужному виду. Существуют определенные правила построения сетевого графика, которые дают возможность изображать каждую работу единственной стрелкой между двумя событиями и позволяют безошибочно составить и проверить сетевую модель любого комплекса работ. Отсылая за подробностями построения сетевого графика к многочисленной литературе, например, здесь лишь отметим, что с точки зрения классификации графов сетевой график представляет собой ориентированный связный, асимметрический граф без контуров с одним входом и одним выходом.
Перед теорией сетевого планирования и управления ставится задача поиска методов решения практических задач исключающих необходимость перебора всех возможных вариантов, поэтому она является объектом приложения различных областей математики: теории графов, теории вероятности, методов линейного, нелинейного и динамического программирования, математической статистики и многих других.
Процесс оптимизации сети, как правило, связан с распределением ресурсов, которые охватывают средства производства (машины, оборудование, изделия, полуфабрикаты, материалы, рабочий и инженерно-технический состав, а также денежные средства). Топология исходного сетевого графа должна отражать не только технические, но и ресурсные связи, поскольку нужно учитывать, что совокупность ряда работ не может выполняться одновременно из-за недостатка в ресурсах.
В рассмотренных выше задачах топология сети считается строго установленной; и в процессе решения задачи, и в оптимальном плане последовательности выполнения работ всего комплекса она остается без изменения.
На практике исходная сетевая модель составляется без учета, является ли она оптимальным вариантом, то есть имеет структуру (конфигурацию дуг графа), решение задачи оптимизации на которой даст самый экономичный вариант.
Поэтому прежде чем решать задачи оптимизации на сетевом графике, необходимо определить сам исходный оптимальный сетевой график, Граф, в котором учтено всё многообразие связей между работами, называют допустимым.
Математически сформулированную задачу можно трактовать как задачу выделения в допустимом графе такого частичного графа, удовлетворяющего определённым условиям, оптимизация ресурсов и времени на котором дала бы наилучший эффект при реализации проекта.