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

 

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

Пусть задан срок выполнения проекта 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
dij
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
dij
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
	tij
dij
kij	0, 05	0, 2	0, 25	0, 08	0, 15	0, 1	0, 06	0, 05	0, 1	0, 5
	tij
dij
kij	0, 08	0, 25	0, 1	0, 15	0, 3	0, 2	0, 08	0, 4	0, 2	0, 1
	tij
dij
kij	0, 05	0, 25	0, 3	0, 07	0, 15	0, 1	0, 05	0, 03	0, 14	0, 5
	tij
dij
kij	0, 25	0, 07	0, 1	0, 2	0, 13	0, 15	0, 06	0, 4	0, 2	0, 1
	tij
dij
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 – Исходные данные для решения задачи

 

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться: