Оптимизация графика с использованием линейного программирования

Эффективность использования симплекс-метода при оптимизации графика работ можно повысить, если сократить размерность системы ограничений и число итераций поиска оптимального решения. Этого можно достичь, если в качестве оптимизируемой переменной использовать Dt_ij - приращения длительностей работ при переходе от «срочного» к оптимальному плану реализация проекта.

Пусть имеется «срочный» план с критическим путем S_ср<=T. В случае S_ср>T задача неразрешима, так как «срочный» план обеспечивает минимально возможные сроки выполнения проекта.

Оптимизируемая переменная Dt_ij представляет разность между длительностью работы и минимально допустимым сроком выполнения d_ij:

Dt_ij= t_ij - d_ij (12.4)

В исходном «срочном» плане Dt_ij=0 для всех (i;j) ÎQ. Увеличение Dt_ij снижает затраты от уровня «срочного» плана, поэтому в качестве критерия оптимальности можно взять максимум суммарной экономии:

(12.5)