Оптимизация на сетях

Июль 29, 2022

Главная
Информатика
Оптимизация на сетях

Содержание

2. СЕТЬ → ГРАФ ВЕРШИНЫ ГРАФА – УЗЛЫ СЕТИ (N) РЕБРА ГРАФА – ДУГИ СЕТИ (A) ОПИСАНИЕ
4. Классификация задач оптимизации на сетях Алгоритм нахождения минимального остового дерева Алгоритм нахождения кратчайшего пути Алгоритм определения
5. Методы решения задач оптимизации на сетях 1. Симплекс-метод, т.к. все перечисленные задачи относятся к задачам линейного
6. Пример сведения задачи к задаче о кратчайшем пути
7. Задача с кольцевыми маршрутами (о коммивояжере)
8. Алгоритм метода ветвей и границ
9. Алгоритм метода ветвей и границ
10. Алгоритм метода ветвей и границ
11. Алгоритм метода ветвей и границ
12. Пример решения задачи о коммивояжере
13. Пример решения задачи о коммивояжере
14. Пример решения задачи о коммивояжере
15. Пример решения задачи о коммивояжере
16. Пример решения задачи о коммивояжере
17. Пример решения задачи о коммивояжере
18. Пример решения задачи о коммивояжере
19. Дерево маршрутов
21. Скачать презентацию

Слайд 2

СЕТЬ → ГРАФ ВЕРШИНЫ ГРАФА – УЗЛЫ СЕТИ (N)
РЕБРА ГРАФА

– ДУГИ СЕТИ (A)
ОПИСАНИЕ СЕТИ – МНОЖЕСТВА (N, A)
ОСНОВНАЯ ТЕРМИНОЛОГИЯ
Поток – пропускная способность дуг (ребер)
Ориентированнная дуга (сеть)
Путь
Цикл (ориентированный цикл)
Связная сеть
Дерево
Остовное дерево

Слайд 3

Слайд 4

Классификация задач оптимизации на сетях
Алгоритм нахождения минимального остового дерева
Алгоритм нахождения

кратчайшего пути
Алгоритм определения максимального потока
Алгоритм минимизации стоимости потока в сети с ограниченной пропускной способностью
Алгоритм нахождения критического пути
Алгоритм определения гамильтонова контура минимальной длины

Слайд 5

Методы решения задач оптимизации на сетях
1. Симплекс-метод, т.к. все перечисленные задачи

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

Слайд 6

Пример сведения задачи к задаче о кратчайшем пути

Слайд 7

Задача с кольцевыми маршрутами (о коммивояжере)

Слайд 8

Алгоритм метода ветвей и границ

Слайд 9

Алгоритм метода ветвей и границ

Слайд 10

Алгоритм метода ветвей и границ

Слайд 11

Алгоритм метода ветвей и границ

Слайд 12

Пример решения задачи о коммивояжере

Слайд 13

Пример решения задачи о коммивояжере

Слайд 14

Пример решения задачи о коммивояжере

Слайд 15

Пример решения задачи о коммивояжере

Слайд 16

Пример решения задачи о коммивояжере

Слайд 17

Пример решения задачи о коммивояжере

Слайд 18

Пример решения задачи о коммивояжере

Слайд 19

Дерево маршрутов