- •Практические работы Практическая работа №1 Построение остовного дерева графа. Нахождение найкратчайшего расстояния между заданными вершинами графа
- •Практическая работа №2 Нахождение наикратчайших расстояний между всеми парами вершин графа. Алгоритм Флойда.
- •Практическая работа №3
- •Практическая работа №4 Нахождение потока заданной величины минимальной стоимости. Алгоритм Басакера-Гоуэна
- •Практическая работа №5
- •Практическая работа №7 Оптимизация проекта по времени.
- •Практическая работа №8
- •Практическая работа №9 Оптимизация целевой функции с помощью двухфазного симплекс метода.
- •Практическая работа №10 Решение двойственных задач. Экономическая интерпретация задач линейного программирования.
- •Практическая работа №11 Решение транспортных задач.
- •Практическая работа №12 Дополнительные условия в транспортных задачах
- •Практическая работа №13 Метод Гомори для решения задачи целочисленного линейного программирования.
- •Практическая работа №14
- •Практическая работа №15 Решение матричных игр в чистых стратегиях
- •Практическая работа №16 Графический метод решения матричных игр.
- •Практическая работа №17
- •Каркас минимального веса. Метод р. Прима.
- •Кратчайшие пути
- •Лабораторная работа №2 Кратчайшее расстояния от заданной вершины до всех остальных вершин графа.
- •Алгоритм Дийкстры.
- •Пути в бесконтурном графе.
- •Лабораторная работа №3 Кратчайшие пути между всеми парами вершин графа.
- •Алгоритм Флойда.
- •Лабораторная работа №4 Построение потока максимальной мощности.
- •Потоки в сетях.
- •Метод построения максимального потока в сети.
- •Лабораторная работа №5 Симплекс метод
- •Лабораторная работа №6 Транспортная задача
- •Список литературы
Практическая работа №11 Решение транспортных задач.
Найти оптимальные планы перевозок ТЗ, условия которых даны в таблицах:
1.
|
Поставщики |
Потребители |
Запас груза аi | |||
|
В1 |
В2 |
В3 | |||
|
А1 А2 А3 |
1 4 6 |
3 5 2 |
2 7 4 |
50 100 130 | |
|
Потребность в грузе bj |
70 |
100 |
110 |
| |
2.
|
Поставщики |
Потребители |
Запас груза аi | |||
|
В1 |
В2 |
В3 |
В4 | ||
|
А1 А2 А3 |
4 3 5 |
7 1 6 |
2 0 3 |
3 4 7 |
30 190 250 |
|
Потребность в грузе bj |
70 |
120 |
150 |
130 |
|
3.
|
Поставщики |
Потребители |
Запас груза аi | |||
|
В1 |
В2 |
В3 |
В4 | ||
|
А1 А2 А3 А4 |
5 6 4 2 |
1 3 5 4 |
2 7 3 6 |
3 1 2 4 |
300 200 500 700 |
|
Потребность в грузе bj |
230 |
420 |
650 |
400 |
|
4.
|
Поставщики |
Потребители |
Запас груза аi | ||||
|
В1 |
В2 |
В3 |
В4 |
В5 | ||
|
А1 А2 А3 |
3 6 5 |
1 4 2 |
5 2 3 |
4 7 4 |
2 3 6 |
200 450 500 |
|
Потребность в грузе bj |
300 |
400 |
200 |
100 |
150 |
|
5.
|
Поставщики |
Потребители |
Запас груза аi | ||||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
В6 |
| ||
|
А1 А2 А3 А4 |
5 4 1 3 |
3 2 3 4 |
1 3 7 6 |
4 6 4 7 |
2 1 5 1 |
6 3 2 5 |
1780 2000 1530 2860 | |
|
Потребность в грузе bj |
850 |
1870 |
1950 |
1670 |
1000 |
830 |
| |
6.
|
Поставщики |
Потребители |
Запас груза аi | ||||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
В6 |
| ||
|
А1 А2 А3 А4 |
2 5 3 1 |
4 7 6 3 |
3 4 1 2 |
1 5 4 6 |
6 2 3 4 |
3 1 7 5 |
3000 5000 1250 7300 | |
|
Потребность в грузе bj |
2300 |
3200 |
4000 |
1760 |
1500 |
2220 |
| |
7.
|
Поставщики |
Потребители |
Запас груза аi | |||||
|
В1 |
В2 |
В3 |
В4 |
В5 | |||
|
А1 А2 А3 А4 |
4 7 6 2 |
1 3 4 5 |
2 4 7 6 |
5 2 1 4 |
6 5 8 7 |
100 70 130 150 | |
|
Потребность в грузе bj |
80 |
120 |
70 |
130 |
50 |
450 | |
8.
|
Поставщики |
Потребители |
Запас груза аi | |||||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
В6 |
В7 |
| ||
|
А1 А2 А3 А4 |
5 4 7 2 |
1 2 3 5 |
4 6 1 7 |
3 5 4 1 |
6 1 2 4 |
7 8 5 3 |
2 3 6 4 |
1040 2700 1885 1457 | |
|
Потребность в грузе bj |
590 |
740 |
875 |
1537 |
1200 |
1500 |
640 |
| |
9.
|
Поставщики |
Потребители |
Запас груза аi | |||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
В6 | ||
|
А1 А2 А3 А4 А5 |
7 1 4 5 2 |
1 3 5 3 4 |
4 5 6 7 3 |
6 2 3 2 5 |
5 4 1 8 6 |
8 6 7 4 3 |
600 800 550 730 900 |
|
Потребность в грузе bj |
750 |
580 |
440 |
620 |
550 |
640 |
|
10.
|
Поставщики |
Потребители |
Запас груза аi | |||
|
В1 |
В2 |
В3 |
В4 | ||
|
А1 А2 А3 |
6 8 16 |
4 10 12 |
2 14 6 |
7 12 13 |
40 36 24 |
|
Потребность в грузе bj |
24 |
20 |
30 |
26 |
|
11.
|
Поставщики |
Потребители |
Запас груза аi | |||
|
В1 |
В2 |
В3 |
В4 | ||
|
А1 А2 А3 А4 |
8 4 6 10 |
4 10 7 12 |
6 5 8 8 |
2 6 5 9 |
40 25 28 32 |
|
Потребность в грузе bj |
28 |
32 |
20 |
45 |
|
12.
|
Поставщики |
Потребители |
Запас груза аi | |||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
| ||
|
А1 А2 А3 |
9 6 8 |
6 9 7 |
8 13 12 |
11 15 5 |
10 12 9 |
100 80 40 | |
|
Потребность в грузе bj |
60 |
50 |
40 |
35 |
35 |
| |
13.
|
Поставщики |
Потребители |
Запас груза аi | ||||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
В6 |
| ||
|
А1 А2 А3 А4 |
9 4 5 6 |
3 6 8 2 |
4 7 8 15 |
8 11 4 9 |
10 13 12 6 |
12 9 10 8 |
36 34 32 30 | |
|
Потребность в грузе bj |
20 |
15 |
25 |
27 |
30 |
15 |
| |
14.
|
Поставщики |
Потребители |
Запас груза аi | ||||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
В6 |
| ||
|
А1 А2 А3 |
5 14 7 |
10 9 12 |
15 8 13 |
6 12 15 |
14 11 9 |
13 10 14 |
120 60 150 | |
|
Потребность в грузе bj |
45 |
52 |
48 |
55 |
70 |
60 |
| |
15.
|
Поставщики |
Потребители |
Запас груза аi | ||||
|
В1 |
В2 |
В3 |
В4 |
В5 | ||
|
А1 А2 А3 |
7 8 4 |
5 10 3 |
9 4 15 |
8 11 13 |
6 12 14 |
150 170 200 |
|
Потребность в грузе bj |
120 |
80 |
140 |
70 |
110 |
|
16.
|
Поставщики |
Потребители |
Запас груза аi | |||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
| ||
|
А1 А2 А3 |
7 9 6 |
6 5 8 |
8 7 4 |
10 4 9 |
12 6 7 |
50 60 40 | |
|
Потребность в грузе bj |
30 |
20 |
55 |
20 |
25 |
| |
17.(открытая)
|
Поставщики |
Потребители |
Запас груза аi | ||
|
В1 |
В2 |
В3 | ||
|
А1 А2 А3 |
4 3 9 |
6 5 10 |
7 8 6 |
40 60 50 |
|
Потребность в грузе bj |
30 |
40 |
60 |
|
18.
|
Поставщики |
Потребители |
Запас груза аi | |||
|
В1 |
В2 |
В3 |
В4 | ||
|
А1 А2 А3 |
12 16 19 |
15 20 21 |
14 18 16 |
10 17 13 |
30 50 45 |
|
Потребность в грузе bj |
20 |
25 |
35 |
40 |
|
19.
|
Поставщики |
Потребители |
Запас груза аi | |||
|
В1 |
В2 |
В3 |
В4 | ||
|
А1 А2 А3 |
15 16 13 |
17 12 18 |
14 10 11 |
12 9 15 |
60 45 130 |
|
Потребность в грузе bj |
50 |
70 |
60 |
80 |
|
20.
|
Поставщики |
Потребители |
Запас груза аi | ||||
|
В1 |
В2 |
В3 |
В4 |
| ||
|
А1 А2 А3 А4 |
17 20 18 16 |
15 16 17 12 |
10 18 19 15 |
14 13 20 18 |
70 100 60 80 | |
|
Потребность в грузе bj |
90 |
80 |
50 |
100 |
| |
21.
|
Поставщики |
Потребители |
Запас груза аi | ||||
|
В1 |
В2 |
В3 |
В4 |
| ||
|
А1 А2 А3 А4 |
12 14 18 17 |
9 8 19 15 |
10 13 20 18 |
15 17 14 21 |
1500 500 700 900 | |
|
Потребность в грузе bj |
1000 |
600 |
800 |
1100 |
| |
22.
|
Поставщики |
Потребители |
Запас груза аi | |||
|
В1 |
В2 |
В3 |
В4 | ||
|
А1 А2 А3 |
25 12 19 |
23 18 22 |
19 20 23 |
21 24 17 |
40 50 60 |
|
Потребность в грузе bj |
35 |
30 |
45 |
32 |
|
23.
|
Поставщики |
Потребители |
Запас груза аi | |||
|
В1 |
В2 |
В3 |
В4 | ||
|
А1 А2 А3 |
15 24 23 |
17 18 16 |
20 19 17 |
22 21 20 |
10 12 18 |
|
Потребность в грузе bj |
9 |
10 |
12 |
15 |
|
24.
|
Поставщики |
Потребители |
Запас груза аi | |||||
|
В1 |
В2 |
В3 |
В4 |
В5 | |||
|
А1 А2 А3 |
7 8 3 |
2 4 5 |
11 3 10 |
5 6 7 |
9 1 8 |
150 170 110 | |
|
Потребность в грузе bj |
110 |
120 |
80 |
50 |
70 |
| |
25.
|
Поставщики |
Потребители |
Запас груза аi | |||||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
В6 |
В7 |
| ||
|
А1 А2 А3 |
7 9 6 |
5 4 2 |
3 5 8 |
4 10 7 |
2 3 1 |
1 6 4 |
8 5 3 |
135 270 120 | |
|
Потребность в грузе bj |
80 |
93 |
56 |
100 |
125 |
98 |
73 |
| |
26.
|
Поставщики |
Потребители |
Запас груза аi | |||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
| ||
|
А1 А2 А3 А4 |
7 13 3 9 |
1 4 8 5 |
4 7 0 3 |
5 6 18 4 |
2 3 12 7 |
85 112 72 120 | |
|
Потребность в грузе bj |
75 |
125 |
64 |
65 |
60 |
| |
27.
|
Поставщики |
Потребители |
Запас груза аi | ||||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
В6 |
| ||
|
А1 А2 А3 А4 |
3 8 4 2 |
7 2 9 4 |
6 5 10 7 |
1 10 3 8 |
4 7 6 3 |
9 3 5 1 |
28 30 40 35 | |
|
Потребность в грузе bj |
18 |
10 |
20 |
37 |
10 |
38 |
| |
28.
|
Поставщики |
Потребители |
Запас груза аi | |||
|
В1 |
В2 |
В3 |
В4 | ||
|
А1 А2 А3 |
3 2 3 |
2 3 2 |
4 1 4 |
1 5 4 |
40 50 30 |
|
Потребность в грузе bj |
35 |
40 |
40 |
30 |
|
29.
|
Поставщики |
Потребители |
Запас груза аi | |||
|
В1 |
В2 |
В3 |
В4 | ||
|
А1 А2 А3 |
4 5 8 |
7 9 2 |
1 6 9 |
3 2 11 |
50 70 40 |
|
Потребность в грузе bj |
30 |
60 |
45 |
25 |
|
30.
|
Поставщики |
Потребители |
Запас груза аi | |||
|
В1 |
В2 |
В3 |
В4 | ||
|
А1 А2 А3 |
4 6 8 |
10 7 9 |
5 2 12 |
3 8 11 |
60 100 70 |
|
Потребность в грузе bj |
50 |
55 |
70 |
45 |
|