- •1. Теория графов
- •1.1 Остовные деревья минимального веса.
- •Алгоритм Прим
- •Алгоритм Краскал
- •1.2 Нахождение кратчайших путей между двумя заданными вершинами. Алгоритм Дийкстры
- •Алгоритм Дийкстры
- •Модифицированный алгоритм Дийкстры
- •1.3 Нахождение кратчайших цепей между всеми парами узлов в сети
- •Алгоритм Флойда (Floyd r. W.)
- •Модификация алгоритма Флойда
- •1.4 Построение потоков максимальной мощности. Алгоритм Форда-Фалкерсона
- •Алгоритм Форда-Фалкерсона
- •1.5 Обобщенные задачи о потоке
- •1.5.1 Построение потока в сети с двойным ограничением потока по дугам
- •1.5.2 Построение потока в сети с пропускными способностями узлов
- •1.5.3 Построение потока в сети с несколькими источниками-стоками
- •1.5.4 Построение потока в сети с неориентированными ребрами
- •1.6 Определение потока заданной величины минимальной стоимости. Алгоритмы Басакера-Гоуэна, Клейна
- •Алгоритм Басакера-Гоуэна (Basaker r.G., Gowen p.J)
- •Алгоритм Клейна (Klein m.)
- •2 Сетевое планирование
- •2.1 Построение сетевых моделей
- •2.2 Расчет и анализ сетевых моделей
- •Задача №1
- •Задача №2
- •I. Поиск критических путей
- •II. Поиск резервов работ
- •Правило №2.1
- •3 Линейное программирование
- •3.1 Примеры задач лп
- •3.2 Свойства решений задач линейного программирования
- •3.3 Двумерные задачи линейного программирования. Графический метод решения. Исследование на разрешимость
- •3.3.1 Построение области допустимых решений целевой функции f.
- •3.3.2 Построение прямой уровня
- •3.3.3 Максимизация целевой функции f
- •3.4 Симплекс-метод.
- •3.4.1 Построение начального опорного плана.
- •3.4.2 Симплексные таблицы
- •3.4.3 Примеры решения задач симплекс-методом
- •4. Теория двойственности в линейном программировании
- •4.1 Понятие двойственности. Построение пары взаимно двойственных задач
- •4.2 Теоремы двойственности и их экономическое содержание
- •4.3 Анализ решения задач линейного программирования
- •5. Транспортная задача
- •5.1 Постановка транспортной задачи в матричной форме. Построение исходного опорного плана
- •5.2 Метод потенциалов
- •5.3 Дополнительные условия в транспортных задачах.
- •6. Дискретное программирование.
- •6.1 Метод Гомори для решения задачи целочисленного линейного программирования
- •7. Динамическое программирование
- •7.1 Многошаговые процессы в динамических задачах
- •7.2 Принцип оптимальности и рекуррентные соотношения
- •7.3 Вычислительная схема динамического программирования
- •7.4 Оптимальное распределение средств на расширение производства
- •8. Матричные игры
- •8.1 Парные матричные игры с нулевой суммой
- •8.2 Платежная матрица
- •Нижняя и верхняя цена игры
- •8.3 Смешанные стратегии
- •8.3 Решение матричной игры сведением к задаче линейного программирования
- •8.4 Решение матричной игры графическим методом
- •8.5 Приближенный метод решения матричных игр
- •Практические работы Практическая работа №1 Построение остовного дерева графа. Нахождение найкратчайшего расстояния между заданными вершинами графа
- •Практическая работа №2 Нахождение наикратчайших расстояний между всеми парами вершин графа. Алгоритм Флойда.
- •Практическая работа №3
- •Практическая работа №4 Нахождение потока заданной величины минимальной стоимости. Алгоритм Басакера-Гоуэна
- •Практическая работа №7 Оптимизация проекта по времени.
- •Практическая работа №8
- •Практическая работа №9 Оптимизация целевой функции с помощью двухфазного симплекс метода.
- •Практическая работа №10 Решение двойственных задач. Экономическая интерпретация задач линейного программирования.
- •Практическая работа №11 Решение транспортных задач.
- •Практическая работа №12 Дополнительные условия в транспортных задачах
- •Практическая работа №13 Метод Гомори для решения задачи целочисленного линейного программирования.
- •Практическая работа №14
- •Практическая работа №15 Решение матричных игр в чистых стратегиях
- •Практическая работа №16 Графический метод решения матричных игр.
- •Каркас минимального веса. Метод р. Прима.
- •Кратчайшие пути
- •Лабораторная работа №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 |
|