Оптимизация сетевого графика — процесс улучшения организации выполнения комплекса работ, с учетом срока его выполнения. Проводится с целью сокращения длины критического пути, выравнивания коэффициентов напряженности работ, рационального использования ресурсов. Задачи оптимизации сетевого графика возникают также при стремлении минимизировать стоимость всего комплекса работ (всего проекта) за счет увеличения продолжительности выполнения некоторых работ при заданном времени осуществления проекта.
К оптимизационным относятся также задачи минимизации времени выполнения проекта при заданной его стоимости. Комплексная оптимизация — нахождение оптимального соотношения величин стоимости и сроков выполнения проекта в зависимости от конкретных целей, ставящихся при его реализации.
Обычно предполагается, что прямые затраты с() на выполнение каждой работы (Рi, Рj) убывают с возрастанием продолжительности tij ее выполнения.
В качестве простейшего примера рассмотрим задачу минимизации стоимости проекта при фиксированной его продолжительности.
Задача построения оптимального безрезервного плана.
Пусть для данного проекта с заданными продолжительностями tij=dij выполнения работ (Рi Рj)вычислены минимальные и максимальные времена Tj(0)и Tj(1) наступления событий Рj, и определены критические и некритические работы. Пусть, кроме того, зависимость стоимости сij прямых затрат на выполнение каждой работы (Рi, Рj) от ее продолжительности tij задается формулой:
(линейный вариант)
или
(выпуклый вариант).
Известно, что лишь для некритических работ существуют резервы времени. Предполагается, что по характеру некритической работы допустимо увеличение продолжительности ее выполнения за счет использования этого резерва времени, это уменьшает ее стоимость.
Возникает задача: при найденном критическом времени использовать резервы для некритических работ так, чтобы получить оптимальный план, т.е. план, минимизирующий стоимость всего комплекса работ.
Для математической формулировки задачи выясним предварительно некоторые особенности оптимального плана.
В оптимальном плане продолжительность каждой работы должна достигать наибольшего возможного значения, т.е. каждая работа должна стать критической. Поэтому, считая неизвестными времена Tj наступления событий Рj (j=0, 1,..., n), заключаем, что в оптимальном плане продолжительность tij каждой работы (Рi, Рj) должна быть равной разности Тj–Тi.
Так как мы рассматриваем задачу отыскания оптимального плана при заранее найденном критическом времени и критических путях, то времена наступления событий, лежащих на известных нам критических путях, фиксированы. Следовательно, мы имеем право также считать фиксированными и продолжительности работ (Pi, Рj), оба конца Рi и Рj которых лежат на критических путях.
Множество событий Рj лежащих на критических путях, обозначим через К (очевидно, Р0ÎК, РnÎК), а множество работ (Рi, Рj), у которых по крайней мере один конец не принадлежит множеству К (не лежит ни на одном критическом пути), обозначим через R.
Теперь приведенная выше задача может быть сформулирована так: найти минимум функции
, где (аij³0, bij>0) (линейный вариант)
или функции
, где (аij>0) (выпуклый вариант)
при ограничениях
Тj–Тi³dij для всех работ (Рi, Рj)ÎR,
для всех событий PjÎК
dij — жесткое ограничение продолжительности работы (предполагается, что все dij строго положительны).
Предполагается, что при заданных продолжительностях dij выполнения работ (Рi, Рj) вычислено критическое время Ткp проекта и найдены все критические пути. Поэтому в рассматриваемой задаче оптимальный план является минимальным по стоимости лишь среди всех планов, выполняемых за время Ткр, т.е. выполняемых за минимально допустимое для этого проекта время. Минимальная стоимость проекта снизится, если удлинить время Т его выполнения, так как тогда возможно увеличение продолжительности любой работы. Если время Т выполнения проекта больше, чем Ткp, то оптимальный план ищется во множестве планов, более широком, чем в рассмотренной выше задаче (когда Т=Ткр), и стоимость оптимального плана будет меньше, чем при Т=Ткр.
, где (аij³0, bij>0) (линейный вариант)
, где (аij>0) (выпуклый вариант)
для всех событий PjÎК