Оптимизация проекта по времени

Рассмотрим две постановкизадачи оптимизации проекта по времени с использованием дополнительных средств.

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

Пусть задан сетевой график выполнения проекта, где Е – множество событий, а - множество работ.

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

Составим модель в предположении, что требуется определить количество дополнительных средств , которое необходимо привлечь для выполнения работ , а также время начала и окончания этих работ, чтобы суммарные дополнительные затраты были минимальными, а проект был выполнен в срок .

Так как неизвестными величинами являются , , , а целью задачи – минимизация времени выполнения проекта через дополнительно привлекаемые средства, то математическая модель будет иметь вид:

, (15.1)

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

(15.2)

(15.3)

(15.4)

(15.5)

(15.6)

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

Критический путь L_кр в данной задаче является функцией от объемов дополнительно вкладываемых средств .

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

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

Требуется определить время начала и окончания каждой работы, а также количество дополнительных средств , которое необходимо привлечь для выполнения работ , чтобы суммарные дополнительные затраты не превышали заданной величины В. Математическая модель в этом случае имеет вид:

(15.7)

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

(15.8)

(15.9)

(15.10)

(15.11)

(15.12)

Смысл ограничений (15.9) – (15.12) такой же, как и в предыдущей модели. Если в последнее событие сети входят несколько работ, то необходимо добавить фиктивную работу время выполнения которой равно нулю, т. е. . Тогда целевая функция запишется в виде: .

Пример 15.1. Пусть задан сетевой график, изображенный на рисунке 15.1. Критический путь L = 1-2-5, t_кр=90. Директивный срок выполнения проекта составляет 80 ед. Заданы технологические коэффициенты использования дополнительных средств , которое необходимо привлечь для выполнения работы (i, j): , предполагая, что зависимости продолжительностей работ от вложенных средств описываются линейной функцией

Рисунок 15.1

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

Решение. Математическая модель задачи запишется в виде:

требуется найти количество дополнительных средств , при которых целевая функция

достигает минимального значения, и которые удовлетворяют системе ограничений:

- время завершения проекта не должно превышать директивное время:

;

- время выполнения каждой работы должно быть не меньше минимального времени:

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

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

;

- условия неотрицательности неизвестных: для всех дуг сетевого графика.

Построенная математическая модель является линейной, содержит 17 неизвестных и 20 ограничений, может быть решена симплексным методом на компьютере.

Пример 15.2. Пусть задан сетевой график, изображенный на рисунке 15.2.

Рисунок 15.2

Критический путь L=1-3-5-6-7, = 23. Задан директивный срок выполнения проекта равный: . Для каждой работы известны продолжительности ее выполнения t_ij и минимально возможное время ее выполнения d_ij: d₁₂=4, d₁₃=2, d₁₄=8, d₂₅=5, d₃₅=9, d₄₆=7, d₅₆=5, d₆₇=2. Заданы технологические коэффициенты k_ij использования дополнительных средств: k₁₂=0, 1; k₁₃=0, 5; k₁₄=0, 1; k₂₅=0, 3; k₃₅=0, 2; k₄₆=0, 5, k₅₆=0, 25, k₆₇=0, 2.

Требуется определить:

1) количество дополнительных средств , которое необходимо вложить в работы , чтобы их сумма была минимальной;

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

3) продолжительность выполнения каждой работы была бы не меньше заданной величины , в предположении, что продолжительность выполнения работ линейно зависит от дополнительно вложенных средств и выражается соотношением: .

Решение. Поскольку - дополнительные средства, которые необходимо вложить в работы , то целевая функция, определяющая эту сумму, должна стремиться к минимуму:

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

.

2) Условия требующие выполнения каждой работы за время не меньше максимально возможного времени:

3) Условия, определяющие продолжительность работ от вложенных в них средств:

4) Условия, определяющие своевременность выполнения всех предшествующих работ:

5)Условия неотрицательности неизвестных: для всех дуг сетевого графика.

Решив задачу симплексным методом на ЭВМ, получим:

Пример 15.3. Проект представлен сетевым графиком, изображенным на рисунке 15.3.

Рисунок 15.3

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

Требуется построить математическую модель для определения времени начала и окончания выполнения работ и количества средств, вкладываемых в каждую работу, чтобы время выполнения проекта было минимальным, а сумма вложенных средств не превышала 15 ден.ед.

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

1) Сумма вложенных средств не должна превышать их наличного количества:

2) Время выполнения каждой работы должно быть не меньше минимального времени:

3) Зависимость продолжительностей выполнения работ от вложенных средств удовлетворяет равенствам:

; ; ; ; ; ; .

4) Время выполнения каждой работы должно быть не меньше времени окончания непосредственно предшествующей ей работы:

5) Переменные величины должны быть неотрицательными:

для всех дуг графика.

Сформулированная линейная математическая модель содержит 20 неизвестных и 34 ограничений, может быть решена симплексным методом на ЭВМ.