Оптимизация на сетях (Лекция 6)

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

2. Классификация задач оптимизации на сетях

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

3. Методы решения задач оптимизации на сетях

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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