Экстремальные задачи на графах

1. Задача о кратчайшем пути между двумя вершинами ориентированного графа и ее экономическая интерпретация.

Постановка задачи

Экономическое содержание задачи

Алгоритм Форда

Шаги алгоритма

Алгоритм Форда

Алгоритм Форда

Алгоритм Форда

Алгоритм Форда

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

Отношение порядка

Отношение порядка

Пример

Отношение порядка

2. Задача о пути максимальной длины между двумя вершинами ориентированного графа в сетевом планировании.

о пути максимальной длины

о пути максимальной длины
Решение задачи состоит как в отыскании пути максимальной длины между двумя фиксированными вершинами графа, так и в определении величины этого пути.
Одну из основных задач сетевого планирования составляет отыскание путей максимальной длины между входом и выходом графа-сети.

Алгоритм

Этапы алгоритма

Этапы алгоритма

Этапы алгоритма

Сетевое планирование. Скорейшее время завершения проекта.
Рассмотрим проект – совокупность операций (работ), составляющий некоторый многошаговый процесс. Примером может служить строительство некоторого объекта. Считаем известными все работы, которые предстоит совершить, их последовательность и время, необходимое для выполнения каждой работы.
Проект может быть изображен в виде графа-сети. Зададимся целью определить кратчайший срок завершения проекта.

Пусть данные о строительстве приведены в следующей таблице:

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

Сетевое планирование

Сетевое планирование
Сетевой граф, соответствующий приведенным в таблице данным, изображен на рисунке.
Номер работы обозначен числом вне кружка. Число, обведенное кружком, есть продолжительность данной работы.

Сетевое планирование. Пример

Сетевое планирование

Сетевое планирование