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

Сокращение времени завершения проекта, как правило, связано с привлечением дополнительных средств (количес­тво рабочих, сверхурочные работы). Рассмотрим два примера задачи оптимизации проекта по времени с при­влечением дополнительных средств.

Постановка задачи 1. Для сокращения времени выполнения проекта выделяется некоторая сумма дополнительных средств В. Задан сетевой график выполнения проекта, продолжительность каждой работы равна t_ij. Известно, что вложение дополнительных средств х_ij в работу (i,j) сокращает время ее выполнения от t до t'_ij, причем эта зависимость выражается как t'_ij ⁼ f_ij(x_ij) £ t_ij (f_ij — известные функции). Для каждой работы существует минимально возможное время ее выполнения d_ij.

Если предположить, что продолжительность выполнения ра­бот линейно зависит от дополнительно вложенных средств и выражается соотношением t'_ij = t_ij - k_ij x_ij , где k_ij — технологические коэффициенты использования дополнитель­ных средств, то будем иметь задачу линейного программирования.

Требуется определить время начала t^H_ij и окончания t°_ij вы­полнения работ, а также количество дополнительных средств х_ij, которые необходимо вложить в работы (i,j), чтобы общее время выполнения проекта было минимальным, сумма вложенных дополнительных средств не превышала величины В, время выполнения каждой работы было не меньше минимально возможного времени.

Математически условия задачи можно записать следую­щим образом:

t_кр = t^o _n-1,n (min)                                                          (2.15)

£ B;                                                       (2.16)

t°_ij - t^H_ij³ d_ij ,                                                         (2.17)

t°_ij - t^H_ij = f_ij ,                                                            (2.18)

t^H_rj ³ t°_ir ,                                                                (2.19)

t°_ij ³ 0, t^H_ij ³ 0.                                                       (2.20)

Выражение (2.15) – целевая функция. Ограничение (2.16) определяет сумму вложенных допол­нительных средств: она не должна превышать величины В. Ограничения (2.17) показывают, что продолжительность каждой работы должна быть не менее минимально возмож­ной ее продолжительности. Ограничения-равенства (2.18) показывают зависимость продолжительности каждой работы от вложенных в нее дополнительных средств. Ограничения (2.19) обеспечивают выполнение условий предшествования работ в соответствии с топологией сети: время начала выпол­нения каждой работы должно быть не меньше времени окон­чания непосредственно предшествующих ей работ. Ограничение (2.20) — условие неотрицательности.

Если в последнее событие сети n входят сразу несколько работ, то необходимо добавить фиктивную работу (n,n+1), время выполнения которой равно нулю и до­бавить ограничение (t°_n,n+1 - t^H_n,n+1 = 0) в (2.17).

Постановка задачи 2. Пусть задан срок выполнения проекта tо, а расчетное время t_кр³to. В этом случае оптимизация комплекса работ сводится к сокращению продолжительности критического пути. Задача заключается в определении вели­чины дополнительных вложений x_ij в отдельные работы про­екта с тем, чтобы общий срок его выполнения не превышал заданной величины to, а суммарный расход дополнительных средств был минимальным. Время выполнения каждой рабо­ты должно быть не меньше минимально возможного времени d_ij.

Математическая запись этой задачи:

F(x)=  (min)

t^o _n-1,n £ to,

t°_ij - t^H_ij³ d_ij ,

t°_ij - t^H_ij = f_ij ,

t^H_rj ³ t°_ir ,

t°_ij ³ 0, t^H_ij ³ 0.

Смысл ограничений аналогичен соответствующим огра­ничениям постановки задачи 1.

В каждом варианте в сетевой график добавляется еще одна работа.

При оптимизации графика рекомендуется построить таблицу вида

В таблице заполняются столбцы 1-4. В столбцы 8-9 записываются формулы. В каждом варианте в ячейке в конце столбца xij рассчитывается сумма xij.

Задача решается при помощи функцииСервис -«Поиск решения».

В поле «Установить целевую ячейку» команды «Поиск решения» выделите ячейку со значением целевой функции модели (это будет или ячейка с суммой xij или ячейка t₀(n-1,n), т.е. время окончания последней работы). Чтобы минимизироватьзначение целевой ячейки, установите соответствующее положение переключателя.

В поле «Изменяя ячейки» введите адреса переменных модели, выделяя блок этих ячеек (во всех вариантах это будут столбцы t_н(ij), t₀(ij), xij).

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

tо_ij - tн_ij³ d_ij ,                         

tо_ij - tн_ij = tij-kij*xij,                                                           

tн_rj ³ tо_ir  

будут одинаковы, только в одних вариантах добавится ограничение t^o _n-1,n £ to, где to берется по варианту (ограничение на время), а в других - это будет ограничение £ B, где В берется по варианту (ограничение на затраты).

Чтобы ввести ограничение и приступить к набору нового, нажмите кнопку Добавить, а чтобы вернуться в диалоговое окно Поиск решения, нажмите кнопку OK.

В окне Параметры поиска решения для решения линейных задач надо установить флажки Линейная модель и Неотрицательные значения.  

Нажмем кнопку OK и вернемся в окно команды Поиск решения. Затем нажмем кнопку Выполнить, и, если все сделано правильно, то в таблице данных получим результаты решения задачи.

Пример.

Рис.2.1.Сетевой график схарактеристиками событий

1.Рассчитаем характеристики событий.Для наглядности каждое событие сетевого графика разделено на 4 сектора. Верхний сектор соответствует номеру события, в левом секторе записан ранний срок t_p(i) наступления события i, в правом – поздний срок t_п(i) наступления события i, в нижнем секторе представлен резерв времени R(i) события i. Эти же характеристики представлены в таблице, приведенной ниже.

Анализ таблицы и сетевого графика показывает, что критический путь имеет вид (1-2-5-6-7), а его длина равна t_кр=16.

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

Все расчеты сведены в табл.3.2.(столбцы 2-9)

Таблица 3.2.

Анализ таблицы и сетевого графика показывает, что критический путь имеет вид (1-2-5-6-7), а его длина равна t_кр=16.

3. После нахождения критического пути (1-2-5-6-7) длины 16 перейдем к определению  коэффициентов напряженности работ. Рассмотрим работу (3,5) и найдем все полные пути, проходящие через эту работу, и соответствующие им длины:

L₁: 1-2-3-5-7;           t(L₁)=12 ;

L₂: 1-3-5-7;              t(L₂)=12 ;

L₃: 1-3-5-6-7;           t(L₃)=14 ;

L₄: 1-2-3-5-6-7;        t(L₄)=14 .

Через работу (3,5) проходит два максимальных пути длины 14. Выберем второй из них. Тогда t^'_кр=9 - длина части (1-2, 5-6-7) пути (1-2- 3-5-6-7), совпадающей с критическим путем (1-2-5-6-7). Воспользуемся формулой расчета коэффициента напряженности, в результате получим, что

R_н(3,5) = 1-R_п(3,5) / (t_кр-t^'_кр)=1-2/(16-9)=0,7.

Для остальных работ коэффициент напряженности находится аналогичным способом.

Пример.Оптимизация сетевого графика.

Для сокращения срока реализации проекта, представленного сетевым графиком (рис.2.2), заказчик выделил 14 ед. дополнительных средств. Продолжительность выполнения работ линейно зависит от дополнительно вло­женных средств и выражается соотношением

t'_ij = t_ij - k_ij x_ij .

Известно, что k₁₂ = 0,1; k₁₃ = 0,2; k₂₃ = 0,5; k₂₄ = 0,3; k₃₅ = 0,6; k₄₅ = 0,1. Над каждой работой поставлены ее продолжитель­ность t_ij  и минимально возможное время выполнения d_ij .

Рис. 2.2

Требуется оптимизировать сетевой график по времени, то есть найти такие t^н _ij, t° _ij , x _ij, чтобы:

а)время выполнения всего проекта было минимальным;

б)сумма дополнительно вложенных средств не превышала 14 ед.;

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

Добавим на сетевом графике фиктивную работу (5, 6), как показано на рис. 2.3.

Рис. 2.3

Тогда целевая функция запишется в виде t_кр = t° _5,6 ( min)

Запишем ограничения задачи:

а) сумма вложенных средств не должна превышать их на­личного количества х₁₂ + х₁₃ +х₄₅ + х ₂₃+ х_{2 4}+ х₃₅ £ 14;

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

 t⁰₁₂-t^н₁₂³ 6; t⁰₁₃-t^н₁₃ ³ 12; t⁰₂₃-t^н₂₃³ 5; t⁰₂₄-t^н₂₄³ 6;

t⁰₃₄-t^н₃₄ = 0; t⁰₃₅ - t^н₃₅ ³ 10; t⁰₄₅ - t^н₄₅³ 4; t⁰₅₆-t^н₅₆ =0;

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

t⁰₁₂-t^н₁₂ =10-0,1 х₁₂ ; t⁰₁₃-t^н₁₃ = 20-0,2 х₁₃; t⁰₂₄-t^н₂₄ = 11- 0,3 х_{2 4}; t⁰₃₅ - t^н₃₅ = 16-0,6 х₃₅ ; t⁰₄₅-t^н₄₅= 6 – 0,1 х₄₅ ; t⁰₂₃-t^н₂₃ =12 – 0,5 х ₂₃.

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

t^н₁₂ = 0; t^н₁₃ = 0; t^н₂₃³ t⁰₁₂; t^н₃₄³ t⁰₁₃ ; t^н₃₄³ t⁰₂₃ ;t^н₂₄³ t⁰₁₂; t^н₃₅ ³ t⁰₁₃; t^н₃₅ ³ t⁰₂₃ ; t^н₄₅ ³ t⁰₂₄; t^н₅₆ ³ t⁰₃₅ ; t^н₅₆ ³ t⁰₄₅; t^н₄₅ ³ t⁰₃₄ .

д) условие неотрицательности неизвестных

t^H_ij³ 0; t°_ij ³ 0; t°_ij ³ 0, (i, j)Î U.

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

t^н₁₂ = 0; t°₁₂ = 10; t^н₁₃ = 0; t⁰₁₃= 20; t^н₂₃ = 10; t⁰₂₃= 20;

t^н₂₄= 10; t°₂₄ = 21; t^н₃₄ = 20; t⁰₃₄= 20; t^н₃₅ = 20; t°₃₅ = 30;

t^н₄₅= 24; t°₄₅ = 30; t^H₅₆ = 30; t⁰₅₆ = 30;x₁₂ = 0; x₁₃ = 0; x₂₃ = 4; x₂₄ = 0; x₃₅ = 10; x₄₅ = 0;t_KP = 30.

Таким образом, при дополнительном вложении 14 ед. комплекс работ может быть выполнен за 30 ед. времени. При этом средства распределятся следующим образом: 4 ед. в ра­боту (2, 3) и 10 ед. в работу (3, 5) (рис.2.4).

Рис. 2.4