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

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

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

Качественный характер зависимости затрат от длительности выполнения операции можно представить следующей кривой (рис.12.1).

Рис.12.1 Изменение затрат от длительности выполнения операций

Такой характер кривой объясняется тем, что затраты на выполнение любой производственной операции складываются из заработной платы повременно оплачиваемого персонала и других цеховых расходов, растущих прямо пропорционально времени работ, а также из заработной платы сдельно оплачиваемых рабочих, стоимости материалов и других затрат, зависящих только от объема работ. Эта вторая группа затрат может возрастать при ускоренном выполнении работ за счет привлечения избыточного числа работников, использования дополнительного оборудования и т.д. В результате для каждой операции (i,j) проекта существует срок выполнения D_ij, при котором затраты на ее выполнение минимальны и равны C_ijmin.

Суммарные затраты на весь комплекс работ складываются из затрат на отдельные операции, поэтому при отсутствии ограничений на длительности операций и срок выполнения проекта оптимальным будет график с t_ij=D_ij, для всех (i,j)ÎQ, где Q - множество работ сетевой модели.

В дальнейшем такой график будет называться «нормальным»", так как он соответствует обычным срокам выполнения операций. Если же сократить длительность выполнения операций до значения d_ij, то это приведёт к сокращению срока реализация проекта, но увеличит затраты. Такой график будет называться «срочным».

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

(12.1)

, для всех (i,j)ÎQ (12.2)

(12.3)

где Z - дополнительные затраты, связанные о ускорением сроков реализации проекта по сравнению с «нормальным» графиком работы;

Q - множество работ сетевой модели;

d - удельные затраты на сокращение длительности выполнения операции (i,j) на одну единицу;

d_ij, D_ij - нижний и верхний пределы изменения длительности работы (i,j), выбранные по организационным и технологическим соображениям, так что при t_ij=D_ij затраты на выполнение работы (i,j) – минимальны;

L_k – k-й полный путь сетевой модели (соединяющий исходное и завершающее события);

r - число полных путей модели;

Т - установленный срок реализации проекта.

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