Нахождение потока минимальной стоимости

Сентябрь 14, 2022

Главная
Математика
Нахождение потока минимальной стоимости

Содержание

2. Введение Сетевые и графовые модели охватывают довольно большой класс задач, встречающихся при исследовании целого ряда проблем
3. Постановка задачи Сколько ящиков Вы сможете транспортировать в аэропорт в день, учитывая пропускную способность дорог, при
4. Методы решения Задача о потоке минимальной стоимости может быть решена, используя линейное программирование. Найти любой поток
5. Используемый метод решения Улучшение предыдущего алгоритма: используя потенциалы, можно свести задачу к задаче без отрицательных рёбер,
6. Статистика и анализ статистики
7. Статистика и анализ статистики
8. Пример работы программы. Алгоритм Беллмана-Форда
9. Пример работы программы. Алгоритм Дейкстры
10. Заключение В нашей исследовательской работе были выявлены основные методы решения задачи на потоках, освоены и применены
11. Список используемой литературы Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ /
13. Скачать презентацию

Слайд 2

Введение
Сетевые и графовые модели охватывают довольно большой класс задач, встречающихся при

исследовании целого ряда проблем в транспорте, связи и других областях. Характерной особенностью задач, решаемых с помощью теории графов, является большая размерность поля данных. Поэтому возникает необходимость использования методов оптимизации, которые позволяют экономить вычислительные ресурсы и обеспечивают их гибкость по отношению к изменениям исходных данных.

Слайд 3

Постановка задачи
Сколько ящиков Вы сможете транспортировать в аэропорт в день, учитывая

пропускную способность дорог, при этом, чтобы общее расстояние маршрутов было минимальным? Необходимо найти оптимальный маршрут перевозки – оптимальный поток в графе.

Слайд 4

Методы решения
Задача о потоке минимальной стоимости может быть решена, используя линейное программирование.
Найти

любой поток данной величины, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток. Циклы ищутся алгоритмом Беллмана - Форда.
Использовать модификацию алгоритма Форда — Фалкерсона, в которой на каждом шаге выбирается увеличивающий путь минимальной цены. Для выбора пути можно воспользоваться алгоритмом Беллмана-Форда.

Слайд 5

Используемый метод решения
Улучшение предыдущего алгоритма: используя потенциалы, можно свести задачу к

задаче без отрицательных рёбер, после чего вместо алгоритма Беллмана-Форда воспользоваться алгоритмом Дейкстры. Алгоритм Беллмана-Форда придётся применить лишь на самом первом шаге.
Сложность - O(N^2*M*logM)

Слайд 6

Статистика и анализ статистики

Слайд 7

Статистика и анализ статистики

Слайд 8

Пример работы программы. Алгоритм Беллмана-Форда

Слайд 9

Пример работы программы. Алгоритм Дейкстры

Слайд 10

Заключение
В нашей исследовательской работе были выявлены основные методы решения задачи на

потоках, освоены и применены оптимизационные алгоритмы, а также разобрана реализация этих алгоритмов на языке Java. Подводя итоги, можно отметить следующее: применение аппарата теории графов к решению различных классов задач на первый взгляд выглядит довольно громоздким, но его наглядность и рациональность определяют широту использования в различных сферах производства.

Слайд 11

Список используемой литературы
Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ /

Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с.
Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. М.: Высшая школа, 1976. — 392 с.
Гончаров Г.А., Мочалин А.А. Элементы дискретной математики: Учебное пособие. М.: ФОРУМ: ИНФРА-М, 2003. — 128 с.
Логинов Б.М. Введение в дискретную математику. М.: Калуга, 1998. — 423 с.
Майника Э. Алгоритмы оптимизации на сетях. М.: Мир, 1981. — 323 с.
Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. 455 с.

Нахождение потока минимальной стоимости

Содержание

ВведениеСетевые и графовые модели охватывают довольно большой класс задач, встречающихся при

Постановка задачиСколько ящиков Вы сможете транспортировать в аэропорт в день, учитывая

Методы решенияЗадача о потоке минимальной стоимости может быть решена, используя линейное программирование.Найти

Используемый метод решенияУлучшение предыдущего алгоритма: используя потенциалы, можно свести задачу к

Статистика и анализ статистики

Статистика и анализ статистики

Пример работы программы. Алгоритм Беллмана-Форда

Пример работы программы. Алгоритм Дейкстры

ЗаключениеВ нашей исследовательской работе были выявлены основные методы решения задачи на

Список используемой литературыКормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ /

Похожие презентации

Введение
Сетевые и графовые модели охватывают довольно большой класс задач, встречающихся при

Постановка задачи
Сколько ящиков Вы сможете транспортировать в аэропорт в день, учитывая

Методы решения
Задача о потоке минимальной стоимости может быть решена, используя линейное программирование.
Найти

Используемый метод решения
Улучшение предыдущего алгоритма: используя потенциалы, можно свести задачу к

Заключение
В нашей исследовательской работе были выявлены основные методы решения задачи на

Список используемой литературы
Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ /