<<
>>

Б. Оптимизация комплекса операций по стоимости при фиксированном сроке выполнения проекта

Рассмотрим частный случай оптимизации комплекса операций по стоимости (затратам). Будем предполагать, что затраты на выполнение отдельных операций находятся в обратной зависимости от продолжительности их выполнения.

Коэффициент дополнительных затрат (КДЗ) этой зависимости для операции вычисляется по формуле

, (3.7)

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

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

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

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

Рассмотрим более общий случай, когда .

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

(3.8)

где . Учитывая, что величины известны, раскроем скобки в правой части (3.8) и обозначим через сумму . В результате получим .

Здесь время выполнения операции равно разности между временем ее окончания и временем начала .

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

.

На неизвестные величины задачи налагаются следующие ограничения:

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

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

;

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

; - номер завершающего события;

переменные должны быть неотрицательными:

; для всех , при этом , .

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

Пример 2.

Исходные данные комплекса операций, представленного сетевым графиком (рис. 3.8), приведены в Табл. 3.2. Требуется оптимизировать сетевой график по стоимости при .

Рис. 3.8. Сетевой график примера 2.

Таблица 3.2.

Параметры Операции
(1,2) (1,3) (2,3) (2,5) (3,4) (3,5) (4,5)
9 10 0 3 4 5 8
11 15 0 5 7 8 10
2 5 - 5 4 10 3
20 40 - 30 45 50 25

Решение

Запишем , для всех , принадлежащих сетевому графику:

; ; ;
; ; ;
;

При записи функции принято, что .

Так как при параметрах меньше , то оптимизация возможна за счет всех операций сетевого графика. Запишем ограничения по времени выполнения операций:

Ограничения по предшествованию в выполнении операций:

Все неизвестные должны быть неотрицательными, т.е. для всех операций сети.

Проведем решение задачи в Excel. Введем данные на рабочий лист в соответствии с Рис. 3.9.

Для расчетных значений переменных X1-X12 отведем диапазон ячеек A5:L5. Далее, введем функции-ограничения и формулу для целевой функции в ячейки в соответствии с приводимой ниже таблицей.

Рис. 3.9. Форма для ввода данных примера 2.

Ячейка Формула Ячейка Формула
C6 =D5-C5 C16 =C5-A5
E6 =F5-E5 C17 =E5-A5
G6 =H5-G5 C18 =I5-B5
I6 =J5-I5 C19 =I5-D5
K6 =L5-K5 C20 =G5-B5
B12 =F5 C21 =G5-D5
B13 =J5 C22 =K5-H5
B14 =L5
J19

(целевая функция)

= -2*A5-5*B5-5*F5+5*E5-4*H5+4*G5-10*J5+10*I5-3*L5+3*K5+430

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

$A$5=$E$16
$A$5>=$A$8 $E$6>=$E$8 $I$5>=10 $C$17>=$E$17
$B$5=$G$8 $J$5>=15 $C$18>=$E$18
$B$5>=$B$8 $G$5>=10 $I$6=$E$19
$C$5>=9 $G$6=$I$8 $C$20>=$E$20
$C$6>=$C$8 $F$5=9 $J$5=$K$8 $C$22>=$E$22
$E$5>=9 $L$5
<< | >>

Еще по теме Б. Оптимизация комплекса операций по стоимости при фиксированном сроке выполнения проекта: