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

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

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

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

<img width=«148» height=«53» src=«ref-1_657748193-395.coolpic» v:shapes="_x0000_i1025">,                                                                                 (1.1)

где           <img width=«44» height=«25» src=«ref-1_657748588-225.coolpic» v:shapes="_x0000_i1026"> – коэффициент напряжённости наикратчайшего пути;

<img width=«37» height=«25» src=«ref-1_657748813-216.coolpic» v:shapes="_x0000_i1027"> – длительность наикратчайшего пути, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1028">;

<img width=«40» height=«25» src=«ref-1_657749242-222.coolpic» v:shapes="_x0000_i1029"> – длительность критического пути, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1030">.

Из критерия (1.1) следует, что некоторый рассматриваемый сетевой график принимается оптимальным, если отношение длительности его наикратчайшего пути к длительности его критического пути не менее 0.7, или, что тоже самое, если длительность наикратчайшего пути отличается от длительности критиче­ского пути не более чем на 30%.

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

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

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

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

Итак, сетевой график – есть математическая модель упорядочивания про­ектных работ типа “Сигнальный граф” (см. пример на рис.2.1). Любой сигналь­ный граф состоит только из двух элементов: дуг и вершин. В контексте сетевого пла­нирования, дугами являются отдельные работы, изображаемые на сетевом графике в виде стрелок так, что начала стрелок, соответствует началам выполне­ния работ, концы стрелок – их завершению. Вершинами сигнального графа явля­ются так на­зывае­мые события, которые изображаются на сетевом графике в виде кружков, с поряд­ковыми номерами в нижних квадрантах. Как раз события сете­вого графика и служат для целей упорядочивания проектных работ, которое за­ключается в том, что исходящая из неко­торого события работа не может начаться, пока не завер­шаться все входящие в него работы.

Существует масса правил, узаконенных стандартом, придерживаться кото­рых необходимо при построении сетевых графиков. Наиболее важные из них:

−       Любой сетевой график должен иметь начальное событие, ра­боты из ко­то­рого только исходят, и конечное событие, в которое они только входят;

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

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

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

−       <img width=«645» height=«433» src=«ref-1_657749677-23536.coolpic» v:shapes="_x0000_s2378 _x0000_s1113 _x0000_s1114 _x0000_s1115 _x0000_s1116 _x0000_s1117 _x0000_s1118 _x0000_s1119 _x0000_s1120 _x0000_s1121 _x0000_s1122 _x0000_s1123 _x0000_s1124 _x0000_s1125 _x0000_s1126 _x0000_s1127 _x0000_s1128 _x0000_s1129 _x0000_s1130 _x0000_s1131 _x0000_s1132 _x0000_s1133 _x0000_s1134 _x0000_s1135 _x0000_s1136 _x0000_s1137 _x0000_s1138 _x0000_s1139 _x0000_s1140 _x0000_s1141 _x0000_s1142 _x0000_s1143 _x0000_s1144 _x0000_s1145 _x0000_s1146 _x0000_s1147 _x0000_s1148 _x0000_s1149 _x0000_s1150 _x0000_s1151 _x0000_s1152 _x0000_s1153 _x0000_s1154 _x0000_s1155 _x0000_s1156 _x0000_s1157 _x0000_s1158 _x0000_s1159 _x0000_s1160 _x0000_s1161 _x0000_s1162 _x0000_s1163 _x0000_s1164 _x0000_s1165 _x0000_s1166 _x0000_s1167 _x0000_s1168 _x0000_s1169 _x0000_s1170 _x0000_s1171 _x0000_s1172 _x0000_s1173 _x0000_s1174 _x0000_s1175 _x0000_s1176 _x0000_s1177 _x0000_s1178 _x0000_s1179 _x0000_s1180 _x0000_s1181 _x0000_s1182 _x0000_s1183 _x0000_s1184 _x0000_s1185 _x0000_s1186 _x0000_s1187 _x0000_s1188 _x0000_s1189 _x0000_s1190 _x0000_s1191 _x0000_s1192 _x0000_s1193 _x0000_s1194 _x0000_s1195 _x0000_s1196 _x0000_s1197 _x0000_s1198 _x0000_s1199">
ранние и поздние сроки наступления событий;

−       ранние и поздние сроки начала и окончания работ;

−       резервы времени работ и событий.

Ранний срок наступления события – это минимально возможный срок, необ­ходимый для выполнения всех работ, предшествующих данному событию. Расчёт ранних сроков наступления событий ведут в порядке – от начального собы­тия проекта (с номером 0) до завершающего. При расчёте принимают, что ран­ний срок наступления начального события равен 0. Для определения ран­него срока наступ­ления <img width=«11» height=«19» src=«ref-1_657773213-188.coolpic» v:shapes="_x0000_i1031">-го события пользуются правилом, математически записывае­мым так:

<img width=«185» height=«35» src=«ref-1_657773401-465.coolpic» v:shapes="_x0000_i1032"> ,                                                                        (2.1)

где           <img width=«40» height=«31» src=«ref-1_657773866-254.coolpic» v:shapes="_x0000_i1033"> – ранний срок наступления рассматриваемого события, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1034">;

<img width=«11» height=«19» src=«ref-1_657773213-188.coolpic» v:shapes="_x0000_i1035"> – номер рассматриваемого события;

<img width=«15» height=«23» src=«ref-1_657774521-194.coolpic» v:shapes="_x0000_i1036"> – номера предшествующих событий, соединенных с рассматривае­мым работами;

<img width=«44» height=«33» src=«ref-1_657774715-258.coolpic» v:shapes="_x0000_i1037"> – ранний срок наступления <img width=«15» height=«23» src=«ref-1_657774521-194.coolpic» v:shapes="_x0000_i1038">-го предшествующего события, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1039">;

<img width=«23» height=«29» src=«ref-1_657775380-206.coolpic» v:shapes="_x0000_i1040"> – длительность работы, соединяющей <img width=«15» height=«23» src=«ref-1_657774521-194.coolpic» v:shapes="_x0000_i1041">-е предшествующее собы­тие с рассматриваемым, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1042">.

Таким образом, ранний срок наступления <img width=«11» height=«19» src=«ref-1_657773213-188.coolpic» v:shapes="_x0000_i1043">-го события – есть максимально воз­можная сумма из сумм ранних сроков наступления предшествующих событий и длитель­ностей работ соединяющих предшествующие события с рассматривае­мым. Забегая вперёд, надо сказать, что эти суммы равны ранним срокам окончания соответствующих работ. Тогда, ранний срок свершения события – есть макси­мальный из ранних сроков окончания, входящих в него работ.

Поздний срок наступления события – это максимально допустимый срок на­ступления рассматриваемого события, определяемый из условия, что после насту­пления этого события в свой поздний срок остаётся достаточно времени, чтобы выполнить следующие за ним работы. Расчёт поздних сроков наступлений собы­тий ведут в обратном порядке – от завершающего события проекта до на­чального (с номером 0). При расчёте принимают, что поздний срок на­сту­пления завершаю­щего события совпадает с его ранним сроком наступле­ния. Для расчёта позднего срока наступления <img width=«11» height=«19» src=«ref-1_657773213-188.coolpic» v:shapes="_x0000_i1044">-го события пользуются правилом, матема­тически записывае­мым так:

<img width=«179» height=«35» src=«ref-1_657776369-455.coolpic» v:shapes="_x0000_i1045">,                                                                           (2.2)

где           <img width=«39» height=«31» src=«ref-1_657776824-250.coolpic» v:shapes="_x0000_i1046"> – поздний срок наступления рассматриваемого события, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1047">;

<img width=«11» height=«19» src=«ref-1_657773213-188.coolpic» v:shapes="_x0000_i1048"> – номер рассматриваемого события;

<img width=«15» height=«23» src=«ref-1_657774521-194.coolpic» v:shapes="_x0000_i1049"> – номера последующих событий, соединённых с рассматриваемым работами;

<img width=«41» height=«33» src=«ref-1_657777669-256.coolpic» v:shapes="_x0000_i1050"> – поздний срок наступления <img width=«15» height=«23» src=«ref-1_657774521-194.coolpic» v:shapes="_x0000_i1051">-го последующего события, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1052">;

<img width=«23» height=«29» src=«ref-1_657778332-210.coolpic» v:shapes="_x0000_i1053"> – длительность работы, соединяющей <img width=«15» height=«23» src=«ref-1_657774521-194.coolpic» v:shapes="_x0000_i1054">-е последующее событие с рассматриваемым, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1055">.

Таким образом, поздний срок наступления <img width=«11» height=«19» src=«ref-1_657773213-188.coolpic» v:shapes="_x0000_i1056">-го события – есть минимально воз­можная разность из разностей поздних сроков наступления последующих событий и дли­тельностей работ, соединяющих последующие события с рассматриваемым. Забегая вперёд, необходимо сказать, что эти разности равны позд­ним срокам на­чала соответствующих работ. Тогда, поздний срок свершения события – есть ми­нимальный среди поздних сроков начала, исходящих из него работ.

Зная ранний и поздний сроки наступления события, можно определить ре­зерв времени события:

<img width=«132» height=«31» src=«ref-1_657779137-370.coolpic» v:shapes="_x0000_i1057">,                                                                                    (2.3)

где           <img width=«21» height=«25» src=«ref-1_657779507-213.coolpic» v:shapes="_x0000_i1058"> – резерв времени рассматриваемого события, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1059">.

Резерв времени события показывает насколько можно отсрочить наступление со­бытия по сравнению с его ранним сроком наступления без изменения об­щей про­должительности всего проекта.

Ранний срок начала работы совпадает с ранним сроком наступления её на­чального события, а ранний срок окончания работы превышает его на величину продолжительности этой работы:

<img width=«113» height=«35» src=«ref-1_657779933-366.coolpic» v:shapes="_x0000_i1060">;                                                                                        (2.4)

<img width=«153» height=«35» src=«ref-1_657780299-418.coolpic» v:shapes="_x0000_i1061">,                                                                                (2.5)

где           <img width=«56» height=«35» src=«ref-1_657780717-280.coolpic» v:shapes="_x0000_i1062"> – ранний срок начала работы, исходящей из <img width=«11» height=«19» src=«ref-1_657773213-188.coolpic» v:shapes="_x0000_i1063">-го события и входящей в <img width=«15» height=«23» src=«ref-1_657774521-194.coolpic» v:shapes="_x0000_i1064">-е событие, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1065">;

<img width=«56» height=«35» src=«ref-1_657781592-281.coolpic» v:shapes="_x0000_i1066"> – ранний срок окончания данной работы, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1067">;

<img width=«23» height=«29» src=«ref-1_657778332-210.coolpic» v:shapes="_x0000_i1068"> – длительность этой работы, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1069">;

<img width=«40» height=«31» src=«ref-1_657773866-254.coolpic» v:shapes="_x0000_i1070"> – раннее начало события, из которого исходит рассматриваемая работа, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1071">;

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

<img width=«112» height=«35» src=«ref-1_657782976-355.coolpic» v:shapes="_x0000_i1072">;                                                                                        (2.6)

<img width=«152» height=«35» src=«ref-1_657783331-401.coolpic» v:shapes="_x0000_i1073">,                                                                                (2.7)

где           <img width=«53» height=«35» src=«ref-1_657783732-275.coolpic» v:shapes="_x0000_i1074"> – поздний срок окончания работы, исходящей из <img width=«11» height=«19» src=«ref-1_657773213-188.coolpic» v:shapes="_x0000_i1075">-го события и входящей в <img width=«15» height=«23» src=«ref-1_657774521-194.coolpic» v:shapes="_x0000_i1076">-е событие, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1077">;

<img width=«53» height=«35» src=«ref-1_657784602-274.coolpic» v:shapes="_x0000_i1078"> – поздний срок начала данной работы, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1079">;

<img width=«23» height=«29» src=«ref-1_657778332-210.coolpic» v:shapes="_x0000_i1080"> – длительность этой работы, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1081">;

<img width=«41» height=«33» src=«ref-1_657777669-256.coolpic» v:shapes="_x0000_i1082"> – позднее окончание события, в которое входит рассматриваемая работа, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1083">.

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

<img width=«485» height=«35» src=«ref-1_657785981-780.coolpic» v:shapes="_x0000_i1084">,             (2.8)

где           <img width=«44» height=«35» src=«ref-1_657786761-256.coolpic» v:shapes="_x0000_i1085"> – полный резерв времени работы, исходящей из <img width=«11» height=«19» src=«ref-1_657773213-188.coolpic» v:shapes="_x0000_i1086">-го события и входящей в <img width=«15» height=«23» src=«ref-1_657774521-194.coolpic» v:shapes="_x0000_i1087">-е событие, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1088">.

Свободный резерв времени некоторой работы – максимальное время, на ко­торое можно отсрочить её начало или увеличить её продолжительность при усло­вии, что все события наступают в свои ранние сроки:

<img width=«340» height=«35» src=«ref-1_657787612-622.coolpic» v:shapes="_x0000_i1089">,                                          (2.9)

где           <img width=«49» height=«35» src=«ref-1_657788234-259.coolpic» v:shapes="_x0000_i1090"> – свободный резерв времени работы, исходящей из <img width=«11» height=«19» src=«ref-1_657773213-188.coolpic» v:shapes="_x0000_i1091">-го собы­тия и входящей в <img width=«15» height=«23» src=«ref-1_657774521-194.coolpic» v:shapes="_x0000_i1092">-е событие, <img width=«27» height=«20» src=«ref-1_657749029-213.coolpic» v:shapes="_x0000_i1093">.

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

Как говорилось в предыдущем разделе, длительность критического пути легко найти из расчёта параметров сетевого графика. Теперь можно сказать, чему она равна, – она равна сроку свершения завершающего события сетевого графика и, соответственно, определяет длительность выполнения всех проектных работ. По­следнее заключается в том, что проектные работы не могут завершиться в срок, меньший, чем длительность критического пути, и в тоже время, если все проект­ные работы выполняются вовремя, то срок их завершения равен длительности критического пути.
    продолжение
--PAGE_BREAK--3       Обоснование рациональных методик поиска особых путей сетевых графиков
Обоснование рациональных методик поиска особых путей сетевого графика основано на смысле полного резерва времени работы, который показывает, на сколько можно отсрочить начало или увеличить продолжительность работы без изменения продолжительности всего проекта. Надо сказать, что этот смысл выте­кает из правил расчёта сетевого графика и давно известен, поэтому сейчас он не требуется в специальном рассмотрении. Важно другое – из смысла полного ре­зерва времени работы следует истинность следующего утверждения, на котором основаны некоторые, приводимые ниже доказательства, – полный резерв времени работы может появиться только за счёт существования другого более длительного пути, нежели путь, в состав которого входит рассматриваемая работа. Это утвер­ждение становится очевидным, если подумать – за счёт чего, у некоторой работы, может появиться возможность отсрочить начало её выполнения или увеличить её продолжительность без изменения срока свершения завершающего события сете­вого графика? Естественно, только за счёт того, что этот срок свершения опреде­ляется другим, более продолжительным путём.

Начнём с доказательства методики поиска критического пути сетевого гра­фика. Для этого рассмотрим ряд вспомогательных теорем.

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

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

Докажем это утверждение методом от противного.

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

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

Достаточность – Если все работы некоторого пути имеют нулевые полные резервы времени, то этот путь обязательно является критическим.

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

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

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

Докажем теорему методом от противного.

<img width=«664» height=«452» src=«ref-1_657789088-18193.coolpic» v:shapes="_x0000_s2379 _x0000_s1342 _x0000_s1343 _x0000_s1344 _x0000_s1345 _x0000_s1346 _x0000_s1347 _x0000_s1348 _x0000_s1349 _x0000_s1350 _x0000_s1351 _x0000_s1352 _x0000_s1353 _x0000_s1354 _x0000_s1355 _x0000_s1356 _x0000_s1357 _x0000_s1358 _x0000_s1359 _x0000_s1360 _x0000_s1361 _x0000_s1362 _x0000_s1363 _x0000_s1364 _x0000_s1365 _x0000_s1366 _x0000_s1367 _x0000_s1368 _x0000_s1369 _x0000_s1370 _x0000_s1371 _x0000_s1372 _x0000_s1373 _x0000_s1374 _x0000_s1375 _x0000_s1376 _x0000_s1377 _x0000_s1378 _x0000_s1379 _x0000_s1380 _x0000_s1381 _x0000_s1382 _x0000_s1383 _x0000_s1384 _x0000_s1385 _x0000_s1386 _x0000_s1387 _x0000_s1388 _x0000_s1389 _x0000_s1390 _x0000_s1391 _x0000_s1392 _x0000_s1393 _x0000_s1394 _x0000_s1395 _x0000_s1396">
Пусть для работы, входящеё в событие 2, полный резерв времени <img width=«77» height=«35» src=«ref-1_657807281-286.coolpic» v:shapes="_x0000_i1094">. Предположим противное – среди всех работ, исходящих из события 2, нет ни од­ной работы с нулевым полным резервом времени.

Для начала найдём, чему равен поздний срок свершения события 2. Он, в соответствии с формулой (2.2), определяется как минимальное время позднего на­чала работы среди всех работ, исходящих из рассматриваемого события. Пусть поздний срок свершения события 2 равен позднему началу работы, входящей, на­пример, в событие 4:

<img width=«145» height=«35» src=«ref-1_657807567-391.coolpic» v:shapes="_x0000_i1095">,

или, в соответствии с выражением (2.8) для полного резерва времени,

<img width=«168» height=«35» src=«ref-1_657807958-429.coolpic» v:shapes="_x0000_i1096">.                                                                             (3.1)

Теперь рассмотрим, какое может иметь значение полный резерв времени ра­боты, исходящей из события 1 и входящей в событие 2. В соответствии с форму­лой (2.8):

<img width=«221» height=«35» src=«ref-1_657808387-478.coolpic» v:shapes="_x0000_i1097">.                                                                  (3.2)

Из формулы (3.2) видно, что минимально возможное значение полного ре­зерва времени работы, исходящей из события 1 и входящей в событие 2, достига­ется тогда, когда величина <img width=«100» height=«35» src=«ref-1_657808865-332.coolpic» v:shapes="_x0000_i1098"> достигает своего максимального значения. Из правила определения раннего срока свершения события, задаваемого формулой (2.1), следует, что максимальное значение этой величины может быть равно только раннему сроку свершения события 2, когда ранний срок окончания рассматривае­мой работы самый большой из всех ранних сроков окончания работ, входящих в событие 2. Тогда, минимально возможное значение полного резерва времени ра­боты, исходящей из события 1 и входящей в событие 2 равно:

<img width=«165» height=«35» src=«ref-1_657809197-424.coolpic» v:shapes="_x0000_i1099">,

или, исходя из формулы (3.1):

<img width=«113» height=«35» src=«ref-1_657809621-334.coolpic» v:shapes="_x0000_i1100">.                                                                                        (3.3)

Поскольку мы предположили от противного, что среди всех исходящих из события 2 работ нет работ с нулевым полным резервом времени, то отсюда сразу вытекает, что и работа, исходящая из события 1 и входящая в событие 2, также не может иметь нулевой полный резерв времени, уж если его минимальное значение заведомо неравно нулю, в соответствии с полученным равенством (3.3). Последнее противоречит условию теоремы. Из этого противоречия следует то, что невоз­можна ситуация, когда при нулевом резерве времени работы, входящей в событие 2, все исходящие из этого события работы имели бы ненулевые резервы времени. Если бы это имело место, то в соответствии с приведённым доказательством, ра­бота, входящая в событие 2 также бы имела ненулевой полный резерв времени. Но ведь это не так по условию теоремы. Тогда для работ, исходящих из события 2 ос­таётся другая возможная ситуация – хотя бы одна из них имеет также нулевой полный резерв времени. Теорема доказана.

Из доказанных выше теорем, непосредственно, следует методика поиска критического пути,  приводимая ниже.

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

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

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

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

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

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

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

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

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

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

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

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

<img width=«663» height=«436» src=«ref-1_657809955-24135.coolpic» v:shapes="_x0000_s2380 _x0000_s1397 _x0000_s1398 _x0000_s1399 _x0000_s1400 _x0000_s1401 _x0000_s1402 _x0000_s1403 _x0000_s1404 _x0000_s1405 _x0000_s1406 _x0000_s1407 _x0000_s1408 _x0000_s1409 _x0000_s1410 _x0000_s1411 _x0000_s1412 _x0000_s1413 _x0000_s1414 _x0000_s1415 _x0000_s1416 _x0000_s1417 _x0000_s1418 _x0000_s1419 _x0000_s1420 _x0000_s1421 _x0000_s1422 _x0000_s1423 _x0000_s1424 _x0000_s1425 _x0000_s1426 _x0000_s1427 _x0000_s1428 _x0000_s1429 _x0000_s1430 _x0000_s1431 _x0000_s1432 _x0000_s1433 _x0000_s1434 _x0000_s1435 _x0000_s1436 _x0000_s1437 _x0000_s1438 _x0000_s1439 _x0000_s1440 _x0000_s1441 _x0000_s1442 _x0000_s1443 _x0000_s1444 _x0000_s1445 _x0000_s1446 _x0000_s1447 _x0000_s1448 _x0000_s1449 _x0000_s1450 _x0000_s1451 _x0000_s1452 _x0000_s1453 _x0000_s1454 _x0000_s1455 _x0000_s1456 _x0000_s1457 _x0000_s1458 _x0000_s1459 _x0000_s1460 _x0000_s1461 _x0000_s1462 _x0000_s1463 _x0000_s1464 _x0000_s1465 _x0000_s1466 _x0000_s1467 _x0000_s1468 _x0000_s1469 _x0000_s1470 _x0000_s1471 _x0000_s1472 _x0000_s1473 _x0000_s1474 _x0000_s1475 _x0000_s1476 _x0000_s1477 _x0000_s1478 _x0000_s1479 _x0000_s1480 _x0000_s1481 _x0000_s1482 _x0000_s1483">
Необходимо сказать, что можно поставить и решить общую задачу поиска пути заданной продолжительности. Но данная задача принципиаль­ной важности, при анализе сетевого графика, не несёт. Для анализа оптимально­сти сетевого гра­фика и осуществления его оптимизации, достаточно знать лишь, как  проходят особые пути, и какова их продолжительность. Ответы на эти вопросы и дают ра­циональные методики поиска особых путей, доказанные в этом разделе.

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

Наиболее удобный способ представления структуры сетевого графика в ма­шинной форме, основан на понятии матрицы смежностей <img width=«36» height=«29» src=«ref-1_657834090-238.coolpic» v:shapes="_x0000_i1101">. Пример данной матрицы для структуры сетевого графика на рисунке 2.1представлен на рисунке 4.1.

Матрица смежностей квадратная и имеет размерность <img width=«47» height=«20» src=«ref-1_657834328-243.coolpic» v:shapes="_x0000_i1102">, где <img width=«17» height=«20» src=«ref-1_657834571-205.coolpic» v:shapes="_x0000_i1103"> – число событий сетевого графика. Номера строк матрицы задаются номерами событий <img width=«23» height=«25» src=«ref-1_657834776-212.coolpic» v:shapes="_x0000_i1104">, из которых работы сетевого графика исходят, номера столбцов матрицы зада­ются номерами событий <img width=«25» height=«28» src=«ref-1_657834988-212.coolpic» v:shapes="_x0000_i1105">, в которые работы сетевого графика входят. На пере­сечении строки и столбца <img width=«68» height=«28» src=«ref-1_657835200-274.coolpic» v:shapes="_x0000_i1106">, в матрице смежностей, может быть только одно из двух значений: 0 или 1. Если <img width=«95» height=«28» src=«ref-1_657835474-292.coolpic» v:shapes="_x0000_i1107">, то это означает, что на сетевом гра­фике существует работа, исходящая из события с номером <img width=«11» height=«19» src=«ref-1_657773213-188.coolpic» v:shapes="_x0000_i1108"> и входящая в со­бытие с номером <img width=«15» height=«23» src=«ref-1_657774521-194.coolpic» v:shapes="_x0000_i1109">. Если <img width=«99» height=«28» src=«ref-1_657836148-299.coolpic» v:shapes="_x0000_i1110">, то такой работы на сетевом графике нет.

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

−       <img width=«670» height=«418» src=«ref-1_657836447-8255.coolpic» v:shapes="_x0000_s2382 _x0000_s1484 _x0000_s1485 _x0000_s1486 _x0000_s1487 _x0000_s1488 _x0000_s1489 _x0000_s1490 _x0000_s1491 _x0000_s1492 _x0000_s1493 _x0000_s1494 _x0000_s1495 _x0000_s1496 _x0000_s1497 _x0000_s1498 _x0000_s1499 _x0000_s1500 _x0000_s1501 _x0000_s1502 _x0000_s1503 _x0000_s1504 _x0000_s1505 _x0000_s1506 _x0000_s1507 _x0000_s1509 _x0000_s1510 _x0000_s1511 _x0000_s1512 _x0000_s1513 _x0000_s1514 _x0000_s1515 _x0000_s1516 _x0000_s1517 _x0000_s1518 _x0000_s1519 _x0000_s1520 _x0000_s1521 _x0000_s1522 _x0000_s1523 _x0000_s1524 _x0000_s1525 _x0000_s1526 _x0000_s1527 _x0000_s1528 _x0000_s1529 _x0000_s1530 _x0000_s1531 _x0000_s1532 _x0000_s1533 _x0000_s1534 _x0000_s1535 _x0000_s1536 _x0000_s1537 _x0000_s1538 _x0000_s1539 _x0000_s1540 _x0000_s1541 _x0000_s1542 _x0000_s1543 _x0000_s1544 _x0000_s1545 _x0000_s1546 _x0000_s1547 _x0000_s1548 _x0000_s1549">
Событиям присваиваются номера с таким расчётом, что старший номер соответствует более позднему по времени событию. То есть, если рассмотреть не­которое событие и все входящие в него работы, то номер этого события должен быть больше номеров всех событий, из которых эти работы исходят. В этом случае первая строка и первый столбец матрицы смежностей соответствует начальному событию сетевого графика <img width=«25» height=«25» src=«ref-1_657844702-209.coolpic» v:shapes="_x0000_i1111">, а последние строка и столбец – завершающему со­бытию сетевого графика <img width=«44» height=«29» src=«ref-1_657844911-235.coolpic» v:shapes="_x0000_i1112">, где <img width=«17» height=«20» src=«ref-1_657834571-205.coolpic» v:shapes="_x0000_i1113"> – число всех событий в сетевом графике.

−       Два события сетевого графика может соединять только одна работа. Если все же имеет место факт соединения двух событий несколькими работами, то, для выполнения указанного правила, необходимо ввести дополнительные события,  разрывающие лишние работы и дополняющие их фиктивными работами с нулевой длительностью (см. пример на рис. 4.2). Дополнительные события также должны иметь свои уникальные, в сетевом графике, номера, присвоенные им в соответст­вии с первым правилом.

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

−       <img width=«656» height=«318» src=«ref-1_657845351-11048.coolpic» v:shapes="_x0000_s2383 _x0000_s1553 _x0000_s1555 _x0000_s1557 _x0000_s1558 _x0000_s1561 _x0000_s1563 _x0000_s1565 _x0000_s1573 _x0000_s1574 _x0000_s1577 _x0000_s1578 _x0000_s1579 _x0000_s1580 _x0000_s1581 _x0000_s1582 _x0000_s1583 _x0000_s1584 _x0000_s1585 _x0000_s1586 _x0000_s1587 _x0000_s1588 _x0000_s1589 _x0000_s1590">
Если задаться некоторым номером события <img width=«23» height=«25» src=«ref-1_657834776-212.coolpic» v:shapes="_x0000_i1114">, то единицы в соответст­вующей строке укажут на номера событий <img width=«25» height=«28» src=«ref-1_657834988-212.coolpic» v:shapes="_x0000_i1115">, с которыми событие <img width=«21» height=«25» src=«ref-1_657856823-211.coolpic» v:shapes="_x0000_i1116"> соединено, исходящими из него работами. Это свойство следует из правила построения мат­рицы смежностей.

−       Если задаться некоторым номером события <img width=«25» height=«28» src=«ref-1_657834988-212.coolpic» v:shapes="_x0000_i1117">, то единицы в соответст­вующем столбце укажут на номера событий <img width=«23» height=«25» src=«ref-1_657834776-212.coolpic» v:shapes="_x0000_i1118">, с которыми событие <img width=«24» height=«28» src=«ref-1_657857458-213.coolpic» v:shapes="_x0000_i1119"> соеди­нено, входящими в него работами. Это свойство, также, следует из правила по­строения матрицы смежностей.

−       Если некоторое событие <img width=«23» height=«25» src=«ref-1_657834776-212.coolpic» v:shapes="_x0000_i1120"> указывает единицами в соответствующей строке матрицы смежностей на соединённые с ним события <img width=«25» height=«28» src=«ref-1_657834988-212.coolpic» v:shapes="_x0000_i1121">, то номера этих событий <img width=«15» height=«23» src=«ref-1_657774521-194.coolpic» v:shapes="_x0000_i1122"> могут быть только больше номера <img width=«11» height=«19» src=«ref-1_657773213-188.coolpic» v:shapes="_x0000_i1123">, что ясно из правила присвоения номеров событиям сетевого графика. Из этого свойства следует, что матрица смежностей носит диагональный характер, то есть, единицы в матрице смежно­стей могут присутствовать только в верхней диагональной части матрицы (см. рис. 4.1).

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

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




<img width=«599» height=«536» src=«ref-1_657858477-13924.coolpic» v:shapes="_x0000_s2384 _x0000_s1591 _x0000_s1592 _x0000_s1593 _x0000_s1594 _x0000_s1595 _x0000_s1596 _x0000_s1597 _x0000_s1598 _x0000_s1599 _x0000_s1600 _x0000_s1602 _x0000_s1603 _x0000_s1604 _x0000_s1605 _x0000_s1606 _x0000_s1607 _x0000_s1608 _x0000_s1609 _x0000_s1610 _x0000_s1612 _x0000_s1613 _x0000_s1614 _x0000_s1615 _x0000_s1616 _x0000_s1617 _x0000_s1618 _x0000_s1619 _x0000_s1620 _x0000_s1621 _x0000_s1622 _x0000_s1623 _x0000_s1625 _x0000_s1626 _x0000_s1627 _x0000_s1628 _x0000_s1629 _x0000_s1630 _x0000_s1631 _x0000_s1632 _x0000_s1633 _x0000_s1634 _x0000_s1635 _x0000_s1636 _x0000_s1639 _x0000_s1640 _x0000_s1642 _x0000_s1643 _x0000_s1644 _x0000_s1645 _x0000_s1646 _x0000_s1647 _x0000_s1648 _x0000_s1649 _x0000_s1650 _x0000_s1651 _x0000_s1652 _x0000_s1653 _x0000_s1654">
Блок-схема 4.1– Алгоритм тестирования матрицы смежностей



    продолжение
--PAGE_BREAK--