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

Лабораторная работа №2.

Цель Научиться решать задачу сетевого планирования с одновременной оптимизацией средствами 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.

Таблица 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.

Переменные

X12

X13

X14

X24

X25

X34

X36

Х45

Х46

Х56

t^o12

t^o13

t^o14

t^н24

t^о24

t^н25

t^о25

t^н34

t^о34

t^н36

t^о36

t^н45

t^о45

t^н46

t^о46

t^н56

t^о56

Левая часть

Вид огр

Ограни- чение

Значения

Нижн. гр.

Верхн.гр.

Цел. ф-ия

min

£

£

£

³

³

³

-1

³

-1

³

-1

³

-1

³

-1

³

-1

³

-1

³

0,1

=

0,3

=

0,2

=

0,05

-1

=

0,25

-1

=

0,2

-1

=

0,12

-1

=

0,5

-1

=

0,08

-1

=

0,02

-1

=

-1

³

-1

³

-1

³

-1

³

-1

³

-1

³

-1

³

-1

³

-1

³

-1

³

-1

³

-1

³

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

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 ед. времени.

---

Дата добавления: 2015-08-03