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

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

, (3.7)

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

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

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

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

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

(3.8)

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

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

.

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

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

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

;

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

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

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

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

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

Пример 2.

Исходные данные комплекса операций, представленного сетевым графиком (рис.3.8), приведены в Табл.3.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<=$A$10	$E$6<=$E$10	$H$5>=14	$C$16>=$E$16
$A$5>=$A$8	$E$6>=$E$8	$I$5>=10	$C$17>=$E$17
$B$5<=$B$10	$G$6>=$G$8	$J$5>=15	$C$18>=$E$18
$B$5>=$B$8	$G$5>=10	$I$6<=$I$10	$C$19>=$E$19
$C$5>=9	$G$6<=$G$10	$I$6>=$I$8	$C$20>=$E$20
$C$6>=$C$8	$F$5<=34	$K$6<=$K$10	$C$21>=$E$21
$D$5>=9	$J$5<=34	$K$6>=$K$8	$C$22>=$E$22
$E$5>=9	$L$5<=34

В результате решения получим ответ:

Таким образом, при заданном сроке выполнения проекта минимальная стоимость его реализации составляет 170 д.е.