Постановка задачи 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.

 

Таблица 2.3

Ва-ри- ант	Пара- метры	Работы	Сумма
(1, 2)	(1, 3)	(1, 4)	(2, 3)	(3, 4)	(3, 5)	(4, 5)	средств В
	tij
*	dij								47
	kij	0, 5	0, 2	0, 3	0, 25	0, 4	0, 2	0, 1
	tij
	dij
	kij	0, 5	0, 1	0, 25	0, 4	0, 2	0, 15	0, 3
	tij
	dij
	kij	0, 2	0, 25	0, 15	0, 4	0, 3	0, 12	0, 2
	tij
	dij
	kij	0, 25	0, 2	0, 15	0, 1	0, 3	0, 4	0, 2
	tij
	dij
	kij	0, 3	0, 1	0, 05	0, 2	0, 4	0, 2	0, 25
	tij
	dij
	kij	0, 2	0, 1	0, 16	0, 3	0, 25	0, 1	0, 4

 

 

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

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

 

 

2; 1 4; 2

9; 5

4; 2

7; 4

5; 3

 

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

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

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

 

 

2; 1 4; 2

9; 5

6; 4 7; 4

4; 2

5; 3

 

Целевая функция имеет вид 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₃₅ ;

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.

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

2; 1 4; 2

9; 5

4; 2

7; 4

5; 3

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