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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Лабораторная работа

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

Цель Научиться решать задачу сетевого планирования с одновременной оптимизацией средствами EXCEL.

Постановка задачи 1.

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

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

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

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

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

Номер задачи	Параметры	Работы										Срок выполнения проекта t0
		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
*	dij	4	8	13	5	7	6	10	10	11	7	34
	kij	0,1	0,3	0,2	0,05	0,25	0,2	0,12	0,5	0,08	0,02
	tij	9	12	18	8	12	5	12	10	13	12
1	dij71015610387121035
	kij	0,05	0,2	0,25	0,08	0,15	0,1	0,06	0,05	0,1	0,5
	tij	10	13	24	9	11	17	10	15	15	20
2	dij	5	9	11	6	9	12	7	13	13	15	56
	kij	0,08	0,25	0,1	0,15	0,3	0,2	0,08	0,4	0,2	0,1
	tij	6	13	20	9	14	16	15	10	17	13
3	dij	5	10	16	7	11	13	12	7	15	9	40
	kij	0,05	0,25	0,3	0,07	0,15	0,1	0,05	0,03	0,14	0,5
	tij	19	10	35	18	20	9	22	17	20	18
4	dij	16	5	25	13	15	6	17	13	16	14	60
	kij	0,25	0,07	0,1	0,2	0,13	0,15	0,06	0,4	0,2	0,1
	tij	6	15	26	7	11	10	11	12	13	17
5	dij	5	13	20	5	9	7	8	9	12	15	50
	kij	0,07	0,2	0,3	0,1	0,05	0,1	0,04	0,05	0,15	0,5
	tij	10	18	16	12	7	13	11	10	13	12
6	dij71412105987121042
	kij	0,5	0,1	0,25	0,4	0,2	0,15	0,3	0,5	0,1	0,5
	tij	9	18	21	7	12	19	20	9	15	20
7	dij	6	14	18	4	9	15	16	6	13	15	33
	kij	0,2	0,25	0,15	0,4	0,3	0,12	0,2	0,2	0,2	0,1
	tij	15	8	7	5	13	11	7	15	17	13
8	dij	12	5	4	3	10	8	4	12	15	9	47
	kij	0,25	0,2	0,15	0,1	0,3	0,4	0,25	0,14	0,5
	tij	13	22	19	17	10	25	12	13	20	18
9	dij	10	18	15	14	7	21	9	10	16	14	49
	kij	0,3	0,1	0,05	0,2	0,4	0,2	0,25	0,3	0,2	0,1
	tij	16	12	10	8	3	9	11	16	13	17
10	dij	10	7	6	5	2	7	9	10	12	15	29
	kij	0,2	0,1	0,16	0,3	0,25	0,1	0,4	0,2	0,15	0,5

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

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

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

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

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

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

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

t^о₃₆ £ 34; t^о₄₆ £ 34; t^о₅₆ £ 34;

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

t^о₁₂ - t ^н ₁₂ ³ 4; t^о₃₄ - t ^н ₃₄ ³ 6;

t^о₁₃ - t ^н ₁₃ ³ 8; t^о₃₆ - t ^н ₃₆ ³ 10;

t^о₁₄ - t ^н ₁₄ ³ 13; t^о₄₅ - t ^н ₄₅ ³ 10;

t^о₂₄ - t ^н ₂₄ ³ 5; t^о₄₆ - t ^н ₄₆ ³ 11;

t^о₂₅ - t ^н ₂₅ ³ 7; t^о₅₆ - t ^н ₅₆ ³ 7;

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

t^о₁₂ - t ^н ₁₂ = 7 - 0,1x₁₂; t^о₁₃ - t ^н ₁₃ = 11 - 0,3x₁₃;

t^о₁₄ - t ^н ₁₄ = 16 - 0,2x₁₄; t^о₂₄ - t ^н ₂₄ = 6 - 0,05x₂₄;

t^о₂₅ - t ^н ₂₅ = 10 - 0,25x_25; t^о₃₄ - t ^н ₃₄ = 8 - 0,2x₃₄;

t^о₃₆ - t ^н ₃₆ = 13 - 0,12x_36; t^о₄₅ - t ^н ₄₅ = 12 - 0,5x₄₅;

t^о₄₆ - t ^н ₄₆ = 14 - 0,08x_46; t^о₅₆ - t ^н ₅₆ = 9 - 0,02x₅₆;

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

t ^н ₁₂ = 0; 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 ^н ₅₆ ³ t^о₂₅; t ^н ₅₆ ³ t^о₄₅;

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

t ^н _ij ³ 0, t^о_ij ³ 0, x_ij ³ 0, (i, j) Î .

3.      Численное решение задачи:

Табличную запись математической модели см. табл. 2.2.

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

t ^н₁₂ = 0; t^о₁₂ = 7; t ^н₁₃ = 0; t^о₁₃ = 8; t ^н₁₄ = 0; t^о₁₄ = 15;

t ^н ₂₄ = 7; t^о₂₄ = 13; t ^н ₂₅ = 7; t^о₂₅ = 17;

t ^н ₃₄ = 8; t^о₃₄ = 15; t ^н ₃₆ = 8; t^о₃₆ = 21;

t ^н₄₅ = 15; t^о₄₅ = 25; t ^н ₅₆ = 25; t^о₅₆ = 34;

x₁₂ = 0; x₁₃ = 10; x₁₄ = 5; x₂₄ = 0; x₂₅ = 0;

x₃₄ = 5; x₃₆ = 0; x₄₅ =4; x₄₆ =0; x₅₆ = 0;

f_min = 24.

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

Постановка задачи 2.

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

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

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

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

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

Номер задачи	Пара- метры	Работы								Срок выполнения проекта t0
		1,2	1,3	1,4	2,4	2,5	3,4	3,6	4,5
	tij	7	11	16	6	10	8	13	12
*	dij	4	8	13	5	7	6	10	10	34
	kij	0,1	0,3	0,2	0,05	0,25	0,2	0,12	0,5
	tij	9	12	18	8	12	5	12	10
1	dij7101561038735
	kij	0,05	0,2	0,25	0,08	0,15	0,1	0,06	0,05
	tij	10	13	24	9	11	17	10	15
2	dij	5	9	11	6	9	12	7	13	56
	kij	0,08	0,25	0,1	0,15	0,3	0,2	0,08	0,4
	tij	6	13	20	9	14	16	15	10
3	dij	5	10	16	7	11	13	12	7	40
	kij	0,05	0,25	0,3	0,07	0,15	0,1	0,05	0,03
	tij	19	10	35	18	20	9	22	17
4	dij	16	5	25	13	15	6	17	13	60
	kij	0,25	0,07	0,1	0,2	0,13	0,15	0,06	0,4
	tij	6	15	26	7	11	10	11	12
5	dij	5	13	20	5	9	7	8	9	50
	kij	0,07	0,2	0,3	0,1	0,05	0,1	0,04	0,05
	tij	10	18	16	12	7	13	11	10
6	dij7141210598742
	kij	0,5	0,1	0,25	0,4	0,2	0,15	0,3	0,5
	tij	9	18	21	7	12	19	20	9
7	dij	14	18	4	9	15	16	6	33
	kij	0,2	0,25	0,15	0,4	0,3	0,12	0,2	0,2
	tij	15	8	7	5	13	11	7	15
8	dij	12	5	4	3	10	8	4	12	47
	kij	0,25	0,2	0,15	0,1	0,3	0,4	0,2	0,25
	tij	13	22	19	17	10	25	12	13
9	dij	10	18	15	14	7	21	9	10	49
	kij	0,3	0,1	0,05	0,2	0,4	0,2	0,25	0,3
	tij	16	12	10	8	3	9	11	16
10	dij	10	7	6	5	2	7	9	10	29
	kij	0,2	0,1	0,16	0,3	0,25	0,1	0,4	0,2

Решение варианта *.

1. Запишем все данные на сетевой график.

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

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

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

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

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

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

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

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

t^о₁₂ - t ^н ₁₂ ³ 3; t^о₃₄ - t ^н ₃₄ ³ 5;

t^о₁₃ - t ^н ₁₃ ³ 4; t^о₃₅ - t ^н ₃₅ ³ 4;

t^о₁₄ - t ^н ₁₄ ³ 1; t^о₄₅ - t ^н ₄₅ ³ 2;

t^о₂₃ - t ^н ₂₃ ³ 2; t^о₅₆ - t ^н ₅₆ = 0;

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

t^о₁₂ - t ^н ₁₂ = 5 - 0,5x₁₂; t^о₁₃ - t ^н ₁₃ = 6 - 0,2x₁₃;

t^о₁₄ - t ^н ₁₄ = 2 - 0,3x₁₄; t^о₂₃ - t ^н ₂₃ = 4 - 0,25x₂₃;

t^о₃₄ - t ^н ₃₄ = 9 - 0,4x₃₄; t^о₃₅ - t ^н ₃₅ = 7 - 0,2x_35;

t^о₄₅ - t ^н ₄₅ = 4 - 0,1x₄₅;

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

t ^н ₁₂ = 0; t ^н ₁₃ = 0; t ^н₁₄ = 0;

t ^н ₂₃ ³ t^о₁₂;

t ^н ₃₄ ³ t^о₁₃; t ^н ₃₄ ³ t^о₂₃;

t ^н ₃₅ ³ t^о₁₃; t ^н ₃₅ ³ t^о₂₃;

t ^н ₄₅ ³ t^о₁₄; t ^н ₄₅ ³ t^о₃₄;

t ^н ₅₆ ³ t^о₃₅; t ^н ₅₆ ³ t^о₄₅;

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

t ^н _ij ³ 0, t^о_ij ³ 0, x_ij ³ 0, (i, j) Î .

сетевой математический модель

5.      Численное решение задачи:

Табличную запись математической модели см. табл. 2.4.

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

t ^н₁₂ = 0; t^о₁₂ = 3; t ^н₁₃ = 0; t^о₁₃ = 3; t ^н₁₄ = 0; t^о₁₄ = 2;

t ^н ₂₃ = 3; t^о₂₃ = 3; t ^н ₃₄ = 3; t^о₃₄ = 8; t ^н ₃₅ = 3; t^о₃₅ = 10;

t ^н₄₅ = 8; t^о₄₅ = 10; t ^н ₅₆ = 10; t^о₅₆ = 10;

x₁₂ = 20; x₁₃ = 0; x₂₃ = 0; x₁₄ = 0; x₃₄ = 10; x₃₅ = 0; x₄₅ =20,

t_кр = 10.

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