Xreferat.com » Рефераты по экономико-математическому моделированию » Рациональные методики поиска оптимальных путей сетевых графиков и их автоматизация на ЭВМ

Рациональные методики поиска оптимальных путей сетевых графиков и их автоматизация на ЭВМ

методика поиска критического пути, приводимая ниже.

Рациональная методика поиска критического пути сетевого графика:

  1. Просмотр сетевого графика ведётся от его начального события к конеч­ному;

  2. При рассмотрении начального события сетевого графика, в качестве ра­боты, лежащей на критическом пути, выбирается та, которая имеет нулевой пол­ный резерв времени. В соответствии с теоремой 3.1 (утверждение-необходимость), такая работа обязательно будет существовать;

  3. При рассмотрении работ, исходящих из события, к которому привила ра­бота с нулевым полным резервом времени, выбирается работа, также имеющая нулевой полный резерв времени. В соответствии с теоремой 3.2, такая работа су­ще­ствует;

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

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

В целях проверки, доказанная методика применена для сетевого графика, представленного на рисунке Error: Reference source not found. Здесь, найденные критические пути, выделены жирными стрелками. Как видно, таких путей два, благодаря тому, что среди работ, исходящих из события 0, есть две работы с нулевыми полными резервами вре­мени. Проверить то, что найденные пути являются критическими легко, просум­мировав длительности принадлежащих им работ. Суммы окажутся: во-первых, равными между собой, а во-вторых, наибольшими среди аналогичных сумм дру­гих возможных путей.

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

Теорема 3.3 – Если произвести расчёт параметров заданного сетевого гра­фика по установленным правилам, но заменяя известные длительности работ на те же значения с отрицательным знаком (длительности всех работ будут меньше нуля), то наикратчайший путь сетевого графика станет подчиняться всем свойст­вам кри­тического пути.

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

Для проверки доказанной теоремы, параметры сетевого графика на рисунке Error: Reference source not foundпересчитаны заново, при отрицательных значениях длительностей работ, и пред­ставлены на рисунке Error: Reference source not found. Как видно, сетевой график на рисунке Error: Reference source not foundсодержит путь, работы которого имеют только нулевые полные резервы времени. Данный путь выделен жирными стрелками. Этот путь, являясь критическим для сетевого гра­фика на рисунке Error: Reference source not found, в тоже время является наикратчайшим путем для сетевого гра­фика на рисунке Error: Reference source not found. Последнее можно проверить простым суммированием дли­тельностей его работ. Полученная сумма должна быть наименьшей по абсо­лют­ному значению, среди аналогичных сумм других путей сетевого графика на ри­сунке Error: Reference source not found.

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

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

4Автоматизация анализа оптимальности сетевых графиков на ЭВМ

4.1Представление сетевого графика в машинной форме

Любая ЭВМ нуждается в преобразовании различных абстрактных понятий, ясных для человека, в удобную для неё форму. Сетевой график, как графическое изображение упорядоченных кружков и стрелок само по себе для ЭВМ нечего не значить. Для того, чтобы ЭВМ могла понимать структуру сетевого графика и, главное, обрабатывать её, необходимо представить эту структуру в эквивалентной машинной форме.

Наиболее удобный способ представления структуры сетевого графика в ма­шинной форме, основан на понятии матрицы смежностей . Пример данной матрицы для структуры сетевого графика на рисунке Error: Reference source not foundпредставлен на рисунке Error: Reference source not found.

Матрица смежностей квадратная и имеет размерность , где – число событий сетевого графика. Номера строк матрицы задаются номерами событий , из которых работы сетевого графика исходят, номера столбцов матрицы зада­ются номерами событий , в которые работы сетевого графика входят. На пере­сечении строки и столбца , в матрице смежностей, может быть только одно из двух значений: 0 или 1. Если , то это означает, что на сетевом гра­фике существует работа, исходящая из события с номером и входящая в со­бытие с номером . Если , то такой работы на сетевом графике нет.

Матрица смежностей будет верно отражать структуру сетевого графика, если сетевой график построен по всем, узаконенным стандартом правилам. Здесь, наиболее важны следующие:

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

  • Два события сетевого графика может соединять только одна работа. Если все же имеет место факт соединения двух событий несколькими работами, то, для выполнения указанного правила, необходимо ввести дополнительные события, разрывающие лишние работы и дополняющие их фиктивными работами с нулевой длительностью (см. пример на рис. Error: Reference source not found). Дополнительные события также должны иметь свои уникальные, в сетевом графике, номера, присвоенные им в соответст­вии с первым правилом.

Верно построенная матрица смежностей обладает радом полезных свойств:

  • Е
    сли задаться некоторым номером события , то единицы в соответст­вующей строке укажут на номера событий , с которыми событие соединено, исходящими из него работами. Это свойство следует из правила построения мат­рицы смежностей.

  • Если задаться некоторым номером события , то единицы в соответст­вующем столбце укажут на номера событий , с которыми событие соеди­нено, входящими в него работами. Это свойство, также, следует из правила по­строения матрицы смежностей.

  • Если некоторое событие указывает единицами в соответствующей строке матрицы смежностей на соединённые с ним события , то номера этих событий могут быть только больше номера , что ясно из правила присвоения номеров событиям сетевого графика. Из этого свойства следует, что матрица смежностей носит диагональный характер, то есть, единицы в матрице смежно­стей могут присутствовать только в верхней диагональной части матрицы (см. рис. Error: Reference source not found).

Любопытно заметить, что если последнее из перечисленных свойств не вы­полняется, то в сетевом графике есть петли, то есть, работы, концы которых явля­ются началами других работ, предшествующих первым по времени, при условии, что все события занумерованы, верно. Из этого следует возможность легкой авто­матизации на ЭВМ процесса проверки правильности построения сетевого гра­фика. Данный процесс проверки, алгоритмически, представляется в виде блок-схемы 4. .

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


Б
лок-схема 4. – Алгоритм тестирования матрицы смежностей


4.2Автоматизация расчёта параметров сетевого графика

Анализ оптимальности сетевого графика возможно провести, только после расчёта всех, присущих ему параметров. Исходными данными для расчёта явля­ются длительности всех, входящих в сетевой график работ. Результатами расчёта являются значения, описанных в раз­деле 2, параметров. И первое и второе, можно объединить в одной таблице исход­ных данных и результатов Error: Reference source not found.

Данная таблица – есть двумерная матрица с пронумерованными строками и столбцами. Номера строк изменяются от 0 до (см. таб. Error: Reference source not found), где – число ра­бот в сетевом графике, которое можно найти, подсчитав все единицы в матрице смежностей. Номера столбцов изменяются от 0 до 13, где каждый номер соответ­ствует своему параметру сетевого графика. Нумерация строк и столбцов необхо­дима для представления таблицы исходных данных и результатов в машинной форме.

Столбцы под номерами 0,1 и 2 определяют часть таблицы Error: Reference source not found, отведённую под хранение исходных данных, к которым относятся коды работ и длительности работ. Как видно, коды работ задаются ячейками двух столбцов под номерами 0 и 1. Здесь индекс (столбец 0) определяет номер события, из которого работа исхо­дит, а индекс (столбец 1) определяет номер события, в которое она входит. Найти все возможные коды работ сетевого графика легко по матрице смежностей , если, просматривая её строки, номера которых соответствуют индексу , выбирать в качестве индекса номера тех столбцов, для которых будут отыски­ваться единицы.

Алгоритм заполнения таблицы Error: Reference source not foundисходными данными представлен в виде блок-схемы 4. , где ячейки самой таблицы обозначены символом . Для дан­ного обозначения: – номер строки таблицы исходных данных и результатов, – номер столбца той же таблицы. Алгоритм предполагает, что таблица исходных данных и результатов уже зарезервирована и имеет размерность , – число работ в сетевом графике.


Блок-схема 4. – Алгоритм заполнения исходными данными таблицы исходных данных и результатов


После заполнения таблицы Error: Reference source not foundисходными данными для расчёта, идёт сле­дующая стадия, – непосредственно, сам расчёт параметров сетевого графика. Данная стадия выполняется в три этапа. На первом этапе осуществляется расчёт сетевого графика в порядке – от начального события до завершающего, и опреде­ляются ранние сроки свершения событий, ранние начала и окончания работ. На втором этапе осуществляется расчёт сетевого графика в обратном порядке – от за­вершающего события до начального, и определяются поздние сроки свершения событий, поздние начала и окончания работ. На третьем этапе осуществляется расчёт резервов времени событий и работ, в произвольном порядке.

Рассмотрим расчёт параметров сетевого графика на первом этапе.

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

Теорема 4.1 – Если события сетевого графика занумерованы так, что любая его работа исходит из события с меньшим номером и входит в событие с большим номером, то расчёт ранних сроков свершения событий в порядке: 0-е событие, 1-е, 2-е, и так далее, до завершающего события, в тупик зайти не может, при условии, что рассчитывая ранний срок свершения очередного события, сразу же определя­ются ранние окончания всех, исходящих из него работ.

Докажем эту теорему методом математической индукции.

Зададимся нулевым сроком свершения 0-го события, и рассчитаем ранние окончания всех, исходящих из него работ. Далее. Рассмотрим 1-е событие. В него могут входить только работы, исходящие из событий с меньшими номерами – в данном случае только из 0-го события, при этом ранние окончания этих работ уже известны. Тогда можно рассчитать ранний срок свершения 1-го события. Рассчи­тав ранний срок свершения 1-го события, сразу же рассчитаем ранние окончания всех, исходящих из него работ. Далее. Рассмотрим 2-е событие. В него могут вхо­дить работы, только из 0-го и 1-го события, и ранние окончания которых уже из­вестны. Тогда можем рассчитать ранний срок свершения 2-го события. Рассчитав ранний срок свершения 2-го события, сразу же рассчитаем ранние окончания всех, исходящих из него работ. Далее. Рассмотрим 3-е событие. В него могут входить работы, только из 0-го, 1-го и 2-го события, и ранние окончания которых уже из­вестны. Тогда можем рассчитать ранний срок свершения 3-го события….

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

Из данной теоремы, непосредственно, вырисовывается алгоритм расчёта па­раметров сетевого графика на первом этапе. Данный алгоритм представлен в виде блок-схемы 4. , и основан на том, что после выполнения алгоритма 4. , в таблице исходных данных и результатов уже находятся коды работ сетевого графика и их длительности.

Блок-схема 4. – Алгоритм расчета ранних сроков свершения событий сетевого графика




Рассмотрим расчёт параметров сетевого графика на втором этапе.

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

Теорема 4.2 – Если события сетевого графика занумерованы так, что любая его работа исходит из события с меньшим номером и входит в событие с большим номером, то расчёт поздних сроков свершения событий в порядке: последнее со­бытие, предпоследние событие, предшествующее предпоследнему событию, и так далее, до начального (0-го) события, в тупик зайти не может, при условии, что рас­считывая поздний срок свершения очередного события, сразу же определяются поздние начала всех, входящих в него работ.

Докажем эту теорему методом математической индукции.

Зададимся поздним сроком свершения последнего события, равным его ран­нему сроку свершения, и рассчитаем поздние начала всех, входящих в него работ. Далее. Рассмотрим предпоследнее событие. Из него могут исходит только работы, входящие в события с большими номерами – в данном случае только в последнее событие, при этом поздние начала этих работ уже известны. Тогда можно рассчи­тать поздний срок свершения предпоследнего события. Рассчитав поздний срок свершения предпоследнего события, сразу же рассчитаем поздние начала всех, входящих в него работ. Далее. Рассмотрим событие, предшествующее предпо­следнему. Из него могут исходить работы, только в предпоследнее и в последнее событие, и поздние начала которых уже известны. Тогда можем рассчитать позд­ний срок свершения события, предшествующего предпоследнему….

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

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


Блок-схема 4. – Алгоритм расчёта поздних сроков свершения событий сетевого графика




Рассмотрим расчёт параметров сетевого графика на третьем этапе.

Если, сначала выполнить алгоритм расчёта ранних сроков свершения собы­тий 4. , а затем алгоритм расчёта поздних сроков свершения 4. , то в таблице ис­ходных данных и результатов останутся не заполненными только три последних столбца, с номерами: 11, 12 и 13. Данные столбцы, как видно из таблицы Error: Reference source not found, отве­дены под расчёт резервов времени сетевого графика. Расчёт резервов времени се­тевого графика можно осуществить в любом порядке строк таблицы исходных данных и результатов, например, подряд – с 0-й строки по последнюю. Такой по­рядок расчёта представлен ниже, в виде блок-схемы 4. . Данный алгоритм явля­ется завершающим для процесса расчёта параметров сетевого графика, после вы­полнения которого, все ячейки таблицы исходных данных и результатов Error: Reference source not found, будут заполнены значениями соответствующих параметров.

Блок-схема 4. – Алгоритм расчёта резервов времени сетевого графика


4.3Автоматизация процесса поиска особых путей сетевого графика

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

Из раздела 3 ясно, что для поиска, и критического пути и наикратчайшего, возможно использовать одну и туже методику. Данная методика заключается в по­следовательном выборе, от 0-го события до завершающего, тех работ, которые имеют нулевые полные резервы времени. В случае, если параметры сетевого гра­фика рассчитывались для положительных длительностей, входящих в него работ, то указанная методика даёт критический путь сетевого графика. Если же пара­метры рассчитывались при отрицательных длительностях работ, то методика даст наикратчайший путь сетевого графика.

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

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


Блок-схема 4. – Алгоритм поиска особого пути сетевого графика


Заключение

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

Кроме того, в курсовом проекте были рассмотрены вопросы автоматизации на ЭВМ рациональных методик поиска особых путей сетевого графика. В резуль­тате – разработаны блок схемы алгоритмов расчёта параметров сетевых графиков и поиска их особых путей, которые предполагается использовать при создании конкретной программы анализа оптимальности сетевых графиков на любом из из­вестных языках программирования.

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

Список использованных источников

Технико-экономическое обоснование дипломных проектов проектов: Учеб. Пособие для втузов / Л. А. Астреина, В. В. Балдесов, В. К. Беклешов и др.; Под ред. В. К. Беклешова. – М.: Высш. Шк., 1991. – 176 c.: ил.


Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: