Реферат: Сетевой трафик - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Сетевой трафик

Банк рефератов / Компьютерные сети

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 365 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

РефератКурсовой проект 43 с., 5 рис., 6 блок-схем, 1 таблица, 1 источник.СЕТЕВОЙ ГРАФИК, АНАЛИЗ ОПТЕМАЛЬНОСТИ СЕТЕВЫХ ГРАФИКОВ, РАЦИОНАЛЬНЫЕ МЕТОДИКИ ПОИСКА ОСОБЫХ ПУТЕЙ СЕТЕВЫХ ГРАФИКОВ, АВТОМАТИЗАЦИЯ АНАЛИЗА СЕТЕВЫХ ГРАФИКОВ НА ЭВМ.Направление работы – изучение математических и алгоритмических аспектов анализа оптимальности сетевых графиков. Основная цель работы – найти и доказать рациональные методики поиска особых путей сетевых графиков, легко поддающиеся автоматизации на ЭВМ и сокращающие затраты на сетевое планирование, за счёт уменьшения сроков разработки оптимальных сетевых графиков.Используемый в работе метод исследований – аппарат формальной логики, позволяющий осуществлять математические доказательства с минимальным привлечением, для этого, формул.В ходе работы получены блок-схемы алгоритмов расчёта параметров сетевых графиков и поиска их особых путей, которые предполагается использовать при создании конкретной программы анализа оптимальности сетевых графиков на любом из известных языках программирования.Новизна работы состоит в том, что разработанные методы позволяют найти критический и наикратчайший пути сетевого графика без перебора всех возможных вариантов, что даёт: во-первых – высокую скорость разработки оптимальных сетевых графиков, а во-вторых – возможность точного ответа на вопрос об оптимальности уже готового сетевого графика и высокую степень оптимизации сетевых графиков по длительности в случае их неоптимальности.СодержаниеВведение41 Постановка задачи62 Теоретические основы сетевого планирования93 Обоснование рациональных методик поиска особых путей сетевых графиков154 Автоматизация анализа оптимальности сетевых графиков на ЭВМ224.1 Представление сетевого графика в машинной форме224.2 Автоматизация расчёта параметров сетевого графика 274.3 Автоматизация процесса поиска особых путей сетевого графика40Заключение42Список использованных источников43ВведениеОдним из основных экономических показателей, определяющих себестоимость проведения проектных, научно-исследовательских, опытно-конструкторских и других, поддающихся экономическому анализу, работ, связанных с разработкой и внедрением на предприятие новой техники или с организацией и управлением деятельности всего предприятия, является общая продолжительность их выполнения. Естественно, что в рамках некоторого рассматриваемого проекта, эта продолжительность существенно зависит от структуры упорядочивания отдельных, входящих в него работ. Поэтому, построение оптимальной структуры упорядочивания проектных работ является основной задачей сетевого планирования.В основе решения указанной задачи лежит анализ смыслового содержания работ и установление взаимосвязей между ними, что позволяет выявить возможность их параллельного выполнения. Последнее, является основным фактором сокращения длительности всего проекта.Распространены два метода оптимального планирования или упорядочивания проектных работ. Один из методов, основан на построении ленточного графика, где каждой работе присваиваются такие характеристики как время начала её выполнения, её длительность, которые затем, в виде параллельных отрезков, наносятся на шкалу времени. Другой из методов, основан на построении сетевого графика, где структура упорядочивания работ изображается графически в виде сигнального графа. Выбор того или иного метода планирования зависит от числа работ, входящих в состав проекта. Принято, что если число работ превышает 25, то наиболее наглядный и удобный метод оптимального планирования – есть метод, основанный на построении сетевого графика. На практике этот метод более употребителен, в силу того, что число работ, входящих в некоторый рассматриваемый проект, как правило, достигает нескольких сотен.Для сетевого графика, существует два понятия оптимальности: оптимальность по структуре и оптимальность по длительности. Оптимальность по структуре характеризуется степенью параллельности исполнения отдельных работ. Оптимальность по длительности характеризуется рациональным распределением трудовых ресурсов между параллельными видами работами, которое обеспечивает примерно равную их продолжительность.На сегодняшний день нет, и не предвидится появление, строгих методов и алгоритмов построения оптимального сетевого графика, поддающихся автоматизации на ЭВМ. Это связано с тем, что процесс построения оптимального сетевого графика требует от экономиста-проектировщика опыта и интуитивных свойств мышления, реализовать которые на ЭВМ практически не возможно.По другому обстоит дело с задачей анализа оптимальности уже готового сетевого графика. Надо сказать, что с этой задачей экономист-проектировщик сталкивается систематически при оптимизации сетевого графика по длительности, когда каждое очередное принятое решение о перераспределении трудовых ресурсов требует проверки на достижение оптимального варианта. Очевидно, что если автоматизировать процесс решения рассматриваемой задачи, то это существенно снизит продолжительность разработки сетевого графика, а значит и затраты на сетевое планирование в целом. Так вот, задача анализа оптимальности сетевого графика математически формализуема и, с некоторыми трудностями, решаема на ЭВМ. В данном курсовом проекте, как раз и будут предложены и обоснованы рациональные методики решения задачи анализа оптимальности сетевых графиков, легко автоматизируемые на ЭВМ.Постановка задачиКак правило, экономисту-проектировщику не представляется сложным, с первого раза, построить оптимальный по структуре сетевой график, когда будет обеспечена максимальная параллельность исполнения отдельных работ. Всё зависит от понимания им сущности и содержания каждой работы, входящей в состав сетевого графика.Труднее обстоит дело с распределением трудовых ресурсов по отдельным видам работ, от которого зависит оптимальность сетевого графика по длительности. Проблема в том, что практически невозможно предугадать, как отразится на длительности всего проекта и соотношении длительностей различных путей его сетевого графика, перенос трудовых ресурсов с одних работ на другие, в результате которого, при неизменной трудоемкости работ, происходит увеличение длительности первых и уменьшение длительности вторых. В таких условиях, остаётся только один способ оптимизации сетевого графика по длительности. Этот способ основан на методе проб и ошибок, когда, первостепенную важность играет задача проверки и анализа оптимальности уже готового, полностью рассчитанного сетевого графика, с целью выявления ошибок в распределении трудовых ресурсов. Рассмотрим эту задачу и связанные с ней трудности подробнее.Для сетевого графика существуют понятия пути и его продолжительности. Под путем понимается любая цепочка непрерывно следующих, друг за другом, последовательных во времени работ, от начала проекта до его завершения. Под длительностью пути понимается суммарная длительность всех, входящих в него, последовательных работ. Более понятными, данные определения станут при рассмотрении следующего раздела. Сейчас же, важно другое, что каждый сетевой график имеет в своём составе два особых пути: критический и наикратчайший. Критическим путём является путь, имеющий наибольшую продолжительность среди других возможных путей сетевого графика. Наикратчайшим путём является путь, который, в отличие от критического пути, имеет наименьшую продолжительность во всём сетевом графике. На понятиях этих двух путей основан наиболее простой и распространенный критерий оптимальности сетевого графика, формализуемый следующим образом:,(1.1) – коэффициент напряжённости наикратчайшего пути; – длительность наикратчайшего пути, ; – длительность критического пути, .Из критерия REF Формула1 \h (1.1) следует, что некоторый рассматриваемый сетевой график принимается оптимальным, если отношение длительности его наикратчайшего пути к длительности его критического пути не менее 0.7, или, что тоже самое, если длительность наикратчайшего пути отличается от длительности критического пути не более чем на 30%.Забегая вперёд, можно сказать, что длительность критического пути, легко найти путём расчёта некоторых, принятых параметров сетевого графика, которые будут подробно рассмотрены в следующем разделе. Длительность же наикратчайшего пути, в общем случае неизвестна, и для её нахождения требуется суммировать длительности всех, входящих в него работ.Теперь встаёт проблема, – а как найти работы, принадлежащие наикратчайшему пути, чтобы иметь возможность просуммировать их длительности? Решить данную проблему, для человека, интуитивно или простым перебором вариантов, очень проблематично, особенно при большой, сильно разветвленной структуре сетевого графика. Зачастую и ЭВМ справиться с этой задачей не может, в силу того, что её быстродействие ограничено, а число всех возможных вариантов путей сетевого графика, уже при стах событиях, может достигать миллионов или даже сотен миллионов.Так вот, оказывается, эта проблема решаема, причём без перебора вариантов и сравнительно быстро даже для человека, не говоря уже об ЭВМ. Основной целью данной курсового проекта, как раз и является цель показать, а точнее доказать рациональные методики поиска особых путей сетевого графика, которые не только дают возможность проверки его оптимальности, но и позволяют рационально выполнить его оптимизацию по длительности. Последнее заключается в том, что если экономист-проектировщик будет знать, как проходят особые пути сетевого графика, то он сможет, в целях оптимизации, правильно перераспределить трудовые ресурсы, а именно – перенести ресурсы с работ, принадлежащих наикратчайшему пути, на работы, принадлежащие критическому пути, и тем самым уровнять длительности этих путей, для обеспечения выполнения критерия оптимальности REF Формула1 \h (1.1).Теоретические основы сетевого планированияПрежде, чем преступать к обоснованию рациональных методик поиска особых путей сетевого графика, необходимо напомнить, что вообще собой представляет сетевой график, и какими основными параметрами он характеризуется.Итак, сетевой график – есть математическая модель упорядочивания проектных работ типа “Сигнальный граф” (см. пример на рис. REF Рисунок2_1 \h 2.1 ). Любой сигнальный граф состоит только из двух элементов: дуг и вершин. В контексте сетевого планирования, дугами являются отдельные работы, изображаемые на сетевом графике в виде стрелок так, что начала стрелок, соответствует началам выполнения работ, концы стрелок – их завершению. Вершинами сигнального графа являются так называемые события, которые изображаются на сетевом графике в виде кружков, с порядковыми номерами в нижних квадрантах. Как раз события сетевого графика и служат для целей упорядочивания проектных работ, которое заключается в том, что исходящая из некоторого события работа не может начаться, пока не завершаться все входящие в него работы.Существует масса правил, узаконенных стандартом, придерживаться которых необходимо при построении сетевых графиков. Наиболее важные из них:Любой сетевой график должен иметь начальное событие, работы из которого только исходят, и конечное событие, в которое они только входят;Любой путь сетевого графика должен быть полным. То есть, любая цепочка, непрерывно следующих друг за другом, последовательных во времени работ, должна начинаться в исходном событии сетевого графика, а заканчиваться в конечном;Сетевой график не должен иметь замкнутых петель. То есть, недопустимо, чтобы конец некоторой работы являлся бы началом другой работы, предшествующей первой по времени.Имея только структуру сетевого графика, невозможно разрешить вопрос о его оптимальности. Требуется проводить расчеты еще целого ряда, принятых параметров. К этим параметрам относятся:2. SEQ Рисунок \r 1 1 – Пример сетевого графика02143567034125912151512412953000000000ранние и поздние сроки наступления событий;ранние и поздние сроки начала и окончания работ;резервы времени работ и событий.Ранний срок наступления события – это минимально возможный срок, необходимый для выполнения всех работ, предшествующих данному событию. Расчёт ранних сроков наступления событий ведут в порядке – от начального события проекта (с номером 0) до завершающего. При расчёте принимают, что ранний срок наступления начального события равен 0. Для определения раннего срока наступления -го события пользуются правилом, математически записываемым так: ,(2.1) – ранний срок наступления рассматриваемого события, ; – номер рассматриваемого события; – номера предшествующих событий, соединенных с рассматриваемым работами; – ранний срок наступления -го предшествующего события, ; – длительность работы, соединяющей -е предшествующее событие с рассматриваемым, .Таким образом, ранний срок наступления -го события – есть максимально возможная сумма из сумм ранних сроков наступления предшествующих событий и длительностей работ соединяющих предшествующие события с рассматриваемым. Забегая вперёд, надо сказать, что эти суммы равны ранним срокам окончания соответствующих работ. Тогда, ранний срок свершения события – есть максимальный из ранних сроков окончания, входящих в него работ.Поздний срок наступления события – это максимально допустимый срок наступления рассматриваемого события, определяемый из условия, что после наступления этого события в свой поздний срок остаётся достаточно времени, чтобы выполнить следующие за ним работы. Расчёт поздних сроков наступлений событий ведут в обратном порядке – от завершающего события проекта до начального (с номером 0). При расчёте принимают, что поздний срок наступления завершающего события совпадает с его ранним сроком наступления. Для расчёта позднего срока наступления -го события пользуются правилом, математически записываемым так:,(2.2) – поздний срок наступления рассматриваемого события, ; – номер рассматриваемого события; – номера последующих событий, соединённых с рассматриваемым работами; – поздний срок наступления -го последующего события, ; – длительность работы, соединяющей -е последующее событие с рассматриваемым, .Таким образом, поздний срок наступления -го события – есть минимально возможная разность из разностей поздних сроков наступления последующих событий и длительностей работ, соединяющих последующие события с рассматриваемым. Забегая вперёд, необходимо сказать, что эти разности равны поздним срокам начала соответствующих работ. Тогда, поздний срок свершения события – есть минимальный среди поздних сроков начала, исходящих из него работ.Зная ранний и поздний сроки наступления события, можно определить резерв времени события:,(2.3) – резерв времени рассматриваемого события, .Резерв времени события показывает насколько можно отсрочить наступление события по сравнению с его ранним сроком наступления без изменения общей продолжительности всего проекта.Ранний срок начала работы совпадает с ранним сроком наступления её начального события, а ранний срок окончания работы превышает его на величину продолжительности этой работы:;(2.4),(2.5) – ранний срок начала работы, исходящей из -го события и входящей в -е событие, ; – ранний срок окончания данной работы, ; – длительность этой работы, ; – раннее начало события, из которого исходит рассматриваемая работа, ;Поздний срок окончания работы совпадает с поздним сроком наступления её конечного события, а поздний срок начала работы меньше на величину продолжительности этой работы:;(2.6),(2.7) – поздний срок окончания работы, исходящей из -го события и входящей в -е событие, ; – поздний срок начала данной работы, ; – длительность этой работы, ; – позднее окончание события, в которое входит рассматриваемая работа, .Полный резерв времени некоторой работы – это максимальное время, на которое можно отсрочить её начало или увеличить продолжительность, не изменяя директивного срока наступления завершающего события сетевого графика:,(2.8) – полный резерв времени работы, исходящей из -го события и входящей в -е событие, .Свободный резерв времени некоторой работы – максимальное время, на которое можно отсрочить её начало или увеличить её продолжительность при условии, что все события наступают в свои ранние сроки:,(2.9) – свободный резерв времени работы, исходящей из -го события и входящей в -е событие, .В качестве примера, который потребуется и в дальнейшем, основные рассмотренные параметры сетевого графика рассчитаны для случая, представленного на рисунке REF Рисунок2_1 \h 2.1 . Здесь, длительности работ, являющиеся исходными данными для расчёта, выбраны произвольным образом. Параметры работ обозначены соответствующими символами возле стрелок. Параметры событий отражены в трёх квадрантах соответствующих кружков. В левых квадрантах отражены значения ранних сроков свершения событий. В правых – значения поздних сроков свершения событий. В верхних – значения резервов времени событий.Как говорилось в предыдущем разделе, длительность критического пути легко найти из расчёта параметров сетевого графика. Теперь можно сказать, чему она равна, – она равна сроку свершения завершающего события сетевого графика и, соответственно, определяет длительность выполнения всех проектных работ. Последнее заключается в том, что проектные работы не могут завершиться в срок, меньший, чем длительность критического пути, и в тоже время, если все проектные работы выполняются вовремя, то срок их завершения равен длительности критического пути.Обоснование рациональных методик поиска особых путей сетевых графиковОбоснование рациональных методик поиска особых путей сетевого графика основано на смысле полного резерва времени работы, который показывает, на сколько можно отсрочить начало или увеличить продолжительность работы без изменения продолжительности всего проекта. Надо сказать, что этот смысл вытекает из правил расчёта сетевого графика и давно известен, поэтому сейчас он не требуется в специальном рассмотрении. Важно другое – из смысла полного резерва времени работы следует истинность следующего утверждения, на котором основаны некоторые, приводимые ниже доказательства, – полный резерв времени работы может появиться только за счёт существования другого более длительного пути, нежели путь, в состав которого входит рассматриваемая работа. Это утверждение становится очевидным, если подумать – за счёт чего, у некоторой работы, может появиться возможность отсрочить начало её выполнения или увеличить её продолжительность без изменения срока свершения завершающего события сетевого графика? Естественно, только за счёт того, что этот срок свершения определяется другим, более продолжительным путём.Начнём с доказательства методики поиска критического пути сетевого графика. Для этого рассмотрим ряд вспомогательных теорем.Теорема 3.1 – Для того, чтобы некоторый путь сетевого графика был бы критическим, необходимо и достаточно, чтобы полные резервы времени всех входящих в него работ были бы равны нулю.Необходимость – Если некоторый путь является критическим, то полные резервы времени всех входящих в него работ равны нулю.Докажем это утверждение методом от противного. Пусть известно, что некоторый рассматриваемый путь заведомо критический. Теперь предположим противное – на нём лежит хотя бы одна работа с ненулевым резервом времени. Это означает, что есть другой путь, с большей продолжительностью, чем рассматриваемый, за счёт чего и получается данный резерв времени. Но, раз имеется более продолжительный путь, то рассматриваемый путь уже не может быть критическим. Полученное противоречие доказывает невозможность существования на критическом пути работы с ненулевым полным резервом времени, так как в противном случае, он уже не будет являться критическим. Тогда, для любой работы критического пути остаётся другая возможная ситуация – её полный резерв времени равен нулю. Утверждение доказано.Поскольку любой сетевой график имеет критический путь, то есть путь с наибольшей продолжительностью, то, на основании только что доказанного, в любом сетевом графике можно найти путь, работы которого имеют только нулевые полные резервы времени.Достаточность – Если все работы некоторого пути имеют нулевые полные резервы времени, то этот путь обязательно является критическим.Если некоторый путь имеет работы только с нулевыми полными резервами времени, то это означает, что ни одну работу, указанного пути, нельзя увеличить по длительности без изменения срока свершения завершающего события сетевого графика. Это возможно, только когда сумма длительностей работ, рассматриваемого пути равна сроку свершения завершающего события, то есть длительности критического пути. Тогда, рассматриваемый путь и является критическим, в силу того, что он равен критическому пути по длительности. Утверждение доказано.Теорема 3.2 – Если в некоторое событие сетевого графика входит работа с нулевым полным резервом времени, то среди всех исходящих из данного события работ, обязательно найдётся хотя бы одна, имеющая также нулевой резерв времени. То есть, работы с нулевыми резервами времени следуют друг за другом непрерывно.Для доказательства данной теоремы рассмотрим обобщенный пример на рисунке REF Рисунок3_1 \h 3.1 , где, в целях удобства, событиям присвоены условные номера. Докажем теорему методом от противного. REF _Ref437072476 \w 3. SEQ Формула \r 1 1 – Поясняющий рисунок к Теореме 3.2Пусть для работы, входящеё в событие 2, полный резерв времени . Предположим противное – среди всех работ, исходящих из события 2, нет ни одной работы с нулевым полным резервом времени.Для начала найдём, чему равен поздний срок свершения события 2. Он, в соответствии с формулой REF Формула2_2 \h (2.2), определяется как минимальное время позднего начала работы среди всех работ, исходящих из рассматриваемого события. Пусть поздний срок свершения события 2 равен позднему началу работы, входящей, например, в событие 4:,или, в соответствии с выражением REF Формула2_8 \h (2.8) для полного резерва времени,.(3.1)Теперь рассмотрим, какое может иметь значение полный резерв времени работы, исходящей из события 1 и входящей в событие 2. В соответствии с формулой (2.8):.(3.2)Из формулы REF Формула3_2 \h (3.2) видно, что минимально возможное значение полного резерва времени работы, исходящей из события 1 и входящей в событие 2, достигается тогда, когда величина достигает своего максимального значения. Из правила определения раннего срока свершения события, задаваемого формулой REF Формула2_1 \h (2.1), следует, что максимальное значение этой величины может быть равно только раннему сроку свершения события 2, когда ранний срок окончания рассматриваемой работы самый большой из всех ранних сроков окончания работ, входящих в событие 2. Тогда, минимально возможное значение полного резерва времени работы, исходящей из события 1 и входящей в событие 2 равно:,или, исходя из формулы REF Формула3_1 \h (3.1): .(3.3)Поскольку мы предположили от противного, что среди всех исходящих из события 2 работ нет работ с нулевым полным резервом времени, то отсюда сразу вытекает, что и работа, исходящая из события 1 и входящая в событие 2, также не может иметь нулевой полный резерв времени, уж если его минимальное значение заведомо неравно нулю, в соответствии с полученным равенством REF Формула3_3 \h (3.3). Последнее противоречит условию теоремы. Из этого противоречия следует то, что невозможна ситуация, когда при нулевом резерве времени работы, входящей в событие 2, все исходящие из этого события работы имели бы ненулевые резервы времени. Если бы это имело место, то в соответствии с приведённым доказательством, работа, входящая в событие 2 также бы имела ненулевой полный резерв времени. Но ведь это не так по условию теоремы. Тогда для работ, исходящих из события 2 остаётся другая возможная ситуация – хотя бы одна из них имеет также нулевой полный резерв времени. Теорема доказана.Из доказанных выше теорем, непосредственно, следует методика поиска критического пути, приводимая ниже.Рациональная методика поиска критического пути сетевого графика:Просмотр сетевого графика ведётся от его начального события к конечному;При рассмотрении начального события сетевого графика, в качестве работы, лежащей на критическом пути, выбирается та, которая имеет нулевой полный резерв времени. В соответствии с теоремой 3.1 (утверждение-необходимость), такая работа обязательно будет существовать;При рассмотрении работ, исходящих из события, к которому привила работа с нулевым полным резервом времени, выбирается работа, также имеющая нулевой полный резерв времени. В соответствии с теоремой 3.2, такая работа существует; Если, среди исходящих из некоторого события работ, есть несколько работ с нулевыми полными резервами времени, то выбирается любая. При этом, согласно теореме 3.2, процесс построения критического пути в тупик зайти не может, и рано или поздно дойдет до завершающего события сетевого графика.Реализация указанных правил даёт путь, состоящий только из работ с нулевыми полными резервами времени. Тогда, на основании теоремы 3.1 (утверждение-достаточность), этот путь и будет являться критическим.В целях проверки, доказанная методика применена для сетевого графика, представленного на рисунке REF Рисунок2_1 \h 2.1 . Здесь, найденные критические пути, выделены жирными стрелками. Как видно, таких путей два, благодаря тому, что среди работ, исходящих из события 0, есть две работы с нулевыми полными резервами времени. Проверить то, что найденные пути являются критическими легко, просуммировав длительности принадлежащих им работ. Суммы окажутся: во-первых, равными между собой, а во-вторых, наибольшими среди аналогичных сумм других возможных путей.Теперь рассмотрим вопрос поиска наикратчайшего пути сетевого графика. Оказывается, для его поиска можно применять, методику поиска критического пути, если использовать идею, высказываемую в следующей теореме.Теорема 3.3 – Если произвести расчёт параметров заданного сетевого графика по установленным правилам, но заменяя известные длительности работ на те же значения с отрицательным знаком (длительности всех работ будут меньше нуля), то наикратчайший путь сетевого графика станет подчиняться всем свойствам критического пути.Эту теорему легко доказать, используя правило сравнения отрицательных чисел. Данное правило заключается в том, что одно отрицательное число считается большим другого, если абсолютное значение первого меньше абсолютного значения второго. Поскольку длительность наикратчайшего пути, по абсолютному значению наименьшая, среди длительностей всех других путей сетевого графика, то, на основании указанного правила, отрицательная длительность наикратчайшего пути будет наибольшей среди отрицательных длительностей остальных путей. Тогда, наикратчайший путь, состоящий из работ с отрицательными длительностями, будет критическим, при условии, что все остальные пути, также состоят из работ с отрицательными длительностями. Теорема доказана.Для проверки доказанной теоремы, параметры сетевого графика на рисунке REF Рисунок2_1 \h 2.1 пересчитаны заново, при отрицательных значениях длительностей работ, и представлены на рисунке REF Рисунок3_2 \h 3.2 . Как видно, сетевой график на рисунке REF Рисунок3_2 \h 3.2 содержит путь, работы которого имеют только нулевые полные резервы времени. Данный путь выделен жирными стрелками. Этот путь, являясь критическим для сетевого графика на рисунке REF Рисунок3_2 \h 3.2 , в тоже время является наикратчайшим путем для сетевого графика на рисунке REF Рисунок2_1 \h 2.1 . Последнее можно проверить простым суммированием длительностей его работ. Полученная сумма должна быть наименьшей по абсолютному значению, среди аналогичных сумм других путей сетевого графика на рисунке REF Рисунок2_1 \h 2.1 . Вообще говоря, для нахождения продолжительности наикратчайшего пути, необходимой при анализе оптимальности сетевого графика по критерию REF Формула1 \h (1.1), не обязательно суммировать длительности всех, принадлежащих ему работ. Она уже известна из рассчитанных, при отрицательных длительностях работ, параметров сетевого графика, и равна, как и для любого критического пути, сроку свершения завершающего события. Естественно, что данный срок свершения имеет отрицательное значение, и поэтому, для нахождения фактической длительности наикратчайшего пути, требуется менять это значение на противоположное.3. SEQ Рисунок 2 – Пример сетевого графика при отрицательных длительностях работ021435670-3-1-6-5-7-7-9-9-62-6-6-4-3001110030Необходимо сказать, что можно поставить и решить общую задачу поиска пути заданной продолжительности. Но данная задача принципиальной важности, при анализе сетевого графика, не несёт. Для анализа оптимальности сетевого графика и осуществления его оптимизации, достаточно знать лишь, как проходят особые пути, и какова их продолжительность. Ответы на эти вопросы и дают рациональные методики поиска особых путей, доказанные в этом разделе.Автоматизация анализа оптимальности сетевых графиков на ЭВМПредставление сетевого графика в машинной формеЛюбая ЭВМ нуждается в преобразовании различных абстрактных понятий, ясных для человека, в удобную для неё форму. Сетевой график, как графическое изображение упорядоченных кружков и стрелок само по себе для ЭВМ нечего не значить. Для того, чтобы ЭВМ могла понимать структуру сетевого графика и, главное, обрабатывать её, необходимо представить эту структуру в эквивалентной машинной форме.Наиболее удобный способ представления структуры сетевого графика в машинной форме, основан на понятии матрицы смежностей . Пример данной матрицы для структуры сетевого графика на рисунке REF Рисунок2_1 \h 2.1 представлен на рисунке REF Рисунок4_1 \h 4.1 .Матрица смежностей квадратная и имеет размерность , где – число событий сетевого графика. Номера строк матрицы задаются номерами событий , из которых работы сетевого графика исходят, номера столбцов матрицы задаются номерами событий , в которые работы сетевого графика входят. На пересечении строки и столбца , в матрице смежностей, может быть только одно из двух значений: 0 или 1. Если , то это означает, что на сетевом графике существует работа, исходящая из события с номером и входящая в событие с номером . Если , то такой работы на сетевом графике нет.Матрица смежностей будет верно отражать структуру сетевого графика, если сетевой график построен по всем, узаконенным стандартом правилам. Здесь, наиболее важны следующие:52070723900С0С1С2С3С4С5С6С7С0С1С2С3С4С5С6С711111111111111000000000000004. SEQ Рисунок \r 1 1 – Матрица смежностей сетевого графикаCiCj00С0С1С2С3С4С5С6С7С0С1С2С3С4С5С6С711111111111111000000000000004. SEQ Рисунок \r 1 1 – Матрица смежностей сетевого графикаCiCjСобытиям присваиваются номера с таким расчётом, что старший номер соответствует более позднему по времени событию. То есть, если рассмотреть некоторое событие и все входящие в него работы, то номер этого события должен быть больше номеров всех событий, из которых эти работы исходят. В этом случае первая строка и первый столбец матрицы смежностей соответствует начальному событию сетевого графика , а последние строка и столбец – завершающему событию сетевого графика , где – число всех событий в сетевом графике.Два события сетевого графика может соединять только одна работа. Если все же имеет место факт соединения двух событий несколькими работами, то, для выполнения указанного правила, необходимо ввести дополнительные события, разрывающие лишние работы и дополняющие их фиктивными работами с нулевой длительностью (см. пример на рис. REF Рисунок4_2 \h 4.2 ). Дополнительные события также должны иметь свои уникальные, в сетевом графике, номера, присвоенные им в соответствии с первым правилом.Верно построенная матрица смежностей обладает радом полезных свойств:114935683895ВерноНеверно113224. SEQ Рисунок 2 – Пример разрыва параллельных работФиктивная работа00ВерноНеверно113224. SEQ Рисунок 2 – Пример разрыва параллельных работФиктивная работаЕсли задаться некоторым номером события , то единицы в соответствующей строке укажут на номера событий , с которыми событие соединено, исходящими из него работами. Это свойство следует из правила построения матрицы смежностей.Если задаться некоторым номером события , то единицы в соответствующем столбце укажут на номера событий , с которыми событие соединено, входящими в него работами. Это свойство, также, следует из правила построения матрицы смежностей.Если некоторое событие указывает единицами в соответствующей строке матрицы смежностей на соединённые с ним события , то номера этих событий могут быть только больше номера , что ясно из правила присвоения номеров событиям сетевого графика. Из этого свойства следует, что матрица смежностей носит диагональный характер, то есть, единицы в матрице смежностей могут присутствовать только в верхней диагональной части матрицы (см. рис. REF Рисунок4_1 \h 4.1 ).Любопытно заметить, что если последнее из перечисленных свойств не выполняется, то в сетевом графике есть петли, то есть, работы, концы которых являются началами других работ, предшествующих первым по времени, при условии, что все события занумерованы, верно. Из этого следует возможность легкой автоматизации на ЭВМ процесса проверки правильности построения сетевого графика. Данный процесс проверки, алгоритмически, представляется в виде блок-схемы REF Блоксхема4_1 \h 4.1 .Суть алгоритма проверки заключается в определении содержимого элементов нижней диагональной части матрицы смежностей. Если там встретится хотя бы одна единица, то это будет означать, что сетевой график построен неправильно – либо в нем есть петли, либо события занумерованы не верно.4521201000760НачалоМатрица смежностей уже заданаi:=0j:=0Mi j<> 0Ошибка в структуре графикаErr:=1Err=1 – Ошибка в структуре;Err=0 –Ошибок нет.ДаНетj:=j+1j > iДаНетj:=0i:=i+1i < pНетErr:=0p – Число событий на графикеВ структуре ошибок нетКонецДа00НачалоМатрица смежностей уже заданаi:=0j:=0Mi j<> 0Ошибка в структуре графикаErr:=1Err=1 – Ошибка в структуре;Err=0 –Ошибок нет.ДаНетj:=j+1j > iДаНетj:=0i:=i+1i < pНетErr:=0p – Число событий на графикеВ структуре ошибок нетКонецДаБлок-схема REF _Ref437079778 \w 4. SEQ "Блок-схема" \r1 \* MERGEFORMAT 1 – Алгоритм тестирования матрицы смежностейАвтоматизация расчёта параметров сетевого графикаАнализ оптимальности сетевого графика возможно провести, только после расчёта всех, присущих ему параметров. Исходными данными для расчёта являются длительности всех, входящих в сетевой график работ. Результатами расчёта являются значения, описанных в разделе 2, параметров. И первое и второе, можно объединить в одной таблице исходных данных и результатов REF Таблица4_1 \h 4.1 .Данная таблица – есть двумерная матрица с пронумерованными строками и столбцами. Номера строк изменяются от 0 до (см. таб. REF Таблица4_1 \h 4.1 ), где – число работ в сетевом графике, которое можно найти, подсчитав все единицы в матрице смежностей. Номера столбцов изменяются от 0 до 13, где каждый номер соответствует своему параметру сетевого графика. Нумерация строк и столбцов необходима для представления таблицы исходных данных и результатов в машинной форме. Столбцы под номерами 0,1 и 2 определяют часть таблицы REF Таблица4_1 \h 4.1 , отведённую под хранение исходных данных, к которым относятся коды работ и длительности работ. Как видно, коды работ задаются ячейками двух столбцов под номерами 0 и 1. Здесь индекс (столбец 0) определяет номер события, из которого работа исходит, а индекс (столбец 1) определяет номер события, в которое она входит. Найти все возможные коды работ сетевого графика легко по матрице смежностей , если, просматривая её строки, номера которых соответствуют индексу , выбирать в качестве индекса номера тех столбцов, для которых будут отыскиваться единицы.Алгоритм заполнения таблицы 4.1 исходными данными представлен в виде блок-схемы 4.2 , где ячейки самой таблицы обозначены символом . Для данного обозначения: – номер строки таблицы исходных данных и результатов, – номер столбца той же таблицы. Алгоритм предполагает, что таблица исходных данных и результатов уже зарезервирована и имеет размерность , – число работ в сетевом графике.-19177043815 Таблица REF _Ref437079778 \w 4. SEQ Таблица \r 1 1 – Таблица исходных данных и результатовКод работыПараметры работ и событийij01234567891011121301k-1N строкиN Столбца00 Таблица REF _Ref437079778 \w 4. SEQ Таблица \r 1 1 – Таблица исходных данных и результатовКод работыПараметры работ и событийij01234567891011121301k-1N строкиN Столбца Блок-схема REF _Ref437079778 \w 4. SEQ "Блок-схема" \* MERGEFORMAT 2 – Алгоритм заполнения исходными данными таблицы исходных данных и результатов1511300363855j:= j+1j
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Переехав в город, Вася Муходрищев вскоре выяснил, что зубная паста сама по себе не помогает сохранить крепкие, здоровые зубы. Нужно еще как минимум не ставить свой ржавый жигуль на тротуар.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по компьютерным сетям "Сетевой трафик", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru