5) Определить, на сколько дней можно отложить выпол­нение работы a6 без отсрочки завершения проекта в целом?

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

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

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

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

Пример решения задачи 1

Постановка задачи 1. Проект представлен сетевым графиком. Для каждой работы известна ее продолжительность t_ij и минимально возможное время вы­полнения d_ij. Пусть задан срок выполнения проекта t_o, а расчетное t_кр > t_о. Про­должительность выполнения работы (i, j) линейно зависит от суммы дополни­тельно вложенных средств х_ij и выражается соотношением: t’_ij = t_ij - k_jjx_ij. Техно­логические коэффициенты k_ij известны.

Требуется найти такие t^н_ij, t^о_ij, х_ij, чтобы:

- срок выполнения всего комплекса работ не превышал заданной величины t_о;

- суммарное количество дополнительно вложенных средств было мини­мальным;

- продолжительность выполнения каждой работы t’_ij была не меньше за­данной величины d_ij.

При выполнении работы используйте данные, приведенные в таблице 6.6.

Таблица 6.6 – Исходные данные по вариантам

Параметры	Работы										Срок выполнения проекта tо
	1,2	1,3	1,4	2,4	2,5	3,4	3,6	4,5	4,6	5,6
tij	7	11	16	6	10	8	13	12	14	9	34
dij	4	8	13	5	7	6	10	10	11	7
kij	0,1	0,3	0,2	0,05	0,25	0,2	0,12	0,5	0,08	0,02

Решение задачи

1 Запишем все данные на сетевой график (рисунок 6.4) и рассчитаем сроки свершения событий.

Рисунок 6.4 – Исходный сетевой график

Расчеты показали, что срок выполнения проекта t_кр = 40, т.е. превышает директивный срок t_o = 34.

2 Составление математической модели задачи

Целевая функция имеет вид

f = х₁₂ + х₁₃ + х₁₄ + х₂₄ + х₂₅ + х₃₄ + х₃₆ + х₄₅ + х₄₆ + х₅₆ (min).

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

а) срок выполнения проекта не должен превышать t_о = 34

t°₃₆ < 34; t°₄₆ < 34; t°₅₆ < 34;

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

; ; ; ; ;

; ; ; ; ;

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

; ; ; ; ; ;

; ; ; ;

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

; ; ; ; ;

; ; ; ;

; ; ; ; ;

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

; ; ; .

3 Технология решения задачи в Excel.

Сделать форму и ввести данные математической модели на рабочем листе Excel в ячейках А1:АЕ40 (таблица 6.7).

Решить данную задачу средствами Excel как оптимизационную с помощью инструмента Поиск решения (рисунок 6.5). В параметрах Поиска решения установить флажки «Линейная модель» и «Неотрицательные значения».

Рисунок 6.5 – Решение задачи с помощью инструмента Поиск решения

Для нашего примера получаем следующие результаты:

; ; ; ; ; ;

; ; ; ; ; ;

; ; ; ; ; ; ; ; ;;;;

; ;;;;;

.

Результаты оптимизации представим на сетевом графике (рисунок 6.6).

Рисунок 6.6 – Сетевой график в результате оптимизации

4 Анализ полученных результатов.

Чтобы выполнить работы проекта за директивное время t_o = 34, необходимо дополнительно вложить 24 ден. ед. При этом средства распределятся следующим образом: 10 ден. ед. - в работу (1,3), 5 ден. ед. - в работу (1,4), 5 ден. ед. - в работу (3,4) и 4 ден. ед. - в работу (4,5), что приведет к сокращению продолжительности работы (1,3) на 3 дня, работ (1,4) и (3,4) - на 1 день и работы (4,5) - на 2 дня. Сокращение срока реализации проекта за счет вложения дополнительных средств составит 6 ед. времени.

Пример решения задачи 2

Постановка задачи 2. Проект представлен сетевым графиком. Для каждой работы известна ее продолжительность t_ij и минимально возможное время вы­полнения d_ij. Для сокращения срока реализации проекта выделено В ден. ед. Вложение дополнительных средств х_ij в работу (i, j) сокращает время ее выпол­нения до t’_ij = t_ij - k_ijx_ij. Технологические коэффициенты k_ij известны.

Требуется найти такие t^н_ij, t^о_ij, х_ij, чтобы:

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

- количество используемых дополнительных средств не превышало В ден. ед.;

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

При выполнении заданий воспользуйтесь данными, приведенными в таблице 6.8.

Таблица 6.8 – Исходные данные для решения задачи

Параметры	Работы							Сумма средств, В
	(1,2)	(1,3)	(1,4)	(2,3)	(3,4)	(3,5)	(4,5)
tij	5	6	2	4	9	7	4	47
dij	3	4	1	2	5	4	2
kij	0,5	0,2	0,3	0,25	0,4	0,2	0,1

Решение задачи

1 Запишем все данные на сетевой график и рассчитаем сроки свершения событий (рисунок 6.7).

Рисунок 6.7 – Исходный сетевой график

Видим, что по первоначальному условию t_кр = 22, т.е. проект может быть выполнен за 22 ед. времени.

2 Составление математической модели задачи.

Чтобы однозначно записать целевую функцию, добавим на сетевом графи­ке (рисунок 6.8) фиктивную работу (5,6).

Рисунок 6.8 – Измененный сетевой график

Целевая функция имеет вид t_кр = t°₅₆ (min).

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

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

х₁₂ + х₁₃ + х₁₄ + х₂₃ + х₃₄ + х₃₅ + х₄₅ < 47;

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

; ; ; ;

; ; ; ;

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

; ; ; ; ; ; ;

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

; ; ; ; ; ; ; ; ; ; ; ;

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

; ; ; .

3 Технология решения задачи средствами Excel.

Сделать форму и ввести данные математической модели на рабочем листе Excel в ячейках А1:АЕ40 (таблица 6.9).

Решить данную задачу средствами Excel как оптимизационную с помощью инструмента Поиск решения (рисунок 6.9). В параметрах Поиска решения установить флажки «Линейная модель» и «Неотрицательные значения».

Рисунок 6.9 – Решение задачи с помощью инструмента Поиск решения

Решив данную задачу средствами Excel, получаем следующие результа­ты:

; ; ; ; ; ;

; ; ; ; ; ; ; ; ; ; ;;;;;;;.

Результаты решения представим на сетевом графике (рисунок 6.10).

Рисунок 6.10 - Сетевой график в результате оптимизации

4 Анализ полученных результатов.

При дополнительном вложении 47 ден. ед. проект может быть выполнен за 12 ед. времени. При этом средства распре­делятся следующим образом: 4 ден. ед. - в работу (1,2), 5 ден. ед. - в работу (1,3), 8 ден. ед. - в работу (2,3), 10 ден. ед. - в работу (3,4) и 20 ден. ед. - в ра­боту (4,5), что приведет к сокращению продолжительности работ (1,2), (2,3) и (4,5) на 2 дня, работы (1,3) на 1 день, работы (3,4) на 4 дня. Сокращение срока реализации проекта за счет вложения дополнительных средств составит 10 ед. времени.

Задачи для самостоятельного решения

Задача 1

Проект представлен сетевым графиком. Для каждой работы известна ее продолжительность t_ij и минимально возможное время вы­полнения d_ij. Пусть задан срок выполнения проекта t_o, а расчетное t_кр > t_о. Про­должительность выполнения работы (i, j) линейно зависит от суммы дополни­тельно вложенных средств х_ij и выражается соотношением: t’_ij = t_ij - k_jjx_ij. Техно­логические коэффициенты k_ij известны.

Требуется найти такие t^н_ij, t^о_ij, х_ij, чтобы:

- срок выполнения всего комплекса работ не превышал заданной величины t_о;

- суммарное количество дополнительно вложенных средств было мини­мальным;

- продолжительность выполнения каждой работы t’_ij была не меньше за­данной величины d_ij.

При выполнении работы используйте данные, приведенные в таблице 6.10.

Таблица 6.10 – Исходные данные по вариантам

Номер варианта	Параметры	Работы										Срок выполнения проекта tо
		1,2	1,3	1,4	2,4	2,5	3,4	3,6	4,5	4,6	5,6
1	tij	9	12	18	8	12	5	12	10	13	12	35
	dij	7	10	15	6	10	3	8	7	12	10
	kij	0,05	0,2	0,25	0,08	0,15	0,1	0,06	0,05	0,1	0,5
2	tij	10	13	24	9	11	17	10	15	15	20	56
	dij	5	9	11	6	9	12	7	13	13	15
	kij	0,08	0,25	0,1	0,15	0,3	0,2	0,08	0,4	0,2	0,1
3	tij	6	13	20	9	14	16	15	10	17	13	40
	dij	5	10	16	7	11	13	12	7	15	9
	kij	0,05	0,25	0,3	0,07	0,15	0,1	0,05	0,03	0,14	0,5
4	tij	19	10	35	18	20	9	22	17	20	18	60
	dij	16	5	25	13	15	6	17	13	16	14
	kij	0,25	0,07	0,1	0,2	0,13	0,15	0,06	0,4	0,2	0,1
5	tij	6	15	26	7	11	10	11	12	13	17	50
	dij	5	13	20	5	9	7	8	9	12	15
	kij	0,07	0,2	0,3	0,1	0,05	0,1	0,04	0,05	0,15	0,5

Задача 2

Проект представлен сетевым графиком. Для каждой работы известна ее продолжительность t_ij и минимально возможное время вы­полнения d_ij. Для сокращения срока реализации проекта выделено В ден. ед. Вложение дополнительных средств х_ij в работу (i, j) сокращает время ее выпол­нения до t’_ij = t_ij - k_ijx_ij. Технологические коэффициенты k_ij известны.

Требуется найти такие t^н_ij, t^о_ij, х_ij, чтобы:

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

- количество используемых дополнительных средств не превышало В ден. ед.;

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

При выполнении заданий воспользуйтесь данными, приведенными в таблице 6.11.

Таблица 6.11 – Исходные данные для решения задачи

Вариант	Параметры	Работы							Сумма средств, В
		(1,2)	(1,3)	(1,4)	(2,3)	(3,4)	(3,5)	(4,5)
1	tij	10	18	16	12	7	13	11	42
	dij	7	14	12	10	5	9	8
	kij	0,5	0,1	0,25	0,4	0,2	0,15	0,3
2	tij	9	18	21	7	12	19	20	33
	dij	6	14	18	4	9	15	16
	kij	0,2	0,25	0,15	0,4	0,3	0,12	0,2
3	tij	15	8	7	5	13	11	7	47
	dij	12	5	4	3	10	8	4
	kij	0,25	0,2	0,15	0,1	0,3	0,4	0,2
4	tij	13	22	19	17	10	25	12	49
	dij	10	18	15	14	7	21	9
	kij	0,3	0,1	0,05	0,2	0,4	0,2	0,25
5	tij	16	12	10	8	3	9	11	29
	dij	10	7	6	5	2	7	9
	kij	0,2	0,1	0,16	0,3	0,25	0,1	0,4