Экономика и менеджмент \ Управление предприятием

Задачи сетевого планирования и управления. Свободный резерв времени, страница 8

Таблица 6

№

(i,j)

Тminij

tij

Тmaxij

Rijс

Тijопт

Сminij

Cij

Cmaxij

hij

∆Cij

1

(0,1)

5

7

13

0

-

89

123

215

18

-

2

(0,2)

8

9

17

8

17

38

60

110

8

64

3

(1,2)

5

10

18

0

-

11

15

24

1

-

4

(1,3)

3

8

14

0

-

35

48

90

5

-

5

(2,4)

13

21

31

0

-

29

60

155

7

-

6

(3,4)

2

4

24

19

23

14

20

80

3

57

Итого:

326

121

9.4. Решение задач сетевого планирования и управления на ЭВМ Excel.

Решение первой задачи

Упорядоченная структурная таблица комплекса работ имеет следующий вид:

№

Работа (i,j)

Предшественник

Продолжительность, tij

1

(0,1)

-

t01 = 7

2

(0,2)

-

t02 = 9

3

(1,2)

(0,1)

t12 = 10

4

(1,3)

(0,1)

t13 = 8

5

(2,4)

(0,2) (1,2)

t24 = 21

6

(3,4)

(1,3)

t34 = 4

Найти критический путь (максимальный по времени), т.е. сколько времени потребуется для завершения проекта.

Решение.1.В соответствии с условиями задачи строим ориентированную сеть (рис. 16) и с каждой работой (i,j) связываем свою булеву переменную

xi = 1,2,…,6.

2.Сведем задачу к задаче линейного программирования с булевыми переменными. Найти

при условии

,                                                                          (1)

,                                                                         (2)

,                                                                 (3)

,                                                                (4)

,                                                                         (5)

xi = 0 или 1; i = 1,2,…,6.                                                    (6)

3.Отведем для булевых переменных диапазон В2:В7.

4.В ячейку В8 введем целевую функцию

.

5.В ячейки В9:В13 введем левые части ограничений (1)…(6)

= В2 + В3,

= В6 + В7,

= В2 – В4 – В5,

= В3 + В4 – В6,

= В5 – В7.


Рис. 16

6.Выделяем диапазон В2:В13 и устанавливаем дробный формат числа.

7.В диалоговом окне «Поиск решения» вводим параметры, представленные ниже. В результате получаем следующее решение.

Ответ: критический путь 0→1→2→4;Ткр = 38.

Задача о коммивояжере

Имеется n городов А1, А2, … Аn, и задана матрица Cij (i = 1, 2, …, n;

j = 1, 2, …, n, i ≠ j) расстояний (время, путевые расходы) между этими городами. Коммивояжер, выезжая из города А1, должен побывать в каждом городе ровно один раз и вернуться в А1.

Требуется найти самый короткий маршрут.

Решение

1.Введем неизвестные величины:

если коммивояжер из города i переезжает в город j,

в противном случае.
Скачать файл