Рефераты - Афоризмы - Словари
Русские, белорусские и английские сочинения
Русские и белорусские изложения
 
У нас есть несколько работ на данную тему. Вы можете создать свою уникальную работу объединив фрагменты из уже существующих:
  1. Оптимизация сетевого графика по времени 43.9 Кб.
  2. Оптимизация сетевого графика по времени 43.9 Кб.

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

Работа из раздела: «Математика»

/

/

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

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

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

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

Проект представлен сетевым графиком. Для каждой работы известна ее продолжительность tij и минимально возможное время выполнения dij. Пусть задан срок выполнения проекта t0, а расчетное tкр > t0. Продолжительность выполнения работы (i, j) линейно зависит от суммы дополнительно вложенных средств хij и выражается соотношением: t'ij = tij - kijxij. Технологические коэффициенты kij известны.

Требуется найти такие t н ij, toij, xij, чтобы:

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

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

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

Номер

задачи

Параметры

Работы

Срок выполнения

проекта 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

dij

7

10

15

6

10

3

8

7

12

10

35

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

dij

7

14

12

10

5

9

8

7

12

10

42

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,2

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, т.е. превышает директивный срок t0 = 34.

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

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

f= х12 + х13 + х14 + х34 + х35 + х45 + х14 + х34 + х35 + х45 (min).

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

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

tо36 34; tо46 34; tо56 34;

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

tо12 - t н 12 4; tо34 - t н 34 6;

tо13 - t н 13 8; tо36 - t н 36 10;

tо14 - t н 14 13; tо45 - t н 45 10;

tо24 - t н 24 5; tо46 - t н 46 11;

tо25 - t н 25 7; tо56 - t н 56 7;

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

tо12 - t н 12 = 7 - 0,1x12; tо13 - t н 13 = 11 - 0,3x13;

tо14 - t н 14 = 16 - 0,2x14; tо24 - t н 24 = 6 - 0,05x24;

tо25 - t н 25 = 10 - 0,25x25; tо34 - t н 34 = 8 - 0,2x34;

tо36 - t н 36 = 13 - 0,12x36; tо45 - t н 45 = 12 - 0,5x45;

tо46 - t н 46 = 14 - 0,08x46; tо56 - t н 56 = 9 - 0,02x56;

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

t н 12 = 0; t н 13 = 0; t н14 = 0;

t н 24 tо12; t н 25 tо12;

t н 34 tо13; t н 36 tо13;

t н 45 tо14; t н 45 tо24;

t н 45 tо34;

t н 46 tо14; t н 46 tо24;

t н 46 tо34;

t н 56 tо25; t н 56 tо45;

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

t н ij 0, tоij 0, xij 0, (i, j) .

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

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

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

t н12 = 0; tо12 = 7; t н13 = 0; tо13 = 8; t н14 = 0; tо14 = 15;

t н 24 = 7; tо24 = 13; t н 25 = 7; tо25 = 17;

t н 34 = 8; tо34 = 15; t н 36 = 8; tо36 = 21;

t н45 = 15; tо45 = 25; t н 56 = 25; tо56 = 34;

x12 = 0; x13 = 10; x14 = 5; x24 = 0; x25 = 0;

x34 = 5; x36 = 0; x45 =4; x46 =0; x56 = 0;

fmin = 24.

4. Анализ полученных результатов. Чтобы выполнить работы проекта за директивное время t0=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.

Проект представлен сетевым графиком. Для каждой работы известна ее продолжительность tij и минимально возможное время выполнения dij. Для сокращения срока реализации проекта выделено В ден. ед. Вложение дополнительных средств хij в работу (i, j) сокращает время ее выполнения до t'ij = tij - kijxij. Технологические коэффициенты kij известны.

Требуется найти такие t н ij, toij, xij, чтобы:

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

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

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

Номер

задачи

Пара-

метры

Работы

Срок выполнения

проекта 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

dij

7

10

15

6

10

3

8

7

35

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

dij

7

14

12

10

5

9

8

7

42

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

6

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о56 (min).

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

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

х12 + х13 + х14 + х23 + х34 + х35 + х45 47;

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

tо12 - t н 12 3; tо34 - t н 34 5;

tо13 - t н 13 4; tо35 - t н 35 4;

tо14 - t н 14 1; tо45 - t н 45 2;

tо23 - t н 23 2; tо56 - t н 56 = 0;

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

tо12 - t н 12 = 5 - 0,5x12; tо13 - t н 13 = 6 - 0,2x13;

tо14 - t н 14 = 2 - 0,3x14; tо23 - t н 23 = 4 - 0,25x23;

tо34 - t н 34 = 9 - 0,4x34; tо35 - t н 35 = 7 - 0,2x35;

tо45 - t н 45 = 4 - 0,1x45;

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

t н 12 = 0; t н 13 = 0; t н14 = 0;

t н 23 tо12;

t н 34 tо13; t н 34 tо23;

t н 35 tо13; t н 35 tо23;

t н 45 tо14; t н 45 tо34;

t н 56 tо35; t н 56 tо45;

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

t н ij 0, tоij 0, xij 0, (i, j) .

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

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

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

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

t н12 = 0; tо12 = 3; t н13 = 0; tо13 = 3; t н14 = 0; tо14 = 2;

t н 23 = 3; tо23 = 3; t н 34 = 3; tо34 = 8; t н 35 = 3; tо35 = 10;

t н45 = 8; tо45 = 10; t н 56 = 10; tо56 = 10;

x12 = 20; x13 = 0; x23 = 0; x14 = 0; x34 = 10; x35 = 0; x45 =20,

tкр = 10.

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

ref.by 2006—2019
contextus@mail.ru