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

, (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 |
При решении данной задачи наибольшую сложность представляет ввод ограничений на переменные, число которых достаточно велико. Вызовем Поиск решения и введем следующий набор ограничений