Сетевое моделирование при планировании. Задача о коммивояжере.... Реферат.

Страница: 2 из 5
<-- предыдущая следующая -->

Перейти на страницу:
скачать реферат | 1 2 3 4 5

Ф. ц.
22
28
18
35
28
25
55
15
100

max

Решение

x1= 6
x2= 9
x3= 8
x4= 12
x5= 7
x6= 4
x7= 11
x8= 4
x9= 5,4
Т. к. x9= 5,4, то длина критического пути уменьшится на эту величину. Проверим это утверждение:
x3+ x7+ x8= 8 + 11 + 4 = 23
Уменьшение времени выполнения работы, как правило, связано с увеличением затрат. В таблице 1.3 определим прирост затрат при уменьшении времени реализации проекта.

Таблица 1.3

Изменение затрат при уменьшении времени реализации проекта

Работа

х
tHB
Dx
Куск
Dзатрат
Стоимость
Итого затрат

A
6
5,2
-0,8
22
-17,6
110
92,4

B
9
8,2
-0,8
28
-22,4
130
107,6

C
8
9,8
1,8
18
32,4
160
192,4

D
12
10,8
-1,2
35
-42
190
148

E
7
6,8
-0,2
28
-5,6
150
144,4

F
4
5,2
1,2
25
30
130
160

G
11
13,4
2,4
55
132
260
392

H
4
5,2
1,2
15
18
90
108

Всего затрат

124,8

1220
1344,8

Таким образом, время выполнения работ A, B, D, E увеличилось по сравнению с наиболее вероятным; продолжительность остальных работ уменьшилась. Затраты на реализацию проекта возросли на 124,8 тыс. $. Увеличение затрат произошло, в основном, из-за работы G, по которой наблюдается наибольшее сокращение времени в сочетании с наивысшим коэффициентом затрат на выполнение работы.
Из-за сокращения критического пути проект будет введен в эксплуатацию на 5,4 недели раньше. Т. к. прибыль за неделю составляет 100 тыс. $, то за этот срок она составит 100 тыс. $ * 5,4 = 540 тыс. $.
В результате дополнительная прибыль с учетом возрастания затрат на проведение работ составит 540 тыс. $ - 124,8 тыс. $ = 415,2 тыс. $

Задание №2
Тема: Графы
Задача о коммивояжере

Имеется 4 пункта. Время переезда из пункта I в пункт j представлено в таблице 2.1.

Таблица 2.1

Исходные данные

Из пункта i

В пункт j

1

2
3
4

1
0
8
8
6

2
4
0
6
12

3
10
12
0
18

4
8
10
4
0

График представлен на рисунке.

Требуется найти оптимальный маршрут, вычеркнув из таблицы отсутствующие маршруты.

Математическая модель

Обозначим за x маршруты, приведенные в таблице 2.2.

Таблица 2.2

Обозначения

xi
Пункт отправления
Пункт назначения
Время переезда

x1
1
2
8

x2
1
3
8

Продолжение

x3
1
4
6

x4
2
1
4

x5
2
3
6

x6
2
4
12

x7
3
1
10

x8
3
2
12

x9
3
4
18

x10
4
1
8

x11
4
2
10

x12
4
3
4

Сумма входящих и исходящих маршрутов в каждом пункте равна 1. Следовательно, система условий-ограничений выглядит следующим образом:
x1+ x2+ x3= 1(1)
x4+ x5+ x6= 1(2)
x7+ x8+ x9= 1(3)
x10+ x11+ x12= 1(4)
x4+ x7+ x10= 1(5)
x1+ x8+ x11= 1(6)
x2+ x5+ x12= 1(7)
x3+ x6+ x9= 1(8)
Функция цели: 8x1+ 8x2+ 6x3+ 4x4+ 6x5+ 12x6+ 10x7+ 12x8+ 18x9+ 8x10+ 10x11+ 4x12min
Исходная матрица условий задачи представлена в таблице 2.3.

Таблица 2.3

№
x1
x2
x3
x4
x5
x6
x7
x8
x9
х10
x11
x12
Св.чл.
Зн

1
1
1
1
0
0
0
0
0
0
0
0
0
1
=

2
0
0
0
1
1
1
0
0
0
0
0
0
1
=

3
0
0
0
0
0
0
1
1
1
0
0
0
1
=

4
0
0
0
0
0
0
0
0
0
1
1
1
1
=

5
0
0
0
1
0
0
1
0
0
1
0
0
1
=

6
1
0
0
0
0
0
0
1
0
0
1
0
1
=

7
0
1
0
0
1
0
0
0
0
0
0
1
1
=

8
0
0
1
0
0
1
0
0
1
0
0
0
1
=

Фц.
8
8
6
4
6
12
10
12
18
8
10
4
min

Исходная матрица

Решение

x3= 1
x5= 1
x7= 1
x8= 0
x11= 1
Это означает, что на графике остаются только пути, соответствующие переменным х3, х5, х7, х11(1 4, 2 3, 3 1, 4 2). Функционал равен 12, т. е. время пути будет равно 12 единицам. График при этом выглядит следующим образом.

Задание №3
Тема: Графы
Задача о максимальном потоке

Имеется трубопроводная сеть с заданной Sijпропускной способностью каждого участка из i-го узла в j-й узел и мощностью насосной станции, расположенной в узле. Необходимо рассчитать максимальную пропускную способность сети из начального узла в конечный узел.

aистокaсток

Пропускная способность Sij, тыс. тонн
S12= 4
S13= 7
S14= 8
S23= 3
S25= 5
S34= 8
S35= 9
S45= 9

Математическая модель

Обозначим за х1, 2, …, 8перевозки по маршрутам 12, 13, 14, 23, 25, 34, 35, 45 соответственно, а за х9– пропускную способность конечного узла сети.
Сумма входящих в каждый узел потоков равна сумме выходящих, причем интенсивность каждого потока не может превышать пропускную способность своего участка сети. Поэтому система условий-ограничений выглядит следующим образом.
х9-х1–х2–х3= 0(1)
х1–х4–х5= 0(2)
х2+х4–х6–х7= 0(3)
х3+х6–х8= 0(4)
х5+х7+х8–х9= 0(5)
х1Ј4(6)
х2Ј7(7)
х3Ј8(8)

Страница: 2 из 5
<-- предыдущая следующая -->

Перейти на страницу:
скачать реферат | 1 2 3 4 5

Работа	х	tHB	Dx	Куск	Dзатрат	Стоимость	Итого затрат
A	6	5,2	-0,8	22	-17,6	110	92,4
B	9	8,2	-0,8	28	-22,4	130	107,6
C	8	9,8	1,8	18	32,4	160	192,4
D	12	10,8	-1,2	35	-42	190	148
E	7	6,8	-0,2	28	-5,6	150	144,4
F	4	5,2	1,2	25	30	130	160
G	11	13,4	2,4	55	132	260	392
H	4	5,2	1,2	15	18	90	108
Всего затрат					124,8	1220	1344,8

xi	Пункт отправления	Пункт назначения	Время переезда
x1	1	2	8
x2	1	3	8