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

Требуется найти такие 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

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.

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