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

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

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

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

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

Таблица 2.1

Но-мер задачи	Пара- метры	Работы	Срок выпол- нения проекта t0
1,2	1,3	1,4	2,4	2,5	3,4	3,6	4,5	4,6	5,6
	tij
*	dij											34
	kij	0,1	0,3	0,2	0,05	0,25	0,2	0,12	0,5	0,08	0,02
	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
	tij
	dij
	kij	0,5	0,1	0,25	0,4	0,2	0,15	0,3	0,5	0,1	0,5
	tij
	dij
	kij	0,2	0,25	0,15	0,4	0,3	0,12	0,2	0,2	0,2	0,1
	tij
	dij
	kij	0,25	0,2	0,15	0,1	0,3	0,4	0,2	0,25	0,14	0,5
	tij
	dij
	kij	0,3	0,1	0,05	0,2	0,4	0,2	0,25	0,3	0,2	0,1
	tij
	dij
	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₂₅ ; t^о₃₄ - t ^н ₃₄ = 8 - 0,2x₃₄;

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

t^о₄₆ - t ^н ₄₆ = 14 - 0,08x₄₆ ; 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.

Результаты представим на сетевом графике: