Параметры работ сетевого графика.

Шифр работы (i,j)	tij	t рн(i,j)	t ро(i,j)	t пн(i,j)	t по(i,j)	R П(i,j)	R 1(i,j)	R с(i,j)	R н(i,j)
1-2
1-3
2-5
2-3
3-4
4-5
4-6
5-6

 

Проверим правильность табличных расчётов:

L _кр = (1-3-4-5-6) → т.к. на критическом пути лежат начальные события 1,3,4,5,6, то должно выполняться равенство R _П(1,2) = R ₁(1,2); R _П(1,3) = = R ₁(1,3); R _П(3,4) = R ₁(3,4); R _П(4,5) = R ₁(4,5); R _П(4,6) = R ₁(4,6); R _П(5,6) = R ₁(5,6).

Если на критическом пути лежит конечное событие, то должно выполняться равенство R _П(1,3) = R _с(1,3); R _П(2,5) = R _с(2,5); R _П(2,3) = R _с(2,3); R _П(3,4)= = R _с(3,4); R _П(4,5) = R _с(4,5); R _П(4,6) = R _с(4,6); R _П(5,6) = R _с(5,6).

Если на критическом пути лежат начальное и конечное события, то выполняется следующее равенство:

R _П(1,3) = R ₁(1,3) = R _с(1,3) = R _н(1,3); R _П(3,4) = R ₁(3,4) = R _с(3,4) = R _н(3,4);

R _П(4,5) = R ₁(4,5) = R _с(4,5) = R _н(4,5); R _П(5,6) = R ₁(5,6) = R _с(5,6) = R _н(5,6).

В представленном примере все перечисленные условия выполняются, следовательно, расчёты произведены правильно. Для небольших проектов удобным дополнением к сетевому графику является линейный график или график Ганта. (рис.3.8).

На линейном графике каждая работа (i,j) изображается в привязке к оси времени 0t горизонтальным отрезком, длина которого в соответствующем масштабе равна продолжительности работы t_ij. Начало каждой работы совпадает с ранним сроком свершения её начального события. Работы изображаются в той же последовательности, что и на сети.

 

Анализ сетевой модели

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

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

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

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

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

Если совпадающую с критическим путем величину отрезка пути обозначить как t^, (L _кр ), длину критического пути – t(L _кр ), а протяженность максимального из некритических путей, проходящего через данную работу, – t(L _max ), то коэффициент напряженности работ

К

Формулу можно выразить через резерв времени:

К_Н

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

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

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

Резервная зона – это совокупность работ, имеющих значение Кн _ij значительно меньше единицы.

Следующим этапом анализа является расчет вероятностных характеристик сетевых моделей.

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

Р(Т≥Т_Д)= Ф (и)= Ф .

 

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

Здесь – дисперсия i -й работы критического пути; п – число работ критического пути.

Для величины Р(Т ≥ Т _Д ) устанавливаются вполне определенные пределы, именуемые границами допустимого риска. По данным практики выполнения работ по графикам, при Р(Т ≥ Т _Д ) > 0,65 можно утверждать, что на работах критического пути имеются из­быточные ресурсы, следовательно, общая продолжительность работ может быть сокращена. При Р(Т ≥ Т _Д ) < 0,35 опасность срыва заданного срока выполнения работ очень велика и необходимо повторное планирование с перераспределением ресурсов.

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

а) перераспределения ресурсов как временных, так и других;

б) интенсификация выполнения работ критического пути;

в) изменений в характере комплекса работ.

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

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

 

Задачи оптимизации на сетях

Сетевые оптимизационные модели обычно являются частными случаями моделей линейного программирования. Чаще всего они используются в задачах распределения и расписаний. Модели этого класса имеют экономический смысл для хозяйственной деятельности. Достоинством сетей является то, что они идентичны структуре реальных операционных процессов. Кроме того, математическая структура сетей хорошо описывает операционные модели. Это и определяет широкое применение сетевых моделей. Рассмотрим некоторые из них.

Модель транспортной задачи является одним из примеров оптимизации на линейных сетях. Она имеет вид:

максимизировать

при ограничениях

j= (спрос),

i= (наличные ресурсы),

x_ij= 1, j=

Мы рассмотрели решение этой задачи симплекс-методом (методом потенциалов). Однако модель рассмотрена для одного продукта. Для многопродуктных задач спрос на всю номенклатуру продуктов необходимо привести к агрегированному продукту (например, все продукты выразить в тоннах) и к условной стоимости c_ij. Кроме того, канал поставки может быть с ограничением на объем перевозок x_ij ^огр, то есть канал имеет определенную пропускную способ­ность, так что x_{ij <} x_ij ^огр.

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

В некоторых задачах величина s_i – наличные ресурсы – являет­ся переменной. При таких условиях транспортная модель оказыва­ется частным случаем более общей задачи линейного программирования.

Другое важное обобщение классической транспортной задачи связано с учетом возможностей доставки ресурсов от поставщика i к потребителю j по маршруту, проходящему через промежуточный пункт. Этот случай часто возникает в системе товародвижения от предприятия к оптовому покупателю и далее к потребителю.

Модель назначений можно кратко сформулировать следующим образом. Задано n работ, каждую из которых может выполнить любой из m исполнителей. Стоимость выполнения работы i исполнителем j равна c_ij. Нужно распределить исполнителей по работам, то есть назначить одного исполнителя на каждую работу, таким образом, чтобы минимизировать общие затраты.

Математическая модель будет выглядеть следующим образом:

 

минимизировать

при ограничениях

i=

j=

x_ij= 0 при 1 для всех i и j.

Отметим, что модель назначений является частным случаем классической транспортной задачи, в которой s_i=D= 1.

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

Математическая постановка задачи имеет следующий вид:

минимизировать

при ограничениях

для всех (i, j) сети,

где c_ij может быть расстоянием от с, или стоимостью переезда из узла i в узел j; источник – начальный узел, сток – конечный узел пути.

Задача коммивояжера относится к ситуации: агент по сбыту собирается посетить каждый из городов п по одному разу, выехав из города i и вернувшись в него же. Расстояние между городами i и j равно c_ij. Каков кратчайший путь агента?

Пример:

Минимизировать

где i= j=

при ограничениях

(отъезд),

j= (прибытие),

где x_ij – неотрицательные целые решения при всех i и j, решение есть цикл.

Полученное решение может содержать два и более несвязанных цикла. То есть можно получить, например, два независимых маршрута, один из которых проходит через города 1, 2,..., 3, а другой – через 4, 5,..., п. Требование о том, чтобы решение давало один цикл, значительно усложняет эту задачу, которая является комбинаторной.

Задача планирования трудовых ресурсов возникает, когда требуется заключить контракт на выполнение определенного объема работ.

Для построения математической модели, с помощью которой можно получить оптимальный план выполнения работ от начала 1 до конца п, обозначим: x_ij – число бригад, приступающих к работе в начале периода i и заканчивающих работу в начале периода j (где 1 i < j n), а c_ij ≥ 0 – соответствующие общие текущие затраты на содержание этих бригад. Предположим, что величина c_ij возрастает, если увеличивается период использования рабочей силы, то есть

c_ij c_nk при n i < j k.

Примем далее, что R_k – число бригад, действительно требую­щихся для выполнения заданного объема работ в течение периода k, где k=

При этих условиях ограничения задачи выража­ются следующим образом:

k=

Минимизация целевой функции имеет вид:

min.

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